найти повторное слово в бесконечном потоке слов

Question

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

Answer 1

Как и в случае большинства последовательных данных, здесь неплохо бы использовать trie. Используя trie, вы можете хранить новые слова очень экономично и при этом обязательно найдете новые слова. Попытки могут фактически рассматриваться как форма множественного хеширования слов. Если это все еще приводит к проблемам, потому что размер слов слишком велик, вы можете сделать его более эффективным, создав направленный ациклический граф слов *1002* (DAWG) из слов, чтобы уменьшить также общие суффиксы в качестве префиксов.

Answer 2

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

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

Answer 3

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

Хорошее описание: http://en.wikipedia.org/wiki/Bloom_filter.