2

我对自然语言处理和 Java 编程很陌生。我有一个非常大的文本文件，其中包含 ngram 和相关频率（aaprox. 250 mb）。我需要在程序运行时获取频率值，给定一个 ngram。文件中提供的 ngram 频率如下（仅作为示例）：

the quick 445
quick brown 458
brown fox 11
fox jumped 123

我尝试在启动时通过填充一个哈希集来读取文件……但一个 18mb 的文件花了将近 1500 毫秒（使用 System.currentTimeMillis() 测试）。现在我正在考虑对 n-gram 计数进行排序并将 250mb 文件分成小块并填充一个列表并通过在单独的索引中索引文件集并引用它来按需获取频率。

但是，我不确定是否有另一种更简单或更有效的方法来做到这一点。请让我知道是否有更好的方法来做到这一点。（最好不使用任何脚本或库......）。谢谢你们。

4

2 回答 2

2

看看BerkeleyLM，它是一个用于处理 ngram 的特殊库。

于 2013-02-22T19:52:12.743 回答
2

我同意@mbatchkarov 的观点，即加载时间通常不是最重要的优化目标。但是运行时通常与内存占用密切相关（内存访问速度很慢，因此缓存中可以容纳的工作集越多越好）。

您将每个二元组映射到整数计数（大概在 java.util.HashMap 中）的初始方法是明智的，但非常占用内存。您的计数文件包含数百万个二元组，每个元组都必须表示为单独的字符串。这些字符串消耗（至少）大约 40 个字节的内存，并且每个计数都需要一个 Integer 对象——在大多数 JVM 实现中大约需要 20 个字节。我粗略的粗略猜测将该数据结构超过了千兆字节。

但是您可以做得更好，通过观察虽然双元组仅在您的文件（和您的数据结构）中出现一次，但大多数单个单词会重复多次 - 您可以在不重复存储它们的情况下逃脱。

我将从单词到整数索引的映射开始 - 例如，从您的示例中，the=0、quick=1、brown=2 等等。我不知道您的词典有多大，但常用英语单词的典型映射可能有几万或几十万个单词。所以字符串存储必须更小。

要存储计数，您可以将这些整数词索引组合成一个复合键，并将该键用于您的地图。一种简单的“组合”方法是简单地将第一个单词的索引移位，并在第二个索引中进行 OR。

在伪代码中：

HashMap<String, Integer> lexicon = new HashMap<String, Integer>();

// Iterate through the file, mapping each word to 
for (String file line) {
  ... Parse out word1 and word2
  if (!lexicon.containsKey(word1)) {
      lexicon.put(word1, lexicon.size());
  }
  if (!lexicon.containsKey(word2)) {
      lexicon.put(word2, lexicon.size());
  }
}

现在，再次遍历文件，将计数添加到单独的计数映射中。

HashMap<Long, Integer> countMap = new HashMap<Long, Integer>();

for (String file line) {
    ... Parse out word1, word2, and count
    int i1 = lexicon.get(word1);
    int i2 = lexicon.get(word2);
    long key = (i1 << 32) | i2;
    countMap.put(key, count);
}

访问二元计数类似于映射它 - 查找两个单词的索引，创建键，然后在计数映射中查找。这应该会大大减少您的存储空间。但我会更进一步，用FastUtil或Trove之类的特定类型映射替换通用 HashMaps 。原始数据结构将消除数据映射中每个 Long 和 Integer 的大量 ~12-20 字节开销。

上面的伪代码假设您使用 32 位整数作为单词索引，并将它们组合成 64 位长整数。如果您的词典足够小，您可以使用 16 位 short 和 32 位 int 来代替，这样可以节省更多空间。

编辑：我应该很清楚，如果你想实现一个完整的 n-gram 语言模型（trigram、4-gram 等），有更有效的表示，并且 n-gram 模型可以由几个库很好地处理（我建议你看看OpenGRM和Lingpipe）。但是上面的伪代码是一种简单且相对有效的方法来做一个简单的二元模型。

于 2013-02-21T23:19:11.733 回答