Вот наконец-то дошли руки описать результат работы над небольшим проектом — библиотекой на C# для сопоставления строки шаблону (который продолжаю делать и дорабатывать в рамках проекта по-больше).
Суть его такая — есть текст и есть некий шаблон, представленный словами различными операторами. Пример шаблона: (зима | снег | снежн*) & (лёд | гололёд | скользк*)
Этот шаблон можно сопоставить с некоторой строкой — например: «этой зимой очень много снега, из под которого не видно льда вообще…». Строка токенизируется и превращается в массив слов, которые надо сопоставить с шаблоном и определить — соответствует ли он массиву токенов или нет.
Сам шаблон в свою очередь парсится, в результате чего формируется список терминалов и нетерминалов. К каждому терминалу из морфологического словаря подбираются словоформы (если они есть в словаре и если перед токеном не стоит оператор «=» ). Далее с помощью алгоритма сортировочной станции список преобразуется в список в обратной польской нотации (если бы это было арифметическое выражение 1 + 2, то в обратной польской нотации будет 1 2 + ). Далее из него строим бинарное дерево синтаксического разбора, которое при рекурсивной реализации каждой из нод сопоставляется с массивом токенов (нашим текстом). На выходе корень возвращает булево значение — true, если шаблон соответствует строке, и false, если нет.
Нетерминалы в языке формирования шаблонов сделал такие:
& — это AND
| — OR
~ — NOT
«слово1 слово2» — кавычки для идентификации нескольких слов как одного терминала.
/n — максимальное расстояние между операндами (где операндами могут быть как терминальные, так и нетерминальные выражения), где n — целочисленное значение
( и ) — скобки
= — не брать словоформы из словаря для терминала
* — взять из словаря словоформы слов, начинающихся на всё, что идет до звездочки
На мой взгляд, самое хорошее тут, это оператор расстояния. Во всяком случае, мне он нужен очень-очень, но не в виде типа «слово1 слово2″~n — то есть где оператор расстояния работает только с терминалами.
Библиотека на гитхабе ВОТ ТУТ.
Сделал небольшое настольное демо (большей частью для тестов). Вот пример работы:
В третьем поле результат разбора шаблона уже вместе со словоформами.
Мне эта библиотека нужна для проекта чат бота — нужно сопоставлять большое количество шаблонов текста с сообщением пользователя. Собственно, в том же репозитории, что и эта библиотека стал делать проект по чатботу. Потому что так удобнее мне, хоть это и нехорошо 🙂
P.S. Библиотека написана на C#, .NET STANDARD. Бд для словаря — MS SQL.