Algorithme de compression pour coder les listes de mots

Question

Je suis à la recherche de suggestions spécifiques ou de références à un algorithme et / ou à des structures de données pour coder une liste de mots dans ce qui deviendrait effectivement un dictionnaire de vérification orthographique. Les objectifs de ce schéma entraîneraient un taux de compression très élevé de la liste de mots bruts dans la forme codée. La seule exigence de sortie du dictionnaire codé est que l’existence d’un mot cible proposé puisse être vérifiée par rapport à la liste de mots initiale de manière relativement efficace. Par exemple, l’application peut vouloir comparer 10 000 mots à un dictionnaire de 100 000 mots. Ce n'est pas l'obligation pour le formulaire de dictionnaire codé de pouvoir être reconverti [facilement] en formulaire de liste de mots d'origine - un résultat binaire oui / non est tout ce qui reste est nécessaire pour chaque mot testé par rapport au dictionnaire résultant.

Je suppose que le schéma de codage, pour améliorer le taux de compression, tirerait parti des structures connues dans une langue donnée telles que les formes singulières et plurielles, les formes possessives, les contractions, etc. Je suis particulièrement intéressé par le codage de mots principalement anglais, mais pour être clair, le schéma doit être capable de coder tous les "mots" texte ASCII.

L’application que j’ai à l’esprit, vous pouvez l’imaginer, concerne les périphériques intégrés où l’espace de stockage non volatile est très limité et où le dictionnaire constituerait une zone de mémoire en lecture seule accessible au hasard.

MODIFIER : pour résumer les exigences du dictionnaire:

• zéro faux positifs
• zéro faux négatifs
• taux de compression très élevé
• pas besoin de décompression

Answer 1

Voir "Développement d'une liste d'orthographe" de McIlroy à l'adresse sa page de pubs . Vieux papier classique sur la vérification orthographique sur un mini-ordinateur, dont les contraintes correspondent étonnamment bien à celles que vous avez énumérées. Analyse détaillée de la séparation par affixage et de deux méthodes de compression différentes: filtres de Bloom et schéma associé, codage de Huffman d'un jeu de bits fragmenté; Je préférerais utiliser les filtres de Bloom plutôt que la méthode qu'il a choisie, ce qui permet d’extraire quelques kB supplémentaires à un coût considérable en termes de rapidité. ( Programmation des perles contient un court chapitre sur ce document.)

Voir aussi les méthodes utilisées pour stocker le lexique dans les systèmes de recherche en texte intégral, par exemple. Introduction à la récupération d'informations . Contrairement aux méthodes ci-dessus, il n’ya pas de faux positifs.

Answer 2

Un filtre Bloom ( http://en.wikipedia.org/wiki/Bloom_filter et http://www.coolsnap.net/kevin/?p=13 ) est une structure de données utilisée pour stocker les mots du dictionnaire de manière très compacte dans certains correcteurs orthographiques. Il existe toutefois un risque de faux positifs.

Answer 3

Je suggérerais un arbre de suffixe matelassé. Bonne compression des listes de mots et d'excellents temps de recherche.

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

Answer 4

En résumé:

• zéro faux positifs
• zéro faux négatifs
• taux de compression élevé
• pas besoin d'inverser (c'est-à-dire pas de décompression nécessaire)

J'allais suggérer des filtres de Bloom, mais ceux-ci ont des faux positifs non nuls.

Au lieu de cela, Programming Pearls parle d’un ensemble similaire d’exigences ( / usr / share / dict / words en 41 Ko).

Cela a pris l'approche de la contraction des tiges: Par exemple: Envoyé était la racine. Des correctifs préalables et postérieurs pourraient donc être ajoutés:

• présent
• représente
• représentation
• fausse déclaration

Answer 5

Vous pouvez obtenir un taux de compression de 30% + sur le stockage des mots sous forme de suffixes successifs au format 7 bits. Je ne sais pas comment cela s'appelle, mais cela se traduit assez efficacement en une arborescence.

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

est de 26 caractères, comparé à:

a un un d comme et tout andes Android

qui est 33.

En tenant compte du taux de compression de 12,5% pour le stockage en tant que contenu 7 bits, le total de compression est d’environ 31%. Le taux de compression dépend bien sûr de la taille et du contenu de votre liste de mots.

Si vous convertissez cette structure en une arborescence de 26 racines, les recherches seront probablement plus rapides qu'une comparaison de sous-chaîne en texte brut par rapport à un fichier plat.

En y pensant bien, si vous utilisez seulement 26 caractères plus deux pour les délimiteurs, vous pouvez tout faire en 5 bits, ce qui représente 37,5% de compression, ce qui porte l’exemple ci-dessus à plus de 50%. taux.

Answer 6

Je pense que votre meilleur choix est un arbre de suffixe compressé / Tableau de suffixes compressés . Vous pouvez trouver une mine d'informations dans les liens ci-dessus. C’est un domaine de recherche en cours, très intéressant.

Answer 7

Je ne suis pas un expert en la matière, mais l'arbre du préfixe n'est pas assez solution standard à cela? Cela stocke les préfixes communs des mots une seule fois.

Answer 8

Pour la compression pure, le site Compression maximale offre quelques résultats pour 4 Mo liste de mots anglais, le meilleur programme compresse environ 400 Ko. La page du prix Hutter et le Indice de référence de compression de grand texte .

Answer 9

Knuth mentionne un "Patricia trie" dans L'art de la programmation informatique vol. 3 . Je ne l'ai jamais utilisé pour un travail réel, mais peut-être que ce serait utile.

modifier: quelle est votre contrainte de RAM? Si vous disposez de beaucoup plus de RAM que de ROM, la compression des données en ROM (nécessitant une décompression en RAM) est peut-être la bonne solution. Je suppose que si vous avez une quantité de RAM moyenne mais pas importante, vous pouvez techniquement également stocker des parties de la structure de données sous forme de blobs compressés en mémoire, ainsi qu'un cache le moins récemment utilisé pour en conserver plusieurs, puis décompresser dynamiquement le fichier approprié. blob quand il n'est pas dans le cache.