Очистка удваивается из массивного списка слов

Question

Я получил список слов, который составляет 56 ГБ, и я хотел бы удалить двойные.Я пытался приблизиться к этому в Java, но у меня не хватает места на моем ноутбуке после 2,5 млн слов.Поэтому я ищу (онлайн) программу или алгоритм, который позволил бы мне удалить все дубликаты.

Заранее спасибо, сэр Тролль

edit: то, что я делал в java, было помещенов TreeSet, чтобы они были упорядочены и удалены из дубликата

Answer 1

Фреймворки, такие как Mapreduce или Hadoop, идеально подходят для таких задач.Вам нужно будет написать свою собственную карту и уменьшить количество функций.Хотя я уверен, что это должно быть сделано раньше.Быстрый поиск по stackoverflow дал this

Answer 2

Я думаю, что проблема здесь в огромном количестве данных.На первом шаге я бы попытался разбить данные на несколько файлов: например, создать файл для каждого символа, например, где вы помещаете слова с первым символом, обозначенным «a», в a.txt, первый символ равен «b» в b.txt.,...

• a.txt
• b.txt
• c.txt -

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

если файлы остаются большими, вы также можете разделить их, используя более 1 символа, например:

• aa.txt
• ab.txt
• ac.txt
• ...

Answer 3

Я предлагаю вам использовать Фильтр Блума для этого.

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

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

Answer 4

Мне действительно нравятся комментарии «разделяй и властвуй», но я должен признать: если у вас возникли проблемы с 2,5 млн слов, что-то идет не так с вашим первоначальным подходом.Даже если мы предположим, что каждое слово является уникальным в пределах этих 2,5 миллионов (что в основном исключает то, что мы говорим о тексте на естественном языке), и предположим, что каждое слово в среднем имеет длину 100 символов Юникода, мы находимся на 500 МБ для храненияуникальные строки плюс некоторые накладные расходы на хранение заданной структуры.Значение: у вас должно быть все в порядке, поскольку эти цифры уже полностью завышены.Может быть, перед установкой Hadoop вы можете попробовать увеличить размер кучи?