文本处理简介：让我们在 Python 中快速制作字典（第 2 部分）

创建 double 数组

双精度数组是如何实现 Trie 树的？

首先，准备一个名为 “base” 的一维整数数组。
此数组的每个元素都表示一个节点。
基数组的索引从 1 开始。 （不使用 0 位置）
换句话说，节点 1 是 root。 这里有一个 1。
base[1] = 1。

在前面的示例中，headword 的首字母是 “で” 和 “ど”。
那么，根通过 “at” 转换到的下一个节点在哪里？

要进行准备，请为标题的每个字母分配一个标识号。
您可以按原样使用某些编码的字符代码。
由于字符数较少，因此我们在此处从 1 开始，并适当地分配字符 ID。
单词和字母的显示顺序如下。

和: 1毫米: 2做: 3这: 4血: 5你: 6（二）: 7是的: 8

“De” 现在是 1，“Do” 现在是 3。 code['in']=1， code['ど']=3.
顺便说一句，正如我稍后将解释的那样，字符 ID 的数字 0 是单词的结尾（过渡到叶节点）。
由于我们讨论了叶节点，我将按照单词的出现顺序为单词分配 ID。

书房:1哪里:2砰:3东灿:4稳步:5东贝:6

现在，以这种方式，从 root 过渡到字符 “at” 的节点的位置是
它采用 root base 的值加上字符 ID。 你什么意思：

base[1] + code['in'] = 1 + 1 = 2

它来到了。 在 “do” 的情况下执行相同的作，

base[1] + code['ど'] = 1 + 3 = 4

这将重新填充基数组编号 2 和 4。
这样，过渡目标的节点位置就是 “基础值 + 字符 ID” 的值。
这有点神奇。 文本信息已被吸收到 “过渡移动量” 中。

这里的问题是，通过将任意字符 ID 值添加到 base[1] 的值中，
可以从 root 过渡到任何节点。
我不希望下一个字符只是“で”和“ど”，所以这是一个问题。
因此，我们将准备另一个名为 “check” 的一维整数数组。
在 check，放入它的来源 （= 父节点的索引）。
如果父节点是 root，则为 1。 此外，根本身应设置为 0。 如果你把它写在公式中：

检查 [1] = 0
检查[2] = 1
检查[4] = 1

通过这种方式，Trie 树由两个数组表示，base 和 check。
这就是 “double array” 这个名字的由来。
可以将其视为“double 数组中的节点具有位置信息、基本组件和 check 组件”。
这可能会很好。
让我们看一下到目前为止的表格。

现在，节点 1、2 和 4 已填充。 3 仍为空。
数字 2 和 4 的基值仍然存在，但如何确定它们呢？

当通过字母 c 从位置 s 过渡到位置 t 时，情况如下。

t = 基数 [s] + 代码 [c]
检查[t] = s

如果你按照自己的喜好决定 base[s] 的值，那么当将来节点数稳步增加时，
发生具有预先存在节点的位置击球。
相反，这样就不会发生这种情况，也就是说，这样下一个节点就会过渡到一个非常空置的地方。
确定 base[s] 的值。

标题： “Den”， “Where”， “Don”， “Donchan”， “Dondon”， “Donbe”，
例如，从「don」的第二个字母「n」开始，就是「词尾」、「chi」、「do」、「be」
子节点有四个分支，因此我们必须确保所有分支都不会相互碰撞。
我认为您可以将基本组件称为偏移值。
通常，您应该选择最小化偏移值，即尽可能减少目标组合的左侧。
随着 double 数组的增长，空间似乎从左侧被填充了。

现在，让我们一步一步地看一下 double 数组的增长。
其实，只剩下一个更重要的概念需要解释：叶节点处理，请放轻松。
即使你第一次没有得到它，如果你一边做笔记一边读几遍，你也一定会把它记在你的脑海里。

顺便说一句，这次我们将按照单词 ID 的顺序注册，所以
这意味着它是一个深度优先的创作。
作为替代方法，您可以先为所有 headwords 注册从根到第一个字符的过渡，然后使用
也可以在所有词条中注册第一个字母→第二个字母的过渡。
在这种情况下，它将是一个广度优先的创作。

第 1 步：“In”→“Den”

它是从过渡源 s = 2 的过渡。 字符 ID 为代码 ['ん'] = 2。
如果 base[2] = 1，则过渡目标是 t = base[s] + code[c ] = 1 + 2 = 3。
您可以过渡到空位置（在最左侧）。 将父节点位置放在该处。
检查[3] = s = 2

现在，我用 “den” 来结束这个词。 由于“Den...”后面没有其他标题。
过渡没有分支（叶节点没有同级节点）。
通常，您可以通过将转换目标视为 code[leaf node] = 0 来创建叶节点。
如果没有分支，就不要费心创建叶子节点，并添加
将单词 ID 的符号倒置为负数。
它可以节省内存并略微加快搜索速度。
“den” 的单词 ID 为 1，因此 base[3] = -1
在上表中，“de” → “den” 之间的过渡简化为 “→”。

第 2 步：“执行”→“在哪里”“唐”

它是从过渡源 s = 4 的过渡。
“do”、“ko”和“n”有两个过渡目标。
code['こ'] = 4 且 code['ん'] = 2，所以如果 base[4] = 3，则
目标节点位置已明确。 让我们来看看每个。

“Do” → “Where”
转换为 t = base[4] + code['ko'] = 3 + 4 = 7，因此 check[7] = s = 4
我来到了“where”这个词的结尾，但没有分支（“where...”后面没有其他词头），所以
和以前一样，单词 ID 2 被倒置，使得 base[4] = -2

“Do” → “Don”
转换为 t = base[4] + code['n'] = 3 + 2 = 5，因此 check[5] = s = 4
我来到了 “don” 这个词的结尾，但从 “don” 开始，它分支成 “chi”、“do” 和 “be”。
由于无法将单词 ID （倒置符号） 放在 base[t] 中，因此将创建一个新的叶节点。
我现在先说到这里，下一步再考虑。

这样，在 double 数组中，即使你以深度优先的方式创建它，你也可以使用
有必要始终考虑连接的宽度（分支的数量）。 这有点有趣。

第 3 步：“Don” → “Don （end of word）”， “Donchi”， “Dondo”， “Donbe”

它是从过渡源 s = 5 的过渡。
代码[end] = 0， 代码['ち'] = 5， 代码['ど'] = 3， 代码['べ'] = 7。
base[5] = 6 是确定目标节点位置的好方法。
让我们来看看每个。

单词结尾 → “don”
这是我之前推迟的过程。
转换为 t = base[5] + code[end] = 6，因此 check[6] = s = 5
由于它是单词的结尾，因此“Don”的单词 ID 的 3 的符号是倒置的。
基数[6] = -3
如果有分支，请创建一个像这样的新叶节点，然后使用
将单词 ID（倒置符号）放在那里是
这是与没有分支的情况相比，处理方式的差异。

“Don” → “Donchi”
转换到 t = base[5] + code['chi'] = 6 + 5 = 11，所以 check[11] = s = 5

“Don” → “Dondo”
转换为 t = base[5] + code['do'] = 6 + 3 = 9，因此 check[9] = s = 5

“Don” → “Donbe”
转换为 t = base[5] + code['be'] = 6 + 7 = 13，因此 check[13] = s = 5

第 4 步：“Donchi” → “Doncha” → “Donchan”

到目前为止，我一直在一次处理一个字母，但 “Donchi” → “Donchan” 没有分支。
我将用两个字母来总结解释。

“Donchi” → “Doncha”
过渡源 s = 11。 code['ゃ'] = 6，所以如果 base[11] = 2，则转换为 t = base[11] + code['ゃ'] = 8
所以 check[8] = 11

“Doncha” → “Donchan”
过渡源 s = 8。 code['ん'] = 2，所以如果 base[8] = 8，那么转换为 t = base[8] + code['ん'] = 10
所以 check[10] = 8
我已经到了这个词的结尾，但在过渡到叶节点时也没有分支。 由于单词 ID 为 4
反转符号，使 base[10] = -4

第 5 步：“Dondo” → “Donbe”、“Donbe” → “Donbe”

double 数组是完整的。 （哦，解释......？ 感谢您的光临。
最后，以下是有关创建 double 数组的一些重要信息。

1234法典