Получение шаблонов из коллекции строк

Question

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

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

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

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

Answer 1

В некоторых кругах эта проблема известна как «Индукция HTML Wrapper» или «Обучение Wrapper». В этой статье вы можете найти интересный - хотя и старый - обзор вместе со ссылками на некоторые коммерческие приложения: 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 Он включает в себя как вводную оболочку, так и обучение в режиме онлайн, поэтому вы можете начать классифицировать страницы по мере продолжения процесса сканирования.

Answer 2

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

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

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

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

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

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

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

Answer 3

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

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

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

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

Answer 4

Учитывая большое количество страниц, которые используют один шаблон, мы ожидаем, что самая длинная общая подпоследовательность (LCS) этих страниц близко соответствует шаблону "shell". (Если у нас есть только 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]
    }
}