Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, korzh.pavel, Вы писали:

К>>>Так, наверное, ты ещё забыл добавить, что тебе нужна строка, максимально близкая к исходной? В таком случае нельзя выбрасывать * и +.

К>Для небольших строк, наверное, можно сделать перебор.

К>Немножко модифицируем (относительно обычного) механизм сопоставления.
К>Переход по символу совершается, если этот символ есть в остатке строки (а не просто если это первый символ остатка). Причём сразу же измеряем расстояние Левенштейна (как далеко этот символ от начала остатка). И естественно, изымаем символ из строки.
К>Финишный переход совершается, даже если остаток непуст. Эти символы нужно будет выбросить.

К>Ну а дальше всё просто. Найдя совпадение, получили его вес. Делаем откат, и накатываем с отсечением по этому весу.
К>И так далее, пока не получим приемлимый минимум.

ну да. Спасибо. Сейчас я уже вижу что задача не такая уж сложная. А то сначала я что то напрягся.

К>Естественно, тут мы не делаем никакого просмотра вперёд и разделения-властвования. Но с учётом того, что ожидаемые регекспы — простые, вряд ли будет много совпадений.
К>Хотя погонять на реальном наборе было бы интересно. Выложи (если не секрет) образцы?

Вообще задача такая:
Есть очень большой набор html, который собирался в результате нескольких лет эксплуатации системы.
Встречается Html совершенно "дикий". Надо всю эту базу преобразовать в абсолютно валидный html.

На него напускается htmltidy, но всё равно, даже после htmltidy, встречаются достаточно много html, который не проходит валидацию.

Одна из проблем это content specification validate and recovery.

Например для table имеем такой content specification: <!ELEMENT table (caption?, (col*|colgroup*), thead?, tfoot?, (tbody+|tr+))>

У меня возникла мысль сделать это в общем случае, поэтому я и задал вопрос.
Но сроки поджимают поэтому сейчас я починил наиболее встречающиеся частные случаи.

Здравствуйте, korzh.pavel, Вы писали:

KP>Вообще задача такая:

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

KP>Есть очень большой набор html, который собирался в результате нескольких лет эксплуатации системы.
KP>Встречается Html совершенно "дикий". Надо всю эту базу преобразовать в абсолютно валидный html.

KP>На него напускается htmltidy, но всё равно, даже после htmltidy, встречаются достаточно много html, который не проходит валидацию.

KP>Одна из проблем это content specification validate and recovery.
KP>Например для table имеем такой content specification: <!ELEMENT table (caption?, (col*|colgroup*), thead?, tfoot?, (tbody+|tr+))>

А в чём засада — нужно пропатчить эвристики у tidy; или сделать ещё одну прогу, которая после tidy дорабатывает; или что ещё?

Кстати, а как насчёт такого варианта:
— взять DOM-парсер HTML, нечувствительный к дикости (ну скажем, из мозиллы)
— всосать в него дикий HTML
— как-бы-рендерить — сериализовать обратно в валидный HTML с правильной структурой и сбалансированными тэгами

Медленное удовольствие, конечно... зато (имхо) надёжное.
Правда, есть заподлянка: дикость-то исправлена будет, а вот ошибки легализуются. Например, одинокий <p>...<b>...</p> сделает жирным весь документ до конца (а после легализации появится куча <p><b>...</b></p>).

С другой стороны, — судя по документации tidy, она излишне бдит.

<p>Plain <b>bold <i>bold-italic</b> italic</i> text</p>

который рендерится как
Plain bold bold-italic italic text

она превращает в
<p>Plain <b>bold <i>bold-italic</i> italic</b> text</p>

что даёт
Plain bold bold-italic italic text

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, korzh.pavel, Вы писали:

KP>>Вообще задача такая:

К>Вот с этого и надо было начинать.
К>А я, дурень, забыл спросить, просто набросился на прикольный этюд.

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

KP>>Есть очень большой набор html, который собирался в результате нескольких лет эксплуатации системы.
KP>>Встречается Html совершенно "дикий". Надо всю эту базу преобразовать в абсолютно валидный html.

KP>>На него напускается htmltidy, но всё равно, даже после htmltidy, встречаются достаточно много html, который не проходит валидацию.

KP>>Одна из проблем это content specification validate and recovery.
KP>>Например для table имеем такой content specification: <!ELEMENT table (caption?, (col*|colgroup*), thead?, tfoot?, (tbody+|tr+))>

К>А в чём засада — нужно пропатчить эвристики у tidy; или сделать ещё одну прогу, которая после tidy дорабатывает; или что ещё?

нужно сделать прогу которая после tidy дорабатывает

К>Кстати, а как насчёт такого варианта:
К>- взять DOM-парсер HTML, нечувствительный к дикости (ну скажем, из мозиллы)
К>- всосать в него дикий HTML
К>- как-бы-рендерить — сериализовать обратно в валидный HTML с правильной структурой и сбалансированными тэгами

К>Медленное удовольствие, конечно... зато (имхо) надёжное.
К>Правда, есть заподлянка: дикость-то исправлена будет, а вот ошибки легализуются. Например, одинокий <p>...<b>...</p> сделает жирным весь документ до конца (а после легализации появится куча <p><b>...</b></p>).

да не, я лучше после tidy подчищу.

К>С другой стороны, — судя по документации tidy, она излишне бдит.
К>

К><p>Plain <b>bold <i>bold-italic</b> italic</i> text</p>

К>который рендерится как
К>Plain bold bold-italic italic text

К>она превращает в
К><p>Plain <b>bold <i>bold-italic</i> italic</b> text</p>

К>что даёт
К>Plain bold bold-italic italic text
К>

да, с tidy не всё идельно, но в общем случае она нормально отрабатывает

Здравствуйте, korzh.pavel, Вы писали:

KP>ну так вроде моя задача в общем случае сводится как раз к задаче подгона строки под рег.выражение

Не совсем понятно, как она сводится.
И уж во всяком случае, как можно свести контекстно-свободный язык к регулярному? Те же самые вложенные таблицы, например.

Может быть, лучше налепить простецкий SAX-парсер и для тех узлов, на которых tidy проскальзывает, строить AST и затем сериализовывать.


P.S. Я на всякий случай выделил ветку, чтобы не сферокавалерийское решение искать.

KP>Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, korzh.pavel, Вы писали:

KP>Встречается Html совершенно "дикий". Надо всю эту базу преобразовать в абсолютно валидный html.
я так подозреваю что в разных браузерах по разному отображается ...

KP>На него напускается htmltidy, но всё равно, даже после htmltidy, встречаются достаточно много html, который не проходит валидацию.
пробовал http://htmlcleaner.sourceforge.net/ чистит более агресивно но валидацию в большем количестве случаев проходит

К>Может быть, лучше налепить простецкий SAX-парсер и для тех узлов, на которых tidy проскальзывает, строить AST и затем сериализовывать.
если ошибки похожие то конечно поможет ....
а вот если количество типов ошибок перевалит за 1000
нужно (IMHO) собирать некоторую глобальную базу с шаблонами для анализа и правок
собственно подобного проекта никто не встречал ?

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, korzh.pavel, Вы писали:

KP>>ну так вроде моя задача в общем случае сводится как раз к задаче подгона строки под рег.выражение

К>Не совсем понятно, как она сводится.
К>И уж во всяком случае, как можно свести контекстно-свободный язык к регулярному? Те же самые вложенные таблицы, например.

Извини, что долго не отвечал. Зашиваюсь.
Не понял про вложенные таблицы. Там вроде всё нормально.

Ещё раз: вот кусок DTD для таблицы

<!ELEMENT table (caption?, (col*|colgroup*), thead?, tfoot?, (tbody+|tr+))>
<!ELEMENT caption  %Inline;>
<!ELEMENT thead    (tr)+>
<!ELEMENT tfoot    (tr)+>
<!ELEMENT tbody    (tr)+>
<!ELEMENT colgroup (col)*>
<!ELEMENT col      EMPTY>
<!ELEMENT tr       (th|td)+>
<!ELEMENT th       %Flow;>
<!ELEMENT td       %Flow;>

значит для table имеем такое рег. выражение: a?(b*|c*)d?e?(f+|g+)
a — caption
b — col
c — colgroup
d — thead
e — tfoot
f — tbody
g — tr

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

Вот откуда у меня возникла идея про подгон строки к рег. выражению.

Но, сейчас я пришёл к выводу что я всё таки всё усложняю, потому что на моей базе(где то 7000 html документов)
самые распрастраннёные ошибки после прогона через htmltidy:

1. невалидные значения аттрибутов
например IE для аттрибута align часто ставит absmiddle, в стандарте такого значения нет

тут ещё важно не просто отбросить невалидное значение а постараться перевести его в валидное, в данном случае в middle

для этого у меня есть recovery rules

2. у элемента нет обязательных аттрибутов
например <img> не имеет аттрибута src

3. в списке детей элемента присутствует элемент, который не должен там присутствовать.
Например <font> внутри <pre>

4. Элемент не имеет детей, хотя должен.
например список без единого элемента

Вот. Это практически все ошибки на моей базе.

К>Может быть, лучше налепить простецкий SAX-парсер и для тех узлов, на которых tidy проскальзывает, строить AST и затем сериализовывать.

Да. Я уже строю дерево. И все ошибки которые описал выше чиню.

Здравствуйте, korzh.pavel, Вы писали:

KP>Не понял про вложенные таблицы. Там вроде всё нормально.
<...>
KP>и мне пришла к примеру таблица в html у которой caption стоит не на первом месте (не знаю насколько это реально и как браузеры на это отреагирует)
KP>ну и вот, мне надо понять что я должен взять этот caption и переместить его на первую позицию и тогда у меня валидация замечательно пройдёт.

Пожалуйста

<table>
<tr><td>
    Начало
    <table>
        <tr><td>Первая ячейка вложенной таблицы</td></tr>
        <caption>Вложенная таблица</caption>
        <tbody><tr><td>Вторая ячейка вложенной таблицы</td></tr>
    </table>
    Конец
</td></tr>
</table>

Первая ячейка вложенной таблицы добавлена для того, чтобы закрыть скобки тэга <tr> внешней — если твой регексп просекает такую фишку.
А если не просекает, то можно смело убрать эту ячейку, и получим полностью валидный код... Из которого будет выхвачен <caption.../>, относящийся ко вложенной таблице.
И уверяю тебя, на любой сколь угодно умный регексп можно придумать контрпример с достаточной вложенностью. Пусть даже невалидный — но его невалидность будет иная, чем подумает твой регексп.

KP>Вот откуда у меня возникла идея про подгон строки к рег. выражению.

Любой автомат, более сложный чем конечный, тебя выручит. Хоть строящий AST (т.е. DOM-парсер), хоть просто стековый.
Понятно, конечно, что регекспы — "распарсить-заменить" — это расхожее выразительное средство, т.е. тебе не пришлось бы изобретать собственный язык описания.
Но с другой стороны, банальный яваскрипт, манипулирующий DOM-деревом — вполне выразительное средство, хотя и многословное.
Особенно, если припахать удобные фреймворки для навигации и трансформации HTML. Например, JQuery

Автор(ы): Dmitrii 'Mamut' Dimandt
Дата: 11.04.2002
В статье описана библиотека jQuery. Разобраны ключевые моменты работы с библиотекой — нахождение элементов на странице, манипуляция объектной моделью документа, базовая анимация, работа с технологией AJAX. В статье приведено большое количество примеров работающего кода.

.

KP>Но, сейчас я пришёл к выводу что я всё таки всё усложняю, потому что на моей базе(где то 7000 html документов)
KP>самые распрастраннёные ошибки после прогона через htmltidy:

Вот с этого и следовало начинать!

KP>3. в списке детей элемента присутствует элемент, который не должен там присутствовать.
KP>Например <font> внутри <pre>

Это нарушение корпоративной этики? Почему нельзя, например, раскрашивать моноширинный текст?

KP>Да. Я уже строю дерево. И все ошибки которые описал выше чиню.

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