memoria di ricerca efficace nella lista suffisso

Question

V'è un compito di costruire una sorta di dizionario per lista di suffissi, per un'istanza:

[., .com., a.com., a.b.com., org., some.org., ...] 

e per ogni stringa in entrata, per un'istanza "test.some .org." trova il suffisso più lungo nel dizionario costruito. Ci sono alcuni limiti di memoria. Qual è l'algoritmo/struttura dati più adatto per questo caso?

La scelta più ovvia per me è un trie per stringhe invertite, ma sembra consumare molta memoria. Ho provato ad usare array suffisso ma sembra che non si adatti all'operazione.

Il dizionario è immutabile, deve essere costruito una volta. Le rappresentazioni più efficienti in termini di memoria di prove immutabili?

Answer 1

Per un insieme di stringa immutabile, il compressed trie funziona molto bene. L'idea principale è quella di rappresentare un singolo ramo nel trie come un nodo. Ci sono molte descrizioni/documenti utili di questo metodo nel web.