在大文件中查找重复项

Question

我有一个大小约为1500万条目的非常大的文件。 文件中的每一行都包含一个单独的字符串(称之为键)。

我需要使用Java查找文件中的重复条目。 我试图使用哈希表来检测重复条目。 显然，这种方法会抛出"java.lang.OutOfMemoryError: Java heap space"错误。

如何解决这个问题?

我认为我可以增加堆空间并尝试它，但我想知道是否有更好、更有效的解决方案，而无需调整堆空间。

- Maximus

---

离题：你是如何一开始就获得了1500万条目的？ - Mob

好的工作方式应该是不要有重复项。不应该需要删除重复项。 - Martijn Courteaux

@Martijn Courteaux：你不知道这是什么类型的数据。举个例子，如果你有一本书想要知道书中使用了哪些单词，首先不能避免像“the”这样的重复单词。 - DarkDust

@Martijn Courteaux - 你在哪里工作？你总是能要求所有输入的格式都符合你的需求吗？我也想在那里工作！ - Peter Recore

@PeterRecore：我还没有工作。我正在上中学... :( 但是，是的。我明白。我的表兄在IT行业工作，他讲述的故事相当令人失望。很多菜鸟在重要公司工作等等。 - Martijn Courteaux

@Martijn Courteaux - 啊，所以你还年轻和乐观 :) 不仅是“新手”是问题。现实世界很凌乱。我们的工作之一就是克服混乱，生产出有用的东西。想象一下如果Google只索引拼写正确、语法完美的英文网页。或者如果福特汽车制造一辆只能在晴天崭新道路上行驶的汽车。 - Peter Recore

Answer 1

关键在于你的数据无法适应内存。您可以使用外部排序算法：

将文件划分为多个适合内存的小块。对每个块进行排序，消除重复项（现在相邻元素）。

合并块并再次消除重复项。由于这里有n路合并，因此您可以在内存中保留来自每个块的下一个k个元素，一旦某个块的项目用尽（它们已经合并），则从磁盘抓取更多项目。

- BrokenGlass

---

不要使用固定大小的批次，继续读取，直到看到足够数量的唯一行以使字典增长到一定容量，然后将其作为排序批次写出以进行外部合并。请参见我的回答https://dev59.com/gY_ea4cB1Zd3GeqPIwnA#32537772。只想要重复项意味着您可以优化合并阶段，一旦您将批次数量合并到足以在一个宽度足够的合并中查看*所有*排序批次的点。 - Peter Cordes

Answer 2

我不确定你是否会考虑在Java之外实现这个功能，但如果可以，使用shell非常简单：

cat file | sort | uniq

- Michael

---

@augurar：OP 询问如何找到重复的条目，而不是唯一化输出。sort file | uniq --repeated（也称为 uniq -d）。Michael：永远不要写 cat file | something，那只是愚蠢的行为，与 something < file（或 something file，如果结果相同）相比，浪费 CPU 时间和内存带宽。 - Peter Cordes

@PeterCordes 是的，我的评论只涉及到这个答案。 - augurar

Answer 3

您可能无法一次加载整个文件，但是可以将哈希值和行号存储在HashSet中，没有问题。

伪代码...

for line in file
    entries.put(line.hashCode, line-number)
for entry in entries
    if entry.lineNumbers > 1
         fetch each line by line number and compare

- Andrew White

---

或者存储一组MD5或SHA1哈希行的字典，并假设非相同行不会发生冲突。当该哈希的计数从1变为2时，打印刚刚哈希的输入行。输出将是所有重复行的一个副本。如果确实需要存储某些内容的行号，请存储字节偏移量。文本文件无法通过行号进行随机访问，因为它们的长度是可变的，没有映射。 - Peter Cordes

如果要为键的哈希值存储某些内容，我会选择一些可以快速访问键的东西，比如RandomAccessFile.seek()的偏移量。 - greybeard

Answer 4

我认为您不需要对数据进行排序以消除重复项。只需使用快速排序的方法即可。

1. 从数据中挑选k个枢轴（除非您的数据真的很奇怪，否则这应该相当简单）
2. 使用这些k个枢轴将数据分成k+1个小文件
3. 如果其中任何一个块太大而无法适合内存，请针对该块重复该过程。
4. 一旦您有可管理的大小块，只需应用您喜欢的方法（哈希？）来查找重复项

请注意，k可以等于1。

- ElKamina

---

因此，步骤1和2实际上是：选择k个元素并对它们进行排序。遍历文件：对于每一行，二分搜索您的枢轴数组，并将该行写入桶“i”，其中pivot[i-1] < line < pivot[i]。如果您的字符串具有相当均匀的第一个或两个字符分布，则使用前一个或两个字符作为基数将输入散布到桶中要容易得多，而不是搜索枢轴列表。 - Peter Cordes

Answer 5

我能想象解决这个问题的一种方法是首先使用外部排序算法来对文件进行排序(搜索external sort java可以得到很多带有代码的结果)。然后，您可以逐行迭代文件，重复项现在显然会直接跟在彼此后面，所以您只需要在迭代时记住前一行即可。

- DarkDust

---

如果重复项不在相邻行中怎么办？ - hellodear

@hellodear：这里排序的目的是确保重复项在相邻行中。 - DarkDust

Answer 6

如果由于内存不足而无法建立完整的列表，则可以尝试循环操作。例如，创建一个哈希表，但仅存储一小部分项（例如以A开头的项）。然后，您收集重复项，然后继续使用“B”等内容。

当然，您可以选择任何类型的“分组”（即前3个字符，前6个字符等）。

这只会需要（许多）更多的迭代。

- Michel Keijzers

Answer 7

如果你愿意接受一定的统计误差，可以尝试使用布隆过滤器。Guava提供了一个，但目前存在一个相当严重的错误，预计下周将在11.0.2版本中修复。

- Louis Wasserman

---

那也是我的答案。假阳性可以在第二阶段消除（候选列表的大小会小得多）。 - Victor P.

Answer 8

#!/bin/bash

# This script will sort a file and remove duplicates
# It will use external merge sort to do this
# It will use a temporary directory to store the sorted chunks
# It will use a temporary directory to store the merged chunks
# It will use a temporary directory to store the final sorted file

# The script will take the following parameters
# $1 - The file to sort
# $2 - The number of lines to sort in each chunk
# $3 - The number of chunks to merge at a time
# $4 - The temporary directory to use

# The script will output the sorted file to stdout

# The script will return 0 on success
# The script will return 1 if the file does not exist
# The script will return 2 if the temporary directory does not exist

# Check that the file exists
if [ ! -f "$1" ]; then
    echo "The file $1 does not exist"
    exit 1
fi

# Check that the temporary directory exists
if [ ! -d "$4" ]; then
    echo "The temporary directory $4 does not exist"
    exit 2
fi

# Create a temporary directory to store the sorted chunks
chunk_dir="$4/chunks"
mkdir -p "$chunk_dir"

# Create a temporary directory to store the merged chunks
merge_dir="$4/merge"
mkdir -p "$merge_dir"

# Create a temporary directory to store the final sorted file
sort_dir="$4/sort"
mkdir -p "$sort_dir"

# Split the file into chunks
split -l "$2" "$1" "$chunk_dir/chunk"

# Sort each chunk
for chunk in "$chunk_dir"/chunk*; do
    sort "$chunk" > "$chunk.sorted"
done

# Merge the chunks
while [ $(ls "$chunk_dir" | wc -l) -gt 0 ]; do
    # Merge the first $3 chunks
    merge_chunks=""
    for i in $(seq 1 "$3"); do
        chunk=$(ls "$chunk_dir" | head -n 1)
        merge_chunks="$merge_chunks $chunk_dir/$chunk"
        rm "$chunk_dir/$chunk"
    done
    merge_file="$merge_dir/merge$(date +%s%N)"
    sort -m "$merge_chunks" > "$merge_file"
    # Remove duplicates from the merged file
    uniq "$merge_file" > "$merge_file.uniq"
    mv "$merge_file.uniq" "$merge_file"
    # Move the merged file to the chunk directory
    mv "$merge_file" "$chunk_dir"
done

# Move the final sorted file to the sort directory
mv "$chunk_dir"/* "$sort_dir"

# Output the sorted file to stdout
cat "$sort_dir"/*

# Remove the temporary directories
rm -rf "$chunk_dir"
rm -rf "$merge_dir"
rm -rf "$sort_dir"

- Mike

---

这个回答解决了什么问题？它有何改进，以回答如何避免java.lang.OutOfMemoryError的问题，是否比Michael的回答更好？ - greybeard

你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心中找到有关如何编写良好答案的更多信息。 - Community

Answer 9

关键是你的数据无法放入内存。(BrokenGlass)
如果有足够的内存来存储key哈希值到某个东西的Map，比如RandomAccessFile.seek()的偏移量或像Andrew White建议的行号，您可以在识别出非唯一键时处理它们。

否则，在第一遍中建立哈希值到“可能之前见过”的映射(例如，使用key.hashCode() % (3<<23)索引的3MB位图)，在第二遍中仅处理至少命中两次的桶中的键。

- greybeard