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

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

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

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

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

Ответы

Ответ 1

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

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

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

Ответ 2

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

cat file | sort | uniq

Ответ 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

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

Конечно, вы можете выбрать любую "группировку" (т.е. первые 3 символа, первые 6 и т.д.).

Это займет всего несколько итераций.

Ответ 7

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