前缀树

前缀树的概念

参考地址

前缀树也称之为单词查找树，Trie树，是一种N叉树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

性质

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
3. 每个节点的所有子节点包含的字符都不相同。

优缺点

可以最大限度地减少无谓的字符串比较，故可以用于词频统计和大量字符串排序。

　　跟哈希表比较：

　　　　1，最坏情况时间复杂度比hash表好

　　　　2，没有冲突，除非一个key对应多个值（除key外的其他信息）

　　　　3，自带排序功能（类似Radix Sort），中序遍历trie可以得到排序。

1，虽然不同单词共享前缀，但其实trie是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针（不包含卫星数据）。

每个结点的子树的根节点的组织方式有几种。1>如果默认包含所有字符集，则查找速度快但浪费空间（特别是靠近树底部叶子）。2>如果用链接法(如左儿子右兄弟)，则节省空间但查找需顺序（部分）遍历链表。3>alphabet reduction: 减少字符宽度以减少字母集个数。,4>对字符集使用bitmap，再配合链接法。

2，如果数据存储在外部存储器等较慢位置，Trie会较hash速度慢（hash访问O(1)次外存，Trie访问O(树高)）。

3，长的浮点数等会让链变得很长。可用bitwise trie改进。

理解

前缀树本身是一种数据结构，是一种树形结构。常见的实现方式包括：1.字典 2.数组。通常其节点由两部分组成：

1. 字符数据
2. 单词尾椎标识

常见操作

搜索操作

1. 从根结点开始一次搜索；
2. 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；
3. 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
4. 迭代过程……
5. 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。

插入操作

1. 从头到尾遍历字符串的每一个字符
2. 从根节点开始插入，若该字符存在，那就不用插入新节点，要是不存在，则插入新节点
3. 然后顺着插入的节点一直按照上述方法插入剩余的节点
4. 为了统计每一个字符串出现的次数，应该在最后一个节点插入后occurances++，表示这个字符串出现的次数增加一次

实现方式

字典实现

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {"End":False}

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        curNode = self.root
        for  c in word:
            if c not in curNode.keys()  :
                curNode[c] = {"End":False}
            curNode = curNode[c]
        curNode["End"] = True     


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        curNode = self.root
        for  c in word:
            if c not in curNode.keys()  :
                return False
            curNode = curNode[c]
        if curNode["End"] :
            return True
        else:
            return False


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        curNode = self.root
        for c in prefix:
            if c not in curNode.keys():
                return False
            else:
                curNode = curNode[c]
        return True

数组实现

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = [0 for i in range(27) ]


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        curNode = self.root
        for  c in word:
            if curNode[ord(c)-ord("a")] ==0  :
                curNode[ord(c)-ord("a")] = [0 for i in range(27) ]
            curNode = curNode[ord(c)-ord("a")]
        curNode[26] = True     


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        curNode = self.root
        for c in word:
            if curNode[ord(c)-ord("a")] == 0:
                return False
            else:
                curNode = curNode[ord(c)-ord("a")]
        if curNode[26] :
            return True
        else:
            return False


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        curNode = self.root
        for c in prefix:
            if curNode[ord(c)-ord("a")] == 0:
                return False
            else:
                curNode = curNode[ord(c)-ord("a")]
        return True