java - 构建基于计数的分布模型时，ngram 长度可达 5 的数据结构选择

Question

我正在根据文本构建分布模型(基于计数)。基本上，对于每个 ngram(单词序列)，我必须存储一个计数。我需要相当快速地访问计数。对于 n=5，从技术上讲，所有可能的 5-gram 都是 (10^4)^5，即使我假设保守估计为 10k 个单词，这太高了。但这些 n 元语法的许多组合不会存在于文本中，因此 5d 数组类型的结构不予考虑。

我构建了一个特里树，其中每个单词都是一个节点。所以这个 trie 会非常宽，最大深度为 5。这给我节省了大量的内存。但在我训练足够的文件后，我仍然耗尽内存(64GB)。公平地说，我在这里并没有使用任何 super 高效的 Java 实践。每个节点都有一个计数，单词索引为 int。然后我有一个 HashMap 来存储 child 。我最初是从一个 list 开始的。每次我添加一个 child 时都尝试对其进行排序，但我在那里浪费了很多时间，所以转向了 HashMap。即使有一个列表，在阅读更多文件后我也会耗尽内存。

所以我想我需要将我的任务分成几个部分，将每个部分存储到磁盘上。但最终，在访问时我需要合并这些数据结构。所以我认为前进的方向是基于磁盘的解决方案，我知道要访问哪个文件来访问以某些内容(某种顺序)开头的 ngram。在我看来，trie 的问题在于，当我四处合并它时，它的效率不是很高。我需要将两个部分加载到内存中进行合并。这实际上行不通。

您会推荐什么方法？我研究了一种基于 HashMap 编码的语言模型结构(如 berkeleylm 使用的结构)。但在他们的用例中，他们不需要重建 ngram，因此他们只需对其进行散列并将散列值存储为上下文。我需要稍后能够访问上下文。

有什么建议吗？使用数据库有什么值(value)吗？他们可以在不内存的情况下做到这一点吗？

Answer 1

我不会使用HashMap，它非常占用内存，一个简单的排序数组应该更好，然后你可以对其使用二分搜索。

也许您也可以尝试二进制前缀特里树。首先，您创建一个字符串，例如通过将单词的字母交错成一个字符串(我想您也可以将它们连接起来，用空格分隔)。然后可以将这个长字符串存储在二进制特里树中。请参阅CritBit1D举个例子。

您还可以使用多维树。许多树仅限于 64 位数字，但您可以将每个单词的前八个 ASCII 字符冷转换为 64 位整数，然后将其存储为 5D key 。这应该比 5D 数组高效得多。多维索引有:kd 树、R 树或四叉树。 5 克计数和完整 5 克(包括剩余字符)可以单独存储在可与每个 5D-KEY 关联的 VALUE 中。

如果您使用 Java，您可以尝试我自己的 tree 。它是一个前缀共享的按位四叉树。它的内存效率非常高，非常适合较大的数据集(1M 条目以上)，并且 native 使用“整数”而不是“浮点”。它还具有非常好的最近邻搜索功能。