Найти наиболее повторяющуюся фразу на огромном тексте

У меня огромные текстовые данные. Вся моя база данных - это текстовый формат в UTF-8

Мне нужно иметь список самых повторяющихся фраз для всех моих текстовых данных.

Например, мое желание выводит что-то вроде этого:

{
  'a': 423412341,
  'this': 423412341,
  'is': 322472341,
  'this is': 222472341,
  'this is a': 122472341,
  'this is a my': 5235634
}

Обработать и сохранить каждую фразу за большой размер базы данных. Например, хранить в MySQL или MongoDB. Вопрос: есть ли более эффективная база данных или алгорифм для поиска этого результата? Solr, Elasticsearch и т.д.

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

Ответ 1

Я бы предложил объединить идеи из двух полей: Streaming Algorithms и Алгоритм Apriori из анализа рыночной корзины.

Давайте начнем с проблемы поиска k наиболее частых одиночных слов без загрузки всего корпуса в память. Очень простой алгоритм Выборка (см. Поиск частых элементов в потоках данных]), может сделать это очень легко. Более того, он очень поддается параллельной реализации (описано ниже). Существует множество работ по top-k-запросам, в том числе в распределенных версиях (см., Например, Эффективное вычисление запросов Top-K в распределенных сетях).
Теперь к проблеме k наиболее часто встречающихся фраз (возможно, нескольких фраз). Очевидно, что наиболее частые фразы длины l + 1 должны содержать наиболее часто встречающиеся фразы длины l в качестве префикса, поскольку добавление слова к фразе не может увеличить ее популярность. Следовательно, как только у вас есть k наиболее частых одиночных слов, вы можете сканировать корпус только для них (что быстрее) для создания наиболее часто встречающихся фраз длины 2. Используя это, вы можете построить наиболее часто используемые фразы длины 3 и скоро. Условием остановки является то, что фраза длины l + 1 не выдает никакой фразы длины l.

Краткое описание алгоритма выборки

Это очень простой алгоритм, который с большой вероятностью найдет верхние k элементов из тех, которые имеют частоту не менее f. Он работает в два этапа: первый находит элементы-кандидаты, а второй подсчитывает их.

На первом этапе произвольно выбирайте слова ~ log (n)/f из корпуса (обратите внимание, что это намного меньше n). С большой вероятностью все нужные слова появляются в наборе этих слов.

На втором этапе поддерживайте словарь отсчетов этих элементов-кандидатов; сканировать корпус и подсчитывать вхождения.

Выведите верхний k элементов, полученных на втором этапе.

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

Ответ 2

Если вы можете сохранить данные в Apache Solr, тогда Luke Обработчик запросов можно использовать для поиска наиболее распространенных фраз. Пример запроса:

http://127.0.0.1:8983/solr/admin/luke?fl=fulltext&numTerms=100

Кроме того, Компонент терминов может помочь найти наиболее распространенные отдельные слова. Ниже приведена статья о Self Updating Solr Stopwords, которая использует Компонент терминов, чтобы найти 100 наиболее распространенных проиндексированных слов и добавить их в файл Stopwords. Пример запроса:

http://127.0.0.1:8983/solr/terms?terms.fl=fulltext&terms.limit=100

Ответ 3

Считаете ли вы использование MapReduce?

Предполагая, что у вас есть доступ к соответствующей инфраструктуре, это, по-видимому, подходит для этого. Вам понадобится токенизатор, который разбивает строки на многословные токены до 10 слов. Я не думаю, что это очень важно. Результатом задания MR будет пара token -> frequency, которую вы можете передать другому заданию для сортировки по частотам (один вариант). Я бы посоветовал прочитать Hadoop/MapReduce перед рассмотрением других решений. Вы также можете использовать HBase для хранения любых промежуточных выходов.

Оригинальная бумага на MapReduce от Google.

Ответ 4

tokenize от 1 до 10 слов и вставить в 10 таблиц SQL по длинам токенов. Обязательно используйте хэш-индекс в столбце со строковыми токенами. Затем просто вызовите SELECT token,COUNT(*) FROM tablename GROUP BY token в каждой таблице и дамп-результаты где-нибудь и подождите.

EDIT: это было бы недопустимо для больших наборов данных, только для каждого N-грамма обновляйте счет на +1 или вставляйте новую строку в таблицу (в MYSQL будет полезен запрос INSERT...ON DUPLICATE KEY UPDATE). Тем не менее, вы все равно должны использовать хэш-индексы.

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

С осторожностью относитесь к эвристическим методам, предложенным Ами Тавори, если вы выберете неправильные параметры, вы можете получить неправильные результаты (недостаток алгоритма выборки можно увидеть на некоторых классических терминах или фразах - например, "habeas corpus" - ни habeas, ни corpus будет выбрана как частая сама по себе, но в виде слова из 2-х слов она может значительно превышать некоторые фразы, которые вы получаете, добавляя/добавляя к общему слову). Разумеется, нет необходимости использовать их для токенов меньшей длины, вы можете использовать их только тогда, когда классические методы терпят неудачу (занимают слишком много времени или памяти).

Ответ 5

Это может быть значительно упрощено. Вам вообще не нужна база данных. Просто сохраните полный текст в файле. Затем напишите PHP script, чтобы открыть и прочитать содержимое файла. Используйте функцию регулярного выражения PHP для извлечения совпадений. Держите общее число в глобальной переменной. Запишите результаты в другой файл. Это.