Implementacja Patricii Trie do użycia jako słownik

Question

Próbuję zaimplementować Patricię Trie metodami addWord(), isWord() i isPrefix() jako sposobu na przechowywanie dużego słownika słów w celu szybkiego pobrania (w tym wyszukiwania prefiksów). Przeczytałem te koncepcje, ale one po prostu nie wyjaśniają implementacji. Chcę wiedzieć (w języku Java lub w języku Python) jak zaimplementować Trie, szczególnie węzły (lub czy powinienem je rekursywnie implementować). Widziałem jedną osobę, która zaimplementowała ją z tablicą 26 węzłów potomnych ustawioną na null/None. Czy istnieje lepsza strategia (na przykład traktowanie liter jako bitów) i jak ją wdrożyć?

Answer 1

Ktoś jeszcze zadał pytanie na temat Patricii, która próbowała jakiś czas temu, a ja myślałem o wprowadzeniu w życie Pythona, ale tym razem postanowiłem dać mu szansę (tak, to jest droga za burtą, ale wydawało mi się to miłe mały projekt). To, co zrobiłem, może nie jest czystą implementacją Patricii, ale lubię swoją drogę. Inne Patricia próbuje (w innych językach) użyć tylko listy dla dzieci i sprawdzić każde dziecko, aby zobaczyć, że jest dopasowanie, ale myślałem, że to raczej nieefektywne, więc używam słowników. Oto w zasadzie, jak to skonfigurowałem:

Zacznę od głównego węzła. Katalog główny to tylko słownik. Słownik ma klucze, które są wszystkie pojedyncze znaki (pierwsze litery słów) prowadzące do oddziałów. Wartości odpowiadające każdemu kluczowi są listami, gdzie pierwszy element jest ciągiem, który daje resztę łańcucha, który pasuje do tego odgałęzienia trie, a drugi element jest słownikiem prowadzącym do dalszych gałęzi z tego węzła. Słownik ten ma również pojedyncze klawisze znaków, które odpowiadają pierwszej literze reszty słowa, a proces jest kontynuowany w dół.

Inną rzeczą, o której powinienem wspomnieć, jest to, że jeśli dany węzeł ma gałęzie, ale jest również słowem w samym tytule, oznacza to, że ma klucz '' w słowniku, który prowadzi do węzła z listą ['',{}].

Oto mały przykład, który pokazuje, jak słowa są przechowywane (węzeł główny jest zmienna _d):

>>> x = patricia() 
>>> x.addWord('abcabc') 
>>> x._d 
{'a': ['bcabc', {}]} 
>>> x.addWord('abcdef') 
>>> x._d 
{'a': ['bc', {'a': ['bc', {}], 'd': ['ef', {}]}]} 
>>> x.addWord('abc') 
{'a': ['bc', {'a': ['bc', {}], '': ['', {}], 'd': ['ef', {}]}]} 

Zauważ, że w tym ostatnim przypadku, klucz „” została dodana do słownika oznaczać, że "abc" jest słowem dodanym do "abcdef" i "abcabc".

kod źródłowy

class patricia(): 
    def __init__(self): 
     self._data = {} 

    def addWord(self, word): 
     data = self._data 
     i = 0 
     while 1: 
      try: 
       node = data[word[i:i+1]] 
      except KeyError: 
       if data: 
        data[word[i:i+1]] = [word[i+1:],{}] 
       else: 
        if word[i:i+1] == '': 
         return 
        else: 
         if i != 0: 
          data[''] = ['',{}] 
         data[word[i:i+1]] = [word[i+1:],{}] 
       return 

      i += 1 
      if word.startswith(node[0],i): 
       if len(word[i:]) == len(node[0]): 
        if node[1]: 
         try: 
          node[1][''] 
         except KeyError: 
          data = node[1] 
          data[''] = ['',{}] 
        return 
       else: 
        i += len(node[0]) 
        data = node[1] 
      else: 
       ii = i 
       j = 0 
       while ii != len(word) and j != len(node[0]) and \ 
         word[ii:ii+1] == node[0][j:j+1]: 
        ii += 1 
        j += 1 
       tmpdata = {} 
       tmpdata[node[0][j:j+1]] = [node[0][j+1:],node[1]] 
       tmpdata[word[ii:ii+1]] = [word[ii+1:],{}] 
       data[word[i-1:i]] = [node[0][:j],tmpdata] 
       return 

    def isWord(self,word): 
     data = self._data 
     i = 0 
     while 1: 
      try: 
       node = data[word[i:i+1]] 
      except KeyError: 
       return False 
      i += 1 
      if word.startswith(node[0],i): 
       if len(word[i:]) == len(node[0]): 
        if node[1]: 
         try: 
          node[1][''] 
         except KeyError: 
          return False 
        return True 
       else: 
        i += len(node[0]) 
        data = node[1] 
      else: 
       return False 

    def isPrefix(self,word): 
     data = self._data 
     i = 0 
     wordlen = len(word) 
     while 1: 
      try: 
       node = data[word[i:i+1]] 
      except KeyError: 
       return False 
      i += 1 
      if word.startswith(node[0][:wordlen-i],i): 
       if wordlen - i > len(node[0]): 
        i += len(node[0]) 
        data = node[1] 
       else: 
        return True 
      else: 
       return False 

    def removeWord(self,word): 
     data = self._data 
     i = 0 
     while 1: 
      try: 
       node = data[word[i:i+1]] 
      except KeyError: 
       print "Word is not in trie." 
       return 
      i += 1 
      if word.startswith(node[0],i): 
       if len(word[i:]) == len(node[0]): 
        if node[1]: 
         try: 
          node[1][''] 
          node[1].pop('') 
         except KeyError: 
          print "Word is not in trie." 
         return 
        data.pop(word[i-1:i]) 
        return 
       else: 
        i += len(node[0]) 
        data = node[1] 
      else: 
       print "Word is not in trie." 
       return 


    __getitem__ = isWord 

Można zauważyć, że w końcu mogę ustawić __getitem__ metody isWord. Oznacza to, że zostanie zwrócony tekst "abc" w kliencie lub nie.

Myślę, że może powinienem zrobić moduł z tego i przesłać go do PyPI, ale potrzebuje więcej testów i przynajmniej metody usuwania. Jeśli znajdziesz jakieś błędy, daj mi znać, ale wygląda na to, że działa całkiem nieźle. Ponadto, jeśli zauważysz jakąkolwiek znaczącą poprawę wydajności, chciałbym również o tym usłyszeć. Zastanawiałem się nad zrobieniem czegoś z opróżnianiem słowników na dole każdej gałęzi, ale na razie to zostawiam. Te puste słowniki można zastąpić danymi związanymi ze słowem, aby na przykład rozszerzyć zastosowania implementacji.

W każdym razie, jeśli nie podoba ci się sposób, w jaki go zaimplementowałem, przynajmniej może to da ci kilka pomysłów na temat tego, jak chcesz wprowadzić własną wersję.

Answer 2

Oto rekurencyjna realizacja przy użyciu metod bardziej pythonic:

def matching_prefix_index(word1, word2): 
    max_len = min(len(word1),len(word2)) 
    for i in range(max_len): 
     if word2[i] != word1[i]: 
      return i 
    return max_len 

class PatriciaTrie(object): 
    def __init__(self): 
     self._storage = {} 
     self._complete_prefix_flag = False 

    def _find_storage_key(self, word): 
     for key in self._storage: 
      prefix_index = matching_prefix_index(key, word) 
      if prefix_index > 0: 
       return (key, prefix_index) 
     return (None, None) 

    def add(self, word): 
     if word == '': 
      self._complete_prefix_flag = True 
      return True 

     key, prefix_index = self._find_storage_key(word) 
     if key is not None: 
      if prefix_index == len(key): 
       return self._storage[key].add(word[len(key):]) 
      else: 
       new_tree = PatriciaTrie() 
       new_tree._storage[key[prefix_index:]] = self._storage.pop(key) 
       self._storage[key[0:prefix_index]] = new_tree 
       return new_tree.add(word[prefix_index:]) 
     else: 
      self._storage[word] = PatriciaTrie() 
      self._storage[word].add('') 
      return True 

    def remove(self, word): 
     if word == '': 
      self._complete_prefix_flag = False 
      return True 

     key, prefix_index = self._find_storage_key(word) 
     if key is None or prefix_index != len(key): 
      return False 

     subword = word[prefix_index:] 
     subtrie = self._storage[key] 
     if subtrie.remove(subword): 
      if (not subtrie._complete_prefix_flag) and len(subtrie._storage) == 0: 
       self._storage.pop(key) 
      return True 
     else: 
      return False 

    def __contains__(self, word): 
     if word == '': 
      return self._complete_prefix_flag 

     key, prefix_index = self._find_storage_key(word) 
     if key is None or prefix_index != len(key): 
      return False 
     else: 
      return (word[prefix_index:] in self._storage[key]) 

    def has_prefix(self, word): 
     if word == '': 
      return True 

     key, prefix_index = self._find_storage_key(word) 
     if key is None: 
      return False 
     elif len(key) > len(word): 
      return (prefix_index == len(word)) 
     elif len(key) != prefix_index: 
      return False 
     else: 
      return self._storage[key].has_prefix(word[prefix_index:])