Найти наиболее длинную подстроку

[gregzem]

Задача навеяна вот этой темой: Для просмотра ссылки Войди или Зарегистрируйся

Есть две строки, у которых встречаются общие фрагменты. Условно - две HTML страницы (по ~90Kb). Задача - найти эти подстроки.

Цитата из вышепреведенного топика.

Наиболее простой вариант видится следующим: необходимо проанализировать N страниц сайта. Из каждой страницы выкинуть повторяющиеся элементы (например, футер).

То есть находим наиболее длинный кусок текста, одинаковый в обеих страницах и выкидываем его. Затем следующий. И так далее, пока, скажем, не останется общий фрагмент длиной менее N байт (например, 10).

Написать, оказалось проще, чем реализовать.

Есть такой алгоритм - Для просмотра ссылки Войди или Зарегистрируйся. Он как раз и позволяет найти эту максимально-длинную подстроку.

И все бы ничего, но на поиск в двух подстроках размером по 90Kb выделяется двумерный массив в 7,5Gb. Что, имхо, многовато. C# на это сразу посылает.

Есть какие-нибудь идеи, как еще можно реализовать поиск наиболее длинной подстроки?

 

[gregzem]

Из буржуйских источников стало известно, что оптимизация данного поиска становится возможной при построении суффиксного дерева для строк (Suffix Tree), суффиксное дерево должно строится таким образом, чтобы каждый узел (суффикс) имел два флага "присутствует в первой строке" и "присутствует во второй строке". После чего нужно просто выполнить обход дерева и найти максимальные суффиксы, у которых оба флага в "true". Готового решения не нашел, только алгоритмы. Как появится какая-то свежая информация - отпишусь.

Да, забыл сказать, сложность обычного алгоритма O(m x n), где m и n - длины строк. И памяти нужно пропорционально m x n. А для суффиксного варианта сложность становится O (m + n). Выигрыш очевиден.

 

[Jeurey]

Ну кто так реализации делает?

Алгоритм нааамного проще: при нахождении СРАЗУ подсчитываем длины подстрок. Сразу срваниваем максимальную длину с текущей

 

[gregzem]

Есть готовое решение на каком-нибудь языке с учетом описанного упрощения? Есть подозрение, что не все так просто.

 

[ZCFD]

почитал по первому линку -- задача : найди то , не знаю что

в таком случае множество частных решений на порядок-два проще чем общее

Если речьопарсинге страниц ( на сколько я понял ) -- поверь мне, парсер одного ресурса пишется минут за 10. То что описано по ссылке -- ппц просто.

Конкретный вопрос есть ?
,Как ты например будешь различать конец подстроки ?

Если у тебя есть начало подстроки , и признак ее конца ( пусть по примеру это будет "</div>" , хотя спорный момент со своими тонкостями ) -- поиск простым регулярным выраждением вернет тебе массив. Найти самую длинную строку-член из массива не проблема.

Совет : не надо так глобально замахиваться

 

[Jeurey]

ZCFD, фишка в том, что подстрок может быть на 7.5 га )

 

[ZCFD]

две HTML страницы (по ~90Kb). За

а про массив в 7,5Gb это я так понял особенностьтого алгоритма.

PS я конечно с ним не знаком , но имхо найти самую длинную подстроку с двух страниц можно даже регуляркой,объеденив страницы в одну

 

[gregzem]

Это уже второе по счету сообщение вида "это ппц как просто". Но до сих пор никто свой вариант поиска общих фрагментов строки не привел.

Итак, еще раз постановка задачи (исторический экскурс есть по ссылке в первом моем посте есть две HTML страницы. У них есть общие блоки (хедер, футер, левое меню, например). Задача найти общие фрагменты (хедер, футер, левое меню). То есть определить смещение блока и длину для каждой страницы. Для начала более простой вариант - считаем блоки на 100% одинаковыми. То есть футер, хедер и левое меню полностью идентичны.

Вот такая задача. Страницы могут быть по 100-150 клибайт. Страницы имеют разный контент, но одинаковые обрамляющие их блоки.

Для небольших страниц я написал подобный поиск действительно за 10 минут с использованием алгоритма поиска Longest Common String. Для больших никак не попробую заюзать суффиксные деревья. Уже, наверное, после отпуска

 

[zaartix]

ну хидер и футер наверное не стоит описывать это просто

А вот одинаковые блоки внутри текста - это интереснее.

Попробуем решать задачу в лоб, блок описан как правило либо таблицей, либо дивами. Дергаем регуляркой все дивы и таблицы и сравниваем Кстати можно сравнивать для начала внутри самой страницы (позволит избавиться от повторяющихся блоков на одной странице), а потом уже с дивами с других страниц. Сравнивать не обязательно кстати через "==", можно через similar_text, но это все надо на реальных примерах тестить, имхо можно сделать более менее качественный механизм без применения суффиксных деревьев, соответветственно памяти будет в разы меньше жрать.