Поиск похожих строк

[yevhen...@gmail.com]

Комрады!!!
Нужно найти в куче разных текстов
строки (2 и больше слов подряд) которые
повторяются.

пример:
text1:
This is a test text.

text2:
This is another test text.

text2:
What do you think about this test text.

Результат сколько и в каких текстах
встречается такая фраза:
"test text" - 3 (1,2,3)
"This is" - 2 (1,2)

Задача не теоретическая, а вполне
практическая. Размеры текстов большие
+/- 400 тыс. (20 гиг.) и поиск нужно делать
довольно часто (несколько раз в день).
интересует аглоритм разбора/поиска.

[Nikolay Gorylenko]

Посмотри здесь: http://algolist.manual.ru/search/index.php

[Timofey Kolesnik]

Попробуй регулярные выражения. Это
самое мощное средство для работы с
текстом.

[Mike Gorchak]

Hello, yevhen...@gmail.com!

ym> Задача не теоретическая, а вполне
ym> практическая. Размеры текстов большие
ym> +/- 400 тыс. (20 гиг.) и поиск нужно делать
ym> довольно часто (несколько раз в день).
ym> интересует аглоритм разбора/поиска.

1) Каждому слову присваивается свой численный идентификатор (лучше хеш n
бит, n приблизительно равно 32-64 бита). Весь текст преобразуется в массив
идентификаторов. Сами идентификаторы - это словарь.

2) Весь текст, по которому будет идти поиск преобразуется в массив
идентификаторов (произойдет небольшая компрессия текстов). Для каждого
текста составляется массив присутствующих идентификаторов.

3) При поиске, строка поиска преобразуется в массив идентификаторов, если
один из этих идентификаторов не присутствует в словаре, то искомой
последовательности в тексте нет. Далее проверяется каждый текст на
присутствие всех идентификаторов строки поиска. Если хоть одного нет, текст
пропускается.

4) Если присутствуют все идентификаторы поиска в массиве идентификаторов
присутствия для каждого текста, то производится их поиск в массиве
идентификаторов самого текста.

Естественно все доступы к словарям, поиск подстрок в строке (из пункта 4)
организовываются быстрыми алгоритмами с постоянным временем поиска.

P.S. можно посмотреть тут: http://goog-sparsehash.sourceforge.net/ очень
шикарную имплементацию мап'ов и хешей от гугля на C++. Всё под BSD
лицензией.

With best regards, Mike Gorchak. E-mail: mi...@malva.ua

[yevhen...@gmail.com]

Не согласен.
Для таких масивных текстов - регулярка
даст ОГРОМНЫЕ тормоза.

[yevhen...@gmail.com]

Nikolay Gorylenko написав:

Как раз курю :)

[Max Ischenko]

> ym> Задача не теоретическая, а вполне
> ym> практическая. Размеры текстов большие
> ym> +/- 400 тыс. (20 гиг.) и поиск нужно делать
> ym> довольно часто (несколько раз в день).
> ym> интересует аглоритм разбора/поиска.

...

> Естественно все доступы к словарям, поиск подстрок в строке (из пункта 4)
> организовываются быстрыми алгоритмами с постоянным временем поиска.

А не проще ли взять какой-нибудь Lucene или PyLucene? Или на худой конец загнать в MySQL-базу с FULLEXT индексом.

[Andrey Kolyadenko]

Вот в википедии локанично описано:
http://en.wikipedia.org/wiki/Inverted_index

On 8/16/06, Andrey Kolyadenko <akoly...@gmail.com> wrote:

Думаю что на этапе предобработки текста нужно создать поисковые индексы на базе инвертированных файлов и потом юзать их как это делают поисковики:
http://www.google.com/search?q=inverted+files

[Andrey Kolyadenko]

Думаю что на этапе предобработки текста нужно создать поисковые индексы на базе инвертированных файлов и потом юзать их как это делают поисковики:
http://www.google.com/search?q=inverted+files

On 8/16/06, Nikolay Gorylenko <n0...@ukr.net> wrote:

[Andrey Kolyadenko]

К сожалению на 20 гигах любой рег експ инжайн загнется.

[Andrey Kolyadenko]

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

[Andrey Kolyadenko]

Кстати да, и еще в догонку куча ссылок: http://www.searchtools.com/tools/tools-opensource.html

[yevhen...@gmail.com]

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

[Andrey Kolyadenko]

То есть на вход программы попадает набор текстов а ей на выходе нужно выдать ВСЕ строки которые повторяются хотя бы два раза? Или исходную строку в каком то виде все таки задает пользователь программы?

On 8/16/06, yevhen...@gmail.com <yevhen...@gmail.com> wrote:

[yevhen...@gmail.com]

Andrey Kolyadenko написав:

Именно, искомых подстрок нет в начале,
их нужно определять.

[Andrey Kolyadenko]

Ну я думаю что тогда адгоритм будет следующий:
Загнать в какой нибудь search engine тексты. А потом опять проходить по текстам, выделять фразы, и искать их используя search engine, если они где то еще встречаются то анализировать результаты запроса, и вытаскивать из них нужную статистику. Ну и понятно что желательно уже обработанные фразы где то хранить, что бы повторно не обрабатывать. Алгоритм видимо близок к линейному относительно количества фраз и лучше не придумаешь скорее всего(конечно с поправкой на правильность реализации search engine).
Но мне кажеться что на 20 гигах это может занять очень много времени!

[Nikolay Gorylenko]

Строите собственный http://www.copyscape.com/ ?

On 8/17/06, yevhen...@gmail.com <yevhen...@gmail.com> wrote:

[...]

[yevhen...@gmail.com]

Nikolay Gorylenko написав:

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

[Nikolay Gorylenko]

Я ссылку привёл к тому, что возможно покупка готового решения
обойдётся дешевле разработки собственного.
Хотя олимпийцам, думаю, будет стыдно покупать
чужие программы для обработки строк :)

[Yevhen Moroz]

Nikolay Gorylenko написав:

типа того :)
ну и если чесно интересен алгоритм
таких систем. Да и покупать думаю никто
не согласится, стыдно, что сами не
сможем реализовать :)

[Segrey Druzkin]

Стартап от алгоритма шинглов (shingles algorithm)