Блог

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

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

Я был бы очень признателен за любые ссылки на литературу или существующие библиотеки.

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

В некоторых кругах эта проблема известна как «Индукция HTML-оболочки» или «Изучение оболочки». В этой статье вы можете найти интересный — хотя и старый — обзор вместе со ссылками на некоторые коммерческие приложения: http://www.xrce.xerox.com/Research-Development/Historical-projects/IWRAP-Intelligent-Wrapper-Learning-Tools )

Возможно, вас заинтересует эта библиотека Python:http://code.google.com/p/templatemaker /«Ну, допустим, вы хотите получить необработанные данные с нескольких веб-страниц, которые используют один и тот же шаблон — например, обзоры ресторанов на Yelp.com например. Вы можете предоставить templatemaker произвольное количество HTML-файлов, и он создаст «шаблон», который использовался для создания этих файлов.» (http://www.holovaty.com/writing/templatemaker /)

Кроме того, другая библиотека Python под названием scrapy, похоже, имеет библиотеку индукции оболочки: http://dev.scrapy.org/wiki/Scrapy09Changes#Addedwrapperinductionlibrary

Однако я не могу много рассказать об алгоритмах. Если вы хотите реализовать один из них самостоятельно, это выглядит как хорошая отправная точка: http://portal.acm.org/citation.cfm?id=1859138 Он включает в себя как вводную оболочку, так и онлайн-обучение, так что вы можете начать классифицировать страницы по мере продолжения процесса обхода.

Рассматривали ли вы обнаружение клонов? Эти инструменты определяют, как многократно использовался скопированный код, что очень похоже на то, что вы хотите. Конечно, эти страницы были созданы таким образом или, возможно, сгенерированы как «экземпляры шаблона». Такие детекторы клонов автоматически определяют общие черты.

Некоторые детекторы клонирования сопоставляют идентичные подстроки максимальной длины. Проблема в том, что тривиальные различия в веб-структуре (дополнительные пробелы, новые строки, HTML-комментарии) препятствуют многим совершенно допустимым совпадениям, поэтому вы пропускаете случаи. У этого также есть недостаток, заключающийся в том, что он находит только идентичные строки, а не шаблоны с точками изменения. Алгоритмы, которые выполняют индукцию по строкам (ответ другого участника), могут страдать от этих проблем.

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

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

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

В вашем случае грамматика языка будет представлять собой смесь языков, из которых создаются ваши веб-страницы, например HTML, JavaScript и любого другого динамического языка, который вы использовали для динамической генерации веб-текста. (У нас есть детекторы клонов для грязного HTML, JavaScript, C #, Java, JSP, PHP, [пока нет ни одного для Perl, но близко!] …). Вы можете увидеть несколько отчетов об обнаружении клонов для разных языков (к сожалению, ни одного для HTML) по ссылке.

Результаты CloneDR в точности отражают общность (шаблонов), точки изменения и то, чем точки изменения отличаются.

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

Из-за требований к дизайну одного веб-сайта каждая из его страниц будет содержать одну и ту же группу функциональных подструктур — таких как меню, боковые панели, макеты, заголовки, нижние колонтитулы и т.д. — Так что на определенной глубине все страницы одного веб-сайта будут структурно одинаковыми, а ниже этой глубины структуры страниц будут отличаться. Определяя эту «глубину сходства», вы должны быть в состоянии выделить те части страницы, которые структурно неизменны во всем корпусе сайта.

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

Остальное — это просто нормализация HTML (с использованием HTMLTidy) и сравнение DOM-деревьев.

Учитывая большое количество страниц, использующих один шаблон, мы ожидали бы обнаружить, что самая длинная общая подпоследовательность (LCS) этих страниц близко соответствует шаблонной «оболочке». (Если у нас всего 2 или 3 страницы, то буквы в тексте, которые случайно появляются в одном и том же порядке на каждой, также попадут в LCS — однако это не является ограничителем показа.)

К сожалению, для нахождения LCS k последовательностей требуется время, экспоненциальное в k, однако можно произвести аппроксимацию путем вычисления LCS (a, LCS (b, LCS (c, …)), где каждая операция LCS () над 2 последовательностями длины n занимает O (n ^ 2) времени. На самом деле я ожидаю, что это приближение лучше справится с отсевом ложных текстовых подпоследовательностей, чем точное решение проблемы.

До этого момента я говорил о гипотетической ситуации, в которой все файлы используют один и тот же шаблон. Но проблема, с которой мы сталкиваемся, заключается в том, что существует несколько шаблонов. Чтобы решить эту проблему, я предлагаю алгоритм кластеризации, в котором мы создаем кластеры файлов по ходу работы. Для каждого кластера мы будем сохранять LCS всех файлов, включенных на данный момент в этот кластер, вычисленные с использованием попарного приближения, приведенного выше; вызовите это clcs[i] для i-го кластера. Для каждого файла по очереди, для каждого кластера i мы вычисляем LCS файла с clcs[i] и сравниваем длину этого LCS с длиной clcs[i] . Если эта длина не намного меньше длины clcs[i] , то этот файл «хорошо подходит», поэтому он добавляется в кластер i , и только что вычисленные LCS становятся новыми clcs[i] . Если ни один существующий кластер не обеспечивает достаточно хорошего соответствия для файла, то создается новый кластер, содержащий только этот файл (и его LCS, который равен самому файлу).

Что касается «не намного меньше»: это весовой коэффициент, который потребует некоторой настройки. Очевидно, что когда новый кластер только что создан и содержит всего один файл, мы ожидаем, что другой файл, созданный с использованием того же шаблона, будет иметь LCS с ним, который немного короче, чем LCS этого кластера до сих пор, поэтому мы должны допустить значительное уменьшение длины LCS. По мере увеличения размера кластера его общий LCS должен стабилизироваться в «оболочке» шаблона, поэтому мы должны быть менее склонны добавлять новый файл в кластер, если это значительно уменьшает длину LCS.

Этот алгоритм, как правило, создает другой набор кластеров, если файлы представлены в другом порядке, поэтому может быть хорошей идеей попробовать несколько разных порядков и проверить, отображаются ли одинаковые кластеры.

Наконец, для извлечения соответствующей изменяющейся информации из данного файла в кластере работает следующий алгоритм:

 i = 0
for (j = 0 to len(file)) {
    if (file[j] == lcs[i]) {
          i;
    } else {
        output file[j]
    }
}