# 高级数据结构之Patricia Tree

Posted by Surflyan on 2017-06-02

# 1. Patricia Tree的提出

PATRICIA （Practical Algorithm to Retrieve Information Coded In Alphanumeric）由D.Morrisonrz 于1968年首次提出，Gonnet 在90年代将PATRICIA 应用到全文检索领域，发展成为PAT tree 并获得巨大成功。它也是TRIE树的一种，

# 3. Patricia tree

## 3.1 Patricia Tree结点结构，

Patricia tree 主要用于检索，那么目的就是能更快的定位到要找的信息。Patricia tree 是将字符串转换为二进制，再通过bit 位来比较的，因此只需要记录两个字符最早开始的不同的位即可，若数据在这一位为‘0’，则将该数据放入左子树，在这一位为‘1’，则将该数据放入右子树。因此这些比较位就构成了路径记录表。patricia tree 为完全二叉树。

1. 左指针： 指向该结点的左子树；
2. 右指针： 指向该结点的右子树；
3. 比较位： 记录从根结点到达该结点所有串最后一个不相同bit位的位置，用来记录关键词的路径，当比较位为0时，位串转向左子树，当比较位为1时，转向右子树。
外部节点 ：作为叶子结点，存储关键词的具体信息。

## 3.2 Trie 和Patricia tree

1. Trie : 来源与单词 retrieval, 每个从根节点出发的路路径都代表一个字符串
2. Patricia tree : 不存在只有一个孩子的结点，每个结点都起到分类的作用，如果字符在这一位相同，不能起到区分的作用，那就没有存在的必要，需要合并。

# 4. Patricia Trie

Starting with the standard trie data structure, we avoid one-way branching via a simple device: we put into each node the index of the bit to be tested to decide which path to take out of that node.
Thus, we jump directly to the bit where a significant decision is to be made, bypassing the bit comparisons at nodes where all the keys in the subtree have the same bit value.
Moreover, we avoid external nodes via another simple device: we store data in internal nodes and replace links to external nodes with links that point back upwards to the correct internal node in the trie.
These two changes allow us to represent tries with binary trees comprising nodes with a key and two links (and an additional field for the index), which we call patricia tries. With patricia tries, we store keys in nodes as with tries, and we traverse the tree according to the bits of the search key, but we do not use the keys in the nodes on the way down the tree to control the search; we merely store them there for possible later reference, when the bottom of the tree is reached.

# 5. PAT Tree

A PAT tree is a patrica tree over all sistring of a text .

PAT tree 是用于全文搜索领域的，它将整个文本的 sistring 都插入到树中：

• 注 : 这里外部节点存储的是sistring 在原文本的起始下标；

## 5.1 PAT tree 应用

• 前缀搜索（prefix searching）
• 邻近搜索（proximity searching）
• 范围搜索（range searching）
• （longest repetiton searching）
• （most frequent searching）
• （regular expression searching）
• （the longest palindrome searching）
这里有篇关于运用PAT tree解决子串匹配的详细讲解 ;