Процессинг текстовых объектов в ERP-системах

Необходимость сложной обработки текстовых данных, хранящихся в ERP-системах (и не только) возникает достаточно часто. В качестве вводных примеров можно привести следующие:

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

Выясним чего мы хотим

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

Так как мы будем работать с текстами, которые вводятся с самым минимальным соблюдением правил, а чаще и вообще без оных, то применение регулярных выражений, языков perl или awk не видится возможным. Вполне доступно это описано на хабре же в статье посвященной аналогичной проблеме.

Наши желания следующие:

Мы хотим преобразовывать тексты в базе данных так, чтобы они были максимально унифицированы.
Например, есть два товара «Мыло жидк. ПАЛМОЛИВ ароматерапия 300 мл» и «Palmolive жидкое мыло вита-масло глубокое питание 300мл».
Мы бы хотели видеть вместо этих двух названий, скажем, такие:
«Мыло жидкое Palmolive ароматерапия 300мл» и «Мыло жидкое Palmolive вита-масло глубокое питание 300мл».
Нам очень хочется писать меньше правил (тем более что синтаксис как будет видно ниже по объективным и субъективным причинам — не подарок). Следовательно, нам понадобятся какие-то группирующий опции, чтобы одним махом заменить несколько вариантов на один.
Допустим: palmolive<<палмолив|palmolv|палмол.
Маркетологи у многих наших клиентов требуют хорошей классификации товаров по 20 признакам, а фитнес-клубы, которые мы автоматизируем, жалуются на то, что какой-то сотрудник у посетителя Иванова Петра Михайловича установил принадлежность к женскому полу.
Следовательно, нам очень важно, что бы программа автоматически расставила у товаров брэнды, принадлежность к группе, крепость и емкость алкогольных напитков — ведь сотрудники уже все или многое указали в наименованиях.
Другими словами, необходим механизм извлечения признаков из текстовых объектов и преобразование этих признаков в формальные атрибуты сущностей.
Хотелось бы иногда, при замене текста или извлечении формальных признаков из него, ограничить контекст применения правила.
Речь вот о чем: для примера, слово «пудра» может означать как сахарную пудру, так и косметическую пудру для лица (для англоязычных текстов все может быть еще многозначнее). Если мы ограничим контекст, то сможем трактовать это слово по-разному. Скажем, ограничив контекст перечнем beauty-брэндов, мы можем точно классифицировать вхождения слова «пудра» в наименование товара как пудру для лица.

Приступим к решению

Фактически, задача упирается в определение языковых конструкций, и действий над ними. Как ни жаль создавать 1001-й язык, но пришлось, благо, он не так чтобы сложный.

Прежде чем рассказать о языке, определю понятия, которые он должен реализовать:

Лексема — буквальное определение слова или разделительного символа
Класс лексем — группирующее определение множества лексем, удовлетворяющих встроенному набору характеристик.
Примеры классов лексем:
- слово — последовательность символов без разделителей (одиночный разделитель так же является подмножеством этого класса)
- цифровое слово — последовательность десятичных цифр без разделителей
- цифровое слово заданной длины — последовательность десятичных цифр без разделителей фиксированной длины
- ANY — не пустая последовательность слов
Операция — действие, которое должно быть произведено над каким-либо участком текста
Операций не много:
- Замена — замещение части текста целевым выражением
- Изменение регистра — простая операция, обеспечивающая установку регистра букв в словах по одному из трех вариантов:
  - Все строчные
  - Все прописные
  - Капитал (первая буква прописная, последующие — строчные)
- Сигнал — формирование специальной хорошо структурированной строки, возвращаемой вызывающему модулю для того, что бы информировать его о том, что текст содержит соответствующую конструкцию и предоставить возможность эффективно выполнить какое-нибудь (на усмотрение вызывающего модуля) задание
Исходное выражение — часть исходного текста, над которой необходимо произвести какую-либо операцию
Целевое выражение — конструкция, замещающая исходное выражение, или выступающая объектом сигнала
Группа — часть исходного выражения, на которую можно ссылаться в целевом выражении. Это понятие идентично аналогичному понятию в регулярных варажениях
Кластер — набор исходных выражений, для которого определена общая операция
Вариант — по-просту говоря, оператор ИЛИ. Используется в исходных выражениях для перечисления различных конструкций, к которым должна применяться одна и та же операция. Строго говоря, вариант и кластер — почти синонимичны. Различия между ними носят синтаксический характер.
Кортеж — именованный кластер. То есть набор исходных выражений, облеченный именем, благодаря чему может быть многократно применен в разных конструкциях. Естественно, кортежи допускают рекурсивность — то есть, элементом или субэлементом кортежа может быть символ другого кортежа
Контекст — набор условий, которым должен удовлетворять текст, для того, чтобы было применено то или иное правило. Эту концепцию мы пока не реализовали, но представляем как она должна работать, по-тому, в скором времени сделаем.

В общем, процесс обработки текста состоит из следующих шагов:

Разбор набора правил
Для каждого текста, который должен обрабатываться данным набором правил:
- Преобразование текста в строку лексем: все буквы текста преобразуются в строчный регистр и текст разбивается на лексемы (слова и разделители), каждая лексема сваливается в общий пул (хэш-таблицу), а текст, подлежащий обработки, превращается в цепочку целочисленных идентификаторов, с которой мы и будем работать.
  Важно: правила обработки проходят аналогичных процесс «переваривания» в результате чего идентификация простого совпадения лексем будет осуществляться целочисленным сравнением.
- Индексация текста. Подробности индексации опишу ниже.
- К полученному образу текста применяется поочередно каждое правило. Если в результате применения правила текст был трансформирован, образ преобразуется обратно в текст и снова в цифровую цепочку. Такой кульбит может показаться расточительным с точки зрения производительности, однако, (пока) он нужен из-за неполной обратимости преобразования (в частности, из-за операции замены регистра символов), а так же из-за необходимости индексировать текст.
  Если правило определяет операцию сигнала, то вызывается callback-функция с результирующим объектом сигнала.
- После обработки последнего правила собирается окончательный текст и используется на усмотрение вызывающего модуля (самое простое — выводится в журнал, но чаще — замещает оригинальный текст)

Особенности деления текста на лексемы

При дроблении оригинального текста на лексемы, кроме очевидного разделения по пробелам и другим разделителям, существует неявное разделение. Сейчас оно осуществляется между цифровыми и нецифровыми символами.
Приведу пример: текст «модель900-а изделие» будет разделен на следующие лексемы: «модель», «900», "-", «а», " ", «изделие».

Язык

Теперь можно приступить к описанию языка. Описание не строгое, сосредоточу больше усилий на примерах. Сейчас эта технология работает на сервере Universe-HTT еженощно обрабатывая более 1,3 миллиона наименований товаров по обновляемому набору правил. Для того, чтобы не быть голословным, примеры я буду приводить из этого набора.

И так.

Общие правила

Основная часть языка описания — собственно лексемы, по тому, практически все символы (пробелы, табуляция и тем более буквы и цифры) значимы. Конец строки — конец правила (или части кластера). Переноса строки (аналога ‘\’ в C-макросах) нет.
Не значимы только хвостовые и ведущие пробелы строк.
Основной префикс служебных конструкций — %. Для буквального представления символа процента используется «дубль» %%.

Исходное выражение

Для представления исходного выражения используются буквальные лексемы с применением служебных конструкций:

%s один или более символов пробела либо табуляции
%z ноль или более символов пробела либо табуляции
%_ явный пробел. Может использоваться в конце строки (ибо завершающие пробелы строки игнорируются)
%t табуляция
%. опциональная точка. Написание сокращений бывает как с точкой так и без нее. Чтобы не плодить лишних правил добавлен такой метасимвол.
%- опциональный дефис. Спорный метасимвол. Введен по причине частых различий в написании одного и того же с дефисом и без, но сам-по-себе работает плохо. Вот почему: допустим надо унифицировать «чупа-чупс» и «чупа чупс». Конструкция «чупа%-чупс» распознает только «чупа-чупс», но «чупачупс» уже является единой лексемой, которая не будет распознана, «чупа чупс» же содержит пробел, который мы не учли. Таким образом, для решения нашей задачи придется написать «чупа%z%-%zчупс» — вся идея лаконичности пошла прахом. Тем не менее есть случаи, когда опциональный дефис хорошо работает. Это — стыковка цифровых и алфавитных лексем.
%^ Начало текста. Важно: не строки, а именно всего текста.
%$ Конец текста.
%w Любая одиночная лексема.
%d Цифровая лексема любой длины. Имеется в виду сплошная последовательность десятичных цифр.
%D[0-9][0-9] Цифровая лексема заданной длины. Длина задается строго двумя цифрами. Например: "%D08" — восемь десятичных цифр следующих друг за другом.
%f Число с опциональной десятичной точкой. То есть, под этот шаблон подпадают как сплошные последовательности десятичных цифр, так и две такие последовательности, разделенные точкой. Лидирующий минус не рассматривается. При отсутствии после точки цифровых символов в рассмотрение принимаются только цифры до точки (без нее).
Примеры:
«100» — «100»
«3.1415926» — «3.1415926»
"-3.R" — «3»
«2. 5» — «2»
%( и %) Обозначают начало и конец группы, соответственно. Самая неприятная с точки зрения использования синтаксиса конструкция.
Приведу пример использования:
"%(%d%),%(%d%)%>%1.%2" — правило, превращающее две цифровые последовательности, разделенные запятой, в число с десятичной точкой. Когда я говорил о неприятности пары %(%) имел в виду то, что читабельность правила эта пара очень заметно ухудшает. Увы, просто скобки использовать нельзя (ПМСМ) из-за того, что они слишком часто встречаются в живых текстах.
%* Произвольная, но не пустая, последовательность лексем. Очень полезный метасимвол для перестановки выражений в тексте и как паллиатив рассмотренных выше еще не реализованных контекстов.
Примеры:
«краска %(%*%) для волос%>краска для волос %1» — унифицируем наименования ассортимента красок для волос.
«bag %(%*%) elk%>bag %1 elkay plastics» — elk является сокращением для elkay plastics, но не везде. В контексте пакетов (bag) — да.
%@cortegename. Обращение к кортежу с именем cortegename (точка после «cortegename» значима — она отделяет символ кортежа от последующего текста). Примеры использования кортежей приведу ниже.
%| Вариант. Разделяет два варианта исходного выражения для применения к каждому из них одного и того же оператора.
Примеры:
gift bag%<gift bags%|gft bg%|gft bgs%|gft/bg — «gift bags», «gft bg», «gft bgs», «gft/bg» будут заменены на «gift bag».
для моделирования%<для моделир%.%|для моделиров%. — сокращения «для моделир» и «для моделиров» (с опциональными точками) будут развернуты до полного варианта «для моделирования».

Целевое выражение

Как уже упоминалось, целевое выражение применяется либо для замены исходного выражения, либо для сигнализации о встреченном исходном выражении.
Целевое выражение так же, как и исходное, содержит лексемы и служебные конструкции. Здесь ассортимент метасимволов по-беднее:

%[1-9] — Ссылка на порядковый номер группы в исходном выражении для подстановки.
Пример:
«mr%.%s%(%w%)%>mr.%1» — уберем пробелы в сочетаниях «мистер x» между «mr.» и фамилией и добавим точку после «mr» (если ее нет) .
%_ — Просто явный пробел.
%E — Пустая строка. Из-за того, что синтаксис правила не допускает пропуск целевого выражения, там, где оно предусмотрено, этот метасимвол спасает при необходимости убрать найденное исходное выражение.
Пример:
"%^_%>%E" — убираем лидирующий пробел в тексте.

Операторы

В примерах выше я уже продемонстрировал использование операторов замены %> (TO) и %< (FROM).
Здесь перечислю все возможные операторы и дам необходимые пояснения:

%> Оператор преобразования «В» («TO»). Предписывает преобразовать левое выражение (которое трактуется как исходное) в правое (целевое).
Пример:
"%(%d%)%zсм3%>%1мл" — заменим единицу измерения «куб см» на «мл».
%< Зеркальный к «TO» оператор преобразования «ИЗ» («FROM»). Предписывает заменить правое выражение (трактуемое как исходное) на левое (целевое).
Пример:
«20th%<20 th» унифицируем написание 20-й на английском языке, убрав пробел.
%A Оператор преобразования всех букв исходного выражения в прописные.
%a Оператор преобразования всех букв исходного выражения в строчные.
%K Оператор преобразования всех буквенных лексем исходного выражения таким образом, что первая буква слова становится прописной, а остальные — строчными (капитал).
%! Оператор сигнала. Предписывает сигнализировать целевым выражением о том, что встречено заданное исходное.
Пример:
«del monte%!brand=del monte» — если в тексте встретится сочетание «del monte», то вызывающий модуль получит сигнал вида «brand=del monte» (применительно к системе Papyrus это будет означать, что у соответствующего товара следует установить атрибут «торговая марка» в значение с именем «del monte»).
Ниже я приведу более сложный пример использования сигналов.
%= Оператор именования кортежа. Обычно следует за кластером для присвоения ему имени с целью последующего использования.
Кластеры я рассмотрю ниже, здесь лишь приведу простой вводный пример кортежа:
```
%{ l'oreal garnier revlon %}%=brandbeauty 
```

Кластеры

Кластеры необходимы для упрощения набора правил.
Синтаксически кластер оформляется метасимволами %{ и %} в начале строк, а содержимое кластера размещается в строках между этими.
После определения кластера должен следовать оператор.
Пример кластеризованного оператора изменения регистра:

%{ edt edp edc bic lg cd usa e%_ qvs vs vsop xo пва пдд эпра сзлк авк свфс %}%A

Кортежи

По кортежам я уже прошелся довольно подробно. Здесь приведу пример определения и использования кортежа:

%{ %dml %dl %dл %dмл %}%=volume  PET %1%<pet%z%(%@volume.%)%|(p.e.t%.)%.%z%(%@volume.%)%|p.e.t%.%z%(%@volume.%)%|(pet)%.%z%(%@volume.%)

В этом примере унифицируется обозначение полиэтиленовой тары перед определением емкости бутылки. Для того, чтобы не перечислять все возможные единицы измерения емкости с числовой величиной мы объединили их в кортеж с именем volume. Замечу, что мы не может просто так сформулировать правило замены «PET%<pet%|(p.e.t%.)%|p.e.t%.%|(pet)%.» поскольку вне контекста емкости тары исходные выражения могут иметь совсем иной смысл.

Обещанный сложный пример использования сигналов

Предприятие, торгующее автомобильными шинами, из своей корпоративной системы экспортирует в свой-же интернет-магазин наименования товаров с остатками и ценами. У себя в офисе все удовлетворены наименованиями и прочими классификаторами товаров. Вместе с тем, на интернет-площадке потенциальный клиент должен иметь возможность выбрать шины по типоразмеру, группе, брэнду.
Следующий пример демонстрирует процесс переформатирования наименований товаров, пришедших из офисной системы на сервере, управляющем интернет-магазином с последующей расстановкой числовых параметров типоразмеров шин. Оговорюсь, что пример, хоть и реальный, но редуцированный — здесь формализуются только типоразмеры, содержащиеся в наименовании в формате «w/h Rd».

%{ автошина специальная автошина %}%=tiretitle  %(%@tiretitle.%) %(%f/%d%)x%(%f%)%>%1 %2 R%3 %(%@tiretitle.%) %(%f%)x%(%f%)%>%1 %2 R%3  %(%@tiretitle.%) %(%f/%d%)%(R%f%)%>%1 %2 %3 %(%@tiretitle.%) %(%f/%d%)%(R%f%)%>%1 %2 %3 %(%@tiretitle.%) %(%f%)%(R%f%)%>%1 %2 %3 %(%@tiretitle.%) %(%f%)%(R%f%)%>%1 %2 %3  %(%@tiretitle.%) %(%f/%d R%f%) с%>%1 %2c %(%@tiretitle.%) %(%f/%d R%f%) c%>%1 %2c %(%@tiretitle.%) %(%f R%f%) с%>%1 %2c %(%@tiretitle.%) %(%f R%f%) c%>%1 %2c  %@tiretitle. %(%d%)/%(%d%)%sr%(%f%)%!class=tire; gcdimx=%1; gcdimz=%2; gcdimy=%3

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

Производительность

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

Что мы предприняли с целью оптимизации скорости выполнения

Прежде всего, как упоминалось выше, процесс сравнения осуществляется на уровне целочисленных идентификаторов лексем. Само по себе это сильно облегчает задачу, переводя ее размерность из терминов символьных длин текста и правил в термины количественной оценки цепочек лексем.
Чтобы сократить константное время выполнения итерации сопоставления исходного выражения правила с текстом пришлось избавиться (на сколько это возможно) от операций распределения и освобождения памяти. Все буферы, будучи однажды распределенными, используются повторно на последующих итерациях.
Наконец, самое существенное ускорение (уменьшающее размерность задачи) достигается за счет индексации текста, подлежащего процессингу. Индексация, в общем, ничего нового из себя не представляет: индекс составлен по каждой лексеме, входящей в текст, и сопоставляет ей номера позиций в тексте, где она встречается. Так как мы используем обобщенные классы, определяемые метасимволами, то вхождения многих из них в текст так же индексируются (вплоть до цифровых последовательностей каждой из 99 возможных длин).
Очевидно, здесь ускорение достигается за счет быстрой идентификации факта отсутствия лексемы в тексте либо быстрого перехода на искомую позицию тексте.
Теоретическую оценку сложности результирующего алгоритма мы не выводили, но абсолютное время работы на тесте, выполняющем в общей сложности более 4E9 операций сопоставления, улучшилось на треть.
Каюсь, не помню как он называется, но есть классический алгоритм для простого сравнения множества образцов с текстом, с похожей индексацией.

В общем итоге, упомянутый ранее процессинг справочника товаров на Universe-HTT, содержащего более 1300000 наименований по набору из нескольких тысяч правил, составляет 3 с половиной часа. Если кто-то может подсказать с чем бы это сравнить — буду благодарен.

Что дальше?

Все, чего не забыл, рассказал. Осталось проинформировать общественность о том, чего не хватает.
Есть несколько важных штрихов, которые следует добавить к описанной технологии:

Контексты (о них я написал чуть выше). В общих чертах идея в том, чтобы задавать набор выражений, которые должны встретиться в тексте для того, чтобы некоторые правила имели могли быть применены.
Стемминг. Необходимо ввести в язык конструкцию, которая бы позволяла сравнивать лексемы с учетом стемминга.
Директива include для включения файлов, например, с подготовленными кортежами (список городов, брэндов, и т.д.).
Директива упрощенного синтаксиса. Уж очень тяжело выглядят символы процентов — в некоторых случаях можно было бы включить упрощенный синтаксис и использовать просто символы (){}<>! как служебные. Если же возникает вероятность путаницы — отключать упрощенный синтаксис.

ссылка на оригинал статьи http://habrahabr.ru/post/202502/