Supposons que je reçois un grand dictionnaire dans un fichier plat avec 200 millions de mots et que ma fonction doit vérifier l'existence d'un mot donné dans le dictionnaire, quel est le moyen le plus rapide de le faire? Vous ne pouvez pas stocker le dictionnaire dans la mémoire car vous n'avez que 1 Go de mémoire. Vous pouvez le stocker dans la base de données, mais qui interrogeait, il serait toujours très lent sans optimisation. Vous ne pouvez pas indexer les mots complets car vous n'avez pas assez de ressources.
Edit: En plus de l'approche d'optimisation des fichiers mentionnée ci-dessous, existe-t-il une optimisation de la base de données? Je pense à créer des indices partiels, disons pour toutes les 2 lettres du mot jusqu'à une limite, je crée un index. Cela accélérerait-il la requête de la DB?
8 Réponses :
Utilisez l'algorithme de recherche String Boyer-Moore String?
http://fr.wikipedia.org/wiki/boyer%e2 % 80% 93moore_string_search_algorithm
Serait-il possible d'utiliser l'algorithme Boyer-Moore sans charger dans la mémoire principale?
Si vous n'avez aucun index, utilisez simplement un flux.
Parfois, la solution la plus simple est la meilleure. P>
public Int32 IndexOf(FileStream file, Byte[] ascii_bytes, Int32 start_index)
{
Int32 index = -1;
{
Int32 current = 0;
Int64 original_index = 0;
Boolean found = true;
file.Position = start_index;
current = file.ReadByte();
while (current >= 0)
{
if ((Byte)current == ascii_bytes[0])
{
found = true;
original_index = file.Position - 1;
for (Int32 i = 1; (i < ascii_bytes.Length && current > 0); i++)
{
current = file.ReadByte();
if ((Byte)current != ascii_bytes[i])
{
file.Position--;
found = false;
break;
}
}
if (found)
{
file.Position = original_index;
index = (Int32)original_index;
break;
}
}
current = file.ReadByte();
}
}
return index;
}
À peine le moyen le plus rapide de le faire
+1 pour le flux. -1 pour la recherche de force brute. Résultat net 0 vote.
@Chaos qu'il a demandé rapidement dans la question
En supposant que le dictionnaire a les mots dans l'ordre alphabétique, je tenterais de modifier Recherche binaire . Divisez et conquérez le fichier en sautant à un emplacement à mi-parcours dans le fichier et en voyant quel mot existe-t-il. Si supposé haut, divisez-le en deux et réessayez jusqu'à ce qu'il n'y ait pas d'emplacement de fichier pour tenter ou que le mot est trouvé.
(comme OUTIS mentionné dans un commentaire , après avoir sauté dans un lieu de fichier, vous devrez numériser à l'envers et en avant pour trouver les limites du mot que vous avez sauté.)
Vous pourrez peut-être l'optimiser en devinant une pièce de localisation juste à côté de la batte en fonction de la première lettre du mot. Par exemple, si le mot commence par "C", démarrez votre recherche autour de la section 3 / 26e du fichier. Cependant, en réalité, je pense que cette devin précoce ne fera qu'une différence négligeable.
D'autres optimisations pourraient inclure la conservation d'un petit sous-ensemble d'un index. Par exemple, conservez un index du premier mot qui commence par chaque lettre de l'alphabet ou gardez un index de chaque mot qui commence par chaque combinaison de deux lettres possible. Cela vous permettrait de limiter immédiatement votre zone de recherche.
J'aime ça, mais cela ne traite pas des limitations de mémoire présentées.
Pourquoi n'est-ce pas? Vous pouvez littéralement charger 100 octets à une heure en mémoire sur chaque saut de milieu de point de vue. Vous n'avez pas besoin de charger tout le fichier en mémoire.
+1, mais manque une chose: une position de fichier arbitraire sera probablement au milieu d'un mot. Facile à corriger en balayant des versements (ou vers l'arrière) jusqu'à ce qu'une limite de mot soit trouvée.
Comment sautez-vous à un endroit donné d'un fichier? Tout échantillon de code dans PHP ou Java?
@wo_shi_ni_ba_ba: Cela dépend de l'API du système de fichiers, mais il doit s'agir d'une seule fonction ou d'un appel de méthode. Pour PHP, il y a fsek . En Java, vous avez recherchablebytechannel.position (long) .
Plutôt que de numériser vers l'avant / en arrière pour trouver des limites de mots, vous pouvez créer un index des compensations dans le dictionnaire. Cela pourrait simplement s'adapter entièrement en mémoire avec des compensations 32 bits en fonction des besoins en mémoire du système d'exploitation et de programme. Vous pouvez vous échapper avec des compensations de 28 bits en échange de code légèrement plus compliqué. De plus, chaque entrée de la table à chaîne pourrait être comprimée avec une bibliothèque telle que SharpziPlib (avec le dictionnaire de compression fixé dans votre programme). Cela réduirait IO lorsque vous lisez des parties du fichier à partir du disque.
... Réduisez IO au coût de certains processeurs.
Fsek (n) traverse-t-il l'une des données avant n? Ou est-ce une opération intangne?
@RYAN: Vous pouvez étendre l'optimisation de la position. Laissez dict être le dictionnaire et mot Soyez le mot recherché. À une itération donnée, supposons que la première différence entre les mots au niveau inférieur l et supérieure u est en position i . Alors m = abs (mot [i] -dict [l] [i] [i]) / abs (dict [u] [i] -dict [l] [i] [i]) + l est le point central devinué . Fondamentalement, vous supposez une distribution uniforme. Toujours O (journal (n))), mais le calendrier devrait impliquer un facteur constant beaucoup plus petit, donnant une vitesse réelle mondiale.
@RYAN: Cette approche a-t-elle eu lieu moins de 2 secondes dans le monde réel ayant reçu un PC normal avec 1 Go de RAM?
@WO_SHI_NI_BA_BA: dépend du système de fichiers, mais dans n'importe quel modernité de modification de la position du fichier actuel met à jour un entier tenant la position. Le dispositif stockant le fichier ne cherchera pas avant la prochaine lecture du fichier, à quel point la plupart des périphériques passeront à l'emplacement car la plupart des périphériques de stockage (disque dur, CD, DVD, mémoire flash et C) sont un accès aléatoire. Si les données sont stockées sur un périphérique d'accès séquentiel (E.G. ruban adhésif), il devrait passer sur (mais pas lire) des données intervenant à la prochaine opération de lecture.
En passant, le stockage des données sur un lecteur flash pourrait être plus rapide que de la stocker sur un disque dur assez rapide. C'est l'idée de base derrière ReadyBoost ... Les transferts IO réels sont plus lents sur un lecteur flash, mais le temps "cherche" est beaucoup plus rapide. Si votre disque dur comporte une grande quantité de cache par rapport à votre ensemble de données, vous êtes probablement mieux à l'abri avec le disque dur.
@wo_shi_ni_ba_ba: (Re: 2 s) difficile à dire, car cela dépend trop de la vitesse du système d'E / S du PC et du périphérique de stockage. Que ce soit un disque dur de 5400 tr / min ou 15 000 tr / min ou un CD fait une différence. Chaque fois qu'un disque doit rechercher, sa tête de lecture doit être repositionnée et le disque doit faire pivoter jusqu'à ce que le secteur approprié soit sous la tête; à la fois augmenter la latence. La mémoire flash n'aura pas de temps de recherche.
@wo_shi_ni_ba_ba Supposons que un disque dur absolument horrible recherche de 50 ms (pour la simplicité de couvrant également tout autre temps de calcul). La perquisition binaire du pire des cas sera la base de journal 2 de 200 000 000, soit 27,5. 27,5 x 50ms = 1,375 secondes. (La plupart des temps de disque dur cherchent des heures environ 9 ms.)
Une optimisation très simple consiste à utiliser des mots de longueur fixe - sûr, cela prendra plus d'espace disque, mais devinera où chercher dans un calcul trivial serait plus que la peine. Utilisez le mot le plus grand comme la taille. Si vous pouvez utiliser des mots de taille fixe + des mots triés, cela devient un problème de recherche binaire assez facile et efficace. Si vous parlez de multiples langues et d'unicode, où vous ne pouvez pas nécessairement regrouper tous les mots dans une sorte - Eh bien, vous parlez d'un monde de blessures.
Ceci est un cas d'utilisation classique pour un Filtre de floraison . Un filtre en fleurs est une structure de données probabilistique optimisée pour les tests d'adhésion ("IS x un membre de cette collection?"), Et fournit O (1) recherche . En échange, vous introduisez une probabilité arbitraire faible d'un faux positif - c'est-à-dire que le filtre dira qu'un mot particulier est présent, mais ce n'est en réalité pas là. Plus vous utilisez de mémoire que vous utilisez, plus vous pouvez faire cette probabilité. Cependant, la probabilité de faux négatifs est zéro: le filtre ne dira jamais qu'un mot est absent s'il est réellement présent.
Dans votre cas spécifique, avec 8 milliards de bits (1 Go) pour travailler, vous pouvez obtenir un faux taux positif un peu mieux que 1 sur 1 000 000 000 essais. C'est un très faible taux de faux positif. Si vous avez regardé 200 millions de chaînes aléatoires, la probabilité que vous ne frappiez jamais un faux faux positif est d'environ 82%.
Cela ne nécessite pas que le dictionnaire soit trié, est hautement efficace et n'a pas besoin d'une base de données ou d'une autre structure de stockage auxiliaire. Dans l'ensemble, c'est probablement un bon choix pour vos besoins.
J'aime vraiment cela comme une suggestion, mais la question indique qu'il semble qu'il n'y ait pas de place pour de faux positifs.
Je ne vois rien penchant d'une manière ou d'une autre à ce sujet. Mais je vais clarifier ma réponse à ajouter que cela ne convient que si vous êtes d'accord avec une infime probabilité de faux positifs. Avec 8 milliards de bits pour travailler, vous pouvez obtenir un taux faux positif un peu mieux que l'un dans chaque milliard essentiel. C'est un très faible taux de faux positif. Si vous avez regardé les 200 millions de mots, la probabilité que vous ne frappiez jamais un faux faux positif est d'environ 82%.
Hypothèses:
Vous pouvez définir partiellement les données, prenant la majeure partie de la mémoire disponible: stocker des mots et leur position de départ dans le fichier à l'aide d'un arbre B ou d'une matrice triée (ce dernier est plus efficace de l'espace, mais nécessite Un seul bloc continu; également, B-Tree nécessite que vous stockiez la position finale d'un morceau pendant que le tableau ne le fait pas). Laissez suffisamment d'espace mémoire pour charger un seul morceau de mots du fichier. Rechercher dans l'index (traverse ou recherche binaire) pour le morceau qui contiendrait le mot. Une fois que vous avez trouvé le morceau spécifique de l'index partiel, chargez le morceau correspondant du fichier en mémoire et effectuez une recherche binaire dessus.
Si vous avez besoin de mémoire supplémentaire, vous pouvez lancer des éléments de la indice. Avec le tableau, vous pouvez réduire l'index des éléments n en utilisant le pseudo-c pseudocode suivant: comme la fin du morceau que je suis < Code> Index [i + 1] .start , l'algorithme est mort simple pour une mise en œuvre de la matrice. Pour les indices basés sur des arbres B, vous pouvez facilement fusionner des feuilles avec leurs parents.
Les problèmes de recherche de mots classiques peuvent être résolus efficacement en utilisant un Trie . Malheureusement, comme vous l'avez mentionné, vous ne pouvez pas stocker tous les des données dont vous avez besoin en mémoire, mais cela ne devrait pas vous empêcher d'utiliser une trigence pour réduire l'espace de recherche. Supposons que, au lieu de stocker l'ensemble de l'ensemble des mots dans la Trie, vous stockez uniquement le segment initial, et vos nœuds d'extrémité indiquent de petites collections de données facilement (et rapidement) recherchées dans la base de données.
+1. Mieux que ma réponse. Trie laisse stocker des positions de démarrage et d'extrémité dans le fichier et de becherch peut trouver le mot dans le fichier de fichier.
Supposons que mon espace d'échantillon soit toutes des lettres et tous les chiffres, puis 36 ^ 4 = 1 679 616, je peux construire au plus 4 à 5 niveaux d'essais, mais je suppose que cela contribue toujours à réduire beaucoup l'espace de recherche.
Bien sûr ... Mais puisque vous codez sur ce qui équivaut à l'ensemble des 4 préfixes de caractères, vous êtes toujours sensiblement réduisant votre ensemble. Cela dépend de la répartition des longueurs de vos mots à quel point cela est efficace, mais dans le pire des cas, vous pouvez rechercher les 4 premiers caractères de O (4) fois et recherchez le sous-ensemble des mots à cette feuille à l'aide de la solution des Outtis, comme Il suggère dans son commentaire.
@WO_SHI_NI_BA_BA: Vos mathématiques sont éteintes, mais cela fonctionne toujours à 5 niveaux en utilisant 1/2 gib. Chaque nœud prend n = 37 * taille de taille (vide *) octets (36 pointeurs de nœud enfant et marqueur de branche / feuille; dans une feuille, les 36 pointeurs sont interprétés comme des plages de fichiers [paires de démarrage / longueur] . Avec alignement, un nœud prend le même espace que 37 pointeurs). Il existe t = 2 * 27 / N Nœuds totaux (1/2 gib divisé par la taille d'un nœud), donnant une profondeur d'environ log (t) / journal (36) + 1 pour un arbre complet. Un nœud ne sait pas quel personnage commence par; Ces informations sont stockées implicitement dans l'indice du nœud dans une matrice de pointeur de l'enfant.
Cette question est posée dans le livre "Le manuel de design d'algorithme" et Afaik auteur a utilisé une trcrette comprimée pour contenir une grande quantité de données similaires (dans son cas, c'était des génomes humains) dans la mémoire / la RAM.
Si certains mots sont consultés avec une fréquence beaucoup plus élevée que d'autres, il peut être logique d'avoir un cache LRU en mémoire et une base de données derrière elle.
Si les mots partagent beaucoup de préfixes et de suffixes, vous pouvez probablement les charger tout en mémoire à l'aide d'un Dirigé Graphique de mot acyclique (quoi de neuf, dawg!)
C'est comme une trie, mais comprime les suffixes partagées. Si cela sera utile dépend de ce qui se trouve dans votre dictionnaire, mais ajustement 200 M en 1 Go de RAM pourrait être réalisable.
+1 pour DAWG sur Trie pour un stockage plus efficace dans un environnement contraint de la mémoire.
Les mots du dictionnaire de fichiers plats sont-ils dans l'ordre alphabétique?
Une base de données ne vous permettra pas de définir un index si l'indice est trop grand pour s'adapter à la RAM?
Cela semble être une question très artificielle donnée a) aucune langue que je connaisse n'a nulle part près de 200 millions de mots; et b) pourquoi imposer la limitation d'une structure de données sous-optimale?
oui les mots sont dans l'ordre alphabétique, il faut simplement trop de temps et trop d'espace Temp pour créer l'index
Cela ressemble plus à une table arc-en-ciel qu'une langue naturelle.
Non, c'est un problème réel mondial. Le problème HW serait plus bien défini.