Методы анализа текста
Задача обработки и анализа текста часто встречается в практике при анализе не очень качественных данных или данных, объединенных из информационных систем нескольких предприятий. Важная для анализа информация часто фиксируется в неожиданных местах: например, ФИО ответственного – в комментариях к документам, внешний номер договора – в названии файла вложения. Чтобы структурировать такие данные, нужно сопоставить их с заранее подготовленным списком. Другой случай: текстовые поля системы (наименования контрагентов, адреса доставки продукции, статьи затрат, наименования номенклатуры и другие). Когда за такими полями в системе не организован должный контроль, без предварительной обработки они часто непригодны для анализа.
Любая задача обработки текста в итоге сводится к задаче сравнения строк. Необходимо оценить, насколько похожи два текста, и в зависимости от этого, например, объединить их в одну группу или разнести в отдельные. При этом важно, чтобы мера близости текста была непрерывной. Недостаточно ответить на вопрос, равны ли строки, нужно сказать, насколько они отличаются. К счастью, существует множество методов, которые решают эту задачу.
К таким методам относится, например, метод/ алгоритм шинглов (от англ. shingles — чешуйки). Тексты документов разбиваются на последовательности соседних букв – их называют «шинглы», или «n-граммы». Например, слово «текст» может быть разбито на такие триграммы: «тек», «екс», «кст». Длинна n-грамм выбирается эмпирически. После этого, в качестве меры сходства двух строк выступает коэффициент Жаккара, который рассчитывается по формуле:
где а — количество уникальных n-грамм в первой строке, b — количество уникальных n-грамм во второй строке, с — количество совпадающих n-грамм в обеих строках.
Другие методы основаны на расчете дистанции редактирования. Этот термин ввел Владимир Иосифович Левенштейн в 1965 году. Он обозначает разницу между двумя строками, измеряемую минимальным количеством операций вставки, удаления и замены, необходимым для преобразования одной строки в другую. Разницу, рассчитанную с применением только 3-х данных операций, называют расстоянием Левенштейна. Позже Фредерик Дамерау дополнил расчет операцией транспозиции – перестановки двух соседних символов. Меру с учетом этой перестановки называют расстоянием Дамерау-Левенштейна. Расстояния редактирования используют для сравнения небольших строк или отдельных слов. При этом важно, чтобы строки были сопоставимой длины.
Существуют и другие подходы: нахождение наибольшей общей последовательности, фонетические методы и другие. Отдельный класс методов основан на векторном представление текста, которое может быть реализовано даже с использованием нейронных сетей (word2vec или fastText). Многие алгоритмы расчета реализованы в современных языках (например, Python или R), достаточно импортировать необходимую библиотеку и воспользоваться готовой функцией. Каждый метод имеет свои преимущества и недостатки и должен рассматриваться к применению в контексте конкретных задач.
Проблема дублей номенклатурного справочника
Один из практических кейсов, в котором были использованы методы работы с текстом, – это задача поиска дублей в номенклатурном справочнике. Этот справочник является ключевым звеном в системе учета хозяйственной деятельности предприятия. Все основные бизнес-процессы в информационных системах ведутся с его использованием.
На промышленных предприятиях часто встречается проблема наличия дубликатов номенклатурных записей. Самый распространенный сценарий их возникновения: специалист, имеющий полномочия заведения новой номенклатуры, не нашел подходящей записи среди существующих и внес новую. Особенно остро этот вопрос стоит в случае, когда ведение справочника децентрализовано, то есть права на внесение записей в единый справочник системы есть у многих пользователей различных служб. Но и при централизации этого процесса остается актуальным вопрос качества алгоритма поиска, так как перед добавлением новой записи необходимо убедиться в ее отсутствии в справочнике.
Наличие дублей номенклатурных записей приводит к потере контроля за складскими запасами. При наличии запаса ТМЦ по одной из номенклатурных записей, отчеты системы сигнализируют об их дефиците по дублирующей записи, производится избыточная закупка ТМЦ. Как результат: рост запасов, снижение оборачиваемости, увеличение потребности в оборотном капитале.
Алгоритм поиска дублей
Интуитивное решение задачи подразумевает определение подпоследовательностей, которыми отличаются наименования номенклатур. Например, номенклатура «БОЛТ ГОСТ 7798 70 16Х40.58» полностью содержит все характеристики номенклатуры «БОЛТ СТАНДАРТНЫЙ 16Х40.58 ГОСТ7798-70». Уточняющее слово «СТАНДАРТНЫЙ» в данном случае не несет дополнительной информации, т.к. первая номенклатура не содержит такого уточнения и потому является обобщающей для всех болтов данного ГОСТа и типоразмера. Укрупненная схема разработанного алгоритма сравнения представлена ниже:
Алгоритм подразумевает различный подход при сравнении описательных характеристик номенклатуры (слов) и технических характеристик. К последним были отнесены слова длиной менее 3-х символов или содержащие хотя бы 1 цифру. Для сравнения слов наилучший результат показал упомянутый ранее метод шинглов. Для технических характеристик был использован метод, представляющий собой последовательный поиск и удаление наибольшей общей подстроки.
Использование особого метода сравнения для технических характеристик номенклатуры вызвано необходимостью обеспечить полное их совпадение. Различие даже в одном символе часто обозначает разные объекты (например, буквами L и R часто отличают левое или правое исполнение детали). При этом может не совпадать порядок следования характеристик, они могут быть разделены пробелами или написаны слитно.
В рассмотренном выше примере технические характеристики «ГОСТ 7798 70 16х40.58» и «16х40.58 ГОСТ7798-70» идентичны. Но выделение и сравнение по словам не даст результата, т.к. часть характеристик написаны слитно, часть – раздельно. Расстояние Дамерау-Левенштейна, при условии удаления всех пробелов, составит 17 при длине строки 18 символов. Количество совпавших биграммам будет 15 из 20 уникальных для двух строк, триграмм – 12 из 21. Подбор критериев для положительного срабатывания при использовании этих методов в данном примере, приведет к ложному срабатыванию для других пар номенклатур, например таких как «КЛЮЧ 12x14» и «КЛЮЧ 12x13».
Для приведенного примера технических характеристик алгоритм последовательного удаления наибольшей общей подстроки через 2 итерации вернет пустые подпоследовательности.
Результаты тестирования
Выявить все дубли в номенклатурном справочнике – это только половина работы. Если с дублирующей записью уже были созданы какие-либо документы, ее невозможно удалить, не нарушив целостность данных. Такие записи, как правило, закрывают для использования (т.е. физически номенклатура есть в справочнике, но использовать в документах ее нельзя). Если же на номенклатуре числятся остатки запасов, то ее нельзя даже закрыть. Эти остатки нужно использовать (списать) или перенести учет на другую запись. У каждого из этих подходов есть свои плюсы и минусы, в нашей организации используют первый вариант. Организован справочник учета дублей и аналогов, в нем, в том числе, учитываются пары дублирующих номенклатур до тех пор, пока не будут израсходованы остатки. Такой подход стал большой удачей, так как на предприятии сохранилась история выявленных ранее дублей. Она была использована для проверки качества работы разработанного алгоритма.
Представленный алгоритм был реализован с использованием языка программирования Python. Перед его использованием необходимо было убедиться, что он работает корректно и способен идентифицировать дубли. Для оценки качества работы алгоритма использован список пар из справочника аналогов и дублей. Он был дополнен контрольными примерами не дублирующих друг друга, но похожих номенклатур. Это необходимо для контроля ложных срабатываний – когда алгоритм ошибочно помечает пары номенклатур как дубли.
При проверке качества работы алгоритма была однозначно идентифицирована большая часть дублирующих записей. В тех случаях, когда дубль не был идентифицирован, алгоритм вернул подстроки, на которые отличаются сравниваемые пары. Часть из них представляет собой единицы измерения, названия фирм производителей или другие несущественные характеристики. Для более полного выявления дублей эти слова могут быть исключены перед выполнением алгоритма вместе с пробелами, предлогами и неинформативными символами.
В дальнейшем полученный алгоритм может быть использован для организации работы по нормализации действующего номенклатурного справочника предприятия. Также, возможно интегрировать его в информационную систему для поиска наименований среди существующих номенклатур перед добавлением новых записей. Это позволит поддерживать справочник в нормализованном состоянии.