python 实现 trie(字典) 树 |
您所在的位置：网站首页 › python字典怎么生成 › python 实现 trie(字典) 树 |
python 实现 trie(字典) 树
|
tire 树 也叫字典树，也是一种 N 叉树，是一种特殊的前缀树结构。 1、前缀树是N叉树的一种特殊形式。通常来说，一个前缀树是用来存储字符串的。前缀树的每一个节点代表一个字符串（前缀）。每一个节点会有多个子节点，通往不同子节点的路径上有着不同的字符。子节点代表的字符串是由节点本身的原始字符串，以及通往该子节点路径上所有的字符组成的。 下面是前缀树的一个例子：
前缀树的一个重要的特性是，节点所有的后代都与该节点相关的字符串有着共同的前缀。这就是前缀树名称的由来。 2、实现tire 树的插入和搜索、以及根据前缀判断是否在trie树操作方式： 下面用几种方式来实现 class Trie: def __init__(self): """ Initialize your data structure here. """ self.root = {} self.end = -1 def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ curNode = self.root for c in word: if not c in curNode: curNode[c] = {} curNode = curNode[c] curNode[self.end] = True def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ curNode = self.root for c in word: if not c in curNode: return False curNode = curNode[c] # Doesn't end here if not self.end in curNode: return False return True def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ curNode = self.root for c in prefix: if not c in curNode: return False curNode = curNode[c] return True # Your Trie object will be instantiated and called as such: # obj = Trie() # obj.insert(word) # param_2 = obj.search(word) # param_3 = obj.startsWith(prefix)第二种查看别人提交的代码，觉得比较好理解。 class Trie: # word_end = -1 def __init__(self): """ Initialize your data structure here. """ self.root = {} self.word_end = -1 def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ curNode = self.root for c in word: if not c in curNode: curNode[c] = {} curNode = curNode[c] curNode[self.word_end] = True def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ curNode = self.root for c in word: if not c in curNode: return False curNode = curNode[c] # Doesn't end here if self.word_end not in curNode: return False return True def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ curNode = self.root for c in prefix: if not c in curNode: return False curNode = curNode[c] return True # Your Trie object will be instantiated and called as such: # obj = Trie() # obj.insert(word) # param_2 = obj.search(word) # param_3 = obj.startsWith(prefix)第三种方式也是在博客看别人的代码，觉得写的也很好。 class Trie: def __init__(self): """ Initialize your data structure here. """ self.root = TrieNode() def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ node = self.root for chars in word: child = node.data.get(chars) if not child : node.data[chars] = TrieNode() node = node.data[chars] node.is_word = True def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ node = self.root for chars in word: node = node.data.get(chars) if not node: return False return node.is_word # 判断单词是否是完整的存在在trie树中 def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ node = self.root for chars in prefix: node = node.data.get(chars) if not node: return False return True def get_start(self, prefix): """ Returns words started with prefix :param prefix: :return: words (list) """ def get_key(pre, pre_node): word_list = [] if pre_node.is_word: word_list.append(pre) for x in pre_node.data.keys(): word_list.extend(get_key(pre + str(x), pre_node.data.get(x))) return word_list words = [] if not self.startsWith(prefix): return words if self.search(prefix): words.append(prefix) return words node = self.root for chars in prefix: node = node.data.get(chars) return get_key(prefix, node) trie = Trie() trie.insert("something") trie.insert("somebody") trie.insert("somebody1") trie.insert("somebody3") print(trie.search("key")) print(trie.search("somebody3")) print(trie.get_start('some'))上述写的几种方法都有参考别人的写法，其他博主请见谅。 |
【本文地址】
今日新闻 |
推荐新闻 |