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

Тема в разделе "Как сделать...", создана пользователем gregzem, 1 авг 2008.

Статус темы:
Закрыта.
  1. gregzem

    gregzem

    Регистр.:
    21 окт 2007
    Сообщения:
    200
    Симпатии:
    63
    Задача навеяна вот этой темой: http://www.nulled.ws/showthread.php?t=61824

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

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

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

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

    Есть такой алгоритм - Longest Common substring. Он как раз и позволяет найти эту максимально-длинную подстроку.

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

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

    gregzem

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

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

    Jeurey

    Регистр.:
    13 сен 2006
    Сообщения:
    419
    Симпатии:
    576
    Ну кто так реализации делает?

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

    gregzem

    Регистр.:
    21 окт 2007
    Сообщения:
    200
    Симпатии:
    63
    Есть готовое решение на каком-нибудь языке с учетом описанного упрощения? Есть подозрение, что не все так просто.
     
  5. ZCFD

    ZCFD

    Регистр.:
    16 янв 2008
    Сообщения:
    989
    Симпатии:
    437
    почитал по первому линку -- задача : найди то , не знаю что

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

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

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

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

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

    Jeurey

    Регистр.:
    13 сен 2006
    Сообщения:
    419
    Симпатии:
    576
    ZCFD, фишка в том, что подстрок может быть на 7.5 га )
     
  7. ZCFD

    ZCFD

    Регистр.:
    16 янв 2008
    Сообщения:
    989
    Симпатии:
    437
    а про массив в 7,5Gb это я так понял особенностьтого алгоритма.

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

    gregzem

    Регистр.:
    21 окт 2007
    Сообщения:
    200
    Симпатии:
    63
    Это уже второе по счету сообщение вида "это ппц как просто". Но до сих пор никто свой вариант поиска общих фрагментов строки не привел.

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

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

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

    zaartix Постоялец

    Регистр.:
    15 май 2006
    Сообщения:
    73
    Симпатии:
    27
    ну хидер и футер наверное не стоит описывать :) это просто

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

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