前綴樹說明
前綴樹Trie是一種用于字符串搜索的樹形數(shù)據(jù)結(jié)構(gòu)玻墅。
我們舉個例子來說明前綴樹是如何表示的呐芥。
有三個單詞"abc"逻杖、"abd"、"bc"思瘟、"a"荸百，要構(gòu)造成一顆前綴樹。
首先定義樹的節(jié)點Trie：
class Trie {
boolean end;
Trie[] next;
}
由單詞"abc"滨攻、"abd"够话、"bc"、"a"構(gòu)造的前綴樹如下：
可以看出來铡买，樹的第i“層”(在這個圖里需要從左向右數(shù))代表了所有單詞第i個字符更鲁。next數(shù)組在這里是固定長度為4，因為我們的幾個單詞只包含了4個字符奇钞。
從任何一個節(jié)點出發(fā)，向其父節(jié)點回溯漂坏，則得到一個已存在的單詞前綴景埃。
end表示單詞結(jié)尾媒至。如果某個Trie節(jié)點的end為true，則表示存在以該節(jié)點為結(jié)尾的單詞谷徙。
前綴樹的應(yīng)用
前綴樹可用于統(tǒng)計和排序大量的字符串拒啰。
下面這幾道算法題涉及到了前綴樹的應(yīng)用，讀者可以體會一下完慧。
實現(xiàn)前綴樹
單詞壓縮編碼
與數(shù)組中元素的最大異或值
Options前綴樹的數(shù)據(jù)結(jié)構(gòu)
okio中的Options也構(gòu)造了一顆前綴樹谋旦，但是這里不是用樹形結(jié)構(gòu)表示的，而是使用數(shù)組表示的∏幔現(xiàn)在我們探索一下他是如何構(gòu)造數(shù)組型結(jié)構(gòu)的前綴樹的册着。
相關(guān)源碼在Options類的buildTrieRecursive方法中，從方法名可以看出來脾歧，他是通過遞歸的方式構(gòu)造一個前綴樹甲捏。
數(shù)據(jù)串和排序
Okhttp中使用到Options的代碼只有一處，如下：
private static final Options UNICODE_BOMS = Options.of(
ByteString.decodeHex("efbbbf"), // UTF-8
ByteString.decodeHex("feff"), // UTF-16BE
ByteString.decodeHex("fffe"), // UTF-16LE
ByteString.decodeHex("0000ffff"), // UTF-32BE
ByteString.decodeHex("ffff0000") // UTF-32LE
);
經(jīng)過排序之后鞭执，這幾個字符串如下：
00 00 FF FF
EF BB BF
FE FF
FF FE
FF FF 00 00
因為Options在構(gòu)造前綴樹的時候是以字節(jié)為單位的司顿，所以這里也以字節(jié)為單位進(jìn)行分組，方便后續(xù)分析兄纺。排序后每一行對應(yīng)源列表中的[Index]分別為：3大溜、0、1估脆、2猎提、4，記住這組數(shù)據(jù)旁蔼，后面要用锨苏。
后面我們用 串 或 數(shù)據(jù)串 表示一個源數(shù)據(jù)，用Index表示排序后的數(shù)據(jù)在源列表中的位置棺聊。
第一輪
計算過程會依次遍歷所有串的每一列伞租。
首先遍歷第一列字節(jié)，把相同的分為一組限佩。這里可分為4組葵诈，分別是00、EF祟同、FE作喘、FF，最后兩行的第一個字節(jié)是一樣的晕城，其他的都不一樣泞坦。
這樣，第一段數(shù)據(jù)就出來了砖顷，他包含四個部分:
第一個位置的4就是我們剛剛計算出來的分組數(shù)量贰锁。
第二個位置表示到當(dāng)前列位置是否有已結(jié)束的串赃梧。-1表示沒有，如果為非負(fù)數(shù)則表示Index豌熄。
第三部分就是分組內(nèi)容授嘀。
第四部分記錄了尾綴在結(jié)果數(shù)組中的偏移，每組需要一個格子锣险，共4個格子蹄皱。到目前為止只知道以00(第一組數(shù)據(jù))為前綴的數(shù)據(jù)將寫在第10個格子內(nèi)(從0計算)，也就是當(dāng)前數(shù)據(jù)的長度芯肤。這里用負(fù)數(shù)表示坐標(biāo)巷折，非負(fù)數(shù)有其他用途，后面會講到纷妆。
第二輪(遞歸1)
接下來進(jìn)入第一次遞歸盔几，此次會對 00 00 FF FF 的后面三個字節(jié)進(jìn)行處理。在這個場景下因為只有一個數(shù)據(jù)掩幢，所以和上面的段落格式有一些區(qū)別逊拍，具體如下：
因為是遞歸調(diào)用，所以每一組數(shù)據(jù)都是同構(gòu)的际邻。上一段中我們用第一個數(shù)據(jù)(第一段第一格的4)表示了分組數(shù)量芯丧，為了進(jìn)行區(qū)分，這里用了負(fù)數(shù)表示第二種值：當(dāng)前僅剩余一個串的時候世曾，表示串中剩余的字節(jié)數(shù)量缨恒。因為我們已經(jīng)記錄的第一個字節(jié)，還剩余3個字節(jié)轮听，所以這里是-3骗露。
第二個格子含義和上一節(jié)一樣，因為當(dāng)前沒有串結(jié)束血巍，所以為-1萧锉。
第三部分記錄剩余字節(jié)內(nèi)容。
第四部分表示Index述寡。上一節(jié)中第四部分表示尾綴在結(jié)果數(shù)組中的偏移柿隙，為了區(qū)分用的是負(fù)數(shù)。因為非負(fù)數(shù)要用來表示Index鲫凶。
第三輪+第四輪
第三輪和第四輪分別處理 EF BB BF 和 FE FF,過程和第二輪一致禀崖，結(jié)果如下，不再做說明了：
第五輪
第五輪處理 FF FE 和 FF FF 00 00螟炫。因為在第一輪中這兩個串有一個共同的前綴FF波附。接下來的處理和第一輪類似，但有一點區(qū)別：
前面的部分都一致，我們看第5個格子叶雹。這里顯示2财饥，表示以FE(第3個格子)為前綴的串已經(jīng)結(jié)束换吧，其Index是2折晦。
看到這里我們可以得出結(jié)論，每一段數(shù)據(jù)的第四部分沾瓦，為負(fù)數(shù)時代表偏移满着，為非負(fù)數(shù)的時候代表Index。
最后一段處理FF FF 00 00 的后兩個字節(jié)贯莺，和第二段一致风喇，結(jié)果如下
補(bǔ)充偏移
第一輪的圖中還有幾個格子沒有填，其實沒完成一輪缕探，就可以填一個數(shù)據(jù)了魂莫，把所有數(shù)據(jù)拼起來就可以得到每個子段落的偏移了，結(jié)果如下：
同理可得出第5輪的數(shù)據(jù)爹耗，需要注意的時偏移指的是在整個結(jié)果中的偏移而不是當(dāng)前子結(jié)果中的偏移耙考，所以第5輪中的偏移是-35。
完整的數(shù)據(jù)如下潭兽，我用縮進(jìn)表示其父子關(guān)系：
好了倦始，完整的流程結(jié)束了，奇怪的知識又增加了山卦。
