java - 在java中对一个巨大的String集合进行uniq和索引

Question

我有一个巨大的 utf8 字符串数据集需要处理，我需要消除重复才能获得唯一的字符串集。

我正在使用散列来检查字符串是否已知，但现在我达到了 100 000 000 个字符串，我没有足够的 RAM 并且进程崩溃了。此外，我只处理了 1% 的数据集，因此内存解决方案是不可能的。

我想要的是一个混合解决方案，比如“内存索引”和“基于磁盘的存储”，这样我就可以使用 10Go 的 RAM，我必须加快这个过程。

=> 你知道有一个 Java 库已经在这样做吗？如果不是，我应该关注哪种算法？

在内存中使用布隆过滤器来检查字符串是否不存在可能是一个解决方案，但我仍然需要有时检查磁盘(误报)，我想知道不同的解决方案。

=> 如何将字符串存储在磁盘上以实现快速读写访问？

_ 我不想使用像 nosql db 或 mysql 这样的外部服务，它必须是嵌入的。

_ 我已经尝试过基于文件的轻型 SQL 数据库，例如 h2sql 或 hsql，但它们在处理大量数据集方面非常糟糕。

_ 我不考虑使用 Trove/Guava Collections 作为解决方案(除非他们提供我不知道的基于磁盘的解决方案)，我已经在使用内存效率极高的自定义哈希集，而且我什至不存储String 但内存中的 byte[]。我已经为 jvm 调整了 -Xmx 内容。

编辑:我正在处理的数据集很大，原始的未排序数据集不适合我的硬盘。我逐字节流式传输并处理它。

Answer 1

你可以做的是使用 External Sorting Technique例如 External Merge Sort您首先要对数据进行排序。

完成此操作后，您可以迭代排序集并保留遇到的最后一个元素。一旦你有了这个，你就可以检查当前项目和下一个项目。如果它们相同，则继续下一个项目。如果没有，您将更新当前拥有的项目。

为了避免巨大的内存消耗，您可以在达到特定阈值时将唯一项目列表转储到硬盘驱动器并继续。

长话短说:

Let data be the data set you need to work with
Let sorted_data = External_Merge_Sort(data)
Data_Element last_data = {}
Let unique_items be the set of unique items you want to yield
foreach element e in sorted_data
    if(e != last_data)
    {
        last_data = e
        add e in unique_items
        if (size(unique_items) == threshold)
        {
             dump_to_drive(unique_items)
        }
    }