Открыть изображение »
Извлечение фактов из текста. Дубль два
23 марта 2014 :: 13 комментариев :: 10228 просмотров :: 681 слово

Некоторое время назад у меня был пост про Томита-парсер, инструмент извлечения структурированных данных из текста на естественном языке, открытый компанией Яндекс для всех желающих уже более года назад. В том посте я уделил особое внимание тому, зачем всё это нужно, потому чтобы не повторяться, отправляю всех пропустивших туда.

В конце я даже написал небольшую обертку, позволяющую запускать Томита-парсер из питона и получать данные в него же. Уже на этом этапе я заметил, что Томита-парсер в том виде, в котором предлагает нам его Яндекс, использовать очень больно. А погружение в документацию дает вдумчивому читателю ясное понимание того, что перед ним всего лишь верхушка того золотого айсберга, который разработали и используют в Яндексе. Простой пример: в списке помет есть упоминание geo-agr — согласование двух слов «по геотезаурусу», что кажется очень интересной фичей, однако поиск по всей документации говорит, что это единственное упоминание географического тезауруса вообще, и скорее всего при составлении этой страницы просто спалили кусок внутренней документации и не заметили. Таких ляпов можно встретить еще несколько, если просто внимательно прочитать эту небольшую документацию.

Впрочем, это всё лишь подчеркивает насколько инструмент извлечения фактов важен для Яндекса сам по себе, и что показали его простым смертным лишь с целью «подразнить», предварительно выпилив и тщательно скрыв в недрах бинарника все конкурентные фичи. Ну а мы люди взрослые, понимаем как и зачем это бывает. «Подсаженные» на Томита-парсер разработчики имеют лишь два выхода: идти в Яндекс за новой дозой, либо научиться варить самостоятельно писать свой велосипед. В общем для меня вопрос стоял лишь хватит ли моих скиллов или нет.

Рабочая неделя выдалась весьма расслабленная, потому начав на прошлых выходных и усердно просидев над ним всю неделю, на этих выходных я родил первую версию.

https://github.com/vas3k/python-glr-parser

Для начала я пошел искать существуют ли реализации алгоритма GLR парсинга на питоне вообще. Питонячая вики рассказала, что действительно есть несколько реализаций, однако практически все они не подходили по разным причинам: первые не обновлялись с какого-нибудь 1999 года, вторые были монстрами с ООП головного мозга, которые требовали записывать грамматику с помощью специальных объектов, а один вообще ничего кроме python 3.x не поддерживал (первый случай в моем опыте, когда я встретил библиотеку только для python 3.x, хотя потом всё же нашел форк под 2.7, который судя по pypi даже популярнее оригинала). В итоге был найден практически удовлетворивший требованиям анализатор — jupyLR. Кроме местами кривого кода и чрезмерного увлечения PEP8 и списковыми выражениями, минусов обнаружено не было, грамматики записывались обычным текстом и он просто работал.

Однако все представленные парсеры разрабатывались с целью парсить строго структурированные языки, например, программирования. В отличии от текстов на естественном языке, в которых бОльшая часть данных является словестным мусором, в них нет лишних объектов и парсеры для них не умеют «забить и пойти дальше». Примерно это мне нужно было реализовать в первую очередь. А еще:

1) Прикрутить pymorphy2 для морфологического анализа;

2) Научиться на лету понимать новые нетерминалы из грамматики, для поддержки 'слов в кавычках';

3) Сделать поддержку словарей, чтобы уметь делать свертки-переносы именно по словарю;

4) Сделать поддержку лейблов как в томите, чтобы уметь указывать грамматические характеристики, а так же сочетаемость слов по роду/числу/падежу.

Прикручивание поддержки частей речи через pymorphy2 оказалось самым простым, в грамматику были введены дополнительные нетерминалы соответствующие определенным частям речи, всё остальное делалось самим GLR парсером. Кроме того к каждому токену сразу добавлялись все его грамматические характеристики, чтобы дальше можно было реализовать лейблы.

Слова 'в кавычках' оказались посложнее. Они требовали добавления нетерминалов в грамматику «на лету», так что пришлось модифицировать парсер грамматик. Но в остальном тоже работали нормально.

Словари оказались первым подводным камнем. Пробегать весь словарь на каждом переносе, а потом учитывать его при свертках было не очень оптимальным решением. Потому было решено приводить словарь к 'словам в кавычках' и каждое слово словаря делать нетерминалом.

Лейблы оказались самым крепким орешком. Не понятно было где их учитывать, при переносе было бы невозможно реализовать лейблы согласования (согласуемое слово обычно еще не перенесено в стек). При свертке надо правильно определять правило, к которому применять лейблы. А потом еще и правильно «падать» если свертка успешно прошла, но лейблы не удовлетворились. В итоге на них ушло почти два полных дня и нервов столько, что я уже хотел было сворачивать проект.

Но в итоге мы видим то, что есть на гитхабе. Как-то оно работает. Документация там же.

Еще? Тогда вот
Комментарии
0
Sergey Slepov ⸬ 19 апреля 2014, 23:04 ⸬ Hammersmith, GB ⸬ Windows лог
#
Интересный проект! А можно ли получить не только распознанную цепочку слов, но и дерево разбора? Т.е. стек парсера в момент нахождения решения?
0
vas3k ⸬ 20 апреля 2014, 04:10 ⸬ Novosibirsk, RU ⸬ Apple лог
#
Sergey Slepov, да, можно, я просто не придумал зачем это нужно, потому и не сохранял его в результаты. Учту пожелания.
0
Sergey Slepov ⸬ 21 апреля 2014, 21:13 ⸬ Hammersmith, GB ⸬ Windows лог
#
Подал на вход грамматику S = adj<agr-gnc=1> noun и следующий список:

text = u"""
белый холодильник
черный холодильник
чёрный холодильник
розовый холодильник
синий холодильник
новый холодильник
гладкий холодильник
красный холодильник
"""

В ответ получил:

FOUND:
белый холодильник

FOUND: розовый холодильник

FOUND: синий холодильник

FOUND: новый холодильник

FOUND: гладкий холодильник

FOUND: красный холодильник

Вероятно, дело в том, что в словаре opencorpora ЧЁРНЫЙ имеет два варианта разбора - как прилагательное и как существительное. В принципе, ничего страшного ("Черные начинают и выигрывают"). Может быть, брать не только первый разбор, а смотреть, удовлетворяет ли ЛЮБОЙ ИЗ разборов заданному тегу?

И багтрекер неплохо бы завести.

Багтрекер увидел, и даже тикет на данную фичу!

https://github.com/vas3k/python-glr-parser/issues/1
0
vas3k ⸬ 22 апреля 2014, 06:23 ⸬ Novosibirsk, RU ⸬ Apple лог
#
Sergey Slepov, ага, спасибо, это действительно важная штука, я в ближайшее время посмотрю что я смогу сделать, чтобы стек-граф строился по всем вариантам разбора. Теоретически он так умеет, ибо для этого и придуман.
0
ЯЯ ⸬ 21 мая 2014, 12:32 ⸬ Moscow, RU ⸬ Apple лог
#
Извиняюсь за дурацкий вопрос. Не могу установить его

делаю pip install git+https://github.com/vas3k/python-glr-parser.git

получаю в лог

------------------------------------------------------------
/Users/gyastrebkov/anaconda/bin/pip run on Wed May 21 16:27:42 2014
Downloading/unpacking git+https://github.com/vas3k/python-glr-parser.git
Cloning https://github.com/vas3k/python-glr-parser.git to /var/folders/3h/4d_jbhgs0v70z1k1spgjn40m0000gn/T/pip-9Fpavo-build
Found command 'git' at '/usr/bin/git'
Running command /usr/bin/git clone -q https://github.com/vas3k/python-glr-parser.git /var/folders/3h/4d_jbhgs0v70z1k1spgjn40m0000gn/T/pip-9Fpavo-build
Running setup.py (path:/var/folders/3h/4d_jbhgs0v70z1k1spgjn40m0000gn/T/pip-9Fpavo-build/setup.py) egg_info for package from git+https://github.com/vas3k/python-glr-parser.git
Traceback (most recent call last):
File "<string>", line 17, in <module>
IOError: [Errno 2] No such file or directory: '/var/folders/3h/4d_jbhgs0v70z1k1spgjn40m0000gn/T/pip-9Fpavo-build/setup.py'
Complete output from command python setup.py egg_info:
Traceback (most recent call last):

File "<string>", line 17, in <module>

IOError: [Errno 2] No such file or directory: '/var/folders/3h/4d_jbhgs0v70z1k1spgjn40m0000gn/T/pip-9Fpavo-build/setup.py'

----------------------------------------
Cleaning up...
Removing temporary dir /private/var/folders/3h/4d_jbhgs0v70z1k1spgjn40m0000gn/T/pip_build_gyastrebkov...
Command python setup.py egg_info failed with error code 1 in /var/folders/3h/4d_jbhgs0v70z1k1spgjn40m0000gn/T/pip-9Fpavo-build
Exception information:
Traceback (most recent call last):
File "/Users/gyastrebkov/anaconda/lib/python2.7/site-packages/pip/basecommand.py", line 122, in main
status = self.run(options, args)
File "/Users/gyastrebkov/anaconda/lib/python2.7/site-packages/pip/commands/install.py", line 274, in run
requirement_set.prepare_files(finder, force_root_egg_info=self.bundle, bundle=self.bundle)
File "/Users/gyastrebkov/anaconda/lib/python2.7/site-packages/pip/req.py", line 1215, in prepare_files
req_to_install.run_egg_info()
File "/Users/gyastrebkov/anaconda/lib/python2.7/site-packages/pip/req.py", line 321, in run_egg_info
command_desc='python setup.py egg_info')
File "/Users/gyastrebkov/anaconda/lib/python2.7/site-packages/pip/util.py", line 697, in call_subprocess
% (command_desc, proc.returncode, cwd))
InstallationError: Command python setup.py egg_info failed with error code 1 in /var/folders/3h/4d_jbhgs0v70z1k1spgjn40m0000gn/T/pip-9Fpavo-build


Подскажите, пожалуйста, как быть? что делать??
0
vas3k ⸬ 21 мая 2014, 15:07 ⸬ Novosibirsk, RU ⸬ Apple лог
#
Я не оформлял пока его как питоновский пакет, там нет необходимых конфигов. Просто скопируйте его в нужную папку.
0
ЯЯ ⸬ 23 мая 2014, 06:12 ⸬ Moscow, RU ⸬ Apple лог
#
Спасибо. Разобрался
Подскажите пожалуйста:
1. C регулярками. Хочу чтобы возможно было повторение любого слова в грамматике нужно написать <regex=Word+> или <regex=Word+> или как? Что-то никак не получилось

2.В GLRParser можно несколько грамматик подавать?
0
vas3k ⸬ 23 мая 2014, 06:55 ⸬ Novosibirsk, RU ⸬ Apple лог
#
ЯЯ,
1. Неа, регулярки нужны для разбора слов. Символов в словах. А не для использования грамматик в них. Повторение слов задается простой грамматикой, а не регуляркой. Что-то типа:
S = ManyWords
ManyWords = ManyWords Word
ManyWords = Word

2. Можно создать несколько GLRParser'ов, никто не мешает :)
0
ЯЯ ⸬ 23 мая 2014, 10:42 ⸬ Moscow, RU ⸬ Apple лог
#
S = ManyWords
ManyWords = ManyWords Word
ManyWords = Word

правильно я понимаю, что она мне выделит по 3 слова? а если, например, мне надо сделать
DICT1 от 0 до 3х любых слов DICT2
0
vas3k ⸬ 23 мая 2014, 12:29 ⸬ Novosibirsk, RU ⸬ Apple лог
#
ЯЯ,
> правильно я понимаю, что она мне выделит по 3 слова
Нет, не правильно, оно выберет вообще все цепочки слов любой длины. Почитайте про LR-грамматики, например, здесь: http://math.msu.su/~vvb/BMSTU/lectLR.html

Составление LR-грамматик для сложных случаев достаточно нетривиальное занятие, но это действительно мощный механизм. А GLRParser лишь инструмент, который их интерпретирует. Как напишете - так и будет :)
0
ЯЯ ⸬ 23 мая 2014, 14:48 ⸬ Moscow, RU ⸬ Apple лог
#
Понял, спасибо за ссылку
0
Илья ⸬ 15 апреля 2015, 23:31 ⸬ Moscow, RU ⸬ Windows лог
#
Подскажите, пожалуйста, а как запустить эту штуку без привязки к словарям, т.е. вывести любой контент, соответствующий грамматике?
(не заполняйте это поле)

me@vas3k.ru :: telegram :: twitter :: instagram :: facebook :: github