función autocompletar-like con un dict python

En PHP, tuve esta línea matches = preg_grep('/^for/', array_keys($hash)); Lo que haría es tomar las palabras: fork, form etc. que están en $ hash.función autocompletar-like con un dict python

En Python, tengo un dict con 400,000 palabras. Sus claves son palabras que me gustaría presentar en una característica similar a la de autocompletar (los valores en este caso no tienen sentido). ¿Cómo podría devolver las claves de mi diccionario que coinciden con la entrada?

Por ejemplo (como el usado anteriormente), si tengo

my_dic = t{"fork" : True, "form" : True, "fold" : True, "fame" : True}

y consigo alguna entrada "for", que va a devolver una lista de "fork", "form".

Fuente

2010-06-03 tipu

''fold'' would not much'' for'' – SilentGhost

SilentGhost: eres absolutamente correcto, editado. – tipu

>>> mydict={"fork" : True, "form" : True, "fold" : True, "fame" : True} 
>>> [k for k in mydict if k.startswith("for")] 
['fork', 'form']

Este debería ser más rápido que usar una expresión regular (y suficiente si solo estás buscando los comienzos de las palabras).

Fuente

2010-06-03 16:18:45

>>> my_dict = {"fork" : True, "form" : True, "fold" : True, "fame" : True} 
>>> import re 
>>> [s for s in my_dict if re.search('^for', s) is not None] 
['fork', 'form']

El uso de expresiones regulares es más universal, ya que podría proporcionar patrones de búsqueda más complejas, si es sólo sobre los prefijos, se puede usar métodos de cadena: str.startwith, por ejemplo:

>>> [s for s in my_dict if s.startswith('for')] 
['fork', 'form']

Fuente

2010-06-03 16:18:34 SilentGhost

Puede obtener las claves de my_dict con my_dict.keys(). Luego, puede buscar a través de cada tecla para ver si coincide con su expresión regular.

m = re.compile('^for') 
keys = [] 
for key in my_dict.keys(): 
    if m.match(key) != None: 
     keys.append(key)

Fuente

2010-06-03 16:18:55

Así que esto no es una respuesta directa a lo que pide, pero ..

Parece como si realmente no quiere un diccionario para este tipo de cosas, que está buscando una estructura de árbol, ¿verdad?

Luego puede recorrer el árbol para cada letra que se escribe (tiempo constante), y devolver hojas de esa subsección del árbol como las palabras que coinciden con ese prefijo.

Fuente

2010-06-03 16:19:23

Este caso particular no es el único momento en que estoy usando el dict. Es un índice invertido, por lo que los valores son un conjunto de documentos ID que son absolutamente vitales para lo que estoy haciendo. La razón por la que estoy usando un dict es porque la búsqueda será mucho más rápida que un árbol (la memoria es suficiente, los ciclos de la CPU no) – tipu

Aunque la búsqueda de claves conocidas será más rápida con un dict que una estructura de árbol, teniendo que probar cada la clave para una coincidencia parcial no será - por lo que, en los casos en que no se conoce la clave por adelantado (como la que se presenta arriba), algo mejor sería un árbol. – pycruft

Fyi, la estructura de datos perfecta para este problema se llama ** trie ** - pero stdlib de python no tiene una. –

Si desea una estrategia de búsqueda específica (como el "startswith 3 chars" descrito anteriormente), probablemente pueda obtener una ganancia rápida al crear un diccionario de búsqueda específico basado en esa idea.

q = {"fork":1, "form":2, "fold":3, "fame":4} 
from collections import defaultdict 
q1 = defaultdict(dict) 
for k,v in q.items(): 
    q1[k[:3]][k]=v

Esto permitirá hacer una búsqueda .startswith tipo durante un mucho más pequeño establecer

def getChoices(frag): 
    d = q1.get(frag[:3]) 
    if d is None: 
     return [] 
    return [ k for k in d.keys() if k.startswith(frag) ]

Esperemos que debería ser mucho más rápido que el procesamiento de enteros los 400.000 llaves.

Fuente

2010-06-03 16:38:45 pycruft

función autocompletar-like con un dict python

Respuesta

Cuestiones relacionadas