Мечта о том, чтобы машина понимала человеческий язык, завладела умами еще когда компьютеры были большими, а их производительность – маленькой. Главная проблема на пути к этому заключается в том, что грамматика и семантика естественных языков слабо поддаются формализации. Кроме того, от языков программирования их отличает присутствие многозначности.
Конечно, мечта о полноценной коммуникации с компьютером на естественном языке пока еще далека от полноценной реализации примерно настолько же, как и мечта об искусственном интеллекте. Однако некоторые результаты есть уже сейчас: машину можно научить находить нужные объекты в тексте на естественном языке, находить между ними связи и представлять необходимые данные в формализованном виде для дальнейшей обработки. В Яндексе уже достаточно давно применяется такая технология. Например, если вам придет письмо с предложением о встрече в определенном месте и в определенное время, специальный алгоритм самостоятельно извлечет нужные данные и предложит внести ее в календарь.
Вскоре мы планируем отдать эту технологию в open source, чтобы любой мог пользоваться ей и развивать ее, приближая тем самым светлое будущее свободного общения между человеком и компьютером. Подготовка к открытию исходных кодов уже началась, но процесс этот не такой быстрый, как нам бы хотелось, и, скорее всего, продлится до конца этого года. За это время мы постараемся как можно больше рассказать о своем продукте, для чего запускаем серию постов, в рамках которой расскажем об устройстве инструмента и принципах работы с ним.
Называется технология Томита-парсер, и по большому счету, любой желающий может воспользоваться ей уже сейчас: бинарные файлы доступны для скачивания. Однако прежде чем пользоваться технологией, нужно научиться ее правильно готовить.
Алгоритм GLR
Назван инструмент в честь японского ученого Масару Томита, автора алгоритма GLR-парсинга (Generalized left-to-right algorithm), на основе которого и был создан Томита-парсер. Еще в 1984 году он описал имплементацию этого алгоритма, поставив перед собой задачу эффективно и точно производить анализ текстов на естественном языке. В некотором роде GLR-алгоритм — это расширенная версия алгоритма LR-парсинга. Но LR-алгоритм предназначен для анализа текстов, написанных на достаточно строго детерминированных языках программирования, и с естественным языком работать не может. Томита решил эту проблему путем параллелизации стеков, что позволило рассматривать различные трактовки тех или иных участков текста: как только возникает возможность различной трактовки, стек разветвляется. Таких последовательных разветвлений может быть несколько, но в процессе анализа ошибочные ветви отбрасываются, и результатом становится наиболее длинная цепочка. При этом алгоритм выдает результаты своей работы в режиме реального времени, по мере продвижения вглубь текста, другие алгоритмы обработки естественного языка такой особенностью не обладают.
Однако одного лишь алгоритма для полноценного анализа текста и извлечения из него структурированной информации недостаточно. Нужно учитывать морфологию и синтаксис языка обрабатываемого текста, подключить необходимые словари, понятные парсеру. Все это было доступно только лингвистам с опытом программирования. Томита-парсер разрабатывался специально с прицелом на упрощение работы с алгоритмом. Был составлен несложный синтаксис для создания словарей и грамматик, продумана работа с морфологией русского и украинского языков. Теперь при должном упорстве и понимании устройства русского языка, разобраться в синтаксисе и подготовить парсер для своих целей может практически любой. Конечно, более глубокие познания в лингвистике и умение работать с регулярными выражениями будет безусловным плюсом, но уже не обязательным условием.
Где используется Томита
На сегодняшний день Томита используется в четырех сервисах Яндекса:
- Почта. Как уже говорилось выше, если вам придет письмо, в котором вам в произвольной форме предлагают встретиться, Томита определит, где и когда будет проходить эта встреча, и предложит внести ее в календарь. Примерно так же обстоит дело с авиабилетами.
- Новости. В этом сервисе Томита помогает автоматически осуществлять географическую привязку и группировку новостных сюжетов. Если в заметке упоминается название страны, города или полный адрес места, где произошло описываемое событие, Томита выделит эту информацию и привяжет заметку к точке на карте.
- Авто.
Сервис Яндекс.Авто агрегирует отзывы об автомобилях с различных площадок, там же можно оставить свой отзыв. Томита анализирует эти отзывы, оценивает эмоциональную окраску высказываний о различных характеристиках автомобилей. На основе этих данных составляется рейтинг характеристик: внешний вид, ходовые качества, салон и комфорт, эксплуатация, впечатления. - Работа. Подобно Яндекс.Авто Работа собирает с разных площадок объявления о поиске работников. Они также обычно составляются в произвольной форме. Томита анализирует эти тексты и выделяет требования к кандидатам и условия работы, формализует из, благодаря чему при поиске работы пользователи могут фильтровать вакансии.
Как все это работает на практике
В минимальной конфигурации парсеру на входе отдается сам анализируемый текст, а также словарь и грамматика. Объем словаря и сложность грамматики зависят от целей анализа: они могут быть как совсем маленькими, так и огромными. Файл грамматики состоит из шаблонов, написанных на внутреннем языке/формализме Томита-парсера. Эти шаблоны описывают в обобщенном виде цепочки слов, которые могут встретиться в тексте. Кроме того, грамматики определяют, как именно нужно представлять извлеченные факты в итоговом выводе.
В словарях содержатся ключевые слова, которые используются в процессе анализа грамматиками. Каждая статья этого словаря задает множество слов и словосочетаний, объединенных общим свойством. Например, «все города России». Затем в грамматике можно использовать свойство «является городом России». Слова или словосочетания можно задавать явно списком, а можно «функционально», указав грамматику, которая описывает нужные цепочки.
Ниже приведена грамматика, которая помогает извлечь из текста на естественном языке и связать друг с другом имя режиссера, название и жанр фильма, который он снял. Также приведен словарь, в котором перечислены различные жанры и фоврмы, в которых они могут употребляться в тексте.
#encoding "utf-8"
#GRAMMAR_ROOT S
PersonName -> Word<h-reg1, nc-agr[1]> Word<h-reg1, nc-agr[1]>*; //имя собственное - цепочка, состоящая из одного или более слов с большой буквы и согласованных между собой в числе и падеже
FilmName -> AnyWord<h-reg1, quoted>; //название фильма - слово с большой буквы в кавычках
FilmName -> AnyWord<h-reg1, l-quoted> AnyWord* AnyWord<r-quoted>; //то же самое, но для двух и более слов
GenreChain -> Word<kwtype=genre_type> interp (Film.Genre); //жанр - цепочка, которую грамматика берет из словаря из статьи с типом genre
Film -> 'фильм'; //в качестве шаблона может выступать конкретная лемма
Descr -> GenreChain | Film; //объединение двух ранее описанных шаблонов
Director -> PersonName interp (Film.Director); //цепочку PersonName необходимо положить в поле Director факта Film
S -> Descr Director<gram="род"> FilmName interp (Film.Name::not_norm); //так называемая терминальное правило - вершина дерева. Пример цепочки, попадающей под это правило: Комедия Владимира Меньшова "Любовь и голуби"
//для каждой статьи обязательно должен быть указан тип (в данном случае genre), название и ключ - содержание статьи
genre_type "комедия_1"
{
key = { "романтический комедия" agr=gnc_agr } //слова в ключе должны быть указаны в начальной форме
key = { "лирический комедия" agr=gnc_agr } //можно указывать согласование между словами ключа
key = { "музыкальный комедия" agr=gnc_agr }
mainword = 2 //синтаксически главное слово ключей
lemma = "комедия" //форма, к которой будут приводится все ключи статьи при нормализации
}
genre_type "комедия_2" //название статьи должно быть уникальным
{
key = "комедия"
lemma = "комедия" //леммы могут повторяться
}
genre_type "фильм_ужасов"
{
key = { "фильм ужас" gram={"род,мн", word=2} }
key = "ужастик" | "хоррор"
lemma = "фильм ужасов"
}
genre_type "боевик"
{
key = "боевик"
lemma = "боевик"
}
Как видно из примеров, в грамматике мы первым делом определяем имя и фамилию режиссера в качестве цепочки слов, состоящих их одного или более слов с заглавной буквы, согласованных между собой по числу и падежу. Далее мы указываем, как опознать название фильма: это должно быть одно или несколько слов, заключенные в кавычки, при этом первое слово должно начинаться с заглавной буквы. Для определения жанровой принадлежности фильмов мы ссылаемся на специально подготовленный словарь с жанрами. В словаре содержатся статьи, помеченные тем типом, на который ссылается грамматика. Каждая статья состоит из названия, ключей и леммы. Один или несколько ключей отражают, как то или иное понятие может быть отображен в тексте, при этом можно указывать варианты согласования между словами в ключе. Лемма же – это та форма, к которой будут приводиться все ключи при нормализации, так все будет отображаться в итоговой таблице с фактами.
Вы можете попробовать самостоятельно провести такой же разбор текста о кино. В архиве по ссылке собраны все необходимые для работы файлы и примеры предложений, подходящих под составленные нами шаблоны.
Как использовать Томиту в своих проектах?
В виде бинарных пакетов под Windows, OS X и Linux Томита-парсер доступен уже сейчас, но разобраться самостоятельно в том, как составлять свои грамматики и словари, не так уж просто. Поэтому мы подготовили серию обучающих видео. В следующем посте мы постараемся дать чуть более подробное описание синтаксиса и принципов работы с Томитой на основе этих уроков. Ну а самые нетерпеливые и упорные уже сейчас могут ознакомиться с видео и документацией.
Автор: tlando
