- PVSM.RU - https://www.pvsm.ru -
Продолжаю свой предыдущий пост [1]. Время сфокусироваться на деталях внутреннего устройства синтаксического анализатора. В качестве языка реализации я выбрал 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, которая последовательно производит следующие действия:
С одной стороны лексические терминалы могут легко извлекаться из текста путём поиска символов, отделяющих слова друг от друга (пробел, запятая, и т.д.). С другой стороны существуют устойчивые словосочетания, содержащие в себе такие символы. Рассматриваясь в качестве неделимых лексических единиц они могут иметь другие значения атрибутов и даже другой смысл (что особенно важно для последующего семантического анализа). Поэтому сопоставление лексических терминалов производится следующим образом:
Я использую морфологический словарь русского языка, скачанный с сайта OpenCorpora [2]. Для использования синтаксическим анализатором эти данные должны быть минимизированы и индексированы. Сначала я пробовал для этой цели использовать SQLite, но полученное решение имело неудовлетворительную производительность (даже после включения кэширования). Поэтому пришлось реализовывать специализированную морфологическую базу. Замеры показали примерно 9-кратное ускорение поиска и более чем 300-кратное ускорение начальной индексации.
Формат файла морфологической базы достаточно прямолинеен: заголовок + две большие части. Первая часть состоит из сортированных словоформ, разделённых символом ''. Второй частью является массив структур, содержащих 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 проверяет наличие такого (произведенного ранее) разбора в кэше.
Поскольку в основе кэша лежит хэш-таблица, то для поддержки параллельного доступа требуется защищающий мьютекс. Однако один глобальный мьютекс может стать узким местом, поэтому кэш разбивается на нужное число банков, каждый из которых состоит из хэш-таблицы и соответствующего защищающего мьютекста.
Для использования разработанного анализатора [3] требуется:
Автор: ababo
Источник [5]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/diy-ili-sdelaj-sam/88859
Ссылки в тексте:
[1] предыдущий пост: http://habrahabr.ru/post/255073/
[2] OpenCorpora: http://opencorpora.org
[3] анализатора: https://github.com/ababo/idiot
[4] морфологический словарь: http://ababo.github.io/files/2015-03/dict.opcorpora.txt.zip
[5] Источник: http://habrahabr.ru/post/255711/
Нажмите здесь для печати.