Bon algorithme et structure de données pour rechercher des mots avec des lettres manquantes?

J’ai donc besoin d’écrire un algorithme efficace pour rechercher des mots avec des lettres manquantes dans un dictionnaire et je veux l’ensemble des mots possibles.

Par exemple, si je l’avais, je pourrais peut-être récupérer ceux-ci, ceux-ci, theme, there.etc.

Je me demandais si quelqu’un pouvait suggérer des structures de données ou un algorithme que je devrais utiliser.

Merci!

EDIT: Un Trie est trop peu efficace et le rendrait trop lent. D’autres modifications d’idées?

MISE À JOUR: Il y aura jusqu’à deux points d’interrogation et lorsque deux points d’interrogation se produisent, ils se produiront dans l’ordre.

Actuellement, j’utilise 3 tables de hachage pour une correspondance exacte, 1 point d’interrogation et 2 points d’interrogation. Étant donné un dictionnaire, je hais tous les mots possibles. Par exemple, si j’ai le mot WORD. I hash WORD,? ORD, W? RD, WO? D, WOR ?,? RD, W? D, WO ??. dans le dictionnaire Ensuite, j’utilise une liste de liens pour relier les collisions ensemble. Alors, dites hash (W? RD) = hash (STR? NG) = 17. Le hashtab (17) désignera WORD et WORD indiquera STRING car il s’agit d’une liste liée.

Le temps moyen de recherche d’un mot est d’environ 2e-6s. Je cherche à faire mieux, de préférence de l’ordre de 1e-9.

EDIT: Je n’ai pas encore regardé ce problème mais cela a pris 0,5 secondes pour les insertions de 3m et cela a pris 4 secondes pour la recherche d’entrées de 3m.

Merci!

Je crois que dans ce cas, il est préférable d’utiliser un fichier plat où chaque mot se trouve sur une seule ligne. Avec cela, vous pouvez facilement utiliser la puissance d’une recherche par expression régulière, qui est hautement optimisée et qui surpassera probablement toute structure de données que vous pouvez concevoir vous-même pour résoudre ce problème.

Solution n ° 1: Utiliser Regex

Cela fonctionne le code Ruby pour ce problème:

def query(str, data) r = Regexp.new("^#{str.gsub("?", ".")}$") idx = 0 begin idx = data.index(r, idx) if idx yield data[idx, str.size] idx += str.size + 1 end end while idx end start_time = Time.now query("?r?te", File.read("wordlist.txt")) do |w| puts w end puts Time.now - start_time 

Le fichier wordlist.txt contient 45425 mots (téléchargeable ici ). La sortie du programme pour la requête ?r?te Est:

 brute crate Crete grate irate prate write wrote 0.013689 

Il ne faut donc que 37 millisecondes pour lire tout le fichier et y trouver toutes les correspondances. Et cela s’adapte très bien à tous les types de requêtes, même si un Trie est très lent:

requête ????????????????e

 counterproductive indistinguishable microarchitecture microprogrammable 0.018681 

requête ?h?a?r?c?l?

 theasortingcals 0.013608 

Cela me semble assez rapide.

Solution n ° 2: Regex avec données préparées

Si vous voulez aller encore plus vite, vous pouvez diviser la liste de mots en chaînes contenant des mots de même longueur et simplement rechercher la bonne en fonction de la longueur de votre requête. Remplacez les 5 dernières lignes par ce code:

 def query_split(str, data) query(str, data[str.length]) do |w| yield w end end # prepare data data = Hash.new("") File.read("wordlist.txt").each_line do |w| data[w.length-1] += w end # use prepared data for query start_time = Time.now query_split("?r?te", data) do |w| puts w end puts Time.now - start_time 

La construction de la structure de données prend maintenant environ 0,4 seconde, mais toutes les requêtes sont environ 10 fois plus rapides (en fonction du nombre de mots de cette longueur):

  • ?r?te 0.001112 sec
  • ?h?a?r?c?l? 0.000852 sec
  • ????????????????e 0.000169 sec

Solution n ° 3: une grande table de hachage (exigences mises à jour)

Comme vous avez modifié vos exigences, vous pouvez facilement développer votre idée en utilisant une seule grande table de hachage contenant tous les résultats pré-calculés. Mais au lieu de contourner vous-même les collisions, vous pouvez compter sur les performances d’une table de hachage correctement implémentée.

Ici, je crée une grande table de hachage, où chaque requête possible est mappée à une liste de ses résultats:

 def create_big_hash(data) h = Hash.new do |h,k| h[k] = Array.new end data.each_line do |l| w = l.ssortingp # add all words with one ? w.length.times do |i| q = Ssortingng.new(w) q[i] = "?" h[q].push w end # add all words with two ?? (w.length-1).times do |i| q = Ssortingng.new(w) q[i, 2] = "??" h[q].push w end end h end # prepare data t = Time.new h = create_big_hash(File.read("wordlist.txt")) puts "#{Time.new - t} sec preparing data\n#{h.size} ensortinges in big hash" # use prepared data for query t = Time.new h["?ood"].each do |w| puts w end puts (Time.new - t) 

La sortie est

 4.960255 sec preparing data 616745 ensortinges in big hash food good hood mood wood 2.0e-05 

La performance de la requête est O (1), il s’agit simplement d’une recherche dans la table de hachage. Le temps 2.0e-05 est probablement inférieur à la précision de la timer. Lorsque je l’exécute 1000 fois, j’obtiens une moyenne de 1.958e-6 secondes par requête. Pour le rendre plus rapide, je passerais en C ++ et utiliserais le Google Sparse Hash, qui est extrêmement efficace en termes de mémoire et rapide.

Solution n ° 4: Obtenir vraiment sérieux

Toutes les solutions ci-dessus fonctionnent et devraient être suffisantes pour de nombreux cas d’utilisation. Si vous voulez vraiment devenir sérieux et avoir beaucoup de temps libre, lisez quelques bons articles:

  • Tentative d’appariement de chaînes approximatif – Si elles sont bien implémentées, les tentatives peuvent avoir des besoins en mémoire très compacts (50% moins d’espace que le dictionnaire lui-même) et sont très rapides.
  • Agrep – Un outil de correspondance de modèle rapide et approximatif – Agrep est basé sur un nouvel algorithme efficace et flexible pour la correspondance de chaîne approximative.
  • Google Scholar recherche des correspondances de chaînes approximatives – Plus que suffisant pour lire ce sujet.

Compte tenu des limitations actuelles:

  • Il y aura jusqu’à 2 points d’interrogation
  • Quand il y a 2 points d’interrogation, ils apparaissent ensemble
  • Il y a ~ 100 000 mots dans le dictionnaire, la longueur moyenne des mots est 6.

J’ai deux solutions viables pour vous:

La solution rapide: HASH

Vous pouvez utiliser un hachage dont les clés sont composées de deux “?” Et les valeurs sont une liste de mots adaptés. Ce hachage aura environ 100 000 + 100 000 * 6 + 100 000 * 5 = 1 200 000 entrées (si vous avez 2 points d’interrogation, il vous suffit de trouver la place du premier …). Chaque entrée peut enregistrer une liste de mots ou une liste de pointeurs sur les mots existants. Si vous enregistrez une liste de pointeurs et que nous supposons qu’il y a en moyenne moins de 20 mots correspondant à chaque mot avec deux «?», La mémoire supplémentaire est inférieure à 20 * 1 200 000 = 24 000 000.

Si chaque taille de pointeur est de 4 octets, la mémoire requirejse est alors de (24 000 000 + 1 200 000) * 4 octets = 100 800 000 octets ~ = 96 méga-octets.

Pour résumer cette solution:

  • Consommation de mémoire: ~ 96 Mo
  • Temps pour chaque recherche: calcul d’une fonction de hachage et suivi d’un pointeur. O (1)

Remarque: si vous souhaitez utiliser un hachage de taille inférieure, vous pouvez le faire, mais il est préférable d’enregistrer une arborescence de recherche équilibrée dans chaque entrée au lieu d’une liste chaînée, pour de meilleures performances.

La solution spatiale, mais toujours très rapide: la variation TRIE

Cette solution utilise l’observation suivante:

Si la ‘?’ les signes étaient à la fin du mot, sortinge serait une excellente solution.

La recherche dans le sortinge chercherait à la longueur du mot, et pour les deux dernières lettres, une traversée DFS amènerait toutes les fins. Solution très rapide et très gourmande en mémoire.

Utilisons donc cette observation pour construire quelque chose qui fonctionne exactement comme ça.

Vous pouvez penser à chaque mot que vous avez dans le dictionnaire, en tant que mot se terminant par @ (ou tout autre symbole qui n’existe pas dans votre dictionnaire). Donc, le mot “espace” serait “espace @”. Maintenant, si vous faites pivoter chacun des mots, avec le signe «@», vous obtenez ce qui suit:

 space@, pace@s, ace@sp, *ce@spa*, e@spac 

(no @ comme première lettre).

Si vous insérez toutes ces variations dans un TRIE, vous pouvez facilement trouver le mot que vous recherchez en longueur de mot, en «faisant tourner» votre mot.

Exemple: Vous voulez trouver tous les mots qui correspondent à ‘s ?? ce’ (l’un d’eux est l’espace, un autre est la tranche). Vous construisez le mot: s ?? ce @, et faites-le pivoter pour que le? le signe est à la fin. ie ‘ce @ s ??’

Toutes les variations de rotation existent à l’intérieur du sortingeur, et spécifiquement «ce @ spa» (marqué avec * ci-dessus). Une fois le début trouvé, vous devez parcourir toutes les suites dans la longueur appropriée et les enregistrer. Ensuite, vous devez les faire pivoter à nouveau pour que le @ soit la dernière lettre, et walla – vous avez tous les mots que vous recherchiez!

Pour résumer cette solution:

  • Consommation de mémoire: Pour chaque mot, toutes ses rotations apparaissent dans le sortinge. En moyenne, * 6 de la taille de la mémoire est enregistrée dans le sortinge. La taille du sortingèdre se situe autour de * 3 (juste en devinant…) de l’espace enregistré à l’intérieur. Donc, l’espace total nécessaire pour ce sortinge est de 6 * 3 * 100 000 = 1 800 000 mots ~ = 6,8 méga octets.

  • Temps pour chaque recherche:

    • faire tourner le mot: O (longueur du mot)
    • cherchant le commencement dans le sortinge: O (longueur de mot)
    • passer en revue toutes les fins: O (nombre de correspondances)
    • rotation des fins: O (longueur totale des réponses)

    En résumé, il est très rapide et dépend de la longueur du mot * petite constante.

Pour résumer…

Le second choix a une grande complexité temps / espace et serait la meilleure option à utiliser. Il y a quelques problèmes avec la deuxième solution (dans ce cas, vous pouvez utiliser la première solution):

  • Plus complexe à mettre en œuvre. Je ne suis pas sûr qu’il existe des langages de programmation avec des essais intégrés. S’il n’y en a pas, cela signifie que vous devrez l’implémenter vous-même …
  • Ne pas bien évoluer Si, demain, vous décidez que vous avez besoin de vos points d’interrogation pour qu’ils soient diffusés dans le monde entier et qu’ils ne soient pas nécessairement liés, vous devrez réfléchir à la manière de régler la deuxième solution. Dans le cas de la première solution, il est assez facile de généraliser.

Pour moi, ce problème semble convenir à une structure de données Trie . Entrez le dictionnaire entier dans votre sortinge, puis recherchez le mot. Pour une lettre manquante, vous devriez essayer tous les sous-essais, ce qui devrait être relativement facile à faire avec une approche récursive.

EDIT : J’ai écrit une simple implémentation de ceci dans Ruby tout à l’heure: http://gist.github.com/262667 .

Un Word Word Acyclic dirigé serait la structure de données parfaite pour ce problème. Il combine l’efficacité d’un sortingé (le sortinge peut être considéré comme un cas particulier du DAWG), mais il est beaucoup plus efficace en termes d’espace. DAWG typique prendra une fraction de taille que prendrait un fichier texte avec des mots.

L’énumération des mots répondant à des conditions spécifiques est simple et identique à celle de sortinge – vous devez parcourir le graphe en profondeur d’abord.

La deuxième solution d’Anna est l’inspiration pour celle-ci.

Tout d’abord, chargez tous les mots en mémoire et divisez le dictionnaire en sections en fonction de la longueur des mots.

Pour chaque longueur, effectuez n copies d’un tableau de pointeurs vers les mots. Triez chaque tableau de manière à ce que les chaînes apparaissent dans l’ordre lorsqu’elles sont pivotées d’un certain nombre de lettres . Par exemple, supposons que la liste originale des mots de 5 lettres soit [avion, apple, space, train, happy, stack, hacks]. Ensuite, vos cinq tableaux de pointeurs seront:

 rotated by 0 letters: [apple, hacks, happy, plane, space, stack, train] rotated by 1 letter: [hacks, happy, plane, space, apple, train, stack] rotated by 2 letters: [space, stack, train, plane, hacks, apple, happy] rotated by 3 letters: [space, stack, train, hacks, apple, plane, happy] rotated by 4 letters: [apple, plane, space, stack, train, hacks, happy] 

(Au lieu de pointeurs, vous pouvez utiliser des entiers identifiant les mots, si cela économise de l’espace sur votre plate-forme.)

Pour effectuer une recherche, demandez simplement combien vous devrez faire pivoter le motif pour que les points d’interrogation apparaissent à la fin. Ensuite, vous pouvez effectuer une recherche binary dans la liste appropriée.

Si vous avez besoin de trouver des correspondances pour ?? ppy, vous devrez le faire pivoter de 2 pour faire ppy ??. Donc, regardez dans le tableau qui est dans l’ordre quand il est pivoté de 2 lettres. Une recherche binary rapide montre que “heureux” est le seul match.

Si vous avez besoin de trouver des correspondances pour th, g, vous devrez le faire pivoter de 4 pour créer un gth ??. Donc, regardez dans le tableau 4, où une recherche binary trouve qu’il n’y a pas de correspondances.

Cela fonctionne quel que soit le nombre de points d’interrogation, tant qu’ils apparaissent tous ensemble.

Espace requirejs en plus du dictionnaire lui-même: pour les mots de longueur N, il faut de l’espace pour (N fois le nombre de mots de longueur N) des pointeurs ou des nombres entiers.

Heure par recherche : O (log n) où n est le nombre de mots de la longueur appropriée.

Implémentation en Python:

 import bisect class Matcher: def __init__(self, words): # Sort the words into bins by length. bins = [] for w in words: while len(bins) <= len(w): bins.append([]) bins[len(w)].append(w) # Make n copies of each list, sorted by rotations. for n in range(len(bins)): bins[n] = [sorted(bins[n], key=lambda w: w[i:]+w[:i]) for i in range(n)] self.bins = bins def find(self, pattern): bins = self.bins if len(pattern) >= len(bins): return [] # Figure out which array to search. r = (pattern.rindex('?') + 1) % len(pattern) rpat = (pattern[r:] + pattern[:r]).rssortingp('?') if '?' in rpat: raise ValueError("non-adjacent wildcards in pattern: " + repr(pattern)) a = bins[len(pattern)][r] # Binary-search the array. class RotatedArray: def __len__(self): return len(a) def __getitem__(self, i): word = a[i] return word[r:] + word[:r] ra = RotatedArray() start = bisect.bisect(ra, rpat) stop = bisect.bisect(ra, rpat[:-1] + chr(ord(rpat[-1]) + 1)) # Return the matches. return a[start:stop] words = open('/usr/share/dict/words', 'r').read().split() print "Building matcher..." m = Matcher(words) # takes 1-2 seconds, for me print "Done." print m.find("st??k") print m.find("ov???low") 

Sur mon ordinateur, le dictionnaire système est gros de 909 Ko et ce programme utilise environ 3,2 Mo de mémoire en plus de ce qu’il faut juste pour stocker les mots (les pointeurs sont de 4 octets). Pour ce dictionnaire, vous pouvez réduire ce nombre de moitié en utilisant des nombres entiers de 2 octets au lieu de pointeurs, car il y a moins de 2 16 mots de chaque longueur.

Mesures: Sur ma machine, m.find("st??k") s’exécute en 0.000032 secondes, m.find("ov???low") en 0.000034 secondes et m.find("????????????????e") en 0.000023 secondes.

En écrivant la recherche binary au lieu d’utiliser la class RotatedArray et la bibliothèque class RotatedArray , j’ai obtenu ces deux premiers nombres à 0.000016 secondes: deux fois plus vite. L’implémenter en C ++ le rendrait encore plus rapide.

Nous avons d’abord besoin d’un moyen de comparer la chaîne de requête avec une entrée donnée. Supposons une fonction utilisant des expressions rationnelles: matches(query,sortingalstr) .

Un algorithme O (n) consisterait simplement à parcourir chaque élément de la liste (votre dictionnaire serait représenté sous forme de liste dans le programme), en comparant chacun à votre chaîne de requête.

Avec un peu de calcul préalable, vous pouvez améliorer cela pour un grand nombre de requêtes en créant une liste supplémentaire de mots pour chaque lettre, afin que votre dictionnaire puisse ressembler à ceci:

 wordsbyletter = { 'a' : ['aardvark', 'abacus', ... ], 'b' : ['bat', 'bar', ...], .... } 

Toutefois, cette utilisation serait limitée, en particulier si votre chaîne de requête commence par un caractère inconnu. Nous pouvons donc faire encore mieux en notant où se trouve une lettre particulière dans un mot donné, générant:

 wordsmap = { 'a':{ 0:['aardvark', 'abacus'], 1:['bat','bar'] 2:['abacus']}, 'b':{ 0:['bat','bar'], 1:['abacus']}, .... } 

Comme vous pouvez le voir, sans utiliser d’indices, vous finirez par augmenter considérablement la quantité d’espace de stockage requirejs – en particulier, un dictionnaire de n mots et une longueur moyenne m nécessiteront le stockage de nm 2 . Cependant, vous pouvez très rapidement faire votre recherche pour obtenir tous les mots de chaque ensemble qui peuvent correspondre.

L’optimisation finale (que vous pouvez utiliser rapidement sur l’approche naïve) consiste également à séparer tous les mots de même longueur en magasins distincts, car vous savez toujours combien de temps le mot est.

Cette version serait O ( kx ) où k est le nombre de lettres connues dans le mot de requête, et x = x ( n ) est le moment de rechercher un seul élément dans un dictionnaire de longueur n dans votre implémentation (généralement log ( n ).

Donc, avec un dictionnaire final comme:

 allmap = { 3 : { 'a' : { 1 : ['ant','all'], 2 : ['bar','pat'] } 'b' : { 1 : ['bar','boy'], ... } 4 : { 'a' : { 1 : ['ante'], .... 

Alors notre algorithme est juste:

 possiblewords = set() firsttime = True wordlen = len(query) for idx,letter in enumerate(query): if(letter is not '?'): matchesthisletter = set(allmap[wordlen][letter][idx]) if firsttime: possiblewords = matchesthisletter else: possiblewords &= matchesthisletter 

À la fin, les mots possiblewords définis contiendront toutes les lettres correspondantes.

Si vous générez tous les mots possibles qui correspondent au modèle (arate, arbte, arcte … zryte, zrzte) et que vous les recherchez ensuite dans une représentation en arbre binary du dictionnaire, vous obtiendrez les performances moyennes de O (e ^ N1 * log (N2)) où N1 est le nombre de points d’interrogation et N2 la taille du dictionnaire. Semble assez bon pour moi mais je suis sûr qu’il est possible de trouver un meilleur algorithme.

EDIT : Si vous voulez plus que dire, trois points d’interrogation, regardez la réponse de Phil H et son approche d’indexation des lettres.

Supposons que vous ayez suffisamment de mémoire, vous pouvez créer un hashmap géant pour fournir la réponse en temps constant. Voici un exemple rapide en python:

 from array import array all_words = open("english-words").read().split() big_map = {} def populate_map(word): for i in range(pow(2, len(word))): bin = _bin(i, len(word)) candidate = array('c', word) for j in range(len(word)): if bin[j] == "1": candidate[j] = "?" if candidate.tossortingng() in big_map: big_map[candidate.tossortingng()].add(word) else: big_map[candidate.tossortingng()] = set([word]) def _bin(x, width): return ''.join(str((x>>i)&1) for i in xrange(width-1,-1,-1)) def run(): for word in all_words: populate_map(word) run() >>> big_map["y??r"] set(['your', 'year']) >>> big_map["yo?r"] set(['your']) >>> big_map["?o?r"] set(['four', 'poor', 'door', 'your', 'hour']) 

Vous pouvez voir comment cela se fait en aspell . Il invite des suggestions de mot correct pour les mots mal orthographiés.

Construisez un jeu de hachage de tous les mots. Pour rechercher des correspondances, remplacez les points d’interrogation du motif par chaque combinaison possible de lettres. S’il y a deux points d’interrogation, une requête se compose de 26 2 = 676 recherches rapides et constantes de table de hachage.

 import itertools words = set(open("/usr/share/dict/words").read().split()) def query(pattern): i = pattern.index('?') j = pattern.rindex('?') + 1 for combo in itertools.product('abcdefghijklmnopqrstuvwxyz', repeat=ji): attempt = pattern[:i] + ''.join(combo) + pattern[j:] if attempt in words: print attempt 

Cela utilise moins de mémoire que mon autre réponse, mais cela devient de plus en plus lent lorsque vous ajoutez des points d’interrogation.

Si 80-90% de précision est acceptable, vous pouvez gérer avec le correcteur orthographique de Peter Norvig. La mise en œuvre est petite et élégante.

Une solution basée sur les regex prendra en compte toutes les valeurs possibles dans votre dictionnaire. Si la performance est votre plus grande contrainte, un index pourrait être construit pour l’accélérer considérablement.

Vous pouvez commencer par un index sur chaque longueur de mot contenant un index de chaque index = jeux de mots correspondant aux caractères. Pour la longueur 5 mots, par exemple, 2=r : {write, wrote, drate, arete, arite}, 3=o : {wrote, float, group} , etc. Pour obtenir les correspondances possibles pour la requête originale, dites ‘ ? ro ?? ‘, les ensembles de mots seraient intersectés, donnant lieu à {wrote, group} dans ce cas.

Cela suppose que le seul caractère générique sera un seul caractère et que la longueur du mot est connue à l’avant. Si ce ne sont pas des hypothèses valables, je peux recommander une correspondance de texte basée sur n-gramme, telle que discutée dans cet article .

La structure de données que vous voulez est appelée un sortinge – voir l’ article de Wikipedia pour un bref résumé.

Un sortinge est une arborescence où les chemins à travers l’arbre forment l’ensemble de tous les mots que vous souhaitez encoder – chaque nœud peut avoir jusqu’à 26 enfants, pour chaque lettre possible à la prochaine position de caractère. Voir le diagramme dans l’article de Wikipedia pour voir ce que je veux dire.

Avez-vous envisagé d’utiliser un arbre de recherche ternaire ? La vitesse de recherche est comparable à celle d’un sortinge, mais elle est plus efficace en termes d’espace.

J’ai implémenté cette structure de données à plusieurs resockets et c’est une tâche assez simple dans la plupart des langues.

Mon premier post a eu une erreur que Jason a trouvée, ça n’a pas bien fonctionné quand ?? était au début. J’ai maintenant emprunté les changements cycliques d’Anna.

Ma solution: Introduire un caractère de fin de mot (@) et stocker tous les mots décalés cycliques dans les tableaux sortingés! Utilisez un tableau sortingé pour chaque longueur de mot. En recherchant “th ?? e @”, décaler la chaîne pour déplacer les repères? Jusqu’à la fin (en obtenant e @ th ??) et choisir le tableau contenant les mots de longueur 5 et effectuer une recherche binary du premier mot apparaissant après la chaîne “e @ th”. Tous les mots restants dans le tableau correspondent, c’est-à-dire que nous trouverons “e @ thoo (thoose), e @ thes (ceux-ci), etc.

La solution a une complexité en temps Log (N), où N est la taille du dictionnaire, et augmente la taille des données d’un facteur d’environ 6 (la longueur moyenne des mots)

Voici comment je le ferais:

  1. Concaténer les mots du dictionnaire en une chaîne longue séparée par un caractère non-mot.
  2. Mettez tous les mots dans un TreeMap, où la clé est le mot et la valeur est le décalage du début du mot dans la grande chaîne.
  3. Trouvez la base de la chaîne de recherche. c’est-à-dire la plus grande sous-chaîne principale qui n’inclut pas de '?' .
  4. Utilisez TreeMap.higherKey(base) et TreeMap.lowerKey(next(base)) pour trouver la plage dans la chaîne entre laquelle les correspondances seront trouvées. (La méthode next doit calculer le mot plus grand suivant dans la chaîne de base avec le même nombre ou moins de caractères; par exemple, next("aa") est "ab" , next("az") est "b" .)
  5. Créez une expression régulière pour la chaîne de recherche et utilisez Matcher.find() pour rechercher la sous-chaîne correspondant à la plage.

Les étapes 1 et 2 sont effectuées au préalable en donnant une structure de données à l’aide de l’espace O(NlogN)N est le nombre de mots.

Cette approche dégénère en une recherche de regex en force brute du dictionnaire entier lorsque le '?' apparaît dans la première position, mais plus il est éloigné à droite, moins l’appariement doit être effectué.

EDIT :

Pour améliorer la performance dans le cas où '?' est le premier caractère, créez une table de consultation secondaire qui enregistre les décalages de début / fin des exécutions de mots dont le deuxième caractère est “a”, “b”, etc. Cela peut être utilisé dans le cas où le premier non? est le deuxième personnage. Vous pouvez nous une approche similaire pour les cas où le premier non? est le troisième caractère, le quasortingème caractère, etc., mais vous vous retrouvez avec un nombre de plus en plus grand de séries de plus en plus petites, et finalement cette optimisation devient inefficace.

Une approche alternative qui nécessite beaucoup plus d’espace, mais qui est plus rapide dans la plupart des cas, consiste à préparer la structure de données du dictionnaire comme ci-dessus pour toutes les rotations des mots du dictionnaire. Par exemple, la première rotation comprendrait tous les mots 2 caractères ou plus, le premier caractère du mot étant déplacé à la fin du mot. La deuxième rotation serait composée de mots de 3 caractères ou plus avec les deux premiers caractères déplacés à la fin, etc. Ensuite, pour faire la recherche, recherchez la plus longue séquence de non ‘?’ caractères dans la chaîne de recherche. Si l’index du premier caractère de cette sous-chaîne est N , utilisez la rotation Nth pour trouver les plages et recherchez dans la liste de mots de rotation N

Une solution paresseuse consiste à laisser SQLite ou un autre SGBD faire le travail pour vous.

Créez simplement une firebase database en mémoire, chargez vos mots et exécutez une sélection à l’aide de l’opérateur LIKE.

Résumé: Utilisez deux index binarys compacts, l’un des mots et l’un des mots inversés . Le coût en espace est de 2N pour les index; presque toutes les recherches vont très vite; le pire des cas, “?? e”, est toujours correct. Si vous créez des tableaux séparés pour chaque longueur de mot, cela rendra même le pire des cas très rapide.

Détails: Stephen C. a affiché une bonne idée : rechercher un dictionnaire ordonné pour trouver la plage où le motif peut apparaître. Cela n’aide toutefois pas lorsque le modèle commence par un caractère générique. Vous pouvez également indexer par longueur de mot, mais voici une autre idée: ajoutez un index ordonné sur les mots de dictionnaire inversés ; alors un motif donne toujours une petite plage soit dans l’index direct, soit dans l’index des mots inversés (puisque l’on dit qu’il n’y a pas de motifs comme? ABCD?). Les mots eux-mêmes doivent être stockés une seule fois, avec les entrées des deux structures pointant vers les mêmes mots, et la procédure de consultation les visualisant soit en avant soit en sens inverse; mais pour utiliser la fonction de recherche binary intégrée à Python, j’ai plutôt créé deux tableaux de chaînes séparés, ce qui gaspille de l’espace. (J’utilise un tableau sortingé au lieu d’un arbre, comme d’autres l’ont suggéré, car cela économise de l’espace et va au moins aussi vite.)

Code :

 import bisect, re def forward(ssortingng): return ssortingng def reverse(ssortingng): return ssortingng[::-1] index_forward = sorted(line.rssortingp('\n') for line in open('/usr/share/dict/words')) index_reverse = sorted(map(reverse, index_forward)) def lookup(pattern): "Return a list of the dictionary words that match pattern." if reverse(pattern).find('?') <= pattern.find('?'): key, index, fixup = pattern, index_forward, forward else: key, index, fixup = reverse(pattern), index_reverse, reverse assert all(c.isalpha() or c == '?' for c in pattern) lo = bisect.bisect_left(index, key.replace('?', 'A')) hi = bisect.bisect_right(index, key.replace('?', 'z')) r = re.compile(pattern.replace('?', '.') + '$') return filter(r.match, (fixup(index[i]) for i in range(lo, hi))) 

Tests: (The code also works for patterns like ?AB?D?, though without the speed guarantee.)

 >>> lookup('hello') ['hello'] >>> lookup('??llo') ['callo', 'cello', 'hello', 'uhllo', 'Rollo', 'hollo', 'nullo'] >>> lookup('hel??') ['helio', 'helix', 'hello', 'helly', 'heloe', 'helve'] >>> lookup('he?l') ['heal', 'heel', 'hell', 'heml', 'herl'] >>> lookup('hx?l') [] 

Efficiency: This needs 2N pointers plus the space needed to store the dictionary-word text (in the tuned version). The worst-case time comes on the pattern '??e' which looks at 44062 candidates in my 235k-word /usr/share/dict/words; but almost all queries are much faster, like 'h??lo' looking at 190, and indexing first on word-length would reduce '??e' almost to nothing if we need to. Each candidate-check goes faster than the hashtable lookups others have suggested.

This resembles the rotations-index solution, which avoids all false match candidates at the cost of needing about 10N pointers instead of 2N (supposing an average word-length of about 10, as in my /usr/share/dict/words).

You could do a single binary search per lookup, instead of two, using a custom search function that searches for both low-bound and high-bound together (so the shared part of the search isn't repeated).

If you only have ? wildcards, no * wildcards that match a variable number of characters, you could try this: For each character index, build a dictionary from characters to sets of words. ie if the words are write, wrote, drate, arete, arite , your dictionary structure would look like this:

 Character Index 0: 'a' -> {"arete", "arite"} 'd' -> {"drate"} 'w' -> {"write", "wrote"} Character Index 1: 'r' -> {"write", "wrote", "drate", "arete", "arite"} Character Index 2: 'a' -> {"drate"} 'e' -> {"arete"} 'i' -> {"write", "arite"} 'o' -> {"wrote"} ... 

If you want to look up a?i?? you would take the set that corresponds to character index 0 => ‘a’ {“arete”, “arite”} and the set that corresponds to character index 2 = ‘i’ => {“write”, “arite”} and take the set intersection.

If you seriously want something on the order of a billion searches per second (though i can’t dream why anyone outside of someone making the next grand-master scrabble AI or something for a huge web service would want that fast), i recommend utilizing threading to spawn [number of cores on your machine] threads + a master thread that delegates work to all of those threads. Then apply the best solution you have found so far and hope you don’t run out of memory.

An idea i had is that you can speed up some cases by preparing sliced down dictionaries by letter then if you know the first letter of the selection you can resort to looking in a much smaller haystack.

Another thought I had was that you were trying to brute-force something — perhaps build a DB or list or something for scrabble?