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

К>Здравствуйте, 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+))>

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