ricerca di prefisso in un albero radix / trie patricia

Question

Al momento sto implementando un albero radicato / trie patricia (qualunque cosa si voglia chiamare). Voglio usarlo per le ricerche prefisso in un dizionario su un pezzo gravemente sottodimensionato di hardware. Si dovrebbe funzionare più o meno come il completamento automatico, i. e. che mostra un elenco di parole che il prefisso digitato corrisponde.

La mia applicazione si basa su questo articolo , ma il codice in esso doesn 't includono ricerche prefisso, anche se l'autore dice:

  

[...] Dire che si desidera enumerare tutti i nodi che hanno le chiavi con un prefisso comune "AB". È possibile eseguire una ricerca in profondità a partire da quella radice, fermandosi ogni volta che si incontra di nuovo i bordi.

Ma non vedo come questo dovrebbe funzionare. Per esempio, se io costruisco un albero radicato da queste parole:

  

malattia
  
immaginario   immaginazione
  immaginare
  imitazione
  
immediato   
subito   immensa
  in

mi metterò la stessa identica "migliore corrispondenza" per i prefissi "i" e "a" in modo che sembra difficile per me per raccogliere tutte le parole corrispondenti semplicemente attraversare l'albero da quella migliore corrispondenza.

Inoltre, v'è un href="http://code.google.com/p/radixtree/" rel="nofollow noreferrer"> radix implementazione che ha una ricerca di prefisso implementato in RadixTreeImpl.java . Questo codice controlla in modo esplicito tutti i nodi (a partire da un certo nodo) per una partita di prefisso -. In realtà a confronto byte

Qualcuno mi può puntare a una descrizione dettagliata per l'attuazione di una ricerca di prefisso sugli alberi Radix? È l'algoritmo utilizzato nella implementazione Java l'unico modo per farlo?

Answer 1

Pensate a che cosa il vostro trie codifica. Ad ogni nodo, che il percorso che vi condurrà a quel nodo, così nel tuo esempio, si inizia a Λ (che è un capitale Lambda, questo tipo di carattere greco tipo di fa schifo) il nodo principale corrispondente ad una stringa vuota. Λ ha figli per ogni lettera usata, così nel set di dati, si dispone di un ramo, per "i".

• Λ
• Λ → "i"

Al "i" nodo, ci sono due bambini, uno per "m" e uno per "n". La lettera successiva è "n", in modo da prendere che,

• Λ → "i" → "n"

e dal momento che l'unica parola che inizia "i", "n" nel set di dati è "in", non ci sono bambini da "n". Questa è una partita.

Ora, diciamo che il set di dati, invece di avere "in", aveva "infindibulum". (Che cosa sto SF riferimento è lasciato come esercizio.) Si potrebbe ancora ottenere la "n" nodo allo stesso modo, ma poi se la lettera successiva che si ottiene è "q", è conoscere la parola non compare nel set di dati a tutti, perché non c'è nessun ramo "q". A quel punto, si dice "va bene, nessuna corrispondenza." (Forse poi iniziare ad aggiungere la parola, forse no, a seconda dell'applicazione.)

Ma se la lettera successiva è "f", si può andare avanti. È possibile corto circuito che con un po 'di mestiere, però: una volta raggiunto un nodo che rappresenta un percorso unico nel suo genere, si può appendere il intera stringa off quel nodo. Quando si arriva a quel nodo, si sa che il resto della stringa deve essere "findibulum", così hai utilizzato il prefisso per abbinare l'intera stringa, e restituirlo.

Come si usa la tua che? in un sacco di non-UNIX comandare gli interpreti, come il vecchio VAX DCL, è possibile utilizzare qualsiasi prefisso univoco di un comando. Così, l'equivalente di ls (1) era DIRECTORY, ma nessun altro comando è iniziato con DIR, quindi è possibile digitare DIR e che era buono come fare l'intera parola. Se non si poteva ricordare il comando corretto, è possibile digitare solo 'D', e ha colpito (credo) ESC; la DCL CLI sarebbe tornato tutti i comandi che è iniziato con D, che potrebbe cercare estremamente veloce.

Answer 2

Si scopre le estensioni GNU per lo standard C ++ lib include un'implementazione trie Patricia. Si trova sotto l'estensione-strutture di dati basato su policy. Vedere http://gcc.gnu.org/onlinedocs/libstdc++/ext /pb_ds/trie_based_containers.html

Answer 3

Un algoritmo alternativo: Keep It Simple Stupid

Basta fare un elenco ordinato delle parole chiave. Quando si dispone di un prefisso, ricerca binaria per trovare dove il prefisso sarebbe situato nella lista. Tutti i tuoi possibili completamenti si troverà a partire da tale indice, pronto per l'accesso al suo posto.

Questo algoritmo richiede solo il 5% del codice di un trie Patricia e sarà facile da mantenere, comprendere e aggiornamento. E 'quasi certo questo semplice ricerca lista sarà più efficiente pure.

L'unico lato negativo è che se si dispone di un gran numero di parole chiave lunga con prefissi simili, un trie può risparmiare un po 'di stoccaggio in quanto non ha bisogno di mantenere il prefisso completo per ogni ingresso. In pratica, se si dispone di meno di un paio di milioni di parole, questo non è un risparmio, perché il sovraccarico puntatore dell'albero dominerà. Questo risparmio è di più per le applicazioni come i database alla ricerca di stringhe di DNA con milioni di caratteri, non parole chiave del testo.

Answer 4

Un altro algo alternativa è un ricerca ternario albero (più efficiente della memoria) https://github.com/varunpant/TernaryTree/tree/master/TernaryTree