Un semplice autocompletatore di parole pensato per l'uso in una shell

Question

Problema

Sto scrivendo una semplice shell e voglio avere la bella funzione di completamento automatico che ha bash quando digiti parzialmente una parola e poi premi tab:

Al momento può funzionare indipendentemente da una shell, ma ha caratteristiche che gli permettono di trovare i comandi sul sistema. Esempi:

>>> 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']

Come funziona:

Ogni parola viene inserita in un dizionario annidato lettera per lettera, quindi terminata da un carattere nullo per contrassegnare la fine di una parola:

>>> 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': {}}}}}}}

Per fare una ricerca per trovare le corrispondenze, l'albero viene percorso fino a trovare il dizionario secondario comune, quindi ogni parola viene ricostruita ricorsivamente.

Messa a fuoco:

Onestamente, sono stato a scuola concentrandomi su altre cose oltre al codice, quindi sono diventato un po 'arrugginito. Sto usando un paio di tecniche tutt'altro che ideali, quindi qualsiasi consiglio è il benvenuto:

• La funzione di ricerca _extract_stringsutilizza la ricorsione, perché sembrava un problema doloroso da risolvere iterativamente. Se mi manca un modo alternativo ovvio, apprezzerei eventuali suggerimenti.

• Nella funzione ricorsiva, sto usando stringhe per tenere traccia della parola "finora" e passando copie concatenate ai figli affinché possano usarle. Inizialmente stavo usando gli elenchi in modo da poter semplicemente appendcreare un nuovo oggetto ogni volta, ma condividere l'elenco mutevole tra le ricorsioni si è rivelato problematico. Sto anche restituendo solo le desinenze dalla funzione di ricerca, quindi ricostruendo l'intera parola in find_matching. string +Tuttavia, ciò richiede ogni stringa trovata, il che non è eccezionale.

Queste funzioni in realtà sono sorprendentemente veloci. Stavo per configurare un sistema di memorizzazione nella cache, caricamento da disco all'avvio per evitare di dover ricostruire costantemente la tabella, ma è così veloce che non sembra valerne la pena. Di conseguenza, entrambe le mie preoccupazioni di cui sopra probabilmente rientrano nelle "ottimizzazioni premature", ma mi piacerebbe comunque suggerimenti su di esse o su qualsiasi altra cosa, dallo stile ad altre best practice.

Codice:

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)]

Answer 1

1. Puoi usare dict.setdefaultinvece di modificare in modo condizionale il trie. Questo ha il vantaggio di cercare la chiave solo una volta invece di un massimo di 3 volte con il codice corrente.

2. Non sono un fan della tua terminologia:

   • table mi fa pensare a un array 2d piuttosto che a un albero.
   • Preferirei nodea cur_level.
   • Cosa csignifica?
   • Perché non chiamarlo _add_value?

def _add_value(root: Table, string: str) -> None:
    node = root
    for char in string + _TERMINATOR:
        node = node.setdefault(char, {})

1. In _extract_stringsmi sposterei acc = []dopo la definizione della funzione in modo che il codice non sia dappertutto.

2. Nella funzione ricorsiva, sto usando stringhe per tenere traccia della parola "finora" e passando copie concatenate ai figli affinché possano usarle. Inizialmente stavo usando gli elenchi in modo da poter aggiungere semplicemente senza creare un nuovo oggetto ogni volta, ma condividere l'elenco mutevole tra le ricorsioni si è rivelato problematico. Sto anche restituendo solo le desinenze dalla funzione di ricerca, quindi ricostruendo la parola completa in find_matching. Ciò richiede una stringa + per ogni stringa trovata, il che non è eccezionale.

   Quando ottieni un valore il tuo codice viene eseguito in \$O(l^2)\$dove \$l\$è la lunghezza massima di una stringa. Questo perché ognuno cur_path + charè un \$O(l)\$operazione e lo fai \$l\$ volte.

   Con l'attuale algoritmo suggerirei di seguire un approccio "eh, fanculo" ed essere solo felice che sia sufficientemente veloce. Poiché gestire manualmente lo stack non è divertente .

   Personalmente non sono un fan di acc.append, userei invece yielde 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 funzione di ricerca _extract_strings utilizza la ricorsione, perché sembrava un problema doloroso da risolvere iterativamente. Se mi manca un modo alternativo ovvio, apprezzerei eventuali suggerimenti.

   Sebbene sia possibile costruire manualmente lo stack, non è semplicissimo. Dato che è improbabile che il trie superi il limite di 1000 stack di Python, puoi probabilmente ignorarlo.
   Come accennato in precedenza durante la costruzione dello stack, potremmo facilmente costruire il risultato allo stesso tempo, cambiando il \$O(l^2)\$prestazioni a solo \$O(l)\$.

   Tuttavia, come dovresti essere in grado di vedere, questo è un abominio. Non credo che nessuno voglia mantenerlo.

   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. Non sono un fan di molte delle tue righe vuote. Sembrano casuali e non necessari.

5. Il trie sarebbe meglio descritto in una classe. Una lezione, anche senza zucchero, renderebbe il tuo codice più facile da capire, in quanto in questo modo non devi pensare "cosa è _add_string" e "come gestisco table".
   Ho scritto alcuni tentativi nel corso degli anni , potrebbero essere utili se decidi di farne una lezione.

   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. Il piano fino ad ora sarà quello di avere una chiamata a make_lookup_table_from_pathuna volta quando la shell è caricata, salvare la tabella in una variabile al di fuori del ciclo principale, quindi fare ricerche sulla tabella salvata (più scrivo "tabella", più io ' mi rendo conto che probabilmente non è la parola giusta).

   Usare un Trie qui è una buona soluzione.
   Se dovessi ricostruire il tavolo ogni volta che chiami, find_matchingun semplice str.startswithprobabilmente lo supererebbe per miglia.

Complessivamente

Lo stile del tuo codice sembra un po 'strano. Ma per il resto va bene. Suggerirei di usare soprattutto un corso.