So erstellen Sie eine TRIE in Python

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:

• https://github.com/bdimmick/python-trie
• https://pypi.python.org/pypi/PyTrie

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.

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.

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')

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])

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': {}
    }
  }
}

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'))

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}}}