Найти дубликаты в большом файле

Question

У меня действительно большой файл с приблизительно 15 миллионами записей.Каждая строка в файле содержит одну строку (назовите ее ключом).

Мне нужно найти повторяющиеся записи в файле, используя Java.Я пытался использовать хэш-карту и обнаруживать дубликаты записей.Видимо, такой подход приводит к ошибке «java.lang.OutOfMemoryError: Java heap space».

Как мне решить эту проблему?

Я думаю, что мог бы увеличить пространство кучи и попробовать его, но я хотел знать, есть ли более эффективные решения без необходимости настраивать пространство кучи.

Answer 1

Ключ в том, что ваши данные не поместятся в память.Вы можете использовать внешнюю сортировку слиянием для этого:

Разделите ваш файл на несколько более мелких кусков, которые помещаются в память.Сортируйте каждый фрагмент, устраняйте дубликаты (теперь соседние элементы).

Объединяйте фрагменты и снова удаляйте дубликаты при объединении.Так как здесь у вас будет n-nway слияние, вы можете сохранить следующие k элементов из каждого блока в памяти, как только элементы для блока будут исчерпаны (они уже были объединены), получить больше с диска.

Answer 2

Я не уверен, что вы подумаете сделать это вне Java, но если это так, это очень просто в оболочке:

cat file | sort | uniq

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

Answer 4

Не думаю, что вам нужно сортировать данные для устранения дубликатов. Просто используйте подход, основанный на быстрой сортировке.

1. Выберите k опорных точек из данных (если ваши данные не очень дурацкие, это должно быть довольно просто)
2. Используя эти k стержней, разделите данные на k + 1 маленьких файлов
3. Если какой-либо из этих блоков слишком велик, чтобы поместиться в памяти, повторите процесс только для этого блока
4. Если у вас есть чанки управляемого размера, просто примените ваш любимый метод (хеширование?), Чтобы найти дубликаты

Обратите внимание, что k может быть равно 1.

Answer 5

Один из способов решения этой проблемы, который я могу себе представить, заключается в том, чтобы сначала использовать алгоритм внешней сортировки для сортировки файла (поиск external sort java дает множество результатов с кодом). Затем вы можете перебирать файл построчно, теперь дубликаты, очевидно, будут непосредственно следовать друг за другом, поэтому вам нужно будет помнить только предыдущую строку при переборе.

Answer 6

Если вы не можете создать полный список, так как у вас недостаточно памяти, вы можете попробовать сделать это циклично.Т.е. создать хэш-карту, но хранить только небольшую часть элементов (например, те, которые начинаются с буквы A).Затем вы собираете дубликаты, затем продолжаете с «B» и т. Д.

Конечно, вы можете выбрать любой тип «группировки» (т. Е. Первые 3 символа, первые 6 и т. Д.).

Это толькозаймет (много) больше итераций.

Answer 7

Вы можете попробовать Фильтр Блума , если вы готовы принять определенное количество статистических ошибок.Guava предоставляет один, но в нем сейчас есть довольно серьезная ошибка, которая должна быть исправлена, вероятно, на следующей неделе с выпуском 11.0.2.