Trie vs albero suffisso vs matrice suffisso

Question

Quale struttura fornisce i migliori risultati di performance; trie (albero prefisso), albero di suffissi o array suffisso? ci sono altre strutture simili? Quali sono buone implementazioni Java di queste strutture?

Modifica:. In questo caso voglio fare string matching tra un grande dizionario di nomi e di un grande insieme di testi in linguaggio naturale, al fine di identificare i nomi del dizionario su testi

Answer 1

Il trie è stata la prima struttura di dati di questo tipo scoperto.

L'albero suffisso è un miglioramento rispetto al trie (che ha legami suffisso che permettono di ricerca errore lineare, l'albero suffisso trim rami inutili della trie quindi non richiede più spazio).

La matrice suffisso è una struttura di dati ridotta in base alla albero suffisso (nessun link suffisso (errore lento corrisponde), ma il pattern matching è molto veloce).

Il trie non è per uso del mondo reale perché consuma troppo spazio.

L'albero suffisso è più leggero e più veloce della trie e viene utilizzato per il DNA indice o ottimizzare alcune grandi motori di ricerca web.

L'array suffisso è più lenta in alcune ricerche reticolo rispetto all'albero suffisso ma utilizza meno spazio, ed è più diffuso di albero suffisso.

Nella stessa famiglia di strutture di dati:

Ci sono altre implementazioni, il CST è un'implementazione dell'albero suffisso utilizzando un array di suffissi e alcune strutture di dati aggiuntivi per ottenere alcune delle funzionalità di ricerca albero suffisso.

Il FCST prende ulteriormente, implementa un albero suffisso campionato con una matrice suffisso.

Il DFCST è una versione dinamica della FCST.

Espansione:

I due fattori importanti sono l'uso dello spazio e del tempo di esecuzione dell'operazione. Si potrebbe pensare che con le macchine moderne di giorno questo non è rilevante, ma per indicizzare il DNA di un singolo essere umano richiederebbe 40 gigabyte di memoria (utilizzando un albero di suffissi non compresso e non ottimizzata). E per costruire uno di questi indici su questa quantità di dati può richiedere giorni. Immaginate di Google, ha un sacco di dati ricercabili, hanno bisogno di un grande indice di tutte i dati web e non cambiano ogni volta che qualcuno costruisce una pagina web. Hanno una qualche forma di caching per questo. Tuttavia l'indice principale è probabilmente statica. E ogni paio di settimane o giù di lì che si riuniscono tutti i nuovi siti web e dei dati e costruire un nuovo indice, che sostituisce il vecchio quando il nuovo è finito. Non so quale algoritmo che usano per indicizzare, ma è probabilmente un array di suffissi con proprietà albero suffisso oltre un database partizionato.

Il CST utilizza 8 gigabyte, tuttavia la velocità di operazioni albero suffisso sono fortemente ridotti.

L'array suffisso può fare lo stesso in circa 700 Megas a 2 Gigas. Tuttavia non troverete errori genetici nel DNA con una matrice suffisso (che significa: la ricerca di un modello con un carattere jolly è molto molto più lento).

Il FCST (albero suffisso completamente compresso) può creare un albero suffisso nel 800 a 1,5 gigas. Con un piuttosto piccola peggioramento velocità verso il CST.

Il DFCST utilizza il 20% di spazio rispetto alla FCST, e perde velocità all'attuazione statica del FCST (tuttavia un indice dinamico è molto importante).

Non ci sono molte valide (spazio saggio) implementazioni dell'albero suffisso, perché è molto difficile fare l'aumento di velocità operazioni di compensare il costo delle strutture dati spazio di RAM.

Detto questo, l'albero suffisso ha risultati di ricerca molto interessanti per il pattern matching con errori. Il Corasick Aho non è veloce (se quasi veloce per alcune operazioni, non errore corrispondenti) e il Boyer Moore è lasciato nella polvere.

Answer 2

Quali operazioni si ha intenzione di fare? libdivsufsort era un tempo la migliore realizzazione matrice suffisso C.

Answer 3

Utilizzando Alberi suffisso è possibile scrivere qualcosa che abbinerà il dizionario al testo in O (n + m + k) il tempo dove n è lettere nel vostro dizionario, M è lettere nel testo, e K è il numero di corrispondenze . Tentativi sono molto più lenti per questo. Non sono sicuro di quello che un array suffisso è, quindi non posso commentare in merito.

Detto questo, è non banale per il codice e non mi capita di sapere di eventuali librerie Java che forniscono le funzioni necessarie.

Answer 4

  

EDIT: In questo caso voglio fare string matching tra un grande dizionario di nomi e di un grande insieme di   testi in linguaggio naturale, al fine di identificare i nomi del dizionario su testi.

Questo suona come una domanda di Aho-Corasick algoritmo : costruire un automa dal dizionario (in tempo lineare), che possono poi essere utilizzati per trovare tutte le occorrenze di una qualsiasi delle parole del dizionario in più testi (anche in tempo lineare).

(La descrizione in queste dispense , legata dalla sezione "collegamenti esterni" della pagina di Wikipedia, è molto più facile da leggere rispetto alla descrizione sulla pagina stessa.)

Answer 5

Trie vs albero suffisso

sia la struttura dei dati garantiscono un molto veloce guardare in alto, il tempo di ricerca è proporzionale alla lunghezza della parola di query, il tempo di complessità O (m) dove m è la lunghezza della parola query.

E 'media se abbiamo parola query che hanno 10 caratteri, quindi abbiamo bisogno al massimo 10 passi per trovarlo.

Trie : Un albero per memorizzare stringhe in cui v'è un nodo per ogni prefisso comune. Le stringhe sono memorizzati in nodi foglia in più.

albero suffisso : Una rappresentazione compatta di un trie corrispondente ai suffissi di una determinata stringa in cui tutti i nodi con un bambino vengono uniti con i loro genitori.

def provengono da: Dizionario di Algoritmi e Strutture Dati

generalmente Trie utilizzato per le parole del dizionario index (lessico) o qualsiasi set di stringhe Esempio D = {abcd, abcdd, bxcdf, ....., zzzz}

un albero il suffisso usato per indicizzare il testo utilizzando la stessa struttura dati "Trie" su tutti i suffissi del nostro testo T = abcdabcg tutti i suffissi di T = {abcdabcg, abcdabc, abcdab, abcda, abcd, abc, ab, a}

ora apparire come un gruppo di stringhe. costruiamo un trie oltre oltre questi gruppi di stringhe (tutti i suffissi di T).

la costruzione sia la struttura di dati è in lineare, richiede O (n) nel tempo e nello spazio.

in caso di dicionary (un insieme di stringhe): n = la somma dei caratteri di tutte le parole. nel testo:. n = lunghezza del testo

array suffisso:. È una tecnica per rappresentare un albero suffisso sapce compresso, è un array di tutte le posizioni di partenza di suffissi di stringa

è più lento di albero suffisso nel tempo di ricerca.

Per maggiori informazioni vai a wikipedia, c'è un buon articolo a parlare su questo argomento.

Answer 6

Io preferisco suffisso Auto Machine. Potete trovare maggiori dettagli attraverso il mio sito web: http://www.fogsail.net/2019/03/06/20190306/

entrare descrizione dell'immagine qui

Per prima cosa, Se è stato utilizzato la costruzione normale, esso richiede O (n ^ 2) di viaggiare in tutto il suffisso

Usiamo Radix-ordinamento per ordinare l'array suffisso dal primo carattere.

Ma, se risolveremo il primo carattere, siamo in grado di utilizzare le informazioni.

I dettagli sono mostrato dalle immagini (abbandono cinese)

classifichiamo serie dal primo-chiave, il risultato è presentato dal rettangolo rosso

Answer 7

Questa implementazione della indotto algoritmo di ordinamento (chiamato ISC) ha una versione Java per costruzione di array suffisso.