structure de données la plus efficace pour une liste de chaînes en lecture seule (environ 100 000) avec recherche de préfixe rapide

Question

J'écris une application qui a besoin de lire une liste de chaînes à partir d'un fichier, les enregistrer dans une structure de données, puis Recherchez ces chaînes par des préfixes. La liste des chaînes est simplement une liste de mots dans une langue donnée. Par exemple, si la fonction de recherche obtient "stup" comme paramètre, elle devrait retourner ["stupide", "stupidité", "stupeur" ...]. Il devrait le faire en O (log (n) * m), où n est la taille de la structure de données et m est le nombre de résultats et devrait être aussi rapide que possible. La consommation de mémoire n'est pas un gros problème en ce moment. J'écris ceci en python, donc ce serait génial si vous pouviez me diriger vers une structure de données appropriée (de préférence) implémentée en c avec des wrappers python.

Answer 1

Vous voulez un trie.

http://en.wikipedia.org/wiki/Trie

Je les ai utilisés dans les programmes de Scrabble et Boggle. Ils sont parfaits pour le cas d'utilisation que vous avez décrit (recherche de préfixe rapide).

Voici un exemple de code pour construire un trie en Python. Cela vient d'un programme Boggle que j'ai monté ensemble il y a quelques mois. Le reste est laissé comme un exercice au lecteur. Mais pour la vérification des préfixes, vous avez besoin d'une méthode qui commence au nœud racine (la variable words), qui suit les lettres du préfixe aux nœuds enfants successifs, et renvoie Vrai si un tel chemin est trouvé et Faux dans le cas contraire.

class Node(object): 
    def __init__(self, letter='', final=False): 
     self.letter = letter 
     self.final = final 
     self.children = {} 
    def __contains__(self, letter): 
     return letter in self.children 
    def get(self, letter): 
     return self.children[letter] 
    def add(self, letters, n=-1, index=0): 
     if n < 0: n = len(letters) 
     if index >= n: return 
     letter = letters[index] 
     if letter in self.children: 
      child = self.children[letter] 
     else: 
      child = Node(letter, index==n-1) 
      self.children[letter] = child 
     child.add(letters, n, index+1) 

def load_dictionary(path): 
    result = Node() 
    for line in open(path, 'r'): 
     word = line.strip().lower() 
     result.add(word) 
    return result 

words = load_dictionary('dictionary.txt') 

Answer 2

Un trie (or prefix tree) sonne bien dans votre rue. Il peut faire la recherche sur une chaîne de préfixe de longueur m dans O (m) je crois.

Answer 3

matrice de chaînes.

puis recherche binaire pour rechercher par le premier match étape puis un par un à travers elle pour tous les matches ultérieurs

(i avais initialement liste chaînée ici aussi ... mais bien sûr, cela ne doit pas au hasard l'accès était donc ce « bs » (ce qui explique sans doute pourquoi je downvoted) Mon algorithme de recherche binaire est toujours le moyen le plus rapide d'aller si

Answer 4

Certaines implémentations Python de tries:.

• http://jtauber.com/2005/02/trie.py
• http://www.koders.com/python/fid7B6BC1651A9E8BBA547552FE3F039479A4DECC45.aspx
• http://filoxus.blogspot.com/2007/11/trie-in-python.html