Как удалить повторяющиеся слова, используя Java, если их больше 200 миллионов?

Question

У меня есть файл (размер = ~1,9 ГБ), который содержит ~220 000 000 (~220 миллионов) слов / строк. У них есть дублирование, почти 1 дублированное слово на каждые 100 слов.

Во второй программе я хочу прочитать файл. Я успешно читать файл по строкам, используя BufferedReader.

Теперь для удаления дубликатов мы можем использовать Set (и его реализации), но у Set есть проблемы, как описано ниже в 3 различных сценариях:

1. При размере JVM по умолчанию Set может содержать до 0,7–0,8 миллиона слов, а затем OutOfMemoryError.
2. С размером 512M JVM Set может содержать до 5-6 миллионов слов, а затем ошибка OOM.
3. С размером 1024M JVM Set может содержать до 12-13 миллионов слов, а затем ошибка OOM. Здесь после добавления 10 миллионов записей в Set операции становятся чрезвычайно медленными. Например, добавление следующих ~4000 записей заняло 60 секунд.

У меня есть ограничения, которые я не могу увеличить размер JVM дальше, и я хочу удалить дубликаты слов из файла.

Пожалуйста, дайте мне знать, если у вас есть какие-либо идеи о каких-либо других способах / способах удаления повторяющихся слов с использованием Java из такого гигантского файла. Большое спасибо:)

Добавление информации к вопросу: Мои слова в основном буквенно-цифровые и являются уникальными в нашей системе идентификаторами. Следовательно, они не простые английские слова.

Answer 1

Используйте сортировку слиянием и удалите дубликаты за второй проход. Вы можете даже удалить дубликаты при объединении (просто сохраните последнее слово, добавленное к выводу в ОЗУ, и сравните с ним и кандидатов).

Answer 2

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

Обработайте каждый из файлов письма отдельно, используя Set удалить дубликаты.

Answer 3

Возможно, вы сможете использовать структуру данных Trie для выполнения работы за один проход. У этого есть преимущества, которые рекомендуют это для этого типа проблемы. Поиск и вставка выполняются быстро. И его представление относительно компактно. Вы можете быть в состоянии представить все свои слова в оперативной памяти.

Answer 4

Если вы сортируете элементы, дубликаты будет легко обнаружить и удалить, так как дубликаты будут сгруппированы вместе.

Здесь есть код, который можно использовать для сортировки большого файла: http://www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

Answer 5

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

Answer 6

Вопрос: Это действительно СЛОВА или это что-то еще - фразы, номера деталей и т. Д.?

Что касается СЛОВ на обычном разговорном языке, можно ожидать, что после первых нескольких тысяч вы найдете большинство уникальных слов, поэтому все, что вам действительно нужно сделать, это прочитать слово, проверить его по словарю, если оно найдено, пропустить если он не найден, добавьте его в словарь и запишите.

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

Answer 7

Для больших файлов я стараюсь не считывать данные в память, а вместо этого оперирую файлом, отображенным в память, и позволяю странице OS вводить / выводить память по мере необходимости. Если ваши структуры множеств содержат смещения в этом отображенном в память файле вместо реальных строк, он будет занимать значительно меньше памяти.

Проверьте эту статью:

http://javarevisited.blogspot.com/2012/01/memorymapped-file-and-io-in-java.html

Answer 8

Одним из классических способов решения этой проблемы является фильтр Блума. Обычно вы хешируете свое слово несколько раз, и для каждого результата хеширования задайте несколько битов в битовом векторе. Если вы проверяете слово и все биты из его хэшей установлены в векторе, который вы, вероятно, (вы можете установить эту вероятность произвольно низкой, увеличив число хэшей / битов в векторе) видели его раньше, и это дубликат,

Так работали ранние программы проверки правописания. Они знали, есть ли слово в словаре, но они не могли сказать вам, каково было правильное написание, потому что оно только скажет вам, увидели ли вы текущее слово.

Существует множество реализаций с открытым исходным кодом, включая java-bloomfilter.

Answer 9

Даже в английском языке, который содержит огромное количество слов для естественного языка, верхние оценки составляют всего около 80000 слов. Исходя из этого, вы можете просто использовать HashSet и добавьте все свои слова (вероятно, в нижнем регистре, чтобы избежать проблем с регистром):

Set<String> words = new HashSet<String>();
while (read-next-word) {
    words.add(word.toLowerCase());
}

Если это настоящие слова, это не вызовет проблем с памятью, тоже будет довольно быстро!

Answer 10

Чтобы не беспокоиться о реализации, вы должны использовать систему баз данных, либо простой старый реляционный SQL, либо решение без SQL. Я уверен, что вы можете использовать, например, Berkeley DB Java Edition, а затем сделать (псевдокод)

for(word : stream) {
  if(!DB.exists(word)) {
     DB.put(word)
     outstream.add(word)
  }
}

Проблема по сути проста: вам нужно хранить вещи на диске, потому что не хватает памяти, а затем либо использовать сортировку O(N log N) (необязательно), либо хеширование O(N), чтобы найти уникальные слова.

Если вы хотите решение, которое, скорее всего, будет работать, но не гарантировано, используйте хеш-таблицу типа LRU. Согласно эмпирическому закону Зпифа, вы должны быть в порядке.

Последующий вопрос к какому-нибудь умному парню: что если у меня 64-битная машина и установлен размер кучи 12 ГБ, не должна ли виртуальная память решать проблему (хотя и не оптимальным образом) или java не предназначен сюда?

Answer 11

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

Вот что я имею в виду (в псевдокоде):

• Входные параметры: Offset, Size
• Выделите поисковую структуру размера Size знак равноSet, но не обязательно быть одним)
• Читать Offset (или EOF встречается) элементы из стандартного ввода и просто скопировать их в стандартный вывод
• Читать Size элементы из stdin (или EOF), сохраните их в Set. Если дубликат, отбросьте, иначе пишите в stdout.
• Чтение элементов из stdin до EOF, если они находятся в Set затем брось, иначе пиши в stdout

Теперь передайте столько экземпляров, сколько вам нужно (если с хранилищем проблем нет, может быть, столько, сколько у вас ядер) с увеличением Offsetс и вменяемый Size, Это позволяет вам использовать больше ядер, так как я подозреваю, что процесс связан с процессором. Вы даже можете использовать netcat и распределите обработку по большему количеству машин, если вы спешите.

Answer 12

В этом случае быстрая сортировка была бы хорошей опцией по сравнению с Mergesort, потому что она требует меньше памяти. В этой теме есть хорошее объяснение, почему.

Answer 13

Большинство эффективных решений возникают из-за пропусков ненужных вещей. Вы ищите только дубликаты, поэтому просто не храните слова сами, храните хэши. Но подождите, хэши вас тоже не интересуют, только если они уже были видны - не храните их. Относитесь к хешу как к действительно большому числу и используйте набор битов, чтобы увидеть, видели ли вы уже это число.

Таким образом, ваша проблема сводится к очень большому малонаселенному растровому изображению, размер которого зависит от ширины хеша. Если ваш хэш до 32 бит, вы можете использовать riak bitmap.

... ушел думать о действительно большом растровом изображении для 128+ битных хешей%) (я вернусь)