如何使用 Hunspell 字典中的数据构建用于快速前缀文本搜索的前缀特里树，而不预先计算所有派生单词形式？

Question

我正在查看一个示例 Hunspell 词典，例如 this Sanskrit one（或这个 800,000+ 行 zip 文件 one），其中包含以下内容：

युयुक्ष्ये/3,4,33,34,53,63,76,86,88,94,158,178,179,182,184,185
युयुम्/48,68,445,2789,4633
युयून्/9
युयुङ्ग/300,422,450,606,641,1559,2836,2859,2869,2870,2871,2908,2910,3124,3420,3421,3423,3424,3425,3429,3430,3431,3432,3433,3434,3435
युयुङ्गान
युयुङ्गाना/1,2,3,17,18,22,24,25,26,27,28,29,30,31,32,34,35,36,38,45,46,47
युयुङ्गाने/3,4,12
युयुङ्गे/522,561,562
युयुङ्गिम/81
युयुङ्गिव/81
युयुङ्गुषी/1,2,3,4,17,18,49,58,59,60,61,64,66,67,128
युयुप/300,422,450,606,641,2836,2859,2869,2870,2871,2908,2910,3124,3420,3421,3423,3424,3425,3429,3430,3431,3432,3433,3434,3435
युयुपान

斜杠之前的字符是定义梵文单词的梵文脚本，斜杠之后的字符是该单词可以组合的所有前缀/后缀（在另一个

.aff

文件中定义）。 Hunspell 文档 很稀疏，但它们涵盖了那些好奇的人的主要基础。它基本上是 2 个文件，一个文本文件列出了我刚才展示的字典单词，另一个是用于指定词缀/替换如何工作的词缀文件。但与我的问题无关。

我的问题源于这些文件的组合方式。他们将词缀/替换内容与基本词分开，因为将基本词与词缀进行组合会占用更多空间（例如有 80 万个基本词，但可能至少有 1000 万个组合）。

如果您有一个自动完成输入/小部件，并且您输入了梵文，那么您如何构建数据以便能够自动完成所有可能的派生词/词缀组合？您必须使用派生词“水合”特里树/在运行时添加组合？或者是否有一些神奇的算法/数据结构技巧，您可以将数据保存在这两个文件中（或某种简单的 JSON 结构，像现在一样将基本单词与词缀分开），并且您可以在运行时检查，从而不必构建一个大的内存树？

似乎您必须编写一些自定义的非通用代码来在查询某些自动完成结果时动态构建附加单词，但是除了“后缀”之外还有“前缀”，所以您似乎需要至少预编译那些前缀+基本词？我不太确定在这种情况下可以做什么才能不破坏内存。有没有一种典型的方法可以在高层处理这个问题？

Answer 1

合适的数据结构是“紧凑有向非循环字图”。这只是一个 patricia 树/基数树，只不过每个不同子树只有一个副本。

因为这会重用公共前缀和公共后缀，所以它可以复制源文件中的压缩类型。