Thực hiện một Patricia Trie để sử dụng làm từ điển

Question

Tôi đang cố gắng triển khai Patricia Trie bằng các phương pháp addWord(), isWord() và isPrefix() làm phương tiện lưu trữ từ điển lớn để truy xuất nhanh (bao gồm tìm kiếm tiền tố). Tôi đã đọc về các khái niệm nhưng họ chỉ không làm rõ việc triển khai. Tôi muốn biết (trong Java hoặc mã Python) làm thế nào để thực hiện các Trie, đặc biệt là các nút (hoặc tôi nên thực hiện nó đệ quy). Tôi thấy một người thực hiện nó với một mảng gồm 26 nút con được đặt thành null/None. Có một chiến lược tốt hơn (chẳng hạn như xử lý các chữ cái như bit) và làm thế nào bạn sẽ thực hiện nó?

Answer 1

Có người khác hỏi một câu hỏi về Patricia một lúc trước và tôi đã nghĩ đến việc thực hiện Python, nhưng lần này tôi quyết định thực sự bắn nó (Có, đây là cách overboard, nhưng nó có vẻ như là một dự án nhỏ). Những gì tôi đã thực hiện có lẽ không phải là một việc thực hiện Trium Patricia thuần khiết, nhưng tôi thích cách của tôi tốt hơn. Patricia khác cố gắng (bằng ngôn ngữ khác) chỉ sử dụng một danh sách cho trẻ em và kiểm tra mỗi đứa trẻ để xem có một trận đấu, nhưng tôi nghĩ rằng điều này là khá kém hiệu quả vì vậy tôi sử dụng từ điển. Về cơ bản, đây là cách tôi đã thiết lập:

Tôi sẽ bắt đầu tại nút gốc. Gốc chỉ là một từ điển. Từ điển có các phím là tất cả các ký tự đơn (các chữ cái đầu tiên của từ) dẫn đến các nhánh. Các giá trị tương ứng với mỗi khóa là danh sách trong đó mục đầu tiên là một chuỗi cung cấp phần còn lại của chuỗi khớp với nhánh này của trie và mục thứ hai là từ điển dẫn đến các nhánh khác từ nút này. Từ điển này cũng có các phím ký tự đơn tương ứng với chữ cái đầu tiên của phần còn lại của từ đó và quá trình tiếp tục đi xuống. Một điều khác tôi nên đề cập là nếu một nút nhất định có nhánh, nhưng cũng là một từ trong chính trie, thì được biểu thị bằng cách có một khóa '' trong từ điển dẫn đến một nút có danh sách ['',{}].

Dưới đây là một ví dụ nhỏ cho thấy cách từ được lưu trữ (nút gốc là biến _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', {}]}]} 

Chú ý rằng trong trường hợp cuối cùng, một '' chìa khóa đã được bổ sung vào từ điển để biểu thị rằng 'abc' là một từ trong phần bổ sung 'abcdef' và 'abcabc'.

Source Code

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 

Bạn có thể đã nhận thấy rằng ở cuối tôi đặt __getitem__ với phương pháp isWord. Điều này có nghĩa là

x['abc'] 

sẽ trả về xem 'abc' có trong trie hay không.

Tôi nghĩ rằng có lẽ tôi nên tạo một mô-đun trong số này và gửi nó cho PyPI, nhưng nó cần thử nghiệm nhiều hơn và ít nhất là phương thức removeWord. Nếu bạn tìm thấy bất kỳ lỗi nào cho tôi biết, nhưng có vẻ như nó hoạt động khá tốt. Ngoài ra, nếu bạn thấy bất kỳ cải tiến lớn về hiệu quả, tôi cũng muốn nghe về chúng. Tôi đã xem xét việc làm một cái gì đó về việc có từ điển trống ở dưới cùng của mỗi chi nhánh, nhưng tôi để nó ngay bây giờ. Những từ điển trống này có thể được thay thế bằng dữ liệu được liên kết với từ để mở rộng việc sử dụng thực hiện chẳng hạn.

Dù sao, nếu bạn không thích cách tôi triển khai, ít nhất có thể điều này sẽ cung cấp cho bạn một số ý tưởng về cách bạn muốn triển khai phiên bản của riêng mình.

Answer 2

Dưới đây là một việc thực hiện đệ quy sử dụng phương pháp pythonic hơn:

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