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

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

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

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

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

источник

2012-02-09 Maximus

Offtopic: Как вы получили 15 миллионов записей в первую очередь? – Mob

Хорошим способом работы должно быть отсутствие дубликатов. Не должно быть необходимости в удалении дубликатов. –

@Martijn Courteaux: Вы не знаете, какие данные это. Например, если у вас есть книга и вы хотите знать, какие слова используются в книге, нет способа избежать дубликатов, таких как 'the' в первую очередь. – DarkDust

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

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

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

источник

2012-02-09 17:38:26 BrokenGlass

Вместо партий фиксированного размера продолжайте читать, пока не увидите достаточно уникальных линий, чтобы увеличить свой словарь до определенной емкости, а затем напишите это как отсортированную партию для внешнего слияния. См. Мой ответ на http://stackoverflow.com/questions/32535222/memory-constrained-external-sorting-of-strings-with-duplicates-combinedcounted/32537772#32537772. Желание только дубликатов означает, что вы можете значительно оптимизировать этап слияния, как только вы объединили количество партий до точки, где вы можете видеть * все * отсортированные партии в одном достаточно широком слиянии. –

Возможно, вы не можете загрузить весь файл за один раз, но вы можете сохранить хэш и номер строки в 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

источник

2012-02-09 17:40:39

Или сохраните словарь хешей линий MD5 или SHA1 и предположите, что не будет конфликтов для неидентичных линий. Когда счетчик для этого хэша идет от 1 до 2, напечатайте только что введенную строку ввода. Вывод будет одним экземпляром каждой строки, которая была дублирована. Если вам нужно сохранить номера строк для чего-то, вместо этого храните байтовые смещения. Текстовые файлы не могут быть произвольно доступны по номеру строки, поскольку они являются переменной длиной и нет карты. –

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

источник

2012-02-09 17:41:26 DarkDust

Что делать, если дубликаты не находятся в соседних строках? – hellodear

@hellodear: точка _sorting_ здесь заключается в том, чтобы дублировать _are_ в смежных строках. – DarkDust

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

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

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

источник

2012-02-09 17:42:00

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

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

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

источник

2012-02-09 18:26:51 ElKamina

Итак, шаги 1 и 2 действительно: выберите k элементов и отсортируйте их. Прочитайте файл: для каждой строки, двоичный поиск вашего сводного массива и запись строки в bucket 'i', где' pivot [i-1] <строка

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

cat file | sort | uniq

источник

2012-02-09 19:12:41 Michael

Или 'sort -u <файл' – augurar

@augurar: ОП задал вопрос о том, какие записи дублируются, а не однозначный вывод. 'sort file | uniq --repeated' (aka 'uniq -d'). Майкл: Никогда не пишите 'cat file | что-то », это просто глупо и трата времени процессора и пропускной способности памяти по сравнению с' something

@PeterCordes Правда, мой комментарий просто касался этого ответа. – augurar

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

источник

2012-02-09 22:38:54

Это тоже мой ответ. Фальшивые положительные результаты можно было бы исключить на второй фазе (размер списка кандидатов будет намного меньше) –

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

ответ

Смежные вопросы