前缀树Trie和okio.Options解析

2021-10-23 本文已影响0人愈强

前缀树说明

前缀树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。