Platzsparende Datenstruktur zum Speichern einer Wortliste?

Question

Gibt es etwas Besseres als eine Trie für diese Situation?

• Speichern einer Liste von ~ 100k englischen Wörter
• Needs minimale Speicher
• Lookups angemessen sein müssen, verwenden, sondern müssen Blitz nicht schnell sein

Ich arbeite mit Java, so war mein erster Versuch, nur ein Set <String> zu verwenden. Ich ziele jedoch auf ein mobiles Gerät ab, auf dem bereits wenig Speicher verfügbar ist. Da viele englische Wörter gemeinsame Präfixe haben, scheint ein Trie wie eine gute Wette zu sein, um etwas Speicher zu sparen - weiß jemand andere gute Optionen?

EDIT - Mehr Infos - Die Datenstruktur wird für zwei Operationen

• Answering verwendet werden: Ist einige Wort XYZ in der Liste?
• Generieren der Nachbarschaft von Wörtern um XYZ mit einem Buchstaben verschiedenen

Danke für die guten Anregungen

Answer 1

Was machst du? Wenn es Rechtschreibprüfung ist, könnten Sie einen Bloom-Filter verwenden - siehe code kata.

Answer 2

Sie noch die Baumstruktur selbst mit Trie halten müssen. Huffman encoding Das Alphabet oder N-Buchstaben (für gängige Formen wie "tion", "un", "ing") können die Häufigkeit des Auftretens in Ihrem Wörterbuch nutzen und den Eintrag in Bits komprimieren.

Answer 3

Eine Struktur I zur Minimierung des Raumes in einem Rechtschreibwörterbuch sah, war jedes Wort so zu kodieren:

• die Anzahl der Zeichen (ein Byte) gemeinsam mit dem letzten; und
• das neue Ende.

So die Wortliste

HERE   would encode as THIS 
sanctimonious      0,sanctimonious 
sanction       6,on 
sanguine       3,guine 
trivial       0,trivial 

Sie Speichern 7 Byte gerade dort oben (19%), vermute ich, die Einsparung für ein 20.000 Wort Wörterbuch ähnlich wäre nur aufgrund der Mindestabstände zwischen (gemeinsame Präfixe) benachbarter Wörter.

Um die Suche zu beschleunigen, gab es eine Tabelle mit 26 Einträgen im Speicher, die die Anfangsversätze für Wörter enthielt, die mit a, b, c, ..., z begannen. Die Wörter an diesen Offsets hatten immer 0 als erstes Byte, da sie keine Buchstaben mit dem vorherigen Wort hatten.

Dies scheint eine Art Trie, aber ohne die Zeiger zu sein, die sicherlich platzintensiv würden, wenn jedem Zeichen im Baum ein 4-Byte-Zeiger zugeordnet wäre.

Wohlgemerkt, das war von meinen CP/M Tagen, wo die Erinnerung viel knapper war als jetzt.

Answer 4

A Patricia Trie besser geeignet sein können:

http://en.wikipedia.org/wiki/Patricia_tree

My (fuzzy) Speicher mir sagt, es in einigen der frühen Volltext-Suchmaschinen ...

Paul verwendet wurden.

Answer 5

Völlig wilde Idee ... (das heißt höchstwahrscheinlich sehr falsch)

Wie wäre es, die Worte wie ein Baum aller möglichen Buchstabenkombinationen zu speichern?

Dann kostet jedes "Wort" nur ein einziges Zeichen und zwei Zeiger (eins zum Zeichen und eins zu einem Terminator). Auf diese Weise, je mehr Buchstaben sie gemeinsam haben, desto weniger kostet jedes Wort.

 . . 
    // 
    r-p-s-. 
    /\\ 
    a \s-. 
/ t-. 
c  \ 
     s-. 

Auto Karpfen Autos Wagen Karren

Also für 9 Zeichen und 14 Zeiger Karpfen bekommen wir 6 "Wörter" in Höhe von insgesamt 25 Buchstaben.

Suchvorgänge wären schnell (Zeiger-Lookups statt Char-Vergleiche) und Sie könnten einige Stemming-Optimierungen vornehmen, um noch mehr Speicherplatz zu sparen ...?

EDIT: Sieht aus wie ich das Rad neu erfunden habe. ;-)

Answer 6

Verwandte zu Paul Beitrag:

Gibt es Gründe, warum Sie ein Trie in Ihrem Fall nicht berücksichtigen können? Wenn es nur ein implementaiton Problem, hier ist eine enge Implementierung von Patricia Trie-Einsatz und in C Suche (von NIST):

Patricia Insert in C

Patricia Search in C