Interesują mnie try i DAWG (bezpośredni acykliczny graf słów) i dużo o nich czytałem, ale nie rozumiem, jak powinien wyglądać plik wyjściowy lub plik DAWG.

• Czy trie powinno być przedmiotem zagnieżdżonych słowników? Gdzie każda litera jest podzielona na litery i tak dalej?
• Czy wyszukiwanie w takim słowniku byłoby szybkie, gdyby było 100 000 czy 500 000 wpisów?
• Jak zaimplementować bloki słów składające się z więcej niż jednego słowa oddzielonego -spacją?
• Jak połączyć prefiks lub sufiks słowa z inną częścią w strukturze? (dla DAWG)

Chcę zrozumieć najlepszą strukturę wyjściową , aby dowiedzieć się, jak ją utworzyć i używać.

Byłbym również wdzięczny za to, co powinno być wyjściem DAWG wraz z trie .

Nie chcę widzieć reprezentacji graficznych z bąbelkami połączonymi ze sobą, chcę poznać obiekt wyjściowy, gdy zestaw słów zostanie przekształcony w próby lub DAWG.

Unwind jest zasadniczo poprawne, ponieważ istnieje wiele różnych sposobów realizacji próby; a w przypadku dużej, skalowalnej próby, zagnieżdżone słowniki mogą stać się nieporęczne - lub przynajmniej nieefektywne pod względem miejsca. Ale ponieważ dopiero zaczynasz, myślę, że to najłatwiejsze podejście; możesz zakodować prosty triew zaledwie kilku wierszach. Najpierw funkcja do skonstruowania 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_'}}}}

Jeśli nie jesteś zaznajomiony z tym setdefault, po prostu wyszukuje klucz w słowniku (tutaj letterlub _end). Jeśli klucz jest obecny, zwraca skojarzoną wartość; jeśli nie, przypisuje domyślną wartość do tego klucza i zwraca wartość ( {}lub _end). (To tak, jakby wersja gettego również aktualizowała słownik).

Następnie funkcja sprawdzająca, czy słowo znajduje się w trie:

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

Wkładanie i wyjmowanie pozostawiam tobie jako ćwiczenie.

Oczywiście sugestia Unwind nie byłaby dużo trudniejsza. Może wystąpić niewielka wada szybkości polegająca na tym, że znalezienie właściwego węzła podrzędnego wymagałoby przeszukiwania liniowego. Ale wyszukiwanie byłoby ograniczone do liczby możliwych znaków - 27, jeśli uwzględnimy _end. Poza tym nie ma nic do zyskania tworząc ogromną listę węzłów i uzyskując do nich dostęp za pomocą indeksu, jak sugeruje; równie dobrze możesz po prostu zagnieździć listy.

Na koniec dodam, że utworzenie skierowanego acyklicznego grafu słów (DAWG) byłoby nieco bardziej złożone, ponieważ musisz wykryć sytuacje, w których twoje obecne słowo ma w strukturze przyrostek z innym słowem. W rzeczywistości może to być dość skomplikowane, w zależności od tego, jak chcesz zbudować DAWG! Być może będziesz musiał dowiedzieć się czegoś o dystansie Levenshteina, aby to naprawić.

Zerknij na to:

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

Statyczne wydajne pamięciowo struktury Trie dla Pythona (2.x i 3.x).

Dane ciągów w MARISA-trie mogą zajmować do 50x-100x mniej pamięci niż w standardowym dyktacie Pythona; prędkość wyszukiwania surowego jest porównywalna; trie zapewnia również szybkie zaawansowane metody, takie jak wyszukiwanie prefiksów.

Oparty na bibliotece C ++ marisa-trie.

Oto post na blogu od firmy, która z powodzeniem używa marisa trie:
https://www.repustate.com/blog/sharing-large-data-structure-across-processes-python/

W Repustate wiele naszych modeli danych, których używamy w naszej analizie tekstu, można przedstawić jako proste pary klucz-wartość lub słowniki w żargonie Pythona. W naszym konkretnym przypadku nasze słowniki są ogromne, po kilkaset MB każdy i muszą być stale dostępne. W rzeczywistości dla danego żądania HTTP można uzyskać dostęp do 4 lub 5 modeli, z których każdy wykonuje 20-30 wyszukiwań. Tak więc problem, z którym się spotykamy, polega na tym, jak sprawić, by wszystko działało szybko dla klienta, a jednocześnie jak najmniej dla serwera.

...

Znalazłem ten pakiet, próbuje marisa, który jest opakowaniem Pythona wokół implementacji trie marisa w C ++. „Marisa” to akronim od Matching Algorithm with Recursively Implemented StorAge. Wspaniałe w próbach marisy jest to, że mechanizm magazynowania naprawdę zmniejsza ilość potrzebnej pamięci. Autor wtyczki do Pythona stwierdził 50-100-krotne zmniejszenie rozmiaru - nasze doświadczenie jest podobne.

Wspaniałe w pakiecie marisa trie jest to, że podstawową strukturę trie można zapisać na dysku, a następnie wczytać za pomocą obiektu mapowanego w pamięci. Z mapą pamięci marisa trie, wszystkie nasze wymagania są teraz spełnione. Wykorzystanie pamięci naszego serwera spadło dramatycznie, o około 40%, a nasza wydajność nie zmieniła się od czasu, gdy używaliśmy implementacji słownika Pythona.

Istnieje również kilka implementacji w czystym Pythonie, ale jeśli nie jesteś na ograniczonej platformie, chcesz użyć powyższej implementacji wspieranej przez C ++, aby uzyskać najlepszą wydajność:

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

Oto lista pakietów Pythona, które implementują Trie:

• marisa-trie - implementacja oparta na C ++.
• python-trie - prosta implementacja czystego języka Python.
• PyTrie - bardziej zaawansowana implementacja w czystym Pythonie.
• pygtrie - czysta implementacja Pythona od Google.
• datrie - implementacja trie z podwójną tablicą oparta na libdatrie .

Zmodyfikowano z senderlemetody (powyżej). Odkryłem, że Python defaultdictjest idealny do tworzenia drzewa trie lub prefiksu.

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

Nie ma „powinno”; to zależy od Ciebie. Różne implementacje będą miały różną charakterystykę wydajności, a ich wdrożenie, zrozumienie i poprawne wykonanie zajmie różną ilość czasu. Moim zdaniem jest to typowe dla rozwoju oprogramowania jako całości.

Prawdopodobnie najpierw spróbuję utworzyć globalną listę wszystkich dotychczas utworzonych węzłów trie i przedstawić wskaźniki potomne w każdym węźle jako listę indeksów na liście globalnej. Posiadanie słownika tylko po to, by przedstawiać linkowanie dziecka, wydaje mi się zbyt ciężkie.

Jeśli chcesz TRIE zaimplementowaną jako klasa Pythona, oto coś, co napisałem po przeczytaniu o nich:

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

Ta wersja używa rekurencji

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)

Wynik:

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

Zdefiniuj Trie:

_trie = lambda: defaultdict(_trie)

Utwórz próbę:

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

Wyszukaj:

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

Test:

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

Na zewnątrz

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

Klasa Pythona dla Trie

Trie Data Structure może być używana do przechowywania danych, O(L)gdzie L jest długością łańcucha, więc przy wstawianiu N łańcuchów złożoność czasowa byłaby taka, O(NL)że ciąg można przeszukiwać O(L)tylko w ten sam sposób, co w przypadku usunięcia.

Można sklonować z https://github.com/Parikshit22/pytrie.git

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

Prawda
Fałsz
[„minakshi”, „minhaj”]
7
minakshi
minhajsir
pari
parikshit
shubh
shubham
shubhi