Bon algorithme et bonne structure de données pour la recherche de mots avec des lettres manquantes ?

Question

Je dois é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 j'ai th??e Il se peut que l'on me réponde "ces", "ces", "thème", "là", etc.

Il y aura jusqu'à DEUX points d'interrogation et lorsque deux points d'interrogation apparaissent, ils le font dans l'ordre.

Je me demandais si quelqu'un pouvait me suggérer des structures de données ou des algorithmes à utiliser.

Un Trie est trop peu encombrant et le rendrait trop lent. D'autres idées de modifications ?

Actuellement, j'utilise 3 tables de hachage pour les correspondances exactes, 1 point d'interrogation et 2 points d'interrogation. À partir d'un dictionnaire, j'établis une table de hachage pour tous les mots possibles. Par exemple, si j'ai le mot MOT. J'introduis WORD, ?ORD, W?RD, WO?D, WOR ?, ??RD, W??D, et WO ?? dans le dictionnaire. J'utilise ensuite une liste de liens pour relier les collisions entre elles. Disons que hash(W?RD) = hash(STR?NG) = 17. hashtab(17) pointera sur WORD et WORD pointera sur STRING car il s'agit d'une liste chaînée.

Le temps moyen de consultation d'un mot est d'environ 2e-6s. Je cherche à faire mieux, de préférence de l'ordre de 1e-9. Il a fallu 0,5 seconde pour insérer 3 millions d'entrées et 4 secondes pour consulter 3 millions d'entrées.

Answer 1

Je pense que dans ce cas, il est préférable d'utiliser un fichier plat où chaque mot est sur une seule ligne. Vous pouvez ainsi utiliser la puissance d'une recherche par expression régulière, qui est hautement optimisée et qui surpassera probablement n'importe quelle structure de données que vous pouvez concevoir vous-même pour ce problème.

Solution n° 1 : Utilisation d'une expression rationnelle (Regex)

Voici le code Ruby qui fonctionne 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 dossier wordlist.txt contient 45425 mots (téléchargeable) aquí ). Le résultat 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 l'ensemble du fichier et trouver toutes les correspondances qu'il contient. Et il s'adapte très bien à tous les types de requêtes, même lorsqu'un Trie est très lent :

interrogation ????????????????e

counterproductive
indistinguishable
microarchitecture
microprogrammable
0.018681

interrogation ?h?a?r?c?l?

theatricals
0.013608

Cela semble assez rapide pour moi.

Solution #2 : Regex avec des 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 rechercher le mot correct 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 #3 : Une grande table de hachage (exigences mises à jour)

Puisque vous avez modifié vos exigences, vous pouvez facilement développer votre idée et utiliser une seule grande table de hachage contenant tous les résultats précalculés. Mais au lieu de travailler vous-même sur les collisions, vous pourriez vous appuyer sur les performances d'une table de hachage correctement implémentée.

Je crée ici une grande table de hachage, dans laquelle chaque requête possible est associée à une liste de 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.strip
    # add all words with one ?
    w.length.times do |i|
      q = String.new(w)
      q[i] = "?"
      h[q].push w
    end
    # add all words with two ??
    (w.length-1).times do |i|
      q = String.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} entries 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 entries 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 de 2.0e-05 est probablement inférieur à la précision du timer. En l'exécutant 1000 fois, j'obtiens une moyenne de 1,958e-6 secondes par requête. Pour aller plus vite, je passerais au C++ et j'utiliserais la fonction Google Sparse Hash qui est extrêmement efficace en termes de mémoire et rapide.

Solution n°4 : Soyez vraiment sérieux

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

• Tentatives de correspondance approximative des chaînes de caractères - S'ils sont bien mis en œuvre, les essais peuvent être très peu gourmands en mémoire (50 % d'espace en moins que le dictionnaire lui-même) et sont très rapides.
• Agrep - Un outil rapide de comparaison approximative de motifs - Agrep est basé sur un nouvel algorithme efficace et flexible pour la correspondance approximative des chaînes de caractères.
• Recherche Google Scholar pour une correspondance approximative des chaînes de caractères - Il y a plus qu'assez de choses à lire sur ce sujet.

Answer 2

Compte tenu des limites actuelles :

• Il y aura jusqu'à 2 points d'interrogation
• Lorsqu'il y a 2 points d'interrogation, ils apparaissent ensemble
• Le dictionnaire contient environ 100 000 mots, dont la longueur moyenne est de 6.

J'ai deux solutions viables à vous proposer :

La solution rapide : HASH

Vous pouvez utiliser un hachage dont les clés sont vos mots avec un maximum de deux '?', et les valeurs sont une liste de mots correspondants. 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 l'emplacement du premier...). Chaque entrée peut sauvegarder une liste de mots, ou une liste de pointeurs vers les mots existants. Si vous sauvegardez une liste de pointeurs, et si 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 la taille de chaque pointeur est de 4 octets, le besoin en mémoire est 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 MB
• 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 plus petite, vous pouvez le faire, mais il est alors préférable d'enregistrer un arbre de recherche équilibré dans chaque entrée au lieu d'une liste chaînée, pour de meilleures performances.

La solution la moins encombrante, mais très rapide : TRIE variation

Cette solution s'appuie sur l'observation suivante :

Si les signes '?' étaient à la fin du mot, trie serait une excellente solution.

La recherche dans le tableau porterait sur la longueur du mot et, pour les deux dernières lettres, une traversée DFS apporterait toutes les terminaisons. Cette solution est très rapide et très économe en mémoire.

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

Vous pouvez considérer chaque mot que vous avez dans le dictionnaire comme un mot se terminant par @ (ou tout autre symbole qui n'existe pas dans votre dictionnaire). Ainsi, 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

(pas de @ comme première lettre).

Si vous insérez toutes ces variations dans un TRIE, vous pouvez facilement trouver le mot que vous cherchez à la longueur du mot, en faisant "tourner" votre mot.

Exemple : Vous voulez trouver tous les mots qui correspondent à "s??ce" (l'un d'entre eux est espace, un autre est tranche). Vous construisez le mot : s??ce@, et vous le tournez de manière à ce que le signe ? soit à la fin. c'est-à-dire 'ce@s???'

Toutes les variations de rotation existent à l'intérieur du triangle, et en particulier 'ce@spa' (marqué d'un * ci-dessus). Une fois le début trouvé, vous devez passer en revue toutes les continuations de la longueur appropriée et les sauvegarder. Ensuite, vous devez les faire pivoter à nouveau de façon à ce que le @ soit la dernière lettre, et walla - vous avez tous les mots que vous cherchiez !

Pour résumer cette solution :

• Consommation de mémoire : Pour chaque mot, toutes ses rotations apparaissent dans le tableau. En moyenne, *6 de la taille de la mémoire est sauvegardée dans le triangle. La taille du fichier est d'environ *3 (juste une supposition...) de l'espace sauvegardé à l'intérieur du fichier. Ainsi, l'espace total nécessaire pour ce tableau est de 6*3*100 000 = 1 800 000 mots ~= 6,8 méga-octets.

• Durée de chaque recherche :

  • la rotation de la parole : O(longueur du mot)
  • chercher le début dans le procès : O(longueur du mot)
  • en passant en revue toutes les terminaisons : O(nombre de correspondances)
  • la rotation des fins : O(longueur totale des réponses)

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

En résumé...

Le deuxième choix présente une grande complexité en termes de temps et d'espace, et serait la meilleure option pour vous. La deuxième solution pose quelques problèmes (dans ce cas, il serait préférable d'utiliser la première solution) :

• Plus complexe à mettre en œuvre. Je ne suis pas sûr qu'il existe des langages de programmation qui intègrent d'emblée les essais. Si ce n'est pas le cas, cela signifie que vous devrez l'implémenter vous-même...
• Ne s'adapte pas bien à l'échelle. Si demain vous décidez que vos points d'interrogation doivent être répartis sur l'ensemble du mot, et pas nécessairement reliés entre eux, vous devrez réfléchir sérieusement à la manière d'adapter la deuxième solution. Dans le cas de la première solution, il est assez facile de la généraliser.

Answer 3

Il me semble que ce problème se prête bien à la mise en place d'un système d'information sur la santé. Trie structure des données. Saisissez l'intégralité du dictionnaire dans votre trie, puis recherchez le mot. Pour une lettre manquante, vous devriez essayer tous les sous-triés, ce qui devrait être relativement facile à faire avec une approche récursive.

EDITAR : Je viens d'écrire une implémentation simple de ceci en Ruby : http://gist.github.com/262667 .

Answer 4

Graphe de mots acyclique dirigé serait la structure de données idéale pour ce problème. Elle combine l'efficacité d'un trie (le trie peut être considéré comme un cas particulier de DAWG), mais elle est beaucoup moins encombrante. Un DAWG typique ne prend qu'une fraction de la taille d'un fichier texte contenant des mots.

L'énumération des mots qui répondent à des conditions spécifiques est simple et identique à celle d'un tableau - vous devez parcourir le graphe en profondeur d'abord.

Answer 5

La deuxième solution d'Anna est la source d'inspiration de celle-ci.

Tout d'abord, il faut charger tous les mots dans la mémoire et diviser le dictionnaire en sections en fonction de la longueur des mots.

Pour chaque longueur, faire n des copies d'un tableau de pointeurs sur les mots. Triez chaque tableau de manière à ce que les chaînes apparaissent dans l'ordre lorsqu'il est tourné d'un certain nombre de lettres . Par exemple, supposons que la liste originale de mots de 5 lettres soit [plane, apple, space, train, happy, stack, hacks]. Vos cinq tableaux de pointeurs seront alors les suivants :

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 vous permet d'économiser de l'espace sur votre plate-forme).

Pour effectuer une recherche, il suffit de demander à combien s'élèverait la rotation de la modèle de manière à ce que les points d'interrogation apparaissent à la fin. Vous pouvez ensuite effectuer une recherche binaire dans la liste appropriée.

Si vous devez trouver des correspondances pour ??ppy, vous devrez faire une rotation de 2 pour obtenir ppy ?? Il faut donc chercher dans le tableau ce qui est dans l'ordre lorsqu'on le fait pivoter de 2 lettres. Une recherche binaire rapide révèle que "happy" est la seule correspondance.

Si vous devez trouver des correspondances pour th??g, vous devrez faire une rotation de 4 pour obtenir gth ? Regardez donc dans le tableau 4, où une recherche binaire trouve qu'il n'y a pas de correspondance.

Cela fonctionne quel que soit le nombre de points d'interrogation, à condition qu'ils apparaissent tous ensemble.

Espace nécessaire 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) pointeurs ou entiers.

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

Mise en œuvre 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 fait 909 Ko et ce programme utilise environ 3,2 Mo de mémoire en plus de ce qu'il faut pour stocker les mots (les pointeurs font 4 octets). Pour ce dictionnaire, vous pourriez réduire cette consommation de moitié en utilisant des entiers de 2 octets à la place des 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 seconde, m.find("ov???low") en 0,000034 seconde, et m.find("????????????????e") en 0,000023 seconde.

En écrivant la recherche binaire au lieu d'utiliser la fonction class RotatedArray et le bisect j'ai ramené les deux premiers chiffres à 0,000016 seconde, soit deux fois plus vite. L'implémentation de cette méthode en C++ la rendrait encore plus rapide.