So erstellen Sie eine TRIE in Python

Ich bin neu bei Python und versuche zu lernen und vorzurücken. Ich interessiere mich für TRIEs und DAWGs und ich habe viel darüber gelesen, aber ich verstehe nicht, wie die Ausgabe TRIE oder DAWG Datei aussehen soll.

  • Sollte ein TRIE ein Gegenstand von verschachtelten Wörterbüchern sein? Wo ist jeder Brief in Briefe und so weiter geteilt?
  • Würde ein Blick auf solch ein Wörterbuch schnell sein, wenn es 100k oder 500k Einträge gibt?
  • Wie man Wortblöcke implementiert, die aus mehr als einem Wort bestehen, das mit – oder Raum getrennt ist?
  • Wie verknüpfe ich Präfix oder Suffix eines Wortes mit einem anderen Teil in der Struktur? [Für DAWG]

Ich möchte die beste Ausgabestruktur verstehen, um herauszufinden, wie man erstellt und eins benutzt.

Ich würde auch schätzen, was die Ausgabe eines DAWG zusammen mit TRIE sein sollte .

Ich möchte keine grafischen Darstellungen mit miteinander verbundenen Blasen sehen, ich habe sie beim Lesen gesehen.

Ich möchte das Ausgabeobjekt kennen, sobald ein Satz von Wörtern in TRIEs oder DAWGs umgewandelt wird.

Vielen Dank.

7 Solutions collect form web for “So erstellen Sie eine TRIE in Python”

Unwind ist im Grunde richtig, dass es viele verschiedene Möglichkeiten gibt, eine Trie zu implementieren; Und für eine große, skalierbare Trie, verschachtelte Wörterbücher könnten schwerfällig werden – oder zumindest Raum ineffizient. Aber da du gerade erst anfängst, denke ich, das ist der einfachste Ansatz. Du könntest ein einfaches trie in nur wenigen Zeilen kodieren. Zuerst eine Funktion zum Konstruieren der Trie:

 >>> _end = '_end_' >>> >>> def make_trie(*words): ... root = dict() ... for word in words: ... current_dict = root ... for letter in word: ... current_dict = current_dict.setdefault(letter, {}) ... current_dict[_end] = _end ... return root ... >>> make_trie('foo', 'bar', 'baz', 'barz') {'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}}, 'z': {'_end_': '_end_'}}}, 'f': {'o': {'o': {'_end_': '_end_'}}}} 

Wenn Sie nicht mit setdefault vertraut setdefault , schaut es einfach einen Schlüssel im Wörterbuch (hier, letter oder _end ). Wenn der Schlüssel vorhanden ist, gibt er den zugehörigen Wert zurück; Wenn nicht, gibt es diesem Schlüssel einen Standardwert zu und gibt den Wert ( {} oder _end ) zurück. (Es ist wie eine Version von get dass auch das Wörterbuch aktualisiert.)

Als nächstes eine Funktion zu testen, ob das Wort in der Trie ist. Das könnte knapper sein, aber ich verlasse es so ausführlich, dass die Logik klar ist:

 >>> def in_trie(trie, word): ... current_dict = trie ... for letter in word: ... if letter in current_dict: ... current_dict = current_dict[letter] ... else: ... return False ... else: ... if _end in current_dict: ... return True ... else: ... return False ... >>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'baz') True >>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barz') True >>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barzz') False >>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'bart') False >>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'ba') False 

Ich werde die Einfügung und Entfernung zu Ihnen als Übung lassen.

Natürlich wäre Unwinds Vorschlag nicht viel schwieriger. Es könnte einen leichten Geschwindigkeitsnachteil geben, da das Finden des richtigen Unterknotens eine lineare Suche erfordert. Aber die Suche wäre auf die Anzahl der möglichen Zeichen beschränkt – 27 wenn wir _end . Auch gibt es nichts zu gewinnen durch die Schaffung einer massiven Liste der Knoten und Zugriff auf sie durch Index, wie er vorschlägt; Sie können auch nur die Listen nisten.

Schließlich füge ich hinzu, dass das Erstellen einer DAWG ein bisschen komplexer wäre, weil man Situationen erkennen muss, in denen dein aktuelles Wort ein Suffix mit einem anderen Wort in der Struktur teilt. In der Tat, das kann ziemlich komplex werden, je nachdem, wie Sie die DAWG strukturieren wollen! Sie müssen vielleicht etwas Zeug über Levenshtein Abstand zu bekommen, um es richtig zu bekommen.

Schau dir das an:

https://github.com/kmike/marisa-trie

Statische Speicher-effiziente Trie-Strukturen für Python (2.x und 3.x).

String-Daten in einem MARISA-Trie können bis zu 50x-100x weniger Speicher als in einem Standard-Python-Dict; Die rohe Suchgeschwindigkeit ist vergleichbar; Trie bietet auch schnell erweiterte Methoden wie Präfix-Suche.

Basierend auf marisa-trie C ++ – Bibliothek.

Hier ist ein Blog-Post von einer Firma mit marisa trie erfolgreich:
http://blog.repustate.com/sharing-large-data-structure-across-processes-python/

Bei Repustate können viele unserer Datenmodelle, die wir in unserer Textanalyse verwenden, als einfache Schlüsselwertpaare oder Wörterbücher im Python-Jargon dargestellt werden. In unserem speziellen Fall sind unsere Wörterbücher massiv, ein paar hundert MB pro Person, und sie müssen ständig zugegriffen werden. In der Tat für eine gegebene HTTP-Anfrage, 4 oder 5 Modelle zugegriffen werden können, jeder macht 20-30 Lookups. Also das Problem, mit dem wir konfrontiert sind, ist, wie halten wir die Dinge schnell für den Client sowie Licht wie möglich für den Server.

Ich habe dieses Paket gefunden, Marisa versucht, was ein Python-Wrapper um eine C ++ – Implementierung eines marisa trie ist. "Marisa" ist ein Akronym für Matching Algorithmus mit rekursiv implementiertem StorAge. Was ist großartig an marisa versucht, ist der Speichermechanismus wirklich schrumpft, wie viel Speicher Sie benötigen. Der Autor des Python-Plugins behauptete 50-100X Reduzierung in der Größe – unsere Erfahrung ist ähnlich.

Was ist großartig an der marisa trie-Paket ist, dass die zugrunde liegende Trie-Struktur auf die Festplatte geschrieben werden kann und dann über ein Speicher abgebildetes Objekt eingelesen wird. Mit einem Speicher abgebildet marisa trie, alle unsere Anforderungen sind jetzt erfüllt. Der Speicherverbrauch unseres Servers ging drastisch um etwa 40% zurück, und unsere Leistung war unverändert, als wir Pythons Wörterbuchimplementierung verwendeten.

Es gibt auch ein paar reine Python-Implementierungen, aber wenn du nicht auf einer beschränkten Plattform bist, würdest du die C ++ – unterstützte Implementierung oben für die beste Leistung verwenden möchten:

Hier ist eine Liste von Python-Pakete, die Trie implementieren:

  • Marisa-trie – eine C ++ – basierte Implementierung.
  • Python-trie – eine einfache reine pythonimplementierung.
  • PyTrie – eine fortgeschrittenere reine Python-Implementierung.

Geändert von der Methode des senderle (oben). Ich habe festgestellt, dass Python's defaultdict ideal für die Erstellung eines Trie oder ein Präfix-Baum ist.

 from collections import defaultdict class Trie: """ Implement a trie with insert, search, and startsWith methods. """ def __init__(self): self.root = defaultdict() # @param {string} word # @return {void} # Inserts a word into the trie. def insert(self, word): current = self.root for letter in word: current = current.setdefault(letter, {}) current.setdefault("_end") # @param {string} word # @return {boolean} # Returns if the word is in the trie. def search(self, word): current = self.root for letter in word: if letter not in current: return False current = current[letter] if "_end" in current: return True return False # @param {string} prefix # @return {boolean} # Returns if there is any word in the trie # that starts with the given prefix. def startsWith(self, prefix): current = self.root for letter in prefix: if letter not in current: return False current = current[letter] return True # Now test the class test = Trie() test.insert('helloworld') test.insert('ilikeapple') test.insert('helloz') print test.search('hello') print test.startsWith('hello') print test.search('ilikeapple') 

Es gibt kein "sollte"; Es liegt an dir. Verschiedene Implementierungen haben unterschiedliche Leistungsmerkmale, nehmen viel Zeit, um zu implementieren, zu verstehen und richtig zu werden. Das ist typisch für die Softwareentwicklung als Ganzes, meiner Meinung nach.

Ich würde wahrscheinlich zuerst versuchen, eine globale Liste aller Trie-Knoten so weit erstellt, und die Darstellung der Kind-Zeiger in jedem Knoten als eine Liste von Indizes in die globale Liste. Mit einem Wörterbuch nur um das Kind zu verknüpfen fühlt sich zu schwer-Gewicht, zu mir.

Wenn du eine TRIE als Python-Klasse implementieren möchtest, dann schreibe ich nach dem Lesen über sie:

 class Trie: def __init__(self): self.__final = False self.__nodes = {} def __repr__(self): return 'Trie<len={}, final={}>'.format(len(self), self.__final) def __getstate__(self): return self.__final, self.__nodes def __setstate__(self, state): self.__final, self.__nodes = state def __len__(self): return len(self.__nodes) def __bool__(self): return self.__final def __contains__(self, array): try: return self[array] except KeyError: return False def __iter__(self): yield self for node in self.__nodes.values(): yield from node def __getitem__(self, array): return self.__get(array, False) def create(self, array): self.__get(array, True).__final = True def read(self): yield from self.__read([]) def update(self, array): self[array].__final = True def delete(self, array): self[array].__final = False def prune(self): for key, value in tuple(self.__nodes.items()): if not value.prune(): del self.__nodes[key] if not len(self): self.delete([]) return self def __get(self, array, create): if array: head, *tail = array if create and head not in self.__nodes: self.__nodes[head] = Trie() return self.__nodes[head].__get(tail, create) return self def __read(self, name): if self.__final: yield name for key, value in self.__nodes.items(): yield from value.__read(name + [key]) 

Diese Version benutzt Rekursion

 import pprint from collections import deque pp = pprint.PrettyPrinter(indent=4) inp = raw_input("Enter a sentence to show as trie\n") words = inp.split(" ") trie = {} def trie_recursion(trie_ds, word): try: letter = word.popleft() out = trie_recursion(trie_ds.get(letter, {}), word) except IndexError: # End of the word return {} # Dont update if letter already present if not trie_ds.has_key(letter): trie_ds[letter] = out return trie_ds for word in words: # Go through each word trie = trie_recursion(trie, deque(word)) pprint.pprint(trie) 

Ausgabe:

 Coool👾 <algos>🚸 python trie.py Enter a sentence to show as trie foo bar baz fun { 'b': { 'a': { 'r': {}, 'z': {} } }, 'f': { 'o': { 'o': {} }, 'u': { 'n': {} } } } 
Python ist die beste Programmiersprache der Welt.