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

Ответ 1

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

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

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

Ответ 6

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

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

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

Ответ 7

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

Ответ 8

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

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

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

Ответ 9

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

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

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

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

Ответ 10

Чтобы не беспокоиться о реализации, вы должны использовать систему баз данных, либо простой старый реляционный SQL, либо решение No-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 не разработан таким образом?

Ответ 11

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

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

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

Ответ 12

Quicksort будет хорошим вариантом для Mergesort в этом случае, потому что ему требуется меньше памяти. Этот поток имеет хорошее объяснение, почему.

Ответ 13

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

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

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