前缀树说明
前缀树Trie是一种用于字符串搜索的树形数据结构。
我们举个例子来说明前缀树是如何表示的。
有三个单词"abc"、"abd"、"bc"、"a"，要构造成一颗前缀树。
首先定义树的节点Trie：
class Trie {
boolean end;
Trie[] next;
}
由单词"abc"、"abd"、"bc"、"a"构造的前缀树如下：
image.png
可以看出来，树的第i“层”(在这个图里需要从左向右数)代表了所有单词第i个字符。next数组在这里是固定长度为4，因为我们的几个单词只包含了4个字符。
从任何一个节点出发，向其父节点回溯，则得到一个已存在的单词前缀。
end表示单词结尾。如果某个Trie节点的end为true，则表示存在以该节点为结尾的单词。
前缀树的应用
前缀树可用于统计和排序大量的字符串。
下面这几道算法题涉及到了前缀树的应用，读者可以体会一下。
Options前缀树的数据结构
okio中的Options也构造了一颗前缀树，但是这里不是用树形结构表示的，而是使用数组表示的。现在我们探索一下他是如何构造数组型结构的前缀树的。
相关源码在Options类的buildTrieRecursive方法中，从方法名可以看出来，他是通过递归的方式构造一个前缀树。
数据串和排序
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
);
经过排序之后，这几个字符串如下：
00 00 FF FF
EF BB BF
FE FF
FF FE
FF FF 00 00
因为Options在构造前缀树的时候是以字节为单位的，所以这里也以字节为单位进行分组，方便后续分析。排序后每一行对应源列表中的[Index]分别为：3、0、1、2、4，记住这组数据，后面要用。
后面我们用 串 或 数据串 表示一个源数据，用Index表示排序后的数据在源列表中的位置。
第一轮
计算过程会依次遍历所有串的每一列。
首先遍历第一列字节，把相同的分为一组。这里可分为4组，分别是00、EF、FE、FF，最后两行的第一个字节是一样的，其他的都不一样。
这样，第一段数据就出来了，他包含四个部分:
image.png
第一个位置的4就是我们刚刚计算出来的分组数量。
第二个位置表示到当前列位置是否有已结束的串。-1表示没有，如果为非负数则表示Index。
第三部分就是分组内容。
第四部分记录了尾缀在结果数组中的偏移，每组需要一个格子，共4个格子。到目前为止只知道以00(第一组数据)为前缀的数据将写在第10个格子内(从0计算)，也就是当前数据的长度。这里用负数表示坐标，非负数有其他用途，后面会讲到。
第二轮(递归1)
接下来进入第一次递归，此次会对 00 00 FF FF 的后面三个字节进行处理。在这个场景下因为只有一个数据，所以和上面的段落格式有一些区别，具体如下：
image.png
因为是递归调用，所以每一组数据都是同构的。上一段中我们用第一个数据(第一段第一格的4)表示了分组数量，为了进行区分，这里用了负数表示第二种值：当前仅剩余一个串的时候，表示串中剩余的字节数量。因为我们已经记录的第一个字节，还剩余3个字节，所以这里是-3。
第二个格子含义和上一节一样，因为当前没有串结束，所以为-1。
第三部分记录剩余字节内容。
第四部分表示Index。上一节中第四部分表示尾缀在结果数组中的偏移，为了区分用的是负数。因为非负数要用来表示Index。
第三轮+第四轮
第三轮和第四轮分别处理 EF BB BF 和 FE FF,过程和第二轮一致，结果如下，不再做说明了：
image.png
image.png
第五轮
第五轮处理 FF FE 和 FF FF 00 00。因为在第一轮中这两个串有一个共同的前缀FF。接下来的处理和第一轮类似，但有一点区别：
image.png
前面的部分都一致，我们看第5个格子。这里显示2，表示以FE(第3个格子)为前缀的串已经结束，其Index是2。
看到这里我们可以得出结论，每一段数据的第四部分，为负数时代表偏移，为非负数的时候代表Index。
最后一段处理FF FF 00 00 的后两个字节，和第二段一致，结果如下
image.png
补充偏移
第一轮的图中还有几个格子没有填，其实没完成一轮，就可以填一个数据了，把所有数据拼起来就可以得到每个子段落的偏移了，结果如下：
image.png
同理可得出第5轮的数据，需要注意的时偏移指的是在整个结果中的偏移而不是当前子结果中的偏移，所以第5轮中的偏移是-35。
完整的数据如下，我用缩进表示其父子关系：
image.png
好了，完整的流程结束了，奇怪的知识又增加了。
网友评论