logo标签列表

Java如何在单词多达2亿时去重？

javaduplicates
22

我有一个文件（大小约为1.9 GB），其中包含大约220,000,000（约220百万）个单词/字符串。它们有重复，几乎每100个单词就有1个重复。

在我的第二个程序中，我想读取该文件。我成功使用 BufferedReader 逐行读取了该文件。

现在要删除重复项，我们可以使用 Set（及其实现），但是 Set 存在问题，如下所述的3种不同情况：

  1. 使用默认的 JVM 大小，Set 最多可以包含0.7-0.8百万个单词，然后出现 OutOfMemoryError。
  2. 使用512M的 JVM 大小，Set 最多可以包含5-6百万个单词，然后出现 OOM 错误。
  3. 使用1024M的 JVM 大小，Set 最多可以包含12-13百万个单词，然后出现 OOM 错误。在添加1000万条记录到 Set 后，操作变得极其缓慢。例如，添加下一组 ~4000 条记录，需要60秒。

我有限制，不能进一步增加 JVM 大小，并且我想从这样一个巨大的文件中删除重复的单词。

请让我知道是否有任何其他方法/方法来使用 Java 从如此巨大的文件中删除重复的单词。非常感谢 :)

问题补充：我的单词基本上是字母数字，并且它们是我们系统中唯一的 ID。因此，它们不是纯英语单词。

对于这个问题，你可以使用数据库或者第二个文件来存储结果吗？ - Francisco Spaeth
3
“一个100个单词的副本”是什么意思？每个长度为100的子列表平均包含两次相同的元素，还是文件中99%的单词都是唯一的？ - meriton
5
这里的关键是“外部排序”。一旦单词被排序，所有重复的单词就会排在一起。然后再对数据进行一次快速遍历，过滤掉重复项。 - NovaDenizen
1
在这里定义“word”。它是真正的标准口语单词，还是其他什么东西？ - Hot Licks
请记住，文件本身大于1024M，因此任何试图在内存中存储所有字符串而没有一些复杂的压缩方案的尝试都注定会失败。 - Buhb
显示剩余7条评论
13个回答
14

使用 归并排序 在第二轮处理中去除重复项。甚至可以在合并时就去除重复项（只需将最新添加到输出的单词保留在内存中，并将候选单词与其进行比较）。

这应该是相当简单的问题，有着成熟的工具来解决它。 - Louis Wasserman
3
尽管如此，这可能会导致内存不足。 - Lukasz Madon
1
@lukas，你怎么看待这个问题？归并排序在RAM上可以非常低。 - Tobias Ritzau
11

将巨大的文件根据单词的首字母分成26个较小的文件。如果任何一个字母文件仍然太大，则使用第二个字母将该字母文件再次分割。

使用 Set 处理每个字母文件以去除重复项。

1
这将假设 Q 和 A 一样频繁，否则你可能会超过适合某些字母的 1000 万个单词。 - Joachim Isaksson
3
相较于其他人提供的简单排序解决方案，我认为这个解决方案更加复杂，既难以解释也难以实现。在硬盘上对大文件进行排序是一个常见的任务，并有现成的实现方式。而“如果文件仍然太大，则将其分解”的整个过程需要更多代码或手动干预。直接对整个文件排序真的更简单，一劳永逸。 - John Y
除了约翰Y提到的暗示之外，你可以根据hashcode() % n来分割文件，其中n是一个合理的数字。 - Buhb
@JohnY和Buhb：我的方法保证多个文件中不会有重复的单词。任何一个重复的单词都在同一个文件中。 - Gilbert Le Blanc
@GilbertLeBlanc 我只是在解决99%的单词以相同字母开头的问题。自从你编辑建议对文件进行递归细分后，这个问题就不再存在了。 - Buhb
显示剩余2条评论
7
你也许可以使用trie数据结构来一次性完成这项工作。它具有推荐用于此类问题的优点。查找和插入都很快。而且它的表示相对空间效率较高。你也许能够在RAM中表示所有单词。
这是目前为止最有趣的建议之一。你可能会用尽内存，然后需要考虑完全新的解决方案，但至少它提供了一些希望，可以在内存中存储所有唯一的字符串，这非常方便。 - Buhb
你仍需要超过一个节点来区分单词 - 即使您不存储字符串本身，也至少需要8个字节，并且需要一个节点的链接数组。 - Konstantin Pribluda
5
4
4
问题：这些是真正的单词，还是其他东西——词组、零件编号等等？对于口语常用语言中的单词，人们预计在前几千个之后就已经找到了大部分独特的词汇，因此你唯一需要做的就是读入一个单词，将其与字典进行比较，如果找到则跳过，否则将其添加到字典中并写出。在这种情况下，您的字典只有几千个单词大小。并且您不需要保留源文件，因为一旦发现独特的单词就会立即将其写出(或者在完成后可以直接转储字典)。
4
如果您有可能将单词批量插入数据库的临时表中，那么应该对该表进行select distinct操作。
3
一种解决此类问题的经典方法是使用Bloom过滤器。基本上，您需要对单词进行多次哈希，并为每个哈希结果在位向量中设置一些位。如果您正在检查一个单词，并且其哈希的所有位都在向量中设置，则您可能（通过增加哈希/向量中的位数可以将此概率任意降低）已经看到它了，这是重复的。
这就是早期拼写检查器的工作方式。它们知道一个单词是否在字典中，但不能告诉您正确的拼写，因为它只会告诉您当前单词是否已被看到。
有许多开源实现，包括java-bloomfilter。
你如何验证它确实是一个重复项（而不是误报）？ - Tobias Ritzau
您可以将概率设置得任意低，但代价是内存。不幸的是，这是概率算法的代价。考虑到您的限制、数据大小以及事实上您在事后不需要检查其他成员，排序解决方案可能更加合适。 - Paul Rubel
2
布隆过滤器会不必要地不精确。 - NovaDenizen
如果布隆过滤器表明这个单词很可能是重复的，你可以（代价很大地）回到输出文件的开头，并扫描它以验证它是否真的存在。 - Samuel Edwin Ward
我没有真正使用布隆过滤器，但我正在考虑一种解决方案，其中您可以进行一次遍历以为集合创建过滤器，并进行第二次遍历，将未命中的内容存储在输出文件中。 命中的内容保存在一个集合中，仅当该内容不存在于集合中时才写入。由于只有大约1％的重复项，因此这应该有效。是吗？ - Tobias Ritzau
1
为了不必过于担心实现问题，您应该使用数据库系统，可以是传统的关系型SQL或No-SQL解决方案。我相信您可以使用例如Berkeley DB Java版，然后执行（伪代码）：
for(word : stream) {
  if(!DB.exists(word)) {
     DB.put(word)
     outstream.add(word)
  }
}

问题本质上很简单，你需要将东西存储在磁盘上，因为内存不足，然后使用排序O（N log N）（不必要）或哈希O（N）来查找唯一的单词。
如果您想要一个很可能有效但不能保证有效的解决方案，请使用LRU类型的哈希表。根据经验 Zpif's law，您应该没问题。
对于某些聪明人的后续问题，如果我有64位机器并将堆大小设置为12GB，虚拟内存不应该以最佳方式解决问题吗？还是Java没有设计成这样？
1

即使是英语这种词汇量庞大的自然语言，其单词数量的上限估计仅有大约80000个。基于此，您可以使用HashSet并将所有单词添加到其中(可能都使用小写以避免大小写问题)：

Set<String> words = new HashSet<String>();
while (read-next-word) {
    words.add(word.toLowerCase());
}

如果这些是真实的单词，那么这不会导致内存问题，速度也会相当快！
这也是我最初的想法，但在主题中他说他们已经尝试过使用Sets，但失败了。它们可能不是真正的单词。 - enTropy
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接