Хотел бы посоветоваться как сделать "нечеткий" поиск похожих кусков в тексте, может быть вы знаете как ее решить?

Начну с упрощенной версии задачи, допустим у нас есть книга Гарри Поттер 1, и мы хотим узнать частоту с которой каждое слово встречается в тексте и затем распечатать список слов в порядке убывания частоты. Это решается просто - разбиваем текст на массив слов, проходим по нему и при встрече очередного слова увеличиваем его счетчик, дальше сортируем по частоте и распечатываем, у нас получается такой файл:

the 3500
do 2500
and 1500
...

вобщем, все просто и понятно.

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

Сложности:

- Как определять что два куска текста похожи? Похожими считаются не только "a b c", "a b" но и более сложные, например "x a b c y", "x d y" (x и y, в начале и конце поожи, конкретный пример такого случая - "throw it out", "throw the credit card out")
- Как подсчитывать частоту? В случае слов все просто там либо 0 либо 1, а здесь получается функция "похожести" двух кусков выдаст что они похожи на 20% и нам в частоте приплюсовывать 0.2 ?
- Как разбивать текст на куски? В случае со словами сожность алгоритма простая - O(n) - идем по массиву и плюсуем. Но с фрагментами текста сложность получается сильно выше O(n^2)!

Расчет сложности: допустим у нас в книге всего 1000 слов (N), максимальный размер куска примем равным 10 словам, теперь считаем сколько нам нужно выполнить операций:
1. нам нужно построить массив из всевозможных кусков которые можно создать из текста, размерами от 1 до 10 слов. Таких кусков у нас будет примерно 10 * 1000 = 10^N (1000 однословных, 999 двухсловных, 998 трехсловных и т.д.).
2. нам нужно сравнить всех со всеми (10 * N)^2 = 100 * N^2 => O(n^2) операций сравнения.

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

Может быть вы знаете примеры где это уже реализовано или может ссылки на статьи где описано как это сделать и как это сделать более эффективно?

Попробую описать чуть по другому:

1 Простой случай - найти в тексте самые употребляемые слова и отсортировать их в порядке убывания.
2 Сложный случай - найти в тексте самые употребляемые структуры и отсортировать их в порядке убывания. По английски это вроде бы еще по другому называется text pattern recognition .

Ага, но архиваторы обычно не ищут сложные структуры, они только простой словарь делают, а мне нужен поиск именно сложных структур.

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

Сделал первую версию, https://github.com/alexeypetrushin/code_stats , пока что оч простой, считает только размер исходников. Например вот статистика по модулям Ruby on Rails



Описание http://ruby-lang.info/blog-ru/statistika-koda-i-zakon-parieto-pravilo-80-20-fyp

Вобщем, спасибо за советы, я понял как сделать нечеткий поиск, в седущей версии (недели через 2 наверно, мало своб времени) попробую реализовать его + еще одну интересную идею, интересно какие цифры получатся.