文本处理简介：让我们在 Python 中快速制作字典（第 4 部分）
目录
[第 1 部分]
[第 2 部分]
[第 3 部分]
[第 4 部分]
双精度数组的 Python 实现（第 3 部分）
到目前为止，我们主要讲了 double 数组的创建。
如果你读过它，你可能在某种程度上有搜索的形象。
如果创建的故事还是有点困难，请再阅读一遍 “创建 double array”。
尝试移动你的手，并用双精度数组填充表格。
以下是我想写的关于增量搜索的内容。
在解释的 6 个字中，在搜索 “donchan” 的同时，当你从头到第二个字母 “don” 时，你可以找到叶子节点。
在关联数组（如 Pyrthon's dict）中，“donchan” 和 “don” 是单独的搜索。
在包含 double 数组的 Trie 树中，它还可以同时选取搜索键和正向匹配子字符串之间的匹配项。
特里是树最大的力量。
当您考虑一个查找与句子中的 headword 匹配的所有字符串的过程时，
如果你要使用 dict 创建类似的字典搜索，它将从句子中的每个字符位置开始
您需要创建所有长度的子字符串，并查询每个子字符串的 dict。
刑期越长，看起来就越难。
另一方面，如果您想按 Trie 树搜索怎么办？
你只需要给出每个字符在句子中的位置。
您不必费心创建从该位置开始包含各种长度字符串的搜索键。
此外，如果您无法再在 Trie 树中过渡，您将立即退出该过程。
它甚至没有像 dict 那样使用长而无用的 key 进行搜索。
然后，当您完成一个过程时，您将获得到目前为止子字符串中与字典匹配的所有 headwords。
现在，我将尝试编写一个程序，该程序使用独立于创建它的程序的双精度数组。
在这种情况下，jupyter-notebook 很容易，因为你可以将其移动到底部单元格。
在创建双精度数组的程序中，出现了各种数量（变量）。
但是，当使用 double 数组时，您需要：
它只是给定节点位置的 base 和 check 值。
您甚至不需要费心使用 base 数组或 check 来获取值。
让我们读取文件并直接访问其二进制文件。
在使用的程序中，创建一个类。 DArray 类有四种方法。
方法：__init__
它读取三个字典文件并将它们保留为成员。
但是，字符 = >字符 ID 的对应关系保存在名为 c2code 的字典中。
方法：碱
它是一个类似 getter 的方法，从节点位置返回其 base 组件。
方法：检查
它是一个类似 getter 的方法，从节点位置返回其 check 组件。
方法：search_gen
对 double 数组的搜索与创建时节点之间的过渡完全相同。
不同之处在于没有新的节点创建，当无法转换时，搜索将按原样完成。
在某种程度上，它是一种比创建 double 数组更简单的算法。
此方法是生成器，因为它更容易编写。
调用时，将其转换为 list 或将其写入 for 语句。
该方法的输入是执行增量搜索的搜索键（例如，一个完整的句子）
和角色 ID 列表。 此外，我将尝试编写类似伪代码的句子。
＿＿s = 1
__One搜索键左侧的字母c掏; 将角色位置设置为我（循环）
__字符c是字符身份证未列出时：
＿＿＿＿返回#搜索结束
__字符c是字符身份证在列表中时：
＿＿＿＿基地获取
＿＿＿＿t = 基数 [s] + c2code[c]
＿＿＿＿检查[T]获取
＿＿＿＿检查[t] = s当时：#一致性检查还行
＿＿＿＿＿＿base[t] < 0当时：#叶节点 1
＿＿＿＿＿＿＿＿我和–基地[t]举屈服做#有一个注册词！
______否则：
＿＿＿＿＿＿＿＿t2 = 基数 [t]
＿＿＿＿＿＿＿＿base[t2] < 0和检查[t2] == t当时：#叶节点 2
＿＿＿＿＿＿＿＿＿＿我和-基地[t2]举屈服做#有一个注册词！
＿＿＿＿＿＿s = t#移动到下一个节点位置
＿＿＿＿＿＿下一个
＿＿＿＿检查[t] ！= s当时：#一致性检查议员
＿＿＿＿＿＿返回#搜索结束
DArray 类的程序如下所示： 它很短。
双精度数组的 Python 实现（第 4 部分）
现在，让我们实际使用上面的 DArray 类。
我想搜索一篇较长的维基百科文章，看看维基百科的标题字符串获得了多少次点击。
维基百科禁止抓取，所以快点
从浏览器的文章列表中打开任何文章，复制并粘贴，然后将其另存为文本文件。
“长页（维基百科）”
https://ja.wikipedia.org/wiki/ Special： 长页
我选择了《欧洲政教分离史》（The History of the Separation of Church and State in Europe）并保存为church.txt。
它不到 500 KB，对于一篇文章来说，这是相当长的文本。
搜索文章的过程分为三个步骤：
（1） 阅读文件的行，
（2） 从该行的字符串的每个字符位置开始创建一个子字符串，
（3） 对每个子字符串执行增量搜索。
既然我们用 generator 编写了 search 方法，那么让我们在这里也让每个阶段都成为一个 generator。
多级生成器只是将结果作为变量一个接一个地传递。
通过时，不执行实际计算（惰性计算）
假设你希望上游生成器将两个变量放在一起，并以 Tuples 的形式流它们。
如何在下游生成器中使用其中的一些？
如果在下游生成器中，
(变量 1，变量 2） =上游生成器结果
如果是这种情况，多次调用 upstream generator 的所有结果都将扩展为一个数组。
（太可怕了！ ）
然后它尝试将该数组传递给一个双元素元组，这会导致元素计数错误。
因此，如何使其工作是在下游生成器中创建一个 for 循环 once，
其中，您应该尝试接收：
对于 （变量 1，变量 2）上游生成器结果：
变量 1和变速档 2处理方式
实际查看该程序可能会更快。
文章中大约有 85,000 个字符串与词典匹配。
内存使用量约为 64 MB，在 Core i7 上约为 2 秒。
当我对一个关联数组的 dict 做同样的事情时，它大约需要 20 秒。
在 dict 版本中，从 words.txt 创建 dict 所需的时间被排除在障碍之外。
最初，Trie 树是一种高速算法，但 double 数组特别快。
（↑ 这是本文这一行的摘要）
最后的几点思考
考虑改进此计划所面临的挑战。
“如果你要把它整合到你的系统中，你不需要更多的错误检查吗？”
还有一个故事，但我现在先不说那一面。
“用 C++ 重写”
“处理 UTF8 字节而不是字符单位，并按原样使用字符代码值”
两者都不难，所以如果您有兴趣，请试一试。
“帕特里夏要成为一棵树”
帕特里夏树（radix trie / compact前缀树）是Trie树的独创性之一。
在本文的描述和实现中，我们在 transition 不分支时压缩了 leaf 节点。
在 Patricia 树中，所有节点都被压缩，而不管叶节点如何，因此没有分支和单个路径。
例如，在用于解释的六个词的世界里，“→ →词尾”的过渡没有分支，是一条笔直的路径，因此可以合二为一。
然后，您将需要 9 个节点。 请数一数。
长期以来，帕特里夏木一直被用作压缩特里木的方法。
也许吧，但它似乎也是 double 数组中的一种常见方法。
但是，当双重排列是 Patricia 木材时，就有很大的不同。
也就是说，由于将单个路径放在一起，“每个节点都有多个过渡目标”。
这意味着很难从左侧整齐地填充 double 数组的空白。
创建 double 数组时，无法并行处理多个方面。
由于它必须一次一步地连续处理，因此将其作为填充问题来解决会花费太多时间。
另一方面，如果每次创建节点时都从最左侧的根位置寻找空闲空间，则该过程会逐渐变慢。
这就是为什么“一旦空间填满到一定程度，我们就不会在那个区域更加努力。
这似乎是一种现实的方法。 即使某个地区的所有空缺都没有填补，在某个时间或某些条件下，
左端（您开始查找过渡目标候选项的位置）将向右移动。
其实，在为本文创建程序时，随着 double 数组的增长
我们在研究自由空间会发生什么变化的同时继续进行这项工作。
因此，在处理过程中会发生大量没有分支的过渡。
事实证明，这些节点从左侧填充了越来越多的空白。
因此，双精度数组的创建也非常流畅和快速。
根据任务（或输入数据），例如“当分支过渡在劳动力中占主导地位时”，
本文更新空位的方式可能存在问题。
出于这个原因，我在本文中没有涉及 Patricia 树。
如果有机会，我想再参加一次。
到目前为止，我用 Python 制作了一个字典查找程序。 感谢您的阅读。
* 请自由安排使用本文中的程序。
但是，对于由此类劣势造成的任何劣势，我们概不负责。
哈特布
