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

в 14:13, , рубрики: data mining, ERP-системы, nlp, Алгоритмы, обработка текстов, метки: ,

Необходимость сложной обработки текстовых данных, хранящихся в 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

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js