Un autocompletador de palabras simple diseñado para usarse en un shell

Aug 19 2020

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_stringshace 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 appendsin 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 en find_matching. Sin string +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

3 Peilonrayz Aug 19 2020 at 03:46
  1. Puede usar en dict.setdefaultlugar 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.

  2. No soy fanático de tu terminología:

    • table me hace pensar en una matriz 2d en lugar de un árbol.
    • Preferiría nodehacerlo cur_level.
    • ¿Qué csignifica?
    • ¿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, {})
  1. En _extract_stringsMovería acc = []después de la definición de la función por lo que el código no es por todo el lugar.

  2. 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 + chares 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ía yieldy yield 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)
    
  3. 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)
    
  4. No soy fanático de muchas de tus líneas vacías. Parecen aleatorios y no necesarios.

  5. 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 manejo table".
    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)
    
  6. El plan hasta ahora será tener una llamada a make_lookup_table_from_pathuna 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_matchingentonces un simple str.startswithprobablemente 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.