Un autocompletador de palabras simple diseñado para usarse en un shell
Problema
Estoy escribiendo un shell simple, y quiero tener la característica de autocompletar que tiene bash cuando escribes parcialmente una palabra y luego presionas tab:

En este momento puede funcionar independientemente de un shell, pero tiene características que le permiten encontrar comandos en el sistema. Ejemplos:
>>> table = make_lookup_table_from(["hell", "water", "help", "air", "hello", "fire", "earth"])
>>> find_matching(table, "hel")
['hell', 'hello', 'help']
>>> table = make_lookup_table_from_path()
>>> find_matching(table, "gcc-")
['gcc-ar', 'gcc-ar-8', 'gcc-ar-9', 'gcc-nm', 'gcc-nm-8', 'gcc-nm-9', 'gcc-ranlib', 'gcc-ranlib-8', 'gcc-ranlib-9', 'gcc-8', 'gcc-9']
>>> find_matching(table, "pyth")
['python3.8', 'python3.8-config', 'python3', 'python3-qr', 'python3-futurize', 'python3-pasteurize', 'python3-tor-prompt', 'python3-config', 'python3-wsdump', 'python', 'python-argcomplete-check-easy-install-script', 'python-argcomplete-check-easy-install-script3', 'python-argcomplete-tcsh', 'python-argcomplete-tcsh3', 'python-config', 'python-faraday', 'python2-config', 'python2-futurize', 'python2-pasteurize', 'python2-pbr', 'python2', 'python2.7-config', 'python2.7']
Cómo funciona:
Cada palabra se coloca en un diccionario anidado letra por letra, luego termina con un carácter nulo para marcar el final de una palabra:
>>> make_lookup_table_from(["hell", "water", "help", "air", "hello", "fire", "earth"])
{'h': {'e': {'l': {'l': {'\x00': {}, 'o': {'\x00': {}}}, 'p': {'\x00': {}}}}}, 'w': {'a': {'t': {'e': {'r': {'\x00': {}}}}}}, 'a': {'i': {'r': {'\x00': {}}}}, 'f': {'i': {'r': {'e': {'\x00': {}}}}}, 'e': {'a': {'r': {'t': {'h': {'\x00': {}}}}}}}
Para hacer una búsqueda para encontrar coincidencias, se recorre el árbol hasta que se encuentra el sub-diccionario común, luego cada palabra se reconstruye de forma recursiva.
Atención:
Honestamente, he estado en la escuela enfocándome en otras cosas además del código, así que me he oxidado un poco. Estoy usando un par de técnicas menos que ideales, por lo que cualquier recomendación es bienvenida:
La función de búsqueda
_extract_strings
hace uso de la recursividad, porque parecía un problema doloroso de resolver iterativamente. Si me falta una forma alternativa obvia, agradecería cualquier consejo allí.En la función recursiva, estoy usando cadenas para realizar un seguimiento de la palabra "hasta ahora" y pasando copias concatenadas a los niños para que las usen. Originalmente estaba usando listas para poder simplemente
append
sin crear un nuevo objeto cada vez, pero compartir la lista mutable entre recurrentes resultó ser problemático. También estoy devolviendo solo las terminaciones de la función de búsqueda y luego reconstruyo la palabra completa enfind_matching
. Sinstring +
embargo, esto es necesario para cada cadena encontrada, lo cual no es genial.
En realidad, estas funciones se realizan sorprendentemente rápido. Iba a configurar un sistema de almacenamiento en caché, carga desde el disco al inicio para evitar la necesidad de reconstruir la tabla constantemente, pero es tan rápido que no parece que valga la pena. Como resultado, mis dos preocupaciones anteriores probablemente se incluyan en "optimizaciones prematuras", pero aún me gustaría recibir sugerencias sobre ellas o cualquier otra cosa, desde el estilo hasta otras mejores prácticas.
Código:
import os
from typing import List, Iterable, Dict
_TERMINATOR = "\0"
_PATH_KEY = "PATH"
_PATH_DELIM = ":"
Table = Dict[str, "Table"]
def _get_paths() -> List[str]:
return os.environ[_PATH_KEY].split(_PATH_DELIM)
def _find_filenames_in(paths: List[str]) -> Iterable[str]:
return (fname
for path in paths
for _, _, fnames in os.walk(path)
for fname in fnames)
def _add_string(table: Table, string: str) -> None:
term_string = string + _TERMINATOR
cur_level = table
for c in term_string:
if c not in cur_level:
cur_level[c] = {}
cur_level = cur_level[c]
def make_lookup_table_from(strings: Iterable[str]) -> Table:
table = {}
for string in strings:
_add_string(table, string)
return table
def make_lookup_table_from_path() -> Table:
paths = _get_paths()
fnames = _find_filenames_in(paths)
return make_lookup_table_from(fnames)
def _extract_strings(table: Table) -> Iterable[str]:
acc = []
def rec(cur_path: str, cur_level: Table):
for char, child in cur_level.items():
if char == _TERMINATOR:
acc.append(cur_path)
else:
rec(cur_path + char, child)
rec("", table)
return acc
def find_matching(table: Table, string: str) -> Iterable[str]:
cur_level = table
for c in string:
try:
cur_level = cur_level[c]
except KeyError:
return []
return [string + end for end in _extract_strings(cur_level)]
Respuestas
Puede usar en
dict.setdefault
lugar de modificar condicionalmente el trie. Esto tiene la ventaja de buscar la clave solo una vez en lugar de un máximo de 3 veces con su código actual.No soy fanático de tu terminología:
table
me hace pensar en una matriz 2d en lugar de un árbol.- Preferiría
node
hacerlocur_level
. - ¿Qué
c
significa? - ¿Por qué no simplemente llamarlo
_add_value
?
def _add_value(root: Table, string: str) -> None:
node = root
for char in string + _TERMINATOR:
node = node.setdefault(char, {})
En
_extract_strings
Moveríaacc = []
después de la definición de la función por lo que el código no es por todo el lugar.-
En la función recursiva, estoy usando cadenas para realizar un seguimiento de la palabra "hasta ahora" y pasando copias concatenadas a los niños para que las usen. Originalmente estaba usando listas para poder agregar sin crear un nuevo objeto cada vez, pero compartir la lista mutable entre recursivos resultó ser problemático. También estoy devolviendo solo las terminaciones de la función de búsqueda y luego reconstruyo la palabra completa en find_matching. Sin embargo, esto necesita string + para cada string encontrado, lo cual no es genial.
Cuando obtiene un valor, su código se ejecuta en \$O(l^2)\$donde \$l\$es la longitud máxima de una cadena. Esto se debe a que cada uno
cur_path + char
es un \$O(l)\$operación y lo haces \$l\$ veces.Con el algoritmo actual, sugeriría seguir un enfoque de 'eh, al diablo' y simplemente estar feliz de que sea lo suficientemente rápido. Ya que manejar manualmente la pila no es divertido .
Personalmente, no soy fanático de
acc.append
, en su lugar usaríayield
yyield from
.def _extract_strings(table: Table) -> Iterator[str]: def rec(cur_path: str, cur_level: Table): for char, child in cur_level.items(): if char == _TERMINATOR: yield cur_path else: yield from rec(cur_path + char, child) return rec("", table)
-
La función de búsqueda _extract_strings hace uso de la recursividad, porque esto parecía un problema doloroso de resolver iterativamente. Si me falta una forma alternativa obvia, agradecería cualquier consejo allí.
Si bien es posible construir manualmente la pila, no es muy simple. Dado que es poco probable que el trie supere el límite de pila de 1000 de Python, probablemente pueda ignorar esto.
Como se mencionó anteriormente al construir la pila, podríamos construir fácilmente el resultado al mismo tiempo, cambiando el \$O(l^2)\$rendimiento a solo \$O(l)\$.Sin embargo, como debería poder ver, esto es una abominación. No creo que nadie quiera mantener esto.
def _extract_strings(table: Table) -> Iterator[str]: stack = [iter(table.items())] stack_value = [] while stack: try: key, value = next(stack[-1]) except StopIteration: stack.pop() if stack_value: stack_value.pop() continue if key == '\0': yield ''.join(stack_value) stack_value.append(key) stack.append(iter(value.items())) table = { 'b': {'a': {'r': {'\0': {}}, 'z': {'\0': {}}}}, 'f': {'o': {'o': {'\0': {}}}}, } for path in _extract_strings(table): print(path)
No soy fanático de muchas de tus líneas vacías. Parecen aleatorios y no necesarios.
El trie se describiría mejor en una clase. Una clase, incluso sin azúcar, haría que tu código fuera más fácil de entender, ya que entonces no tienes que pensar "qué es
_add_string
" y "cómo lo manejotable
".
He escrito algunos intentos a lo largo de los años , pueden ayudar si decides convertirlo en una clase.trie = Trie() trie.add('foo') trie.add('bar') trie.add('baz') # Could use the following to add instead if you need a value # trie['foo'] = ??? key = 'ba' for value in trie[key]: print(key + value)
-
El plan hasta ahora será tener una llamada a
make_lookup_table_from_path
una vez cuando se cargue el shell, guardar la tabla en una variable fuera del ciclo principal, luego hacer búsquedas en la tabla guardada (cuanto más escribo "tabla", más I ' Me doy cuenta de que probablemente esa no sea la palabra correcta).Usar un Trie aquí es una buena solución.
Si estuviera reconstruyendo la mesa cada vez que llama,find_matching
entonces un simplestr.startswith
probablemente superaría esto por millas.
En general
El estilo de su código parece un poco extraño. Pero por lo demás es bueno. Sugeriría usar una clase sobre todo.