étant donné les limitations actuelles:

• Il y aura jusqu'à 2 points d'interrogation
• Lorsqu'il y a deux points d'interrogation, ils apparaissent ensemble
• il y a environ 100 000 mots dans le dictionnaire, La longueur moyenne des mots est de 6.

j'ai deux solutions viables pour vous:

la solution rapide: HASH

vous pouvez utiliser un hash quelles clés sont vos mots avec jusqu'à deux"?"et les valeurs sont d'une liste de raccord mots. Cette empreinte sera autour de 100,000 + 100,000*6 + 100,000*5 = 1,200,000 entrées (si vous avez 2 points d'interrogation, vous avez juste besoin de trouver le lieu de la première...). Chaque entrée peut enregistrer une liste de mots, ou une liste de pointeurs sur des mots existants. Si vous enregistrez une liste de pointeurs, et nous supposons qu'il y a en moyenne moins de 20 mots correspondant à chaque mot avec deux"?', alors la mémoire supplémentaire est inférieure à 20 * 1.200.000 = 24,000,000.

si chaque pointeur est de 4 octets, alors l'exigence de mémoire ici est (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 MB
• Temps pour chaque critère de recherche: calcul d'une fonction de hachage, et à la suite d'un pointeur. O (1)

Note: Si vous voulez utiliser un hash d'une plus petite taille, vous peut, mais il est alors préférable de sauvegarder un arbre de recherche équilibré dans chaque entrée au lieu d'une liste liée, pour une meilleure performance.

L'espace de bon sens, mais encore très rapide de la solution: TRIE de variation

Cette solution utilise l'observation suivante:

si le"?"les signes étaient à la fin du mot, trie serait une excellente solution.

la recherche dans le trie chercherait à la longueur du mot, et pour les deux dernières lettres, une traversée DFS apporterait toutes les terminaisons. Très rapide, et très en mémoire savvy solution.

permet donc d'utiliser cette observation, afin de construire quelque chose pour fonctionner exactement comme cela.

Vous pouvez penser à chaque mot que vous avez dans le dictionnaire, un mot se terminant par @ (ou tout autre symbole qui n'existe pas dans votre dictionnaire). Donc, le mot "espace" serait " de l'espace@'. Maintenant, si vous tournez chacun de les mots, avec le signe'@', vous obtenez ce qui suit:

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

(non @ comme première lettre).

si vous insérez toutes ces variations dans un tri, vous pouvez facilement trouver le mot que vous cherchez à la longueur du mot, en "tournant" votre mot.

exemple: Tu veux trouver tous les mots qui correspondent??ce' (l'un d'eux est l'espace, l'autre est la tranche). Vous construisez le mot: s??ce@, et le tourner de sorte que le ? signe est à la fin. c'est à dire 'ce@s??

toutes les variations de rotation existent à l'intérieur du tri, et spécifiquement "ce@spa" (marqué avec * ci-dessus). Après le début est trouvé - vous devez passer en revue toutes les continuations dans la longueur appropriée, et les sauver. Ensuite, vous devez faire pivoter à nouveau de sorte que le @ est la dernière lettre, et walla - vous disposez de tous les mots que vous recherchez!

pour résumer cette solution:

• mémoire Consommation: Pour chaque mot, toutes ses rotations apparaissent dans le trie. En moyenne, *6 de la taille de la mémoire est enregistrée dans le trie. La taille du trie est d'environ * 3 (je suppose...) de l'espace économisé à l'intérieur. Donc l'espace total nécessaire pour ce tri est 6*3*100,000 = 1,800,000 mots ~ = 6,8 méga octets.

• Temps pour chaque recherche:

  • rotation du mot: O (longueur du mot)
  • à la recherche du début dans la trie: O(longueur de mot)
  • passant en revue toutes les fins: O (nombre de matchs)
  • faire tourner les terminaisons: O(longueur totale de réponses)

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

pour résumer...

le deuxième choix a une grande complexité temps/espace, et serait la meilleure option pour vous d'utiliser. Y quelques problèmes avec la deuxième solution (dans ce cas, vous pourriez vouloir utiliser la première solution):

• plus complexe à mettre en œuvre. Je ne suis pas sûr qu'il y ait des langages de programmation avec des essais intégrés à partir de la boîte. S'il n'y a pas - cela signifie que vous aurez besoin de le mettre en œuvre vous-même...
• n'a pas une bonne échelle. Si demain vous décidez que vous avez besoin de vos points d'interrogation répartis partout dans le monde, et pas nécessairement réunis, vous aurez besoin de réfléchir à la façon d'adapter la deuxième solution à elle. Dans le cas de la première solution, il est assez facile de généraliser.

pour moi, ce problème ressemble à un bon ajustement pour une structure de données Trie . Entrez tout le dictionnaire dans votre tri, et cherchez le mot. Pour une lettre manquante, vous devez essayer toutes les sous-tentatives, ce qui devrait être relativement facile à faire avec une approche récursive.

EDIT : je viens d'écrire une simple implémentation de ceci dans Ruby: http://gist.github.com/262667 .

un graphe acyclique dirigé serait une structure de données parfaite pour ce problème. Il combine l'efficacité d'un trie (trie peut être vu comme un cas particulier de DAWG), mais est beaucoup plus efficace de l'espace. Le DAWG typique prendra la fraction de taille que le dossier de texte simple avec des mots prendrait.

énumérer des mots qui répondent à des conditions spécifiques est simple et le même que dans trie - vous devez traverser le graphe en profondeur-première Mode.

la deuxième solution D'Anna est l'inspiration pour celle-ci.

d'abord, chargez tous les mots dans la mémoire et divisez le dictionnaire en sections basées sur la longueur des mots.

Pour chaque longueur, faire n copie d'un tableau de pointeurs vers les mots. Trier chaque tableau de sorte que les chaînes apparaissent dans l'ordre lorsqu'on fait tourner un certain nombre de lettres . Par exemple, supposons la liste originale de 5 lettres les mots de [l'avion, d'apple, de l'espace, train, heureux, pile, hacks]. Alors 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 rechercher, il suffit de demander combien vous auriez à tourner le motif de sorte que les points d'interrogation apparaissent à la fin. Ensuite, vous pouvez rechercher binaire dans la liste appropriée.

si vous avez besoin de trouver des correspondances ??ppy, tu devrais faire tourner ça de 2 pour faire ppy??. Alors regardez dans le tableau qui est dans l'ordre lors de la rotation par 2 lettres. Une recherche binaire rapide trouve que "happy" est la seule correspondance.

si vous avez besoin de trouver des allumettes pour th??g, tu devrais faire tourner ça de 4 pour faire gth??. Alors regardez dans le tableau 4, où une recherche binaire constate qu'il n'existe pas de correspondance.

cela fonctionne peu importe combien de points d'interrogation il y a, aussi longtemps que ils semblent tous ensemble.

espace requis en plus du dictionnaire lui-même: pour les mots de longueur N, cela nécessite de l'espace pour (N fois le nombre de mots de longueur N) pointeurs ou entiers.

Temps par la recherche de : O(log n) où n est le nombre de mots de 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]).rstrip('?')
        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 909KB grand et ce programme utilise environ 3.2 Mo de mémoire en plus de ce qu'il faut juste pour stocker les mots (pointeurs sont de 4 octets). Pour ce dictionnaire, vous pourriez couper cela en deux en utilisant des entiers de 2 octets au lieu de pointeurs, parce qu'il y a moins de 2 ¹⁶ mots de chaque longueur.

mesures: sur ma machine, m.find("st??k") fonctionne en 0.000032 secondes, m.find("ov???low") en 0.000034 secondes, et m.find("????????????????e") en 0.000023 secondes.

en écrivant la recherche binaire au lieu d'utiliser class RotatedArray et la bibliothèque bisect , j'ai obtenu ces deux premiers numéros à 0.000016 secondes: deux fois plus rapide. L'implémentation de ceci 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 regexes: matches(query,trialstr) .

un algorithme O(n) serait de simplement exécuter à travers chaque élément de liste (votre dictionnaire serait représenté comme une liste dans le programme), en comparant chacun à votre chaîne de requête.

avec un peu de pré-calcul, vous pouvez améliorer cela pour un grand nombre de requêtes en construisant une liste supplémentaire de mots pour chaque lettre, donc votre dictionnaire pourrait ressembler à:

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

Cependant, ce serait d'une utilité limitée, en particulier si votre chaîne de requête commence avec un personnage inconnu. Nous pouvons donc faire encore mieux en notant où se trouve, dans un mot donné, une lettre particulière, 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 nécessaire - spécifiquement un dictionnaire de n mots et la longueur moyenne m nécessite nm ² de stockage. Cependant, vous pouvez très rapidement maintenant faire votre recherche pour obtenir tous les mots de chaque ensemble qui peuvent correspondre.

l'optimisation finale (que l'on pourrait utiliser à l'improviste dans l'approche naïve) consiste à séparer tous les mots de la même longueur en magasins séparés, car on sait toujours combien le mot est long.

cette version serait O ( kx ) où k est le nombre de connu lettres dans le mot de requête, et x = x ( n ) est le temps de chercher un seul élément dans un dictionnaire de longueur n dans votre mise en œuvre (Habituellement 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, l'ensemble possiblewords contiendra toutes les lettres correspondantes.

si vous générez tous les mots possibles qui correspondent au motif (arate, arbte, arcte ... zryte, zrzte) et ensuite les rechercher dans une représentation d'arbre binaire du dictionnaire, qui aura les caractéristiques de performance moyenne de O(E^N1 * log(N2)) où N1 est le nombre de points d'interrogation et N2 est la taille du dictionnaire. Ça me semble assez bien pour moi, mais je suis sûr qu'il est possible de trouver un meilleur algorithme.

Modifier : si vous avez plus de dire, trois points d'interrogation, jetez un oeil à la réponse de Phil H et son approche d'indexation de lettre.

supposons que vous avez assez de mémoire, vous pourriez construire 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.tostring() in big_map:
      big_map[candidate.tostring()].add(word)
    else:
      big_map[candidate.tostring()] = 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 jeter un oeil à la façon dont son fait dans aspell . Il invite des suggestions de mot correct pour les mots Mal orthographiés.

construisez un jeu de hash de tous les mots. Pour trouver des correspondances, remplacez les points d'interrogation dans le motif par chaque combinaison possible de lettres. S'il y a deux points d'interrogation, une requête consiste 26 ² = 676 recherche rapide, à temps constant, des tables 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=j-i):
        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 il devient exponentiellement plus lent que vous ajoutez plus de points d'interrogation.

si une précision de 80 à 90% est acceptable, vous pourriez vous débrouiller avec le de Peter Norvig" spell checker . La mise en œuvre est petite et élégante.

une solution basée sur regex considérera chaque valeur possible dans votre dictionnaire. Si la performance est votre plus grande contrainte, un indice peut être construit pour accélérer considérablement.

vous pouvez commencer avec un index sur chaque longueur de mot contenant un index de chaque index=jeux de caractères correspondant aux mots. 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, dire"?ro??'le mot serait entrecoupé résultant dans {wrote, group} dans ce cas.

cela suppose que le seul caractère de remplacement sera un caractère unique et que la longueur du mot est connue à l'avance. Si ces hypothèses ne sont pas valides, je peux recommander l'appariement du texte en n-gramme, tel que discuté dans ce papier .

la structure de données que vous voulez est appelée un trie - voir le article de wikipedia pour un bref résumé.

un trie est une structure d'arbre où les chemins à travers l'arbre forment l'ensemble de tous les mots que vous souhaitez encoder - chaque noeud peut avoir jusqu'à 26 enfants, on pour chaque lettre possible à la position de caractère suivante. Voir le diagramme dans l'article de wikipedia pour voir ce que je veux dire.

avez-vous envisagé d'utiliser un ternaire recherche arbre ? La vitesse de recherche est comparable à celle d'un tri, mais elle est plus efficace sur le plan spatial.

j'ai mis en œuvre cette structure de données à plusieurs reprises, et c'est une tâche assez simple dans la plupart des langues.

Mon premier post avait une erreur que Jason a trouvé, il n'a pas bien fonctionné quand ?? l'était au début. J'ai maintenant emprunté les changements cycliques à Anna..

ma solution: Introduisez un caractère de fin de mot ( @ ) et stockez tous les mots déplacés de façon cyclique dans des tableaux triés!! Utilisez un tableau trié pour chaque longueur de mot. Quand on cherche "th"??e@", déplacer la chaîne pour déplacer le ?- marques à la fin (Obtenir e@th??) et de choisir le tableau contenant les mots de longueur 5 et faire un binaire rechercher le premier mot qui apparaît après la chaîne "e@th". Tous les mots restants dans le tableau correspondent, i.e., nous trouverons " e@thoo (thoose), e@thes (these), etc.

La solution a le temps de la complexité Log( N ), où N est la taille du dictionnaire, et il augmente la taille des données par un facteur de 6 ( la moyenne de la longueur des mots)

Voici comment je ferais:

1. concaténez les mots du dictionnaire en une longue chaîne séparée par un caractère autre que le mot.
2. mettez tous les mots dans une table d'arbre, où la clé est le mot et la valeur est le décalage du début du mot dans la grande corde.
3. trouver la base de la chaîne de recherche; c.-à-d. le plus grand substrat principal qui ne comprend pas un '?' .
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 suivant plus grand à 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éer un regex pour la chaîne de recherche et utiliser Matcher.find() pour rechercher le substrat correspondant à la gamme.

les Étapes 1 et 2 sont faits au préalable donnant une structure de données en utilisant O(NlogN) espace où N est le nombre de mots.

Cette approche dégénère à un brute-force regex recherche de la totalité du dictionnaire lors de la '?' apparaît dans la première position, mais plus loin vers la droite, il est, le moins de correspondance qui doit être fait.

MODIFIER :

pour améliorer la performance dans le cas où '?' est le premier caractère, créer une table de recherche secondaire qui enregistre les offsets de début/fin des passages de mots dont le deuxième caractère est "a", "b", et ainsi de suite. Ceci 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 quatrième caractère et ainsi de suite, mais vous vous retrouvez avec de plus en plus de petits nombres de plus en plus petits, 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, est de préparer la structure de données du dictionnaire comme ci-dessus pour toutes les rotations des mots dans le dictionnaire. Par exemple, la première rotation serait composée de tous les mots 2 caractères ou plus avec le premier caractère du mot déplacé à la fin du mot. La deuxième rotation serait des mots de 3 caractères ou plus avec les deux premiers caractères déplacés à la fin, et ainsi sur. Ensuite, pour effectuer la recherche, cherchez la séquence la plus longue de non-'?"caractères dans la chaîne de recherche. Si l'index du premier caractère de cette sous-couche est N , utilisez la rotation Nth pour trouver les plages, et cherchez dans la liste des mots de la nième rotation.

une solution paresseuse est de laisser SQLite ou un autre SGBD faire le travail pour vous.

créez simplement une base de données en mémoire, chargez vos mots et lancez un select en utilisant l'opérateur LIKE.

résumé: utiliser deux index compacts ayant fait l'objet d'une recherche binaire, l'un des mots, et l'un des mots inversé . Le coût de l'espace est 2N pointeurs pour les index; presque toutes les recherches vont très vite; le pire des cas, "??e", est toujours décent. Si vous faites des tables séparées pour chaque longueur de mot, cela ferait même le pire des cas très rapide.

Détails: Stephen C. posté un bonne idée : rechercher un dictionnaire ordonné pour trouver la gamme où le modèle peut apparaître. Cela n'aide pas, cependant, quand le motif commence avec un joker. Vous pourriez aussi indexer par longueur de mot, mais voici une autre idée: ajouter un index ordonné sur le inversé mots du dictionnaire; puis un modèle donne toujours une petite fourchette dans l'indice avant ou l'index mot inversé (puisque nous avons dit qu'il n'y a pas de modèles comme ?ABCD?). Les mots eux-mêmes n'ont besoin d'être stockés qu'une seule fois, les entrées des deux structures pointant vers les mêmes mots, et la procédure de recherche les regardant en avant ou en arrière; mais pour utiliser la fonction de recherche binaire intégrée de Python j'ai fait deux tableaux de chaînes séparées à la place, gaspillant un peu d'espace. (J'utilise un tableau trié au lieu d'un arbre comme d'autres l'ont suggéré, car il économise de l'espace et va au moins aussi vite.)

Code :

import bisect, re

def forward(string): return string
def reverse(string): return string[::-1]

index_forward = sorted(line.rstrip('\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)))

Essais: (Les le code fonctionne aussi pour des motifs comme ?AB?D? mais sans garantie de vitesse.)

>>> 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')
[]

efficacité: cela nécessite 2N pointeurs plus l'espace nécessaire pour stocker le dictionnaire-mot texte (dans la version accordée). Le pire moment vient sur le schéma??e 'qui regarde 44062 candidats dans mon 235k-word / usr / share/dict / words; mais presque toutes les requêtes sont beaucoup plus rapides, comme' h??lo " en regardant 190, d'indexation et d'abord sur la parole-longueur de la réduire '??e' presque rien, si nous en avons besoin. Chaque vérification de candidat va plus vite que les recherches de hashtable d'autres ont suggéré.

cela ressemble à la solution rotations-index , qui évite à tous les candidats de fausses correspondances au prix d'avoir besoin d'environ 10N pointeurs au lieu de 2N (en supposant une longueur moyenne de mot d'environ 10, comme dans mon /usr/share/dict/words).

vous pouvez faire une recherche binaire unique par recherche, au lieu de deux, en utilisant un fonction de recherche personnalisée qui recherche à la fois les données de base et les données de base (de sorte que la partie partagée de la recherche n'est pas répétée).

si vous avez seulement ? wildcards, no * wildcards qui correspondent à un nombre variable de caractères, vous pouvez essayer ceci: pour chaque index de caractères, construisez un dictionnaire des caractères aux ensembles de mots. i.e. si les mots sont écrire, a écrit, drate, arete, arite , votre structure de dictionnaire ressemblerait à ceci:

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"}
...

si vous voulez chercher a?i?? vous prendriez l'ensemble qui correspond à l'index des caractères 0 => 'un' {"arete", "arite"} et l'ensemble qui correspond à caractère d'index 2 = " i " = > {"écrire", "arite"} et de prendre l'ensemble de l'intersection.

si vous voulez vraiment quelque chose sur l'ordre d'un milliard de recherches par seconde (bien que je ne peux pas rêver pourquoi quelqu'un en dehors de quelqu'un qui fait le prochain grand-maître scrabble AI ou quelque chose pour un service web énorme voudrait que rapide), je recommande l'utilisation filetage filetage pour frayer [nombre de noyaux sur votre machine] fils + un fil maître que les délégués travaillent à tous ces fils. Puis appliquer la meilleure solution que vous avez trouvé jusqu'à présent et espérer que vous ne manquez pas de mémoire.

une idée que j'avais est que vous pouvez accélérer certains cas en préparant des dictionnaires découpés en tranches par lettre puis si vous connaissez la première lettre de la sélection, vous pouvez recourir à la recherche dans une botte de foin beaucoup plus petite.

une autre pensée que j'avais était que vous essayiez de forcer quelque chose -- peut-être construire un DB ou une liste ou quelque chose pour le scrabble?