Поиск популярных ключевых слов в огромном списке

Question

У меня есть огромный список с примерно 100 000 строк, таких как:

• ipadnews
• abcipad
• cddeeffipad
• адский мир
• iworldthis .. и так далее

И хотел бы найти популярные подстроки, в этом случае «ipad» будет самым популярным, а «world» будет на втором месте.Минимальная длина должна составлять три или четыре символа.

Я не могу предсказать подстроки, поэтому использование словаря - нет, нет.

Answer 1

Это довольно сложная проблема ... но ее можно использовать с деревьями префиксов / суффиксов. По сути, это вариация проблем самая длинная общая подпоследовательность и самая длинная общая подстрока . - это то, где я бы начал.

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

Answer 2

Вы можете решить эту проблему, используя обобщенное суффиксное дерево , которое может быть построено за O(n) время.Это фактически игра на проблему LCS .

Answer 3

Я бы решил эту проблему, используя следующий поток логики:

1. Извлечение набора суффиксов для каждого слова.Итак, из «ipadnews» мы получаем: «ipadnews», «padnews», «adnews» и так далее.Таким образом, «news» будет одним из суффиксов, но не «ipad».

2. Чтобы восполнить отсутствующие подстроки на предыдущем шаге, также извлеките префиксы.Мы получаем «ipadnew», «ipadne» и т. Д., Включая «ipad».

3. Для каждой из приведенных выше подстрок хешируем их в счетчик, например $ hash {$ substr} ++.

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

Максимальное количествоКлючи в хеш-таблице будут 2 * k * n, где k - средняя длина слов, а n - общее количество слов.