22

我有一个文件（大小 = ~1.9 GB），其中包含 ~220,000,000（~2.2 亿）个单词/字符串。他们有重复，每 100 个单词几乎有 1 个重复单词。

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

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

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

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

如果您对使用 Java 从如此庞大的文件中删除重复单词有任何想法，请告诉我。非常感谢 ：）

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

4

13 回答 13

14

Use merge sort and remove the duplicates in a second pass. You could even remove the duplicates while merging (just keep the latest word added to output in RAM and compare the candidates to it as well).

于 2012-09-19T19:07:11.630 回答
11

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

使用 a 分别处理每个字母文件Set以删除重复项。

于 2012-09-19T19:07:55.767 回答
7

您也许可以使用trie数据结构一次性完成这项工作。它具有推荐它用于此类问题的优点。查找和插入很快。并且它的表示是相对节省空间的。您可能能够在 RAM 中表示所有单词。

于 2012-09-19T21:33:11.887 回答
5

如果您对项目进行排序，重复项将很容易检测和删除，因为重复项会聚集在一起。

这里有代码可以用来对大文件进行合并排序：http: //www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

于 2012-09-19T19:17:26.767 回答
4

如果您可以在数据库的临时表中插入单词（使用批量插入），那么它将是对该表不同的选择。

于 2012-09-19T20:03:59.517 回答
4

问题：这些真的是单词，还是其他东西——短语、零件编号等？

对于通用口语中的单词，人们会期望在最初的几千个之后，您会找到大部分独特的单词，因此您真正需要做的就是读入一个单词，对照字典检查，如果找到了 跳过它，如果找不到，请将其添加到字典中并写出来。

在这种情况下，您的字典只有几千个单词。而且您不需要保留源文件，因为您一找到唯一单词就写出它们（或者您可以在完成后简单地转储字典）。

于 2012-09-19T19:13:46.637 回答
4

对于大文件，我尽量不将数据读入内存，而是对内存映射文件进行操作，并让操作系统根据需要调入/调出内存。如果您的设置结构包含此内存映射文件的偏移量，而不是实际的字符串，则它将消耗更少的内存。

看看这篇文章：

http://javarevisited.blogspot.com/2012/01/memorymapped-file-and-io-in-java.html

于 2012-09-19T19:07:56.813 回答
3

解决此类问题的一种经典方法是布隆过滤器。基本上，您对您的单词进行多次散列，并为每个散列结果在位向量中设置一些位。如果您正在检查一个单词，并且它的哈希中的所有位都设置在您可能已经看过的向量中（您可以通过增加向量中的哈希/位的数量来将此概率设置为任意低）并且它是重复的.

这就是早期拼写检查器的工作方式。他们知道字典中是否有一个单词，但他们无法告诉您正确的拼写是什么，因为它只会告诉您当前单词是否被看到。

有许多开源实现，包括 java-bloomfilter

于 2012-09-19T19:10:43.967 回答
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 定律，您应该没问题。

对一些聪明人的后续问题，如果我有 64 位机器并将堆大小设置为 12GB，虚拟内存不应该解决这个问题（尽管不是以最佳方式）还是 java 不是设计的这边走？

于 2012-09-20T01:56:01.277 回答
1

即使在自然语言中拥有大量单词的英语中，最高估计也只有大约 80000 个单词。基于此，您可以使用 aHashSet并添加所有单词（可能全部小写以避免大小写问题）：

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

如果它们是真实的话，这不会导致记忆问题，也会很快！

于 2012-09-20T02:32:21.430 回答
1

我会在 Java 中以与其他所有语言相同的方式解决这个问题：编写一个重复数据删除过滤器并根据需要经常对其进行管道传输。

这就是我的意思（在伪代码中）：

  • 输入参数：Offset,Size
  • 分配大小的可搜索结构Size（= Set，但不必是一）
  • 从标准输入读取Offset（或遇到 EOF）元素并将它们复制到标准输出
  • Size从标准输入（或 EOF）读取元素，将它们存储在 Set 中。如果重复，则删除，否则写入标准输出。
  • 从标准输入读取元素直到 EOF，如果它们在Set则删除，否则写入标准输出

Offset现在，随着s 和 sane的增加，您可以根据需要管道尽可能多的实例（如果存储没有问题，可能只有您拥有的核心数量）Size。这使您可以使用更多内核，因为我怀疑该进程受 CPU 限制。如果您赶时间，您甚至可以在更多机器上使用netcat和传播处理。

于 2012-09-19T19:09:20.317 回答
0

Quicksort would be a good option over Mergesort in this case because it needs less memory. This thread has a good explanation as to why.

于 2012-09-19T20:17:53.867 回答
0

大多数高性能解决方案都源于省略不必要的东西。您只查找重复项，所以不要存储单词本身，存储哈希。但是等等，你也对哈希不感兴趣，只有当它们已经被看到时——不要存储它们。将哈希视为非常大的数字，并使用 bitset 来查看您是否已经看到了这个数字。

所以你的问题归结为非常大的稀疏填充位图 - 大小取决于哈希宽度。如果您的哈希值高达 32 位，则可以使用 riak 位图。

... 考虑 128+ 位哈希的真正大位图 %）（我会回来的）

于 2012-10-09T09:18:55.287 回答