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

Question

我有一个文件(大小= ~1.9 GB),其中包含~220,000,000(~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-13百万字,然后是OOM错误.在将1000万条记录添加到Set中之后,操作变得极其缓慢.例如,添加下一个~4000条记录,耗时60秒.

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

如果您对从这样一个巨大的文件中使用Java删除重复单词的任何其他方法/方法有任何疑问,请告诉我.非常感谢 :)

添加信息问题:我的单词基本上是字母数字,它们是我们系统中唯一的ID.因此,它们不是简单的英语单词.

Answer 1

使用合并排序并在第二次传递中删除重复项.您甚至可以在合并时删除重复项(只需将最新的单词添加到RAM中的输出中并将候选项与其进行比较).

Answer 2

根据单词的第一个字母将巨大的文件分成26个较小的文件.如果任何字母文件仍然太大,请使用第二个字母除以该字母文件.

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

Answer 3

您可以使用trie数据结构一次完成工作.它具有推荐它用于此类问题的优点.查找和插入很快.它的表现相对空间有效.您可以在RAM中表示所有单词.

Answer 4

如果对项目进行排序,重复项将很容易被检测和删除,因为重复项将聚集在一起.

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