Kompressions-Algorithmus für die Codierung von Wortlisten

Question

Ich bin auf der Suche nach bestimmten Anregungen oder Hinweise auf einen Algorithmus und / oder Datenstrukturen für die Codierung eine Liste von Wörtern in das, was effektiv würde sich herausstellen würde ein Rechtschreibprüfung Wörterbuch sein. Die Ziele dieser Regelung würde in einem sehr hohen Verdichtungsverhältnis des rohen Wortliste in der codierten Form führen. Die einzige Ausgabeanforderung ich auf dem codierten Wörterbuch ist, dass jedes vorgeschlagene Zielwort für Existenz gegen die ursprüngliche Wortliste in eine relativ effizienten Art und Weise getestet werden kann. Zum Beispiel könnte wollen, dass die Anwendung 10.000 Worte gegen ein 100.000 Wort Wörterbuch überprüfen. Es ist nicht eine Voraussetzung für die codierte Wörterbuch Form [leicht] sein, um wieder in die ursprüngliche Wortliste Form umgewandelt - ein binäres Ja / kein Ergebnis alles, was für jedes Wort gegen das resultierende Wörterbuch getestet benötigt wird.

ich das Codierungsschema gehe davon aus, Kompressionsverhältnis zu verbessern, würde die Vorteile der bekannten Strukturen in einer bestimmten Sprache, wie Singular und Plural Formen annehmen, Possessivformen, Kontraktionen, etc. Ich in Codierung hauptsächlich englische Worte speziell interessiert bin, aber klar zu sein, muss die Regelung der Lage sein, jegliche und alle ASCII-Text „Worte“.

zu kodieren

Die besondere Anwendung, die ich im Sinne habe, können Sie davon ausgehen für Embedded-Geräte ist, wo nicht-flüchtiger Speicherraum an einer Prämie ist und das Wörterbuch würde ein zufällig zugänglich Nur-Lese-Speicherbereich sein.

EDIT : Um den Anforderungen des Wörterbuchs zusammenzufassen:

• Null Fehlalarme
• Null falsch-negative Ergebnisse
• sehr hohe Verdichtungsverhältnis
• keine Notwendigkeit für die Dekomprimierung

Answer 1

Siehe McIlroy "Entwicklung einer Rechtschreibung Liste" in < a href = "http://www.cs.dartmouth.edu/~doug/pubs.html" rel = "noreferrer"> seine Pubs . Klassisches altes Papier auf auf einem Mini-Computer Rechtschreibprüfung, die Einschränkungen Karte überraschend gut auf die, die Sie aufgelistet. Detaillierte Analyse der Affix Strippen und zwei verschiedene Kompressionsverfahren: Bloom-Filter und ein zugehöriges Schema Huffman-Codierung eines spärlichen bitset; Ich würde gehen mit Bloom wahrscheinlich Filter in den Vorzug der Methode er gepflückt, die ein paar mehr kB heraus zu erheblichen Kosten in Geschwindigkeit quetscht. ( Programmierung Pearls hat ein kurzes Kapitel über dieses Papier.)

Sehen Sie Methoden auch das Lexikon in Volltextsuche Systemen zu speichern, z.B. Einführung in Information Retrieval . Im Gegensatz zu dem oben genannten Verfahren hat dies keine Fehlalarme.

Answer 2

A Bloom-Filter ( http://en.wikipedia.org/wiki/Bloom_filter und http://www.coolsnap.net/kevin/?p=13 ) ist eine Datenstruktur in einigen Rechtschreibprüfprogramme zum speichern der Wörter aus dem Wörterbuch in einem sehr kompakt verwendet. Es besteht jedoch ein Risiko für Fehlalarme.

Answer 3

würde ich einen gepolsterten Suffixbaum vorschlagen. Gute Kompression auf Wortlisten und ausgezeichnete Lookup mal.

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

Answer 4

Fazit:

• Null Fehlalarme
• Null falsch-negative Ergebnisse
• hohe Verdichtungsverhältnis
• keine Notwendigkeit für eine inverse (das heißt keine Dekomprimierung notwendig)

Ich wollte Bloom Filter vorzuschlagen, aber diese haben nicht Null Fehlalarme.

Stattdessen Programmierung Perlen sprechen von einem ähnlichen Satz von Anforderungen (/usr/share/dict/words in 41K).

Dieser nahm den Ansatz der Kontraktion der Stämme: Zum Beispiel: geschickt war die Wurzel, so könnte Pre- und Post-Korrekturen hat hinzugefügt:

• vorhanden
• darstellen
• Darstellung
• Entstellung

Answer 5

Sie können ein 30% + Kompressionsverhältnis erhalten aus Worten als aufeinander folgende Suffixe in 7-Bit-Format zu speichern. Ich bin mir nicht sicher, was das heißt, aber es übersetzt ziemlich effektiv in eine Baumstruktur.

ex .: a + n + d + s | an + d + y | und + n + roid

sind 26 Zeichen, im Vergleich zu:

a ein Anzeige wie und irgendein Anden android

, die 33 ist.

Aliquotierung in 12,5% Kompressionsverhältnis für die Speicherung als 7-Bit-Inhalt, das ist etwa 31% Kompression insgesamt. Verdichtungsverhältnis hängt natürlich von der Größe und dem Inhalt Ihrer Wortliste.

Dieses Drehen in eine 26-Root-Baumstruktur wahrscheinlich in Lookups führen würde, die schneller als ein Klar Teilzeichenfolge Vergleich gegen eine flache Datei ist.

Kommen Sie, daran zu denken, wenn Sie nur 26 Zeichen mit plus zwei für Trennzeichen, können Sie in 5 Bits alles tun, was 37,5% Kompression in und von sich selbst, das obige Beispiel auf über 50% Kompression zu bringen Rate.

Answer 6

Ich denke, Ihre beste Wette ist ein Compressed Suffixbaum / Compressed Suffixarray . Sie können eine Fülle von Informationen in den obigen Links. Dies ist ein laufendes Forschungsgebiet, sehr interessant in der Tat.

Answer 7

Ich bin kein Experte auf diesem, aber nicht Präfixbaums ziemlich Standardlösung für dieses? Das speichert gemeinsame Präfixe von Wörtern nur einmal.

Answer 8

Für reine Kompression, das Maximums Compression Website bietet einige Ergebnisse für ein 4 MB Englisch Wortliste, bestes Programm komprimiert diese auf etwa 400 KB. Einige andere Kompressions Ressourcen für Text / Wort Kompression sind der Hutter-Preis und die Großer Text Compression Benchmark .

Answer 9

Knuth erwähnt eine "Patricia Trie" in Die Kunst der Programmierung vol-Computer. 3 . Ich habe es nie für eine wirkliche Arbeit verwenden aber vielleicht wäre hilfreich.

edit: was ist dein RAM Einschränkung? Wenn Sie viel mehr RAM als ROM verfügbar, möglicherweise Datenkompression in ROM (erfordert Dekompression in RAM) ist der richtige Weg zu gehen. Ich nehme an, wenn Sie ein Medium, aber nicht große Menge an RAM haben, technisch Sie auch Teile der Datenstruktur als komprimierten Blobs im Speicher ablegen können, und eines der am wenigsten kürzlich verwendeten Cache mehr von ihnen zu halten, um, dann dekomprimieren dynamisch die entsprechenden Klecks, wenn es nicht im Cache.