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.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
Répondre
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')
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.
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
mon dieu, donne une pause au gars. – moo
tant de downvotes, et personne ne se soucie d'expliquer pourquoi? C'est comme si les gens s'entassaient juste dessus. Cette réponse répond à toutes les contraintes demandées par l'utilisateur initial et est plus simple à comprendre et à maintenir. –
@reinier - J'imagine que vous êtes downvoted car les listes liées ne sont pas bonnes pour l'accès aléatoire, donc votre temps de recherche est linéaire dans le nombre d'éléments. Un tableau serait rapide (ish) s'il était déjà trié, mais ce serait O (log n), alors qu'un trie est O (m), où m est la longueur du préfixe. –
je serais tenté d'écrire Node.add() comme méthode itérative: ajouter def (auto, lettres): suivant = self n = len (lettres) pour l'index, lettre en énumérer (lettres): sinon (lettre dans next.children): next.children [lettre] = Node (lettre, index == n-1) next = next.children [ lettre] – hughdbrown
Mais essayez d'imaginer cela avec une indentation et une ligne correctes pauses. – hughdbrown
Voir également "DAWG", qui est un trie qui utilise moins de mémoire. Mais c'est compliqué à construire (au moins par rapport à un trie). – Fantius