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

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

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

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

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

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

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

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

Ознакомьтесь с этой статьей:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы не беспокоиться о реализации, вам следует использовать систему баз данных, будь то простой старый реляционный 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. Согласно эмпирическому закону Zpif все должно быть в порядке.

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

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

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

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

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