So erstellen Sie einen Versuch in Python

123

Ich interessiere mich für Versuche und DAWGs (Direct Acyclic Word Graph) und habe viel darüber gelesen, aber ich verstehe nicht, wie die Ausgabe-Trie oder DAWG-Datei aussehen soll.

  • Sollte ein Versuch ein Objekt verschachtelter Wörterbücher sein? Wo ist jeder Buchstabe in Buchstaben unterteilt und so weiter?
  • Wäre eine Suche in einem solchen Wörterbuch schnell, wenn 100.000 oder 500.000 Einträge vorhanden wären?
  • Wie implementiere ich Wortblöcke, die aus mehr als einem durch -oder Leerzeichen getrennten Wort bestehen ?
  • Wie verknüpfe ich das Präfix oder Suffix eines Wortes mit einem anderen Teil der Struktur? (für DAWG)

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

Ich würde mich auch freuen, was die Ausgabe einer DAWG zusammen mit Trie sein sollte .

Ich möchte keine grafischen Darstellungen mit miteinander verknüpften Blasen sehen, ich möchte das Ausgabeobjekt kennen, sobald eine Reihe von Wörtern in Versuche oder DAWGs umgewandelt wurde.

Phil
quelle
5
Lesen Sie kmike.ru/python-data-structures für eine Übersicht über exotische Datenstrukturen in Python
Colonel Panic

Antworten:

161

Abwickeln ist im Wesentlichen richtig, dass es viele verschiedene Möglichkeiten gibt, einen Versuch zu implementieren; und für einen großen, skalierbaren Versuch können verschachtelte Wörterbücher umständlich werden - oder zumindest platzsparend. Aber da Sie gerade erst anfangen, denke ich, dass dies der einfachste Ansatz ist. Sie könnten eine einfache triein nur wenigen Zeilen codieren . Zunächst eine Funktion zum Konstruieren des Versuchs:

>>> _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 vertraut sind setdefault, wird einfach ein Schlüssel im Wörterbuch nachgeschlagen (hier letteroder _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 ( {}oder _end) zurück. (Es ist wie eine Version davon get, die auch das Wörterbuch aktualisiert.)

Als nächstes eine Funktion zum Testen, ob das Wort im Versuch ist:

>>> def in_trie(trie, word):
...     current_dict = trie
...     for letter in word:
...         if letter not in current_dict:
...             return False
...         current_dict = current_dict[letter]
...     return _end in current_dict
... 
>>> 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 könnte einen leichten Geschwindigkeitsnachteil geben, wenn das Finden des richtigen Unterknotens eine lineare Suche erfordern würde. Die Suche wäre jedoch auf die Anzahl der möglichen Zeichen beschränkt - 27, wenn wir einschließen _end. Es gibt auch nichts zu gewinnen, wenn Sie eine umfangreiche Liste von Knoten erstellen und über einen Index darauf zugreifen, wie er vorschlägt. Sie können die Listen auch einfach verschachteln.

Abschließend möchte ich hinzufügen, dass das Erstellen eines gerichteten azyklischen Wortgraphen (DAWG) etwas komplexer wäre, da Sie Situationen erkennen müssen, in denen Ihr aktuelles Wort ein Suffix mit einem anderen Wort in der Struktur teilt. Tatsächlich kann dies ziemlich komplex werden, je nachdem, wie Sie die DAWG strukturieren möchten! Möglicherweise müssen Sie einige Dinge über die Levenshtein- Entfernung lernen , um es richtig zu machen.

senderle
quelle
1
Dort vorgenommene Änderungen. Ich würde dabei bleiben dict.setdefault()(es ist nicht ausgelastet und bei weitem nicht bekannt genug), zum Teil, weil es dazu beiträgt, Fehler zu vermeiden, die mit a zu einfach zu erstellen sind defaultdict(wo Sie KeyErrorbei der Indizierung keine für nicht vorhandene Schlüssel erhalten würden). Das einzige, was es jetzt für den Produktionscode verwendbar machen würde, ist die Verwendung von _end = object():-)
Martijn Pieters
@MartijnPieters hmmm, ich habe mich ausdrücklich dafür entschieden, kein Objekt zu verwenden, aber ich kann mich nicht erinnern warum. Vielleicht, weil es schwer zu interpretieren wäre, wenn man es in der Demo sieht? Ich glaube , ich könnte ein Ende Objekt mit einem benutzerdefinierten repr machen
senderle
27

Schau dir das an:

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

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

String-Daten in einem MARISA-Test können bis zu 50x-100x weniger Speicher beanspruchen als in einem Standard-Python-Diktat. Die rohe Suchgeschwindigkeit ist vergleichbar. trie bietet auch schnell erweiterte Methoden wie die Präfixsuche.

Basierend auf der marisa-trie C ++ Bibliothek.

Hier ist ein Blog-Beitrag eines Unternehmens, das Marisa Trie erfolgreich einsetzt:
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üssel-Wert-Paare oder Wörterbücher in Python-Jargon dargestellt werden. In unserem speziellen Fall sind unsere Wörterbücher riesig, jeweils einige hundert MB, und es muss ständig auf sie zugegriffen werden. Tatsächlich kann für eine bestimmte HTTP-Anforderung auf 4 oder 5 Modelle zugegriffen werden, die jeweils 20 bis 30 Suchvorgänge ausführen. Das Problem ist also, wie wir die Dinge für den Client schnell und für den Server so leicht wie möglich halten können.

...

Ich habe dieses Paket gefunden, Marisa versucht, das ist ein Python-Wrapper um eine C ++ - Implementierung eines Marisa-Verses. "Marisa" ist eine Abkürzung für Matching Algorithm with Recursively Implemented StorAge. Was an Marisa-Versuchen großartig ist, ist, dass der Speichermechanismus wirklich verringert, wie viel Speicher Sie benötigen. Der Autor des Python-Plugins behauptete, die Größe sei um das 50-100-fache reduziert worden - unsere Erfahrung ist ähnlich.

Das Besondere am marisa trie-Paket ist, dass die zugrunde liegende trie-Struktur auf die Festplatte geschrieben und dann über ein speicherabgebildetes Objekt eingelesen werden kann. Mit einer Marisa-Trie mit Speicherzuordnung werden jetzt alle unsere Anforderungen erfüllt. Die Speichernutzung unseres Servers ging dramatisch um etwa 40% zurück, und unsere Leistung blieb gegenüber der Verwendung der Python-Wörterbuchimplementierung unverändert.

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

Anentropisch
quelle
Das letzte Commit war im April 2018, das letzte große Commit war wie 2017
Boris
25

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

  • marisa-trie - eine C ++ - basierte Implementierung.
  • python-trie - eine einfache reine Python-Implementierung.
  • PyTrie - eine fortschrittlichere reine Python-Implementierung.
  • pygtrie - eine reine Python-Implementierung von Google.
  • datrie - eine Double-Array-Trie-Implementierung basierend auf libdatrie .
Tzach
quelle
16

Geändert von senderleder Methode (oben). Ich fand, dass Pythons defaultdictideal zum Erstellen eines Trie- oder Präfixbaums 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')
Dapangmao
quelle
Mein Verständnis der Raumkomplexität ist O (n * m). Einige diskutieren hier. stackoverflow.com/questions/2718816/…
Dapangmao
5
@dapangmao u verwendet defaultdict nur für das erste Zeichen. Restzeichen verwenden immer noch das normale Diktat. Wäre besser verschachteltes defaultdict zu verwenden.
Lionelmessi
3
Tatsächlich scheint der Code das Standarddiktat auch nicht für das erste Zeichen zu "verwenden", da er die Standardfabrik nicht festlegt und weiterhin set_default verwendet.
Studgeek
11

Es gibt kein "sollte"; Es liegt an dir. Verschiedene Implementierungen weisen unterschiedliche Leistungsmerkmale auf, benötigen unterschiedliche Zeit, um sie zu implementieren, zu verstehen und richtig zu machen. Dies ist meiner Meinung nach typisch für die gesamte Softwareentwicklung.

Ich würde wahrscheinlich zuerst versuchen, eine globale Liste aller bisher erstellten 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.

entspannen
quelle
2
Nochmals vielen Dank, aber ich denke immer noch, dass Ihre Antwort etwas tiefer erklärt und geklärt werden muss, da meine Frage darauf abzielt, die Logik und Struktur der Funktionalität von DAWGs und TRIEs herauszufinden. Ihre weitere Eingabe wird sehr nützlich und geschätzt sein.
Phil
Sofern Sie keine Objekte mit Slots verwenden, ist Ihr Instanz-Namespace ohnehin ein Wörterbuch.
Mad Physicist
4

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

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])
Noctis Skytower
quelle
2
Vielen Dank, dass Sie @NoctisSkytower. Das ist anfangs großartig, aber ich habe Python und TRIES oder DAWGs aufgrund des extrem hohen Speicherverbrauchs von Python in diesen Fällen aufgegeben.
Phil
3
Dafür ist ____slots____ da. Es reduziert die von einer Klasse verwendete Speichermenge, wenn Sie viele Instanzen davon haben.
Dstromberg
3

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

Definiere Trie:

_trie = lambda: defaultdict(_trie)

Erstellen Sie Trie:

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'))
DingLi
quelle
1
Vorsicht: Dies wird Truenur für ein ganzes Wort zurückgegeben, nicht jedoch für das Präfix, für die Änderung des Präfixes return '_end' in currinreturn True
Shrikant Shete
0
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}}}
Nicht
quelle
0

Python-Klasse für Trie


Die Datenstruktur kann verwendet werden, um Daten zu speichern, O(L)wobei L die Länge der Zeichenfolge ist, sodass zum Einfügen von N Zeichenfolgen die zeitliche Komplexität O(NL)der Zeichenfolge durchsucht werden kannO(L) nur zum Löschen .

Kann von https://github.com/Parikshit22/pytrie.git geklont werden

class Node:
    def __init__(self):
        self.children = [None]*26
        self.isend = False
        
class trie:
    def __init__(self,):
        self.__root = Node()
        
    def __len__(self,):
        return len(self.search_byprefix(''))
    
    def __str__(self):
        ll =  self.search_byprefix('')
        string = ''
        for i in ll:
            string+=i
            string+='\n'
        return string
        
    def chartoint(self,character):
        return ord(character)-ord('a')
    
    def remove(self,string):
        ptr = self.__root
        length = len(string)
        for idx in range(length):
            i = self.chartoint(string[idx])
            if ptr.children[i] is not None:
                ptr = ptr.children[i]
            else:
                raise ValueError("Keyword doesn't exist in trie")
        if ptr.isend is not True:
            raise ValueError("Keyword doesn't exist in trie")
        ptr.isend = False
        return
    
    def insert(self,string):
        ptr = self.__root
        length = len(string)
        for idx in range(length):
            i = self.chartoint(string[idx])
            if ptr.children[i] is not None:
                ptr = ptr.children[i]
            else:
                ptr.children[i] = Node()
                ptr = ptr.children[i]
        ptr.isend = True
        
    def search(self,string):
        ptr = self.__root
        length = len(string)
        for idx in range(length):
            i = self.chartoint(string[idx])
            if ptr.children[i] is not None:
                ptr = ptr.children[i]
            else:
                return False
        if ptr.isend is not True:
            return False
        return True
    
    def __getall(self,ptr,key,key_list):
        if ptr is None:
            key_list.append(key)
            return
        if ptr.isend==True:
            key_list.append(key)
        for i in range(26):
            if ptr.children[i]  is not None:
                self.__getall(ptr.children[i],key+chr(ord('a')+i),key_list)
        
    def search_byprefix(self,key):
        ptr = self.__root
        key_list = []
        length = len(key)
        for idx in range(length):
            i = self.chartoint(key[idx])
            if ptr.children[i] is not None:
                ptr = ptr.children[i]
            else:
                return None
        
        self.__getall(ptr,key,key_list)
        return key_list
        

t = trie()
t.insert("shubham")
t.insert("shubhi")
t.insert("minhaj")
t.insert("parikshit")
t.insert("pari")
t.insert("shubh")
t.insert("minakshi")
print(t.search("minhaj"))
print(t.search("shubhk"))
print(t.search_byprefix('m'))
print(len(t))
print(t.remove("minhaj"))
print(t)

Code Oputpt

Wahr
Falsch
[ 'Minakshi', 'Minhaj']
7
Minakshi
minhajsir
pari
parikshit
shubh
shubham
Shubhi

Parikshit Agarwal
quelle