Patricia Tree? 簡稱PAT tree。 它是 trie 結構的一種特殊形式。是目前信息檢索領域應用十分成功的索引方
法，它是1992年由Connel根據《PATRICIA——Patrical Algorithm to Retrieve Information Coded in Alphanumeric》算法發展起來的。

?

PAT tree 在 字符串子串匹配 上有這非常優異的表現，這使得它經常成為一種高效的全文檢索算法，在自然語言處理領域也有廣泛的應用。其算法中最突出的特點就是 采用半無限長字串(semi-infinite string 簡稱 sistring) 作為字符串的查找結構。

?

采用半無限長字串(sistring): 一種特殊的子串信息存儲方式。

比如一個字符串CUHK。它的子串有C、CU、CUH、CUHK、U、UH、UHK、H、HK、K十種。如果有n個字符的串，就會有n(n+1)/2種子串，其中最長的子串長度為n。因此我們不得不開辟 n(n+1)/2個長度為n的數組來存儲它們，那么存儲的空間復雜度將達到驚人的O(n^3)級別。

?

但是我們發現這樣一個特點：

??????????? CUHK ——? 完全可以表示 C、CU、CUH、CUHK

??????????? UHK?? ——? 完全可以表示 U、UH、UHK

??????????? HK???? ——? 完全可以表示 H、HK、

??????????? K?????? ——? 完全可以表示 K

這樣我們就得到了4個sistring: CUHK、UHK、HK和K。

?

PAT tree的存儲結構

如果直接用單個字符作為存儲結點，勢必構造出一棵多叉樹(如果是中文字符的話，那就完蛋了)。檢索起來將會相當不便。事實上，PAT tree是一棵壓縮存儲的二叉樹結構。現在我們用“CUHK”來構造出這樣一棵PAT tree 。

?

開始先介紹一下PAT tree的結點結構(看了后面的過程就再來理解這些概念)

* 內部結點：用橢圓形表示，用來存儲不同的bit位在整個完整bit sequence中的位置。

* 外部節點(葉子結點)： 用方形表示，用來記錄sistring的首字符在完整sistring中的開始位置(字符索引)和sistring出現的頻次。

* 左指針：如果 待存儲的sistring在 內部結點所存儲的bit位置上的數據 是0，則將這個sistring存儲在該結點的左子樹中。

* 右指針：若數據是1，則存儲在右子樹中。

?

(1) 將所有sistring的字符轉化成1 bytes的ASCII碼值，用二進制位來表示。形成一個bit sequence pattern(沒有的空字符我們用0來填充)。

? ? ? ? ???????????????? sistring?????????????????????????? bit sequence

?完整sistring? -> ? CUHK ? ? ?? 010 00011 ? 01010101 ? 01001000 ? 01001011?? <- 完整bit sequence

? ? ? ? ????????????????? UHK 0 ? ? ?? 010 10101 ? 01001000 ? 01001011 ? 00000000 ?????????????????????????

????????????????????????? HK 00 ? ? ? ? 01001000 ? 01001011 ? 00000000?? 00000000

????????????????????????? K 000 ? ? ? ? 01001011 ? 00000000?? 00000000?? 00000000

?

(2) 從第一個bit開始我們發現所有sistring的前3個bit位都相同010，那么相同的這些0/1串對于匹配來說就毫無意義了，因此我們接下來發現第4個bit開始有所不同了。UHK 的第4個bit是1，而CUHK、HK、K的第4個bit是0。則先構造一個內部結點iNode.bitSize=4（第4個bit），然后將UHK的字符索引 cIndex=2(UHK的開始字符U在完整的CUHK的第2位置上)構造成葉子結點插入到iNode的左孩子上，而CUHK、HK、K放在iNode右子樹中。(如下圖2)

?

(3) 遞歸執行第2步，將CUHK、HK、K進一步插入到PAT tree中。流程如下圖所示。所有sistring都插入以后結束。

注意：既然 PAT tree 是二叉查找樹，那么一定要滿足二叉查找樹的特點。所以，內部結點中的 bit 位就需要滿足，左孩子的 bit 位 < 結點 bit 位 < 右孩子的 bit 位。

?

PAT tree的檢索過程

?

利用PAT tree可以實現對語料的快速檢索，檢索過程就是根據查詢字串在PAT tree中從根結點尋找路徑的過程。當比較完查詢字串所有位置后，搜索路徑達到PAT tree的某一結點。

?

????? 若該結點為葉子結點，則判斷查詢字串是否為葉子結點所指的半無限長字串的前綴，如果判斷為真，則查詢字串在語料中出現的頻次即為葉子結點中記錄的頻次；否則，該查詢字串在語料中不存在。

?

????? 若該結點為內部結點，則判斷查詢字串是否為該結點所轄子樹中任一葉子結點所指的半無限長字串的前綴。如果判斷為真，該子樹中所有葉子結點記錄的頻次之和即為查詢字串的出現頻次。否則，查詢字串在語料中不存在。

?

????? 這樣，通過PAT tree可以檢索原文中任意長度的字串及其出現頻次，所以，PAT tree也是可變長統計語言模型優良的檢索結構。

?

?

例如：要查找 string= “ CU ” (bit sequence=010 00 0 1 1 01010101 ) 是不是在 CUHK 中。

(1) ?? 根據“ CUHK ”的 PAT tree 結構 ( 如上圖 ) ，根結點 r 的 bit position=4 ，那么查找 bit sequence 的第 4 個 bit=0 。然后查找 R 的左孩子 rc 。

(2) ??? rc 的 bit position=5 ，在 bit sequence 的第 5 個 bit=0 。則查找 rc 的左孩子 rcc 。

(3) ?? rcc= ” CUHK ” 已經是葉子結點了，則確定一下 CU 是不是 CUHK 的前綴即可。

?

PAT tree 的效率

?

????? 特點： PAT tree查找的時間復雜度和樹的深度有關，由于樹的構造取決于不同bit位上0,1的分布。因此PAT tree有點像 二叉查找樹 ，最壞情況下是單支樹(如上圖例子)，此時的時間復雜度是O(n-1)，n為字符串的長度。最好情況下是 平衡二叉樹 結構，時間復雜度是O(log2(N))。另外，作為壓縮的二叉查找樹，其存儲的空間代價大大減少了。

?

?

?

PAT tree的實際應用

?

?????? PAT tree在子串匹配上有很好的效率，這一點和Suffix Tree(后綴樹)，KMP算法的優點相同。因此PAT tree在信息檢索和自然語言處理領域是非常常用的工具。比如：關鍵字提取，新詞發現等NLP領域經常使用這種結構。

?

?

?

【串和序列處理 1】PAT Tree 子串匹配結構