Разбор естественного языка: под капотом
API синтаксического анализатораПродолжаю свой предыдущий пост. Время сфокусироваться на деталях внутреннего устройства синтаксического анализатора. В качестве языка реализации я выбрал Go, поскольку хотел малой ценой получить параллельный (в смысле, использующий все доступные ядра CPU) производительный инструмент, без погружения в низкоуровневую пучину C++.Полученный код предоставляет следующий API:
type Attribute struct { Name string Value string }
type ParseMatch struct { Text string Nonterminal string Rule string Attributes []Attribute Submatches []ParseMatch Hypotheses []string HypothesisCount uint }
func Parse (text, nonterminal string, hypotheses_limit uint) []ParseMatch Match ссылается на дочерние объекты того же типа, соотвествующие нетерминалам или лексическим терминалам подошедшего правила. В общем случае, из-за неоднозначности, присущей естественным языкам, тексту соответствует несколько разборов (например, из-за наличия омонимов). Поэтому функция Parse возвращает множество объектов Match. Вышеупомянутая неоднозначность синтаксического разбора должна устраняться на следующем (семантическом) уровне анализа текста.Итак, функция Parse берёт text — текст для разбора, nonterminal — название нетерминала (например, «sentence»), а также максимальное число выдвигаемых гипотез hypotheses_limit (об этом чуть ниже). Параметр nonterminal может быть пустым. В этом случае тексту будет сопоставляться лексический терминал, найденный в морфологической базе.
В терминах данного анализатора гипотеза — это предположение того, что нарушенное ограничение значения атрибута вызвано случайной причиной. Если анализатор встречает несоответствие значения атрибута ограничению, заданному рассматриваемым в данный момент правилом, а число выдвинутых гипотез не достигло hypotheses_limit, то данное несоответствие игнорируется. В противном случае рассматриваемое правило отбрасывается. Данный механизм удобен для отладки правил, но должен избегаться в реальной работе, поскольку чудовищно замедляет процесс разбора.
Сопоставление нетерминалов Прежде чем погружаться в описание этого процесса стоит отметить, что в общем случае сопоставляется не весь текст, а лишь его начало. Анализатор находит все возможные начальные части текста, соответствующие данному нетерминалу (или все лексические терминалы вначале текста).Для данного нетерминала анализатор извлекает все соответствующие правила (исходя из грамматики) и пытается найти соответствия каждому из них. Так, для каждого такого правила анализатор проверяет наличие присвоения значений атрибутов (»@{…}», должно быть вначале правила). Далее вызывается рекурсивная функция parseRulePart, которая последовательно производит следующие действия:
В случае наличия в текущем месте правила терминала сопоставляет его тексту. В случае наличия в текущем месте правила нетерминала или лексического терминала вызывает функцию Parse. Проверяет выполнение ограничений на значения атрибутов для полученных Match-объектов. Для каждого из подходящих Match-объектов функция вызывает саму себя в новом потоке (goroutine) для сопоставления оставшейся части правила. Match-объекты, возвращённые созданными потоками, расширяются данными из текущего Match-объекта и возвращаются. Сопоставление лексических терминалов С одной стороны лексические терминалы могут легко извлекаться из текста путём поиска символов, отделяющих слова друг от друга (пробел, запятая, и т.д.). С другой стороны существуют устойчивые словосочетания, содержащие в себе такие символы. Рассматриваясь в качестве неделимых лексических единиц они могут иметь другие значения атрибутов и даже другой смысл (что особенно важно для последующего семантического анализа). Поэтому сопоставление лексических терминалов производится следующим образом: Из текста извлекается терминал, ограниченный символом, разделяющим слова. В морфологической базе находятся все лексические терминалы, начинающиеся с извлечённого терминала. Из полученных лексических терминалов выбираются те, что соответствуют данному тексту. Морфологическая база Я использую морфологический словарь русского языка, скачанный с сайта OpenCorpora. Для использования синтаксическим анализатором эти данные должны быть минимизированы и индексированы. Сначала я пробовал для этой цели использовать SQLite, но полученное решение имело неудовлетворительную производительность (даже после включения кэширования). Поэтому пришлось реализовывать специализированную морфологическую базу. Замеры показали примерно 9-кратное ускорение поиска и более чем 300-кратное ускорение начальной индексации.Формат файла морфологической базы достаточно прямолинеен: заголовок + две большие части. Первая часть состоит из сортированных словоформ, разделённых символом '\0'. Второй частью является массив структур, содержащих 32-битное смещение текста соответствующей словоформы и упакованные в 32-бита значения её атрибутов. Для высокой скорости поиска обе части морфологической базы полностью загружаются в оперативную память.
Полученный код предоставляет следующий API:
func BuildMorph (txt_filename, morph_filename string) error func InitMorph (morph_filename string) error func FinalizeMorph () func FindTerminals (prefix, separator string) []ParseMatch Функция FindTerminals принимает дополнительный параметр разделителя, поскольку в случае устойчивого словосочетания он является его неотъемлемой частью, в противном же случае разделитель оказывается не нужным и должен быть отброшен.Кэш разбора Даже после ускорения поиска словоформ общая производительность разбора оставляла желать лучшего (разбор распространённых предложений длился несколько секунд). Поскольку структура разработанной грамматики предполагает многократные сопоставления текста одним и тем же нетерминалам (наличие множества похожих правил), то напрашивалось применение кэширования. Поэтому, прежде чем начинать разбор, функция Parse проверяет наличие такого (произведенного ранее) разбора в кэше.Поскольку в основе кэша лежит хэш-таблица, то для поддержки параллельного доступа требуется защищающий мьютекс. Однако один глобальный мьютекс может стать узким местом, поэтому кэш разбивается на нужное число банков, каждый из которых состоит из хэш-таблицы и соответствующего защищающего мьютекста.
Использование анализатора Для использования разработанного анализатора требуется: Скачать морфологический словарь. Собрать на его основе морфологическую базу (morph.bin, см. main.go). Дополнять/изменять правила грамматики в файле rules.yaml. Быть любознательным и ловить кайф от исследований.
