TRIE(前缀树/字典树)
TRIE常用于存储和表示字符串的集合,并实现该集合上的增删字符串运算。其核心思想是用公共前缀表示字符串,比如abcd与abc的公共前缀是abc,当字符串间恰好没有公共前缀时,比如abc,edfg,czx构成的集合,那么其会存储3个前缀abc,edfg,czx。
其常用于存储字符串构成的集合。其结构是这样的,Trie的根节点不存储字符,其他节点仅存储单个字符,且同一层节点无重复字符。节点有变量存储“颜色”,若某节点被“染色”说明从根到该节点的路径存储了一个字符串,除此之外Trie的叶节点肯定是“染色”的。下面讨论Trie的运算结构:
1)插入:首先查找根节点全部孩子节点,若找到待插入串首字符则进入该节点并重复该步骤,若没有则在该处新建节点并插入剩余字符,最终为叶节点染色。如果用哈希表/dict来记录每个节点的儿子,可以在\(O(1)\)时间完成当前层的查找,所以可以认为时间复杂度为字符数\(O(n)\)。
2)遍历:首先想到利用节点遍历来实现,如果在节点遍历的同时记录了当前的途径路径,那只要在节点被遍历时判断当前节点是否被“染色”即可解决这个问题。可以发现这个解决方法与节点的深度优先遍历是同步进行的,所以其代价为节点数\(O(n)\)。
3)删除:首先逐个查找每个字符对应节点,直到到达待删除串尾字符的对应节点,若其是叶节点则将其删除,若其不是叶节点则取消“染色”。若未找到待删除串则返回。删除的代价是字符数\(O(n)\)。
4)查找:删除中已经讨论了查找的逻辑。
5)查找前缀:跟查找差不多。
Trie本身虽然不复杂,但其在字符串处理中的应用十分广泛,举些比较基本的例子:
1)字符串排序:这里排序是指把若干字符串,以英语字典那样的方式来排序。这可以通过规定记录子节点的序列中的元素顺序来实现,如果规定序列元素按照abcd的顺序排序,那么对这个Trie树进行上述字符串遍历即可得到排序结果。
2)字符串统计:该问题指“有一篇A个单词的文章与B个单词组成的单词表,统计单词表中各个单词在该文章的出现次数”。方法是把单词表建成Trie树,然后在Trie上查找每个单词。
3)字符串去重:把这些字符串建成Trie然后再遍历该Trie即可去重。
4)字符串前缀:Trie树可用来解决关于前缀的很多问题,例如“求多个字符串的最大公共前缀”,“求单词表中与目标单词公共前缀最长的单词”。解决第一个问题仅需把这些字符串建成Trie树,然后找出一条最长路径,这个路径的每个节点只有一个子节点。解决第二个问题同样也比较容易。
5)字符串匹配:Trie树是著名多模匹配算法“AC自动机”的基础,后面写了篇文章讨论这个。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | class Node: def __init__(self): self.letterMap = {} self.isEnd = False class Trie: def __init__(self): self.root = Node() @classmethod def _traverse(cls, result, arr, node): if node.isEnd: result.append(''.join(arr)) for key in node.letterMap: arr.append(key) cls._traverse(result, arr, node.letterMap[key]) arr.pop() def traverse(self): result = [] self._traverse(result, [], self.root) return result def insert(self, word): node = self.root for letter in word: if letter not in node.letterMap: node.letterMap[letter] = Node() node = node.letterMap[letter] node.isEnd = True def search(self, word): node = self.root letter = None for letter in word: if letter in node.letterMap: node = node.letterMap[letter] else: return False if letter and node.isEnd: return True return False def remove(self, word): node = self.root parent = None letter = None for letter in word: if letter in node.letterMap: parent = node node = node.letterMap[letter] else: return False if letter and node.isEnd: if len(node.letterMap.keys()) > 0: node.isEnd = False else: parent.letterMap.pop(letter) return True return False def startsWith(self, prefix): node = self.root for letter in prefix: if letter in node.letterMap: node = node.letterMap[letter] else: return False return True |