Считайте частоту слов огромного текстового файла

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

Мой подход:

1. Сортировка данного файла - внешний вид
2. Считайте частоту каждого слова последовательно, сохраните счет в другом файле (вместе со словом)
3. Сортировка выходного файла по частоте - внешняя сортировка.

Я хочу знать, есть ли лучшие подходы к этому. Я слышал о хэш-таблицах на основе дисков? или B +, но никогда не пробовали их раньше.

Примечание. Я видел похожие вопросы, заданные в SO, но ни один из них не должен решать проблему с данными, большими, чем память.

Изменить. Основываясь на комментариях, согласился, что словарь на практике должен вписываться в память современных компьютеров. Но давайте возьмем гипотетический словарь слов, который достаточно огромен, чтобы не вписываться в память.

Я бы пошел с подходом  `map` :

1. Распределите текстовый файл на узлах, предполагая, что каждый текст в узле может поместиться в ОЗУ.
2. Рассчитайте каждую частоту слов в узле. (используя хэш-таблицы )
3. Соберите каждый результат в главном узле и объедините все его.



Все уникальные слова, вероятно, вписываются в память, поэтому я бы использовал этот подход:

* Create a dictionary (`HashMap`).
* Read the huge text file line by line.
* Add new words into the dictionary and set value to 1.
* Add 1 to the value of existing words.

После того, как вы проанализировали весь огромный файл:

* Сортировка словаря по частоте.
* Напишите в новый файл отсортированный словарь со словами и частотой.

Имейте в виду, что для преобразования слов в строчные или прописные.



Лучший способ добиться этого - прочитать файл по строке и сохранить слова в Multimap (например,  [гуавы](https://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap) ). Если эта карта расширяет вашу память, вы можете попробовать использовать хранилище ключей (например, Berkeley JE DB или  [MapDB](https://github.com/jankotek/MapDB)  ). Эти хранилища с ключевыми значениями работают аналогично карте, но они сохраняют свои значения на жестком диске. Я использовал MapDB для аналогичной проблемы, и он быстро вспыхивал.



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

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