Какие есть паттерны или алгоритмы для обработки текста?

Question

[Котик Антон]

Собираюсь написать библиотеку, которая будет выполнять большое число различных преобразований с HTML текстом:
1. Преобразовывать кодировку текста в UTF-8, нормализовывать Unicode;
2. Оборачивать все ссылки в HTML теги <a>...</a> (если ссылка ещё не в тегах);
3. Расставлять пропущенные не закрытые HTML теги;
4. Расставлять неразрывные пробелы после предлогов;
5. Заменять дефисы на тире там, где это необходимо;
6. Удалять запрещенные HTML теги;
7. Заменять некоторых комбинаций символов на изображения (для смайликов);
...и сотни других преобразований.

Как видно, некоторое преобразования осуществляются на уровне всего текста, другие на уровне отдельных HTML тегов, третьи — на уровне отдельных символов. Для некоторых правил важен порядок их применения: одни правила должны выполняться раньше других.

На выходе должна получиться некая смесь типографа и известного многим HTML Purifier. Код должно быть легко расширять (добавлять собственные преобразования) сторонними плагинами.

Самое простое решение — каждое преобразование выполнять отдельно в нужном порядке: в каких-то случаях найти нужные символы в тексте и заменить их (пример из типографа Муравьева), в каких-то случаях использовать регулярные выражения (пример). То есть каждое правило берет и тем или иным образом обрабатывает весь текст целиком. С одной стороны такой код легко понять, легко поддерживать, но тяжело расширять и при большом числе преобразований работает всё очень медленно. А самое ужасное, что при таком подходе внесение изменений в одно преобразование может повлиять на другие и приходится разбивать преобразование на разные стадии.

Как можно архитектурно правильно построить такую библиотеку? Может быть, есть какие-то паттерны для этого?

Comments

[sim3x]

С 0?

Потому что https://en.wikipedia.org/wiki/Libxml2 уже таким занимается

А санитайзинг - сложная сфера и больше пересекается с безопасностью и атаками на фронтенд

[Котик Антон]

sim3x, Да, с нуля. Хочу все правила реализовать сам, чтобы легко можно было вносить правки на любой стадии и в любое преобразование. И в итоге получить комбайн, который один раз настроил, скормил ему сырой текст и получил конфетку. А с помощью плагинов этот комбайн можно будет использовать в самых разных проектах и для самых разных результатов.

[Dima Polos]

Честно, не знаю что посоветовать, так как не задавался этим вопросом, но буквально вчера посмотрел запись web standart days в Москве, который был в субботу, там был доклад про парсинг css, и в общих чертах докладчик говорил о том, какие алгоритмы есть, какие он использовал, давал ссылки на репозитории и так далее, думаю Вам будет что-то полезно из его слов узнать, как минимум интересно. Вот ссылка: https://youtu.be/kDmQcueD4Jk
Начало его речи на 1 час 57 минуте.
PS Мне он чем-то внешне на Вас похож, случайно не Ваш доклад?
27cm)

[Котик Антон]

Dima Polos, нет, это был не я. За ссылку спасибо.

Answer 1

[D3lphi]

Предложу вот такой порядок действий:

1. Лексический анализатор разбивает поток входящих лексем на токены.
   
2. Далее, набор токенов подается на вход парсеру, который выполняет построение "сырого" DOM-дерева, в котором могут присутствовать невалидные теги и тд.
   
3. Производится обход сырого DOM-дерева и его нормализация. Изменяем имена тегов на максимально приближенные к ним валидные имена, проставляем пропущенные теги, удаляем запрещенные и т.д.
   
4. По нормализованному дереву теперь можно делать обход и преобразовывать текст.
   
5. Преобразовываем готовое дерево в html-документ.
   

Comments

[xmoonlight]

D3lphi,

Лексический анализатор разбивает поток входящих лексем на токены.

А можно пояснить на конкретном примере чистого текста...?

[D3lphi]

xmoonlight, что вам конкретно не понятно? Книгу дракона прочтите, там подробно разбирается процесс токенизации, как один из этапов построения компилятора. Этот же подход можно использовать и при написании лексического анализатора любого языка с контекстно-свободной грамматики, коим и является html.

Пример:

<span class="example">some text</span>

Как вариант, можно разбить на следующие токены:

TAG_BEGIN
TAG_ATTRS_BEGIN
ATTR_NAME
ATTR_VALUE_STRING
TAG_ATTRS_END
TAG_CONTENT
TEXT
TAG_END_CONTENT
TAG_END

[Stalker_RED]

Пример реализации такого восстановления кривого html можно посмотреть в исходниках движков браузеров. И да, это все довольно сложно.

[xmoonlight]

D3lphi, чукча у нас писатель?)))

на конкретном примере чистого текста...

без тегов!

Вот цитата 27cm:

То есть может быть огромный текст совсем без HTML тегов, и к нему нужно применить ещё сотни преобразований.

[Котик Антон]

xmoonlight, я так понял, текст также можно разбить на лексемы до нужного уровня. Например текст "слово example.com." можно превратить в лексемы: WORD, SPACE, URL, DOT. А при необходимости и ссылку разделить на составляющие.

[D3lphi]

xmoonlight, для работы с чистым (если предполагается нормализовать слова) текстом, предполагаю, без сторонних решений не обойтись. Можно использовать анализаторы, на подобии тех, что использует easticsearch. Для каждого языка свой. В остальном же, смотрите, что написал 27cm.

[Котик Антон]

D3lphi, под преобразованиями над текстом имелась ввиду не нормализация текста, а типографские преобразования:
mdash.ru/rules.html

[xmoonlight]

27cm, тогда всё, что у меня в ответе - чётко подходит под требования.
А про

Например текст "слово example.com." можно превратить в лексемы: WORD, SPACE, URL, DOT. А при необходимости и ссылку разделить на составляющие.

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

[xmoonlight]

D3lphi, 27cm, заодно, к сторонним решениям: кто-нить знает решение:
1. Для проверки правописания
2. Для проверки пунктуации
3. Для выделения сущностей из текста
Желательно на PHP и только stand-alone, не сервис!

Answer 2

[asd111]

Судя по тому чему вы хотите научится я бы советовал изучить ANTLR. Это очень качественный генератор лексеров и парсеров, правда он на java, но это не проблема.
Там уже есть готовая грамматика для html . Если она не устраивает, то можно сделать свою.
По этой грамматике он строит дерево и для обхода дерева можно быстро написать visitor или что то попроще. Также там нетрудно написать обработку ошибок(отсутствие закрывающего тега и т.п.) .

Comments

[Котик Антон]

Спасибо, буду изучать.

Answer 3

[RuWeb]

Вот уже готовый онлайн сервис TextTools.ru

Comments

[Therapyx]

ухты, какой полезный сайт. Летит в закладки))

Answer 4

[xmoonlight]

1. Вначале нужно "собрать" корректное/валидное DOM-дерево.
2. Затем, добавить все нужные теги
3. Удалить все запрещённые теги
4. Затем, рекурсивно обойти все ветки DOM-"дерева", выполнив текстовые преобразования.

Порядок в общем виде (строго соблюдая последовательность действий!):
Валидация структуры, добавление нужных элементов, удаление запрещённых элементов, модификация "тела" оставшихся элементов.

Comments

[Котик Антон]

Это отлично подходит, если бы задача была только про расстановку тегов, но нужно не только теги расставлять, но и например преобразовывать отдельные символы (например расставить правильные вложенные кавычки в тексте). То есть может быть огромный текст совсем без HTML тегов, и к нему нужно применить ещё сотни преобразований.

[xmoonlight]

27cm, обычная замена через preg_replace() при рекурсивном обходе DOM-"дерева". После изменения очередной ноды делаем те же пункты (п.1-п.4), но уже только для текущей ноды, т.е. рекурсивно следим за всеми правилами.

[Котик Антон]

xmoonlight, Я не прошу готовый код. К тому же бывают вложенные кавычки, кавычки 3-его уровня, знак дюйма и ещё масса нетривиальных случаев. Там регуляркой будет крайне тяжело выкрутиться. Но мысль я понял, и какие с таким подходом есть проблемы написал в вопросе.

[xmoonlight]

27cm, не вижу тут проблем.

но и например преобразовывать отдельные символы (например расставить правильные вложенные кавычки в тексте). То есть может быть огромный текст совсем без HTML тегов, и к нему нужно применить ещё сотни преобразований.

всегда делаем сначала манипуляции со структурами верхнего уровня, постепенно спускаясь к структурам нижнего уровня: разметка, текст, слово (то, что разделено одним или более пробелами), символ.