J'ai une énorme liste de séquences multi-octets (permet de les appeler des mots) que j'ai besoin de stocker dans un fichier et que je dois être capable de rechercher rapidement. Énormes moyens: environ 2 millions de personnes, chacun de 10 à 20 octets de longueur.
En outre, chaque mot doit avoir une valeur étiquette associée à celle-ci, de sorte que je puisse utiliser cela pour référencer davantage de données (externes) pour chaque élément (par conséquent, un dictionnaire de vérification orthographique ne fonctionne pas ici comme qui fournit uniquement un test de hit).
Si c'était juste en mémoire, et si la mémoire était nombreuses, je pouvais simplement stocker tous les mots dans une carte hachée (dictionnaire AKA, alias de paires de clé-valeur) ou dans une liste triée pour une recherche binaire.
Cependant, je voudrais compresser les données hautement et préférerais également ne pas avoir à lire les données en mémoire mais plutôt à rechercher dans le fichier.
Comme les mots sont principalement basés sur la langue anglaise, il y a une certaine probabilité que certains "Sillables" dans les mots se produisent plus souvent que d'autres - ce qui est probablement utile pour un algorithme efficace.
Quelqu'un peut-il me dire une technique ou un algorithme efficace pour cela?
ou même des exemples de code?
Je pense que Dawg ou quoi que ce soit des itinéraires similaires, le chemin dans des suffixes courants de cette façon ne fonctionnera pas pour moi, car je ne pourrai donc pas étiqueter chaque chemin de mot complet avec une valeur individuelle. Si je devais détecter des suffixes courants, je devrais les mettre dans leur propre dictionnaire (table de recherche) afin qu'un nœud trie puisse les référencer, mais le nœud conserverait son propre nœud de fin pour stocker la valeur de cette étiquette de la voie.
En fait, c'est probablement la voie à suivre:
Au lieu de construire les nœuds d'arbres pour des caractères simples uniquement, je pourrais essayer de trouver des séquences de caractères souvent utilisées et de faire un nœud aussi bien. De cette façon, des nœuds individuels peuvent couvrir plusieurs caractères, peut-être conduire à une meilleure compression.
Maintenant, si c'est viable, comment puis-je trouver des sous-séquences souvent utilisées dans toutes mes phrases?
Avec environ 2 millions de phrases consistant en généralement de 1 à 3 mots, il sera difficile de courir toutes les permutations de toutes les substrings possibles ...
5 Réponses :
Vous devez vous familiariser avec le fichier indexé.
Merci d'avoir essayé d'aider, mais je pense que je connais bien le concept de fichiers indexés. J'ai appris que ca. 1982, je pense :)
Je recommanderais d'utiliser une trie ou un dawg (Graphique de mot acyclique dirigé). Stanford, il y a une excellente conférence sur ce que vous voulez ici: http://academkeearth.org/ Conférences / Lexicon-Case-Etude
Merci pour le pointeur vidéo. Un peu long étiré (je pouvais sauter beaucoup de bases), mais explique bien toutes les pensées de conception derrière elle. Je crains aussi que Classic Dawg ne fonctionnera pas - j'ai ajouté des explications à mon message original à ce sujet.
Avez-vous essayé simplement d'utiliser une carte de hachage? Thing est, sur une architecture de système d'exploitation moderne, le système d'exploitation utilisera une mémoire virtuelle pour échanger des segments de mémoire inutilisés sur le disque de toute façon. Donc, il peut s'avérer que tout le chargement dans une carte de hachage est effectivement efficace.
et comme le souligne JKFF, votre liste ne serait que d'environ 40 Mo, ce qui n'est pas tout autant.
40 Mo est beaucoup si je dois l'inclure dans le téléchargement de mon application. Je m'attends à ce que ce soit populaire :)
En outre, j'essaie de garder l'empreinte mémoire sur le disque faible. Une table de hachage ne sera pas utile là-bas.
Il existe une structure de données appelée Trie. Je crois que cette structure de données convient parfaitement à vos besoins. Fondamentalement, une trie est un arbre où chaque nœud est une lettre et chaque nœud a des nœuds d'enfants. Dans une trie basée sur une lettre, il y aurait 26 enfants par nœud.
Selon la langue que vous utilisez, cela peut être plus facile ou mieux à stocker comme une liste de longueur variable pendant la création.
Cette structure donne: a) recherche rapide. Suite à un mot de longueur n, vous pouvez trouver la chaîne dans N liens dans l'arborescence. b) compression. Les préfixes courants sont stockés.
Exemple: Le mot banane et banal auront les deux B, A, N, un nœud de nœuds égal, puis le dernier nœud (a) aura 2 enfants, L et N. Vos nœuds peuvent également stocker d'autres informations sur le mot.
(http://fr.wikipedia.org/wiki/trie)
Andrew JS
J'ai eu un chasseur que ce serait ce que la réponse serait. Bien que je n'ai jamais manipulé de trie expressément, j'ai eu une idée que c'est ce dont on ressemblerait. Néanmoins, je me demande, pour gérer l'arbre, chaque nœud doit porter une liste de tous ses enfants. Dans un fichier compact ou un formulaire de mémoire, cela signifierait que, à condition que l'arborescence dépasse 1 Mo de taille, j'aurai besoin d'un pointeur 32 bits plus la taille du nom de l'enfant (dans un arbre organisé par un octet unique, ce serait un octet) . Je me demande si cela ne conduira pas à une consommation de mémoire excessive en raison de ce ménage.
@THOMAS - Vérifiez la vidéo que j'ai posté. Il s'agit d'un fichier utilisé par un Boggle AI qui contient une DAWG (semblable à une trie mais plus sophistiquée). Vous n'avez pas besoin de 32 bits pour stocker le pointeur - vous pouvez être un peu plus intelligent (compensations et champs de bit).
Regardez le papier "Comment sqezez un lexique" . Il explique comment construire un automate de l'État fini minimisé (qui n'est qu'un autre nom pour une DAWG) avec une cartographie unique de mots à des chiffres et inversement. Exactement ce dont vous avez besoin.
Merci, mais j'ai besoin de noeud de fin distinct pour chaque chemin. Voir mon original (amélioré) Post pourquoi.
Avec la FSA dans cet article, vous obtenez un numéro unique (et dense) pour chaque chemin. Aou peut utiliser ce numéro pour stocker l'iInformation associée à l'externe E.G. Dans un tableau, dans une base de données ou dans un fichier avec une longueur d'enregistrement fixe.
20 octets * 2 millions = 40 Mo. C'est la minuscule par rapport à la quantité typique de la mémoire dans un ordinateur. Si vous les stockez dans une matrice choisie, vous utiliserez une recherche binaire de recherche et vous aurez à peine besoin d'une mémoire supplémentaire du tout.
Oui, 40 Mo n'est pas beaucoup. Et si sa vitesse vous préoccupe, maintenez les données en mémoire la plus simple que possible.
Comme écrit ci-dessous, les 40 Mo doivent venir avec l'application, et j'aime garder la taille de téléchargement de l'application beaucoup plus petite. De plus, ce n'est pas la seule partition. Il y a une plus grande partie d'un autre ensemble de "mots", qui n'a pas besoin d'être consultable mais toujours compressable car il s'élèvera à environ 1 Go dans des chaînes brutes. Une fois que j'ai trouvé une algo appropriée pour ce qui précède, j'espère l'utiliser sur cet autre, plus grand, défini aussi bien.
En outre, pourquoi supposer que je ne voudrais peut-être pas utiliser ceci sur un appareil qui a beaucoup moins de mémoire à jouer avec un PC typique? iPhone, intégré, et ainsi de suite, tout pourrait faire partie de cela.
@THOMAS Je pense que les suggestions viennent de la recherche de personnes micro ou prématurément optimisent des choses. Beaucoup de gens pourraient soupçonner quelque chose comme ça se passe lors de la lecture de votre phrase J'aimerais compresser les données hautement sans autre explication.
@Belisarius: Oui, ça va m'apprendre à essayer d'être concis;)
Knuth a déclaré: «Nous devrions oublier de petites gains d'efficacité, dire environ 97% du temps: l'optimisation prématurée est la racine de tout le mal». Ce qui ne s'appliquerait pas ici, car il ne s'agit pas d'une petite efficacité. 40 Mo est toujours plus grand que la taille moyenne de l'application dans son intégralité. Il n'est pas non plus que des contraintes de taille prématurée ou une sensibilité ne peuvent être connues avant que tout codage soit effectué.