wake-up-neo.net

So erstellen Sie eine TRIE in Python

Ich bin neu in Python und versuche zu lernen und weiterzukommen. Ich interessiere mich für TRIEs und DAWGs und habe viel darüber gelesen, aber ich verstehe nicht, wie die TRIE- oder DAWG-Ausgabedatei aussehen sollte.

  • Sollte ein TRIE ein Objekt verschachtelter Wörterbücher sein? Wo ist jeder Brief in Briefe unterteilt und so weiter?
  • Wäre eine Suche in einem solchen Wörterbuch bei 100.000 oder 500.000 Einträgen schnell?
  • Wie implementiere ich Word-Blöcke, die aus mehr als einem Wort bestehen, mit - oder Leerzeichen?
  • Wie kann man das Präfix oder Suffix eines Wortes mit einem anderen Teil der Struktur verknüpfen? [für DAWG]

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

Ich würde mich auch darüber freuen, was die Ausgabe einer DAWG zusammen mitTRIEsein soll.

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

Ich würde gerne das Ausgabeobjekt wissen, wenn eine Reihe von Wörtern in TRIEs oder DAWGs umgewandelt wird.

Vielen Dank. 

100
Phil

Unwind ist im Wesentlichen richtig, dass es viele verschiedene Möglichkeiten gibt, einen Trie zu implementieren; Bei großen, skalierbaren Tries können verschachtelte Wörterbücher umständlich werden - oder zumindest wenig Platz. Aber da Sie gerade erst anfangen, denke ich, ist dies der einfachste Ansatz. Sie könnten eine einfache trie in nur wenigen Zeilen programmieren. Zunächst eine Funktion zum Erstellen des Tries:

>>> _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 mit setdefault nicht vertraut sind, sucht es einfach nach einem Schlüssel im Wörterbuch (hier letter oder _end). Wenn der Schlüssel vorhanden ist, wird der zugehörige Wert zurückgegeben. Wenn nicht, weist es diesem Schlüssel einen Standardwert zu und gibt den Wert zurück ({} oder _end). (Es ist wie eine Version von get, die auch das Wörterbuch aktualisiert.) 

Als nächstes eine Funktion, um zu testen, ob sich das Wort im Trie befindet. Das könnte knapper sein, aber ich lasse es wortreich, damit 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 überlasse Ihnen das Einfügen und Entfernen als Übung.

Natürlich wäre der Vorschlag von Unwind nicht viel schwieriger. Es kann ein geringfügiger Geschwindigkeitsnachteil darin bestehen, dass das Finden des richtigen Unterknotens eine lineare Suche erfordert. Die Suche wäre jedoch auf die Anzahl möglicher Zeichen begrenzt - 27, wenn wir _end einschließen. Es ist auch nichts zu gewinnen, wenn Sie eine umfangreiche Liste von Knoten erstellen und über den Index darauf zugreifen, wie er es vorschlägt. Sie können die Listen auch gut verschachteln.

Abschließend möchte ich noch hinzufügen, dass das Erstellen einer DAWG etwas komplexer sein würde, da Sie Situationen erkennen müssen, in denen Ihr aktuelles Word ein Suffix mit einem anderen Word in der Struktur teilt. In der Tat kann dies ziemlich komplex werden, je nachdem, wie Sie die DAWG strukturieren möchten! Sie müssen möglicherweise etwas über Levenshteindistance lernen, um es richtig zu machen. 

135
senderle

Guck dir das an:

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

Statisch speichereffiziente Trie-Strukturen für Python (2.x und 3.x).

String-Daten in einem MARISA-Trie benötigen möglicherweise bis zu 50x-100x weniger Speicher als in einem Standard-Python-Diktat; die rohe Suchgeschwindigkeit ist vergleichbar; trie bietet auch schnelle erweiterte Methoden wie die Präfixsuche.

Basierend auf der C++ - Bibliothek von marisa-trie.

Hier ist ein Blog-Post von einem Unternehmen, das marisa trie erfolgreich verwendet:
https://www.repustate.com/blog/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 in Python-Jargon dargestellt werden. In unserem speziellen Fall sind unsere Wörterbücher massiv, jeweils einige hundert MB, und es muss ständig darauf zugegriffen werden. Tatsächlich kann für eine gegebene HTTP-Anfrage auf 4 oder 5 Modelle zugegriffen werden, von denen jedes 20 bis 30 Suchvorgänge durchführt. Das Problem, mit dem wir konfrontiert sind, ist, wie wir die Dinge für den Client so schnell wie möglich halten und den Server so leicht wie möglich halten. 

...

Ich habe dieses Paket gefunden, marisa try, das ein Python-Wrapper für eine C++ - Implementierung einer marisa trie ist. „Marisa“ ist eine Abkürzung für Matching-Algorithmus mit rekursiv implementiertem StorAge. Das Beste an marisa Versuche ist, dass der Speichermechanismus wirklich so viel Speicher benötigt, wie Sie benötigen. Der Autor des Python-Plugins forderte eine 50-100fache Verkleinerung - unsere Erfahrung ist ähnlich.

Das tolle an dem marisa trie-Paket ist, dass die zugrunde liegende trie-Struktur auf die Festplatte geschrieben und dann über ein vom Speicher zugeordnetes Objekt eingelesen werden kann. Mit einer Speicherabbildung von marisa trie sind alle unsere Anforderungen jetzt erfüllt. Die Speicherauslastung unseres Servers ging dramatisch um etwa 40% zurück, und unsere Leistung war gegenüber der Implementierung des Python-Wörterbuchs unverändert.

Es gibt auch eine Reihe von reinen Python-Implementierungen. Wenn Sie sich jedoch nicht auf einer eingeschränkten Plattform befinden, möchten Sie die oben von C++ unterstützte Implementierung verwenden, um optimale Leistung zu erzielen:

23
Anentropic

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

  • marisa-trie - eine auf C++ basierende Implementierung.
  • python-trie - eine einfache reine Python-Implementierung.
  • PyTrie - eine fortgeschrittenere reine Python-Implementierung.
  • pygtrie - eine reine Python-Implementierung von Google.
14
Tzach

Es gibt kein "sollte"; Es liegt an dir. Verschiedene Implementierungen weisen unterschiedliche Leistungsmerkmale auf, benötigen für die Implementierung, das Verstehen und die richtige Einstellung verschiedene Zeit. Dies ist meiner Meinung nach typisch für die Softwareentwicklung insgesamt.

Ich würde wahrscheinlich zuerst versuchen, eine globale Liste aller bisher erstellten Trie-Knoten zu erstellen und die untergeordneten Zeiger in jedem Knoten als Liste von Indizes in der globalen Liste darzustellen. Ein Wörterbuch zu haben, das nur die Verknüpfung des Kindes darstellt, fühlt sich für mich zu schwer an.

13
unwind

Geändert von senderles Methode (oben). Ich fand, dass Pythons defaultdict ideal zum Erstellen eines Trie- oder Präfix-Baums 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')
11
dapangmao

Wenn Sie möchten, dass ein TRIE als Python-Klasse implementiert wird, habe ich Folgendes geschrieben, nachdem ich darüber gelesen hatte:

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])
4
Noctis Skytower

Diese Version verwendet 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': {}
    }
  }
}
3
naren
from collections import defaultdict

Trie definieren:

_trie = lambda: defaultdict(_trie)

Trie erstellen:

trie = _trie()
for s in ["cat", "bat", "rat", "cam"]:
    curr = trie
    for c in s:
        curr = curr[c]
    curr.setdefault("_end")

Sieh nach oben:

def Word_exist(trie, Word):
    curr = trie
    for w in Word:
        if w not in curr:
            return False
        curr = curr[w]
    return '_end' in curr

Prüfung:

print(Word_exist(trie, 'cam'))
1
DingLi
class Trie:
    head = {}

    def add(self,Word):

        cur = self.head
        for ch in Word:
            if ch not in cur:
                cur[ch] = {}
            cur = cur[ch]
        cur['*'] = True

    def search(self,Word):
        cur = self.head
        for ch in Word:
            if ch not in cur:
                return False
            cur = cur[ch]

        if '*' in cur:
            return True
        else:
            return False
    def printf(self):
        print (self.head)

dictionary = Trie()
dictionary.add("hi")
#dictionary.add("hello")
#dictionary.add("eye")
#dictionary.add("hey")


print(dictionary.search("hi"))
print(dictionary.search("hello"))
print(dictionary.search("hel"))
print(dictionary.search("he"))
dictionary.printf()

Aus

True
False
False
False
{'h': {'i': {'*': True}}}
0
Mous