Patricia Tree? 簡稱PAT tree。 它是 trie 結(jié)構(gòu)的一種特殊形式。是目前信息檢索領(lǐng)域應(yīng)用十分成功的索引方
法，它是1992年由Connel根據(jù)《PATRICIA——Patrical Algorithm to Retrieve Information Coded in Alphanumeric》算法發(fā)展起來的。

?

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

?

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

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

?

但是我們發(fā)現(xiàn)這樣一個特點：

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

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

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

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

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

?

PAT tree的存儲結(jié)構(gòu)

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

?

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

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

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

* 左指針：如果 待存儲的sistring在 內(nèi)部結(jié)點所存儲的bit位置上的數(shù)據(jù) 是0，則將這個sistring存儲在該結(jié)點的左子樹中。

* 右指針：若數(shù)據(jù)是1，則存儲在右子樹中。

?

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

?

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

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

?

PAT tree的檢索過程

?

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

?

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

?

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

?

????? 這樣，通過PAT tree可以檢索原文中任意長度的字串及其出現(xiàn)頻次，所以，PAT tree也是可變長統(tǒng)計語言模型優(yōu)良的檢索結(jié)構(gòu)。

?

?

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

(1) ?? 根據(jù)“ CUHK ”的 PAT tree 結(jié)構(gòu) ( 如上圖 ) ，根結(jié)點 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 ” 已經(jīng)是葉子結(jié)點了，則確定一下 CU 是不是 CUHK 的前綴即可。

?

PAT tree 的效率

?

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

?

?

?

PAT tree的實際應(yīng)用

?

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

?

?

?

【串和序列處理 1】PAT Tree 子串匹配結(jié)構(gòu)