如何在单词超过2亿时使用Java删除重复的单词？

我有一个文件（大小=〜1.9 GB），其中包含约2.2亿（〜2.2亿）字/字符串。他们有重复，每100个单词几乎有1个重复的单词。如何在单词超过2亿时使用Java删除重复的单词？

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

我们删除重复，我们可以使用SET（和它的实现），但设置有问题，如描述以下3个不同的场景：

在默认的JVM，集最多可包含0.7- 80万字，然后是OutOfMemoryError。
使用512M JVM大小，Set可以包含高达5-6百万字，然后是OOM错误。
使用1024M JVM大小，Set最多可包含12-13万个字，然后出现OOM错误。这里有1000万条记录添加到Set之后，操作变得非常缓慢。例如，添加下一个约4000条记录，它花费了60秒。

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

请让我知道，如果你有任何其他方式/方法从这样一个巨大的文件中使用Java删除重复的单词的任何想法。许多感谢:)

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

来源

2012-09-19 Ketan

的解决方案，你可以使用一个数据库，甚至第二个文件来存储结果呢？ –

我想你会迭代很长一段时间。 –

我会确保我有足够的内存来完成任务。您可以购买大约100美元的16 GB PC内存。这些日子并没有那么多花费。 –

使用merge sort并在第二遍中删除重复项。你甚至可以在合并的时候删除重复的内容（把最新的单词添加到RAM中输出，并将候选对象也与之相比较）。

来源

2012-09-19 19:07:11

+1。对于这个问题，这应该相当简单明了。 –

而且可能会导致OutOfMemory –

@lukas，你怎么看到这种情况？合并排序在RAM上可能非常低。 –

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

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

来源

2012-09-19 19:07:55

这会假设'Q'与'A'一样频繁，或者您可能会翻阅适合某些字母的10M个单词。 –

@Joachim Isaksson：很好。按前两个字母分解最大的文件。 –

我发现这个解决方案比其他人提供的简单的基于排序的解决方案更复杂，解释也更复杂。对磁盘上的大文件进行排序是现成实现的常见任务。如果它们仍然太大，整个“将更大的文件细分”需要更多代码或手动干预。要继续分类整个事情并且完成它，实际上要简单得多。 –

对于大文件，我尝试不将数据读入内存，而是对内存映射文件进行操作，并根据需要让操作系统页进/出内存。如果你的设置结构在这个内存映射文件中包含偏移量而不是实际的字符串，它会消耗更少的内存。

看看这篇文章：

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

来源

2012-09-19 19:07:56

我会以同样的方式处理这个在Java作为在所有其他语言编写一个重复数据删除过滤，并根据需要管它经常。

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

输入参数：Offset，Size
分配大小Size的搜索结构（= Set，但不必是一个）
阅读从stdin（或EOF）读取Size中的元素，将它们存储在Set中。如果重复，则删除，否则写入标准输出。从标准输入直到EOF，如果他们在Set然后放下，否则写
阅读内容到标准输出

现在管尽可能多的情况下，你需要（如果存储是没有问题的，因为你有可能仅作为多随着Offsets和理智Size增加。这让你可以使用更多的核心，因为我怀疑这个过程是CPU绑定的。如果您匆忙，您甚至可以使用netcat并将处理扩展到更多机器。

来源

2012-09-19 19:09:20

解决这类问题的一个经典方法是Bloom filter。基本上你会多次散列你的单词，并且每个散列结果都将一些位设置在一个位向量中。如果你正在检查一个单词，并且它的哈希中的所有位都被设置在矢量中，那么你可能会看到它，并且它是重复的（可以通过增加矢量中的哈希/位的数目来任意设置此概率）。

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

有一些开源实现在那里，包括java-bloomfilter

来源

2012-09-19 19:10:43

你如何确认它实际上是重复的（而不是误报）？ –

您可以将内存成本设置为任意低的概率。不幸的是，这是您为概率算法付出的代价。考虑到您的限制，数据大小以及在排序解决方案可能更合适之后您不需要检查其他成员的事实。 –

布隆过滤器会不必要地不精确。 – NovaDenizen

问：难道这些真的话，还是他们是别的东西 - 短语，零件编号等？

对于普通口语中的单词，人们会认为在第一个几千之后，你会发现大多数独特的单词，所以你真正需要做的就是读一个单词，在字典中检查它，如果找到，跳过它，如果没有找到，将它添加到字典并写出来。

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

来源

2012-09-19 19:13:46

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

这里有代码，你可以用它来归并大文件： http://www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

来源

2012-09-19 19:17:26

如果你有posibility（使用批量插入）插入词语的数据库的临时表，那么这将是一个选择不同的表格。

来源

2012-09-19 20:03:59

在这种情况下，Quicksort将是一个比Mergesort更好的选择，因为它需要更少的内存。 This thread对于原因有很好的解释。

来源

2012-09-19 20:17:53 Evo510

但是，快速排序是内存排序，并且mergesort只需要足够的RAM来存放2个读取缓冲区和一个写入缓冲区。 – NovaDenizen

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

来源

2012-09-19 21:33:11 gregg

这是迄今为止最有趣的建议之一。您可能会耗尽内存，然后您需要查看全新的解决方案，但这至少可以提供将所有独特字符串存储在内存中的一些希望，这很方便。 – Buhb

你仍然需要不止一个节点亲不同字 - 即使你不存储字符串本身也是至少8字节，并且链接数组节点 –

为了不必太担心实现，您应该使用数据库系统，无论是普通的旧关系SQL还是无SQL解决方案。我很肯定你可以使用例如Berkeley DB Java版，然后做（伪代码）

for(word : stream) { 
    if(!DB.exists(word)) { 
    DB.put(word) 
    outstream.add(word) 
    } 
}

的问题在本质上是容易的，你需要的东西存储在磁盘上，因为没有足够的内存，那么无论使用排序O（N日志N）（不必要的）或散列O（N）来找到唯一的单词。

如果您想要一个很有可能工作但不能保证这样做的解决方案，请使用LRU类型的散列表。根据经验Zpif's law你应该没问题。

后续问题给那里的一些聪明人，如果我有64位机器并且设置堆大小为12GB，那么虚拟内存不应该照顾问题（尽管不是最佳方式），或者java是不是这样设计的？

来源

2012-09-20 01:56:01 user1443778

即使在英语中，对于自然语言而言，单词数量也很大，但上面的估计值只有大约80000个单词。在此基础上，你可以只使用一个HashSet并添加所有你的话它（可能在所有小写，以避免问题的情况下）：

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

如果他们是真正的话，这不会造成内存问题，也会很快！

来源

2012-09-20 02:32:21 Bohemian

这是我第一次想到，但在他说他们已经尝试过设置并失败。他们一定不是真正的话 – enTropy

大多数高性能解决方案都是由于省略了不必要的东西而产生的。你只看重复，所以不要存储单词本身，存储哈希值。但是，等一下，你也不会对哈希感兴趣，只要他们已经见过 - 不要存储它们。将哈希视为非常大的数字，并使用bitset来查看您是否已经看过这个数字。

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

...去思考真正的大位图128+位散列％）（我会回来）

来源

2012-10-09 09:18:55

如何在单词超过2亿时使用Java删除重复的单词？

回答

相关问题