Эффективные методы для поиска наиболее распространенных фраз в тексте AKA трендовые темы - PullRequest
Новая
       17

Эффективные методы для поиска наиболее распространенных фраз в тексте AKA трендовые темы

4 голосов
/ 27 июля 2010

Ранее я задавал аналогичный вопрос по этой теме, в итоге я получил несколько решений, которые работали, одно на основе фильтров Блума + ngrams, другое на основе хеш-таблиц + ngrams.Оба решения хорошо работают с небольшими наборами данных (<1000 текстов, обычно твитов), но время вычислений экспоненциально выросло, что означает, что выполнение 10000 может занять часы. </p>

В настоящее время я работаю в Ruby и, возможно, это проблема, ноЕсть ли другие решения или подходы, которые я мог бы попытаться решить эту проблему?

Ответы [ 2 ]

1 голос
/ 28 июля 2010

Если вы ищете для поиска текста в больших наборах данных, вам может понадобиться что-то вроде solr.Существует действительно простой в настройке solr gem, который называется sunspot http://outoftime.github.com/sunspot/

.
0 голосов
/ 17 марта 2014

Ваша проблема может быть решена с помощью следующих действий:

  • (Необязательно, для повышения производительности). Просмотрите все документы, создайте отображение между уникальным словом и целым числом. Также лучше создать специальное отображение для завершения предложения (.!? И т. Д.). Это облегчает проверку фраз, которые не пересекают границы предложения.
  • Объединить все документы в огромный массив отображенных целых чисел (на предыдущем шаге). Это можно сделать в режиме онлайн (чтобы сэкономить место), когда мы пройдем следующие шаги.
  • Построение массива суффиксов строки на предыдущем шаге, дополненного самым длинным массивом общих префиксов . Самая быстрая из известных реализаций - это SA-IS, которая работает за O (n) наихудшее время. Смотрите здесь . Требуется некоторая специальная обработка, чтобы убедиться, что каждый общий префикс не пересекает границу предложения.
  • Массив LCP - это в основном нужный вам результат. Вы можете делать с ним все, что захотите, например: сортировать его, чтобы найти самые длинные повторяющиеся фразы среди документов, найти все 5-словные, 4-словные, 3-словосочетания и т. Д. Наиболее распространенные фразы (я предполагаю, по крайней мере, 2 ключевые слова здесь) можно найти, взглянув как на LCP, так и на массив суффиксов.

Быстрый поиск в Google показывает, что эта библиотека содержит реализацию массива суффиксов Ruby. Вы можете создать массив LCP оттуда в O (n) Reference .

...