Наиболее часто встречающиеся слова в терабайте данных

Question

Я столкнулся с проблемой, в которой мы должны найти самые 10 частых слов в терабайте файла или строки.

Одним из решений, которое я мог бы подумать, было использование хеш-таблицы (слово, счет) вместе с максимальной кучей. Но при установке всех слов, если слова уникальны, может возникнуть проблема. Я думал о другом решении, используя Map-Reduce, разбивая куски на разных узлах. Другим решением будет создание Trie для всех слов и обновление количества каждого слова при сканировании файла или строки.

Какой из вышеперечисленных вариантов был бы лучшим решением? Я думаю, что первое решение довольно наивно.

Answer 1

Лучшее, что я мог думать:

1. Сплит данных частей, которые можно хранить в памяти.
2. Для каждой части получите N наиболее часто встречающиеся слова, вы получите N * partsNumber слов.
3. Прочтите все данные, снова считая слова, которые вы получили раньше.

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

Answer 2

Разделите имеющуюся память на две половины. Используйте один из них как 4-разрядный counting Bloom filter, а второй - как хэш-таблицу фиксированного размера с подсчетами. Роль счетного фильтра Блума заключается в отфильтровании редко встречающихся слов с высокой эффективностью памяти.

Проверьте свои 1 ТБ слов относительно первоначально пустого фильтра Блума; если слово уже включено и все ведра установлены на максимальное значение 15 (это может быть частично или полностью ложным положительным), пропустите его. Если это не так, добавьте его.

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

Когда первый проход завершен, вы можете исправить неточность со вторым проходом, если это необходимо. Освободите фильтр Bloom, освободите также все подсчеты, которые не входят в 15 случаев за десятым наиболее частым словом. Пройдите через вход снова, на этот раз точно подсчитывая слова (используя отдельную хеш-таблицу), но игнорируя слова, которые не были сохранены в качестве приблизительных победителей с первого прохода.

Примечание

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

Обратите внимание, что ширина ковша (4 бита в приведенном выше описании) является лишь параметром конструкции. Не считая фильтра Bloom (ширина ковша 1) будет красиво отбирать самые уникальные слова, но ничего не делать, чтобы отфильтровывать другие очень редко встречающиеся слова. Более широкий размер ковша будет более подвержен перекрестному разговору между словами (потому что будет меньше ковшей), а также уменьшит гарантированный уровень точности после первого прохода (15 случаев в случае 4 бит).Но эти недостатки будут в количественном отношении незначительными до некоторой степени, в то время как я представляю, что более агрессивный фильтрующий эффект является абсолютно решающим для сохранения хэш-таблицы в размерах до гигабайта с неповторяющимися данными естественного языка.

Что касается порядка памяти для самого фильтра Блума; these people работают ниже 100 МБ и имеют гораздо более сложное приложение («полная» статистика n-грамм, а не пороговая статистика в 1 грамм).

Answer 3

Сортировка терабайтного файла в алфавитном порядке с помощью mergesort. В начальном проходе используйте быструю сортировку с использованием всей доступной физической памяти для предварительной сортировки длинных строк слов.

При этом представляйте непрерывную последовательность одинаковых слов одним одним словом и числом. (То есть вы добавляете подсчеты во время слияний.)

Затем приложите файл, снова используя mergesort с быстрым сортированием сортировки, но на этот раз по графам, а не по алфавиту.

Это медленнее, но проще реализовать, чем мой другой ответ.