Процессинг текстовых объектов в 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 для включения файлов, например, с подготовленными кортежами (список городов, брэндов, и т.д.).
• Директива упрощенного синтаксиса. Уж очень тяжело выглядят символы процентов — в некоторых случаях можно было бы включить упрощенный синтаксис и использовать просто символы (){}<>! как служебные. Если же возникает вероятность путаницы — отключать упрощенный синтаксис.

Автор: antonsobolev

Источник