[Перевод] Игра Престолов. Поиск авторов диалогов в книгах
Привет Хабрахабр,
На основании результата голосования в статье Теория Графов в Игре Престолов, я перевожу обучающий материал Эрика Германи (Erik Germani), который получил социальный граф связей из 5 первых книг серии «Песнь льда и пламени», лёгший в основу вышеупомянутой статьи. Статья не содержит подробного описания методов машинного обучения, а скорее рассказывает как на практике можно использовать существующие инструменты для поиска авторов диалогов в тексте. Осторожно, много букв! Поехали.
Данный обучающий материал нацелен на новичков в машинном обучении, таких как я, когда начинал этот проект год назад. (И коим до сих пор являюсь, хотя сейчас я просто зелёный, а не ярко зелёный в этой теме.) Мы построим модель, способную определить кто говорит строку диалога в книгах Джордж Р.Р. Мартина «Песнь льда и пламени». Для этого, мы будем использовать метод условных случайных полей CRF (прим. от Conditional Random Fields) и замечательную утилиту CRFsuite от Наоаки Оказаки. Для обработки текста воспользуемся Python 2.7 и NLTK (Natural Language Toolkit).
Я хочу быть детальным с этим материалом. Надеюсь, что при описании каждого шага моих действий, вы сможете извлечь для себя новые инструменты и методы, которые будут полезны в ваших собственных проектах. Объяснения кода будут от новичка и для начинающего, того, кто понимает синтаксис Python и знает об абстракции списков, но не более того. Если вы чувствуете, что мои разъяснения кода иссушают вашу душу, пропустите их.
Важно: Если вы хотели найти тут теорию о методе условных случайных полей, то этот материал не для вас. Для меня, CRFsuite — красивый черный ящик, которого я касаюсь своими обезьяньими лапками. Мы потратим некоторое время на улучшении эффективности модели, но это окажется ошибочной попыткой. Если это вас расстраивает, имейте ввиду:
- Мне удалось добиться хорошего результата (~75% точности) с CRFsuite из коробки
- Тут не будет LaTeX
Наш план игры прост. Как и с любым другим алгоритмом для машинного обучения, нам нужно подготовить данные для обучения и проверки. Потом мы выберем свойства, которые алгоритм будет использовать для классификации. После того как мы обработаем текст используя эти свойства, мы скормим результат CRFsuite и поздравим себя с хорошо проделанной работой. (либо обременим себя кропотливым трудом по проверке догадок машины).
Давайте начнём.
В первую очередь, нам надо найти копию источника текста и я оставлю выбор за вами, будете ли вы платить за него железную цену или нет.
Если вы новичок в области обработки естественного языка, то возможно недооцениваете каким непростым может оказаться исходный текст. У каждого файла .txt есть кодировка, которая определяет как будет описываться каждый символ. ASCII, формат в котором я прочитал прохождения игры Ocarina of Time, был вытеснен UTF-8, который может справиться со всеми специальными символами. (ASCII может представить 128 символов.) Моя копия ПЛИП (прим. Песнь Льда и Пламени) в UTF-8, что доставит небольшие неудобства, но на самом деле является бонусом.
Мы загрузим этот текст в NLTK чтобы легче манипулировать им. NLTK может проделать массу задач, и именно так я изучил Python, если это окажется интересным для вас, то взгляните на их отличную онлайн книгу. В наших целях использовать этот инструмент, чтобы разбить текст на токены. Это подразумевает разделение предложения на слова и знаки препинания, это часто делают в проектах по обработке естественного языка.
import nltk
nltk.word_tokenize("NLTK is ready to go.")
['NLTK', 'is', 'ready', 'to', 'go', '.']
В NLTK есть предзагруженные корпуса, но нам нужно загрузить свой.
Создайте папку и вставьте туда текстовые файлы ПЛИП. Так как книги очень большие, то общедоступного текста источника будет почти 10 Мб. Не идеально для поиска и замены в тексте. Я разделил текст на книги, но настоящие профессионалы, которые собираются анализировать больше, скорее разделят ещё каждую книгу по главам и последовательно пронумеруют.
Но не будем сейчас всё усложнять! Как только в папке оказался текст, мы можем запустить следующее:
corpus = nltk.corpus.PlaintextCorpusReader(r'corpus', 'George.*\.txt', encoding = 'utf-8')
Здесь r указывает не обрабатывать строку. Тут это неважно, т.к. я напрямую обращаюсь к папке «corpus», но если в вашем случае у папки сложное местоположение, лучше не забывать об этом.
Второй аргумент — регулярное выражение, которое указывает NLTK брать все файлы в папке, в названиях которых присутствует «George» и с расширением ».txt».
Параметр кодировки очень важен — если кодировка текста не будет соответствовать указанной, то посыпятся ошибки.
Корпус в NLTK очень полезен, с ним можно получить информацию из текста на разных уровнях.
corpus.words("George R. R. Martin - 01 - A Game Of Thrones.txt")[-5:]
[u’the', u’music', u’of', u’dragons', u'.']
corpus.words()[0]
u’PROLOGUE'
corpus.sents()[1][:6]
[u'\u201c', u'We', u'should', u'start', u'back', u',\u201d']
Тут мы слышим обреченного Гареда из пролога Игры Престолов и видим некоторые символы в кодировке Юникод, представленные в Python. Вы видите, что все строки Юникод начинаются с u, и содержат специальные символы. \u201c это левая кавычка, \u201d правая. Я упоминал что UTF-8 это скорее бонус, и вот почему. Давайте посмотрим что будет если мы откроем этот же файл без указания кодировки.
bad_corpus = nltk.corpus.PlaintextCorpusReader(r'corpus', '.*\.txt')
bad_corpus.sents()[1][:9]
['\xe2', '\x80\x9c', 'We', 'should', 'start', 'back', ',', '\xe2', '\x80\x9d']
Так же как \u указывает на строку в формате Юникод, \x указывает на шестнадцатеричную строку, таким образом NLTK даёт нам 3 шестнадцатеричных байта — \xe2, \x80, \x9c — и пытается разбить их. Можно видеть, что он не знает как это сделать.
Мы будем работать с параграфами, поэтому давайте взглянем на один из них:
print corpus.paras()[1]
[[u'\u201c', u'We', u'should', u'start', u'back', u',\u201d', u'Gared', u'urged', u'as', u'the', u'woods', u'began', u'to', u'grow', u'dark', u'around', u'them', u'.'], [u'\u201c', u'The', u'wildlings', u'are', u'dead', u'.\u201d']]
Вы можете заметить, как NLTK структурирует данные. Предложения это список токенов, а параграф список предложений. Достаточно легко!
Далее нам нужно подготовить данные для обучения, но чтобы сделать это, нужно определиться с метками, которые мы будем использовать. При парсинге текста, алгоритм знает принадлежность любого токена к лексической категории, каждый из которых имеет свою метку. JJ это прилагательное, NN — существительное, IN — предлог. Эти метки играют ключевую роль для достоверности работы нашей модели. The Penn Treebank (прим. проект по метке текста) выделяет 36 таких меток.
Какие же будут наши метки? Простейший вариант это имена персонажей. Это не сработает по нескольким причинам:
- ПЛИП содержит больше тысячи персонажей. Это слишком большой выбор для нашей бедной модели. Нам нужно отсеять как можно больше меток, чтобы правильно классифицировать полагаясь на банальную удачу.
- К персонажам обращаются по разному. Джоффри может быть как «Джоффри», так и «Джофф», «Принц» или даже просто «он».
- Если мы будем использовать имена персонажей в качестве меток, то они должны быть определены в обучающих данных. Иначе, наша модель не будет в курсе о их существовании и поэтому никак не сможет их определить.
- Все персонажи звучат просто напросто одинаково. (Я это понял благодаря другому опыту с машинном обучением, где я пытался разделить персонажей по их словарному запасу). У некоторых есть броские фразы, такие как «прискорбно» (прим. grievous) для Вариса и «Ходор» для Ходора, но это редкость. К тому же, для многих отведено недостаточно времени для разговоров, чтобы различить их от остальных.
Хоть и определение по именам персонажей звучит весьма заманчиво, давайте отбросим эту идею и подумаем над процессом, который происходит в голове у читателя при решении аналогичной задачи.
Возьмите ближайшую к вам книгу, откройте случайную страницу, и попробуйте определить кто там разговаривает. Как вы это сделаете? Вы посмотрите на ближайшие собственные имена рядом с диалогом.
«Уилл видел их» отвечал Гаред.
[…]
Сир Уэймар Ройс поглядел на небо без всякого интереса. «Ночь каждый день приходит примерно в это же время. Неужели тьма лишает тебя мужества, Гаред?»
Хотя не каждая строка диалога бывает помечена. Посмотрите дальше и увидите:
«А ты заметил положение тел?»
Вы взглянете на параграфы сверху и снизу. Вот 2 сверху:
«А оружие?»
«Несколько мечей и луков. У одного был топор, тяжелый такой, с двумя лезвиями… жестокое железо. Он лежал на земле возле этого человека, прямо у руки.»
Ни капли намёка. Два параграфа ниже:
Уилл пожал плечами. «Один сидел возле скалы. Остальные были на земле, попадали, что ли.»
«Или спали,» предположил Ройс.
Мы знаем что Уилл не стал бы спрашивать самого себя, поэтому мы можем сказать что он не автор этой речи, и так как многие диалоги растягиваются на несколько параграфов, мы предположим что автор первых строк Ройс.
Эта схема и поможет помечать нашей модели. Мы научим её определять собственные имена рядом с текстом и если таких не найдётся, искать в близлежащих параграфах. Тогда, нашими метками будут:
PS ±2, FN ±2, NN ±2, Другие.
PS — после говорящий. Если метка параграфа PS -2, то это будет означать что имя, говорящего часть диалога, располагается двумя параграфами выше. Если FN 1, то первое имя в следующем параграфе. NN 0 обозначает как минимум 2 имени предшествуют диалогу и нам нужен ближайший к диалогу.
Я так же буду определять и ADR ±2, для персонажей, к которым обращаются в тексте диалога.
Теперь мы подготовим обучающие данные. Поможет нам в этом SublimeText. Я открыл текст «Игра Престолов», выделил левую кавычку, выбрал Find → Quick Find All, и дважды нажал клавишу Home. Теперь курсор оказался возле начала каждого параграфа с диалогом. Дальше я набрал »{}». Т.к. в тексте нет фигурных скобок, то мы можем использовать их чтобы оставлять заметки, которые будем использовать в будущем.
Мы будем использовать регулярное выражение (? <=\{)(?=\}) чтобы прыгать по фигурным скобкам. Если вы не встречались с данной конструкцией, то они называются положительные ретроспективные и опережающие проверки. Первое выражение в скобках заставит SublimeText начать выделять строки, у которых в начале стоит открывающая фигурная скобка (экранированная обратным слэшем). Следущее выражение скажет остановиться когда найдется закрывающая фигурная скобка. Как вы могли заметить оба выражения состоят из конструкции ?=, только первая содержит еще и <.
Теперь вы можете переходить по скобкам нажимая на F3, что является горячей клавишей для поиска следующего в SublimeText под Windows. Такого рода оптимизация важна, т.к. вы будете помечать приблизительно тысячи диалогов. Как минимум столько сделал я. Это не было столь тяжело и время затратно как я предполагал. (Хотя возможно я вру, т.к. я закончил спустя лишь год).
Прежде чем вы приступите, хочу сделать одно замечание: подумайте над тем, хотите ли вы использовать позиционные метки (PS, FN, NN) или все же имена персонажей. Я знаю, что уже сказал что не будем использовать имена, но если вы решились использовать позиционные метки то вы связываете эти обучающие данные с соответствующей моделью. Если вы пометите диалоги Джона меткой «Jon», то в будущем у вас будет возможность поменять метку на позиционную, либо же использовать другие метки, если найдёт лучше.
Я думаю, что тут нет однозначного ответа. В прошлом году я помечал именами персонажей. Теперь же мне необходимо совершать предварительные манипуляции, которые добавляют неоднозначности. Если имя Эддарда появляется 2 параграфа выше и один параграф ниже, то какой выбрать? Это напрямую затронет поведение модели и совершая это автоматически делает процесс еще больше неточным. Поэтому я не уверен что посоветовать. Мне кажется, что с точки зрения ручной метки, легче написать имя персонажа, но, с точки зрения автоматизации, намного удобнее иметь позиционные метки.
Ну что ж, вы пометили часть текста. Я аплодирую вам за приверженность делу обработки естественного языка. Всё что нам нужно сделать теперь, это написать несколько функций, которые будут принимать параграф в качестве аргумента и помечать их свойствами, которые нам интересны.
Напомни, какие свойства? Рабочими лошадками, ответственными за точность модели являются следующие функции: существуют ли в текущем, либо в соседних параграфах PS, FN или NN.
Поиск имён
Наша первая функция должна находить имена собственные. Это можно сделать с помощью определения частей речи.
sentence = corpus.paras()[33][0]
print " ".join(sentence)
print nltk.pos_tag(sentence)
" Such eloquence , Gared ," Ser Waymar observed . [(u'\u201c', 'NN'), (u'Such', 'JJ'), (u'eloquence', 'NN'), (u',', ','), (u'Gared', 'NNP'), (u',\u201d', 'NNP'), (u'Ser', 'NNP'), (u'Waymar', 'NNP'), (u'observed', 'VBD'), (u'.', '.')]
NPP возле Ser и Waymar означает что это имена собственные. Но тут есть и минусы:
- Случаются ошибки. Заметили как закрывающая кавычка стала именем собственным?
- Определение частей речи занимает время.
%timeit nltk.pos_tag(sentence)
100 loops, best of 3: 8.93 ms per loop
asoiaf_sentence_count = 143669
( asoiaf_sentence_count * 19.2 ) / 1000 / 60
45.974079999999994
В ПЛИП много параграфов для обработки и 45 с лишним минут для определения частей речи затянет процесс тестирования и рефакторинга. Конечно, можно было бы один раз всё проанализировать и дальше работать с тем, что получилось. Но для этого пришлось бы иметь дело с ещё одной структурой данных и такое определение пришлось бы переделывать каждый раз когда исходный текст меняется. (И это неизбежно.)
К счастью, не обязательно связываться с частями речи для определения имён персонажей. Это одно из преимуществ выбора ПЛИП для анализа: существуют тонны данных которые уже получены. Давайте наскребём некоторые из них.
Существующая информация
Тут оказалась очень полезной Wiki Песни Льда и Пламени, я получил практически исчерпывающий список имён персонажей буквально скопировав страницу со списком героев. Результат можно найти тут. Если этого для вас достаточно, то встретимся в следующей главе статьи. Для тех, кому интересно как можно автоматически извлечь данные со страницы, я приведу пару способов которыми я пользовался в других проектах.
Wget
Отличная утилита которая очень проста, если вам нужно пройтись по заранее известным ссылкам. Не придётся думать как обходить ссылки, нужно лишь создать файл со списком и передать его используя флаг -i, вот так:
wget -i list_of_links.txt
Requests
В Python есть библиотека requests, которая хорошо подходит для работы с отдельными страницами.
import requests
r = requests.get("http://awoiaf.westeros.org/index.php/List_of_characters")
html = r.text
print html[:100]
<p> <br /></p> <h2>Парсинг</h2><p> <br />После скачивания html, нам нужно отшелушить страницу от лишних тегов, чтобы добраться до ссылок. BeautifulSoup это HTML парсер, который позволит без лишней суеты получить ссылки. После установки и парсинга, найти все ссылки можно просто запустив: </p> <pre> <code class="python">parsed_html.find_all("a")</code> </pre><p> <br />Тут можно почитать об этом больше.</p> <p>Мне хочется рассказать еще об одном способе, в котором используется библиотека lxml. С помощью этой библиотеки можно работать с Xpath. Я новичок в Xpath, но это мощный способ двигаться по древовидной структуре.<br /></p> <pre> <code class="python">import lxml.html tree = lxml.html.fromstring(html) character_names = tree.xpath("//ul/li/a[1]/@title") print character_names[:5]</code> </pre> <pre> ['Abelar Hightower', 'Addam', 'Addam Frey', 'Addam Marbrand', 'Addam Osgrey'] </pre><p> <br />Если вы косо посмотрели на выражение Xpath сверху, то вот что оно делает: </p> <pre> <code class="python">tree.xpath("//ul # выбирает все не нумерованные списки /li # выделяет элементы списков /a[1] # выделяет первую ссылку в элементе. /@title # возвращает атрибут title ")</code> </pre><p> <br />Теперь, нужно выделить среди результата имена и удалить то, что к имени никакого отношения не имеет. Просто пробежавшись по странице ПЛИП, я заметил элементы вида «Taena of Myr». Мы ведь не хотим чтобы наша модель сопоставляла диалогам частицу «of».</p> <p>NLTK поможет в этом. В нём есть корпус текста с «плохими» словами — stopwords. Такими, которые встречаются настолько часто, что не несут никакого смысла для характеристики текста.<br /></p> <pre> <code class="python">particles = ' '.join(character_names).split(" ") print len(set(particles)) stopwords = nltk.corpus.stopwords.words('english') print stopwords[:5] particles = set(particles) - set(stopwords) print len(particles) # Кое что всё же проскользнёт. Т.к. Aegon I в списке ПЛИП, то римская # цифра I будет восприниматься как имя. Нужно почистить это вручную. "I" in particles</code> </pre> <pre> 2167 ['i', 'me', 'my', 'myself', 'we'] 2146 True </pre><p> <br />И в конце нужно добавить еще некоторые, возможно, упущенные прозвища, такие как Дени, Чёрная Рыба или Джофф. Если вы довольны списком имён, то сохраните его в файле для дальнейшего использования.</p> <h2>Поиск имён. Часть 2</h2><p> <br />Мы отказались от идеи поиска имён используя части речи и обзавелись списком имён. Мы извлечём последовательности токенов и посмотрим сможем ли найти их в нашем списке имён. Наконец настало время написать код.</p> <pre> <code class="python">import itertools from operator import itemgetter particles = [particle.rstrip('\n') for particle in open('asoiaf_name_particles.txt')] tokens = [u'\u201c', u'Such', u'eloquence', u',', u'Gared', u',\u201d', u'Ser', u'Waymar', u'observed', u'.'] def roll_call(tokens, particles): speakers = {} particle_indices = [i for (i, w) in enumerate(tokens) if w in particles] for k, g in itertools.groupby(enumerate(particle_indices), lambda (i,x): i-x): index_run = map(itemgetter(1), g) speaker_name = ' '.join(tokens[i] for i in index_run) speakers[min(index_run)] = speaker_name return speakers</code> </pre><p> <br />Эта функция использует лямбда-выражение, которыми я не мог пользоваться в прошлом году, когда сделал этот проект. Скрипт, который я использовал тогда, настолько ужасен и не читаем что я не решился его публиковать. К тому же, я думаю, что в этом скрипте новички могут научиться чему нибудь новому, поэтому чуть подробнее об этом.</p> <p>Itertools — инструмент, заслуживающий внимания. Я часто использую его чтобы избавиться от вложенности или для перестановок. В нём нам нужна функция <em>groupby</em>. По причине выхода новой версии этой функции к моменту написания материала, я полностью предпочёл <em>groupby</em>, нежели dropwhile и takewhile, которые я использовал в рекурсивной манере.</p> <p>При программировании, я подумал, что функция <em>roll_call</em> должна знать позиции имён, которые он нашёл. Поэтому я решил хранить все порядковые номера имён. Это можно заметить в 3-й строке кода функции.</p> <pre> <code class="python">particle_indices = [i for (i, w) in enumerate(tokens) if w in particles]</code> </pre><p> <br />Enumerate очень помог мне при знакомстве с Python. Он принимает список и для каждого элемента возвращает связку порядкового номера и самого элемента.</p> <p>4-я строка самая хитрая часть кода во всём материале и не я его писал. Она взята прямо из документации к библиотеке.<br /></p> <pre> <code class="python">for k, g in itertools.groupby(enumerate(particle_indices), lambda (i,x): i-x):</code> </pre><p> <br />Groupby проходит через список и группирует элементы в зависимости от результата лямбда функции. Лямбды — анонимные функции. В отличии от roll_call их не нужно заранее определять. Это лишь часть кода, которая принимает аргументы и возвращает значение. В нашем случае она просто вычитает из порядкового номер число.</p> <p>Давайте взглянем как это работает.<br /></p> <pre> <code class="python">print tokens particle_indices = [i for (i, w) in enumerate(tokens) if w in particles] print particle_indices for index, location in enumerate(particle_indices): lambda_function = index-location print "{} - {} = {}".format(index, location, lambda_function)</code> </pre> <pre> [u'\u201c', u'Such', u'eloquence', u',', u'Gared', u',\u201d', u'Ser', u'Waymar', u'observed', u'.'] [4, 6, 7] 0 - 4 = -4 1 - 6 = -5 2 - 7 = -5 </pre><p> <br />В этом и заключается уловка с <em>groupby</em>: индексы пронумерованы последовательно, поэтому если элементы в списке так же идут друг за другом, то результат лямбды будет для них одинаков.</p> <p><em>groupby</em> видит -4 и присваивает значение 4 для группы. 6 и 7-й элементы оба имеют -5 и соответственно группируются.</p> <p>Теперь мы знаем где находятся составные имена и должны использовать их. Что возвращает <em>groupby</em>? Ключ, результат нашей лямбды, и саму группу, объект <em>grouper</em>. Далее воспользуемся функцией <em>map</em> чтобы применить <em>itemgetter (1)</em>, извлекающий из связки элемент, ко всем элементам группы и таким образом мы создадим список из позиций имён в исходном списке токенов.</p> <p>После <em>groupby</em> нам нужно всего лишь извлечь найденные имена и сохранить их в ассоциативном массиве <em>speakers</em>.<br /></p> <pre> <code class="python">roll_call(tokens, particles)</code> </pre> <pre> {4: u'Gared', 6: u'Ser Waymar'} </pre><p> <br /></p> <h2>Оптимизация</h2><p> <br />Давайте сравним скорость работы этой функции с методом, в котором мы использовали части речи.</p> <pre> <code>%timeit roll_call(tokens, particles)</code> </pre> <pre> 100 loops, best of 3: 3.85 ms per loop </pre><p> <br />Не плохо, в 5–6 раз быстрее. Но мы можем улучшить результат использовав <em>set</em>. Множества <em>set</em> почти мгновенно проверяют находится ли элемент в списке.</p> <pre> <code class="python">set_of_particles = set(particle.rstrip('\n') for particle in open('asoiaf_name_particles.txt')) %timeit roll_call(tokens, set_of_particles)</code> </pre> <pre> 10000 loops, best of 3: 22.6 µs per loop </pre><p> <br />Вы понимаете что хороши, когда видите в скорости греческие буквы.</p> <h2>Поиск имён касательно диалогов</h2><p> <br />Теперь нам надо написать программку, которая будет вызывать вышеописанную функцию в нужных местах, так, чтобы найти имена персонажей перед, в и после текста диалогов. Мы соберём всё это в класс, который сможет собрать нам полный список позиций имён персонажей, который мы дальше передадим другому алгоритму для извлечения свойств и потом уже в CRFsuite.</p> <p>Но прежде, я бы хотел привести в порядок наши данные.</p> <h3>XML парсер</h3><p> <br />После успешной одно-строчной команды с Xpath, я решил написать XML парсер для наших текстовых файлов. В выборе этого формата есть тонна смысла. ПЛИП это множество книг, в которых есть главы, которые в свою очередь состоят из параграфов, и некоторые из них содержат диалоги — и нам нужно незаметно их пометить. Если бы я не перевёл текст в XML (и сначала я этого не сделал), то метки бы замусорили сам текст.</p> <p>Я предпочту умолчать о скрипте ниже: он напоминает мне мои первые шаги в Python, огромные функции, костыли и переменные с длиннющими наименованиями.<br /></p> <pre> <code class="python">from lxml import etree import codecs import re def ASOIAFtoXML(input): # Каждый элемент input должен быть ассоциативным массивом названий глав с расположением его на диске. root = etree.Element("root") for item in input: title = item["title"] current_book = etree.Element("book", title=item["title"]) root.append(current_book) with codecs.open(item["contents"], "r", encoding="utf-8") as book_file: #Ловушка для глав, названия которых не распознаются регулярным выражением. current_chapter = etree.Element("chapter", title="Debug") for paragraph in book_file: paragraph = paragraph.strip() if paragraph != "": title_match = re.match("\A[A-Z\W ]+\Z", paragraph) if title_match: current_chapter = etree.Element("chapter", title=title_match.group()) current_book.append(current_chapter) else: current_graf = etree.SubElement(current_chapter, "paragraph") while paragraph != "": current_dialogue = current_graf.xpath('./dialogue[last()]') speaker_match = re.search("(\{(.*?)\} )", paragraph) if speaker_match: speaker_tag = speaker_match.group(1) speaker_name = speaker_match.group(2) paragraph = paragraph.replace(speaker_tag, "") open_quote = paragraph.find(u"\u201c") if open_quote == -1: if current_dialogue: current_dialogue[0].tail = paragraph else: current_graf.text = paragraph paragraph = "" elif open_quote == 0: current_dialogue = etree.SubElement(current_graf, "dialogue") if speaker_name: current_dialogue.attrib["speaker"] = speaker_name close_quote = paragraph.find(u"\u201d") + 1 if close_quote == 0: # функция find возвращает -1 в данном случае, поэтому сравнивая с 0 # мы определяем нет ли там больше закрывающей кавычки. Это происходит # в длинных монологах разбитых по параграфам. close_quote = len(paragraph) current_dialogue.text = paragraph[open_quote: close_quote] paragraph = paragraph[close_quote:] else: if current_dialogue: current_dialogue[0].tail = paragraph[:open_quote] else: current_graf.text = paragraph[:open_quote] paragraph = paragraph[open_quote:] return root tree = ASOIAFtoXML([{"title": "AGOT", "contents": "corpus/train_asoiaf_tagged.txt"}]) # Так мы сохраняем дерево в файл. # et = etree.ElementTree(tree) # et.write(codecs.open("asoiaf.xml", "w", encoding="utf-8"), pretty_print=True)</code> </pre><p> <br />Суть кода выше: мы используем lxml чтобы создать дерево, потом построчно пробегаемся по тексту. Если строка распознаётся как имя главы (заглавные буквы, пунктуация и пробелы), мы добавляем новую главу в вершину текущей книги. Как только мы оказались в тексте главы, мы пробираемся сквозь параграфы, используя другое регулярное выражение чтобы определить кто говорил диалог и добавить его в соответствующую вершину диалога. Предварительно они должны быть уже помечены, конечно же.</p> <p>Интересное замечание по XML. Это иерархическая структура, поэтому она по своей природе требует строгого ветвления, вершина в вершине. Но это не так в прозе. В прозе диалоги находятся внутри текста. lxml предоставляет решение: <em>text</em> и <em>tail</em>. Таким образом вершина XML хранит текст, но этот текст прерывается после очередного добавления вершины.<br /></p> <pre> <code>markup = '''<paragraph>Worse and worse, Catelyn thought in despair. My brother is a fool. Unbidden, unwanted, tears filled her eyes. <dialogue speaker="Catelyn Stark"> "If this was an escape,”</dialogue> she said softly, <dialogue speaker="Catelyn Stark">"and not an exchange of hostages, why should the Lannisters give my daughters to Brienne?”</dialogue></paragraph>''' graf = lxml.etree.fromstring(markup) print graf.text</code> </pre> <pre> Worse and worse, Catelyn thought in despair. My brother is a fool. Unbidden, unwanted, tears filled her eyes. </pre> <pre> <code class="python">print graf[0].text</code> </pre> <pre> "If this was an escape," </pre><p> <br />Что же произойдёт с оставшимся «she said softly»? Мы сохраним в его в переменной вершины <em>tail</em>.</p> <pre> <code class="python">print graf[0].tail</code> </pre> <pre> she said softly, </pre><p> <br />И так далее, добавляя к каждой вершине диалога оставшуюся часть текста.</p> <p>Как следствие, это сильно упрощает нам поиск авторов диалогов, когда они нам понадобятся. А понадобятся они нам прямо сейчас! <br /></p> <pre> <code class="python">class feature_extractor_simple: """Analyze dialogue features of a paragraph. Paragraph should be an lxml node.""" def __init__(self, paragraph_node, particles, tag_distance=0): self.paragraph = paragraph_node self.particles = set(particles) self.tag_distance = tag_distance self.raw = ''.join(t for t in self.paragraph.itertext()) self.tokens = self.tokenize(self.raw) def tokenize(self, string): return nltk.wordpunct_tokenize(string) def find_speakers(self, tokens): speakers = {} particle_indices = [i for (i, w) in enumerate(tokens) if w in self.particles] for k, g in itertools.groupby(enumerate(particle_indices), lambda (i,x): i-x): index_run = map(itemgetter(1), g) speaker_name = ' '.join(tokens[i] for i in index_run) speakers[min(index_run)] = speaker_name return speakers def pre_speak(self, prior_tag="FN", near_tag="NN"): # Имена до диалога. features = {} if self.paragraph.text is not None: speakers = self.find_speakers(self.tokenize(self.paragraph.text)) if len(speakers) > 0: features.update({"{} {}".format(prior_tag,self.tag_distance): speakers.values()[0]}) if len(speakers) > 1: features.update({"{} {}".format(near_tag,self.tag_distance): speakers[max(speakers.keys())]}) return features def dur_speak(self, tag="ADR"): # Имена адресатов. features = {} for dialogue in self.paragraph.itertext("dialogue", with_tail=False): tokens = self.tokenize(dialogue) named = self.find_speakers(tokens) addressed = {k: v for (k, v) in named.items() if tokens[k-1] == "," or tokens[k + 1 + v.count(" ")].startswith(",")} if len(addressed) > 0: features.update({"{} {}".format(tag, self.tag_distance): addressed[max(addressed.keys())]}) return features def post_speak(self, tag="PS"): features = {} # Имена после диалогов. tails = [line.tail for line in self.paragraph.iterfind("dialogue") if line.tail is not None] for tail in tails: tokens = self.tokenize(tail) speakers = {k: v for (k, v) in self.find_speakers(tokens).items() if k <= 1} if len(speakers) > 0: features.update({"{} {}".format(tag, self.tag_distance): speakers[min(speakers.keys())]}) break return features</code> </pre><p> <br />Пару слов об этих функциях.</p> <p>Если вы новичок в Python, то не бойтесь классов. Вам просто напросто нужно написать обычные функции, передавая им в качестве аргумента <em>self</em>. Это позволит Python знать с каким объектом функция в данный момент работает. Класс это как фабрика клонов, а объект и есть клон. У всех клонов одинаковый ДНК, это методы и переменные, но из за их жизненного опыта их личности различаются, чем в данном контексте являются переданные им данные.</p> <p>У классов есть также специальная функция <em>__init__</em>, которая позволяет инициализировать переменные объекта.<br />Теперь вы можете расслабиться, т.к. ваши данные находятся в руках специализированного класса. И раз вы абстрагировали его поведение, то вы можете по щелчку пальца получить обработанную им информацию.<br /></p> <pre> <code class="python">paragraph = tree.xpath(".//paragraph")[32] example_extractor = feature_extractor_simple(paragraph, particles) print example_extractor.raw print example_extractor.pre_speak() print example_extractor.dur_speak() print example_extractor.post_speak()</code> </pre> <pre> "Such eloquence, Gared," Ser Waymar observed. "I never suspected you had it in you." {} {'ADR 0': u'Gared'} {'PS 0': 'Ser Waymar'} </pre><p> <br />Если вы смущены работой некоторых функций, я коротко объясню что они делают. Если же всё сверху выглядит для вас приемлемо, то вы знаете что делать, до встречи в следующей главе.</p> <p>Тут происходит неуклюжая манипуляция с ассоциативным массивом, и это потому, что они не упорядочены в Python. Мне это напоминает чувство, когда выходя из дома вы чувствуете, что в кармане нет ключей, запирая дверь. Мне приходилось постоянно проверять, получаем ли мы первого или последнего персонажа, в зависимости от случая, я смотрю на значение ключей и выбираю минимум/максимум.</p> <h3>pre_speak</h3><p> <br />Как я уже говорил выше, атрибут <em>text</em> содержит весь текст до первой строки диалога. Нам просто нужно найти в нём имена персонажей.</p> <h3>dur_speak</h3><p> <br />В случае когда имя находится в теле диалога, который может состоять из множества строк, нам нужно пробежаться по им всем: </p> <pre> <code class="python">for dialogue in self.paragraph.itertext("dialogue", with_tail=False)</code> </pre><p> <br />Функция <em>itertext</em> в <em>lxml</em> позволяет получить весь текст вершины. Мы, так же, поставим флаг <em>with_tail=False</em> чтобы искать только вершины без «хвоста», а значит только текст диалога.</p> <p>Как только мы найдём имена персонажей, нам нужно выделить в них только те, которые обособлены запятой, что позволит нам найти обращение. (например, «Нед, обещай мне.» / «Обещай мне, Нед.»)</p> <p>Я нутром чувствую, что последнее имя, найденное в диалоге, с большой вероятностью ответит в следующем параграфе, поэтому мы будем перезаписывать адресата последним упомянутым именем.</p> <h3>post_speak</h3><p> <br />Для этой функции нам нужен только первый персонаж после диалога. Поэтому мы прерываем цикл как только нашли такого.</p> <p>Функция смотрит в первые 2 токена после закрывающей кавычки. Так вы найдёте диалоги типа: <br /></p> <blockquote> <p>«Прощай,» сказал Джон.</p> </blockquote><p> <br />Совет для начинающих программистов: можно вызывать функцию выборки при постройке списка.</p> <pre> <code class="python">tails = [line.tail for line in self.paragraph.iterfind("dialogue") if line.tail is not None]</code> </pre><p> <br />Это позволило получить диалоги одной строкой. (нужно просто указать условие, чтобы убрать все результаты без «хвоста») <br />Возможно, это самая любопытная часть для вас. В нём заключены условно случайные поля, что бы они не значили, и запускается с командной строки, но никак не посмотреть как он работает изнутри.</p> <p>Но по факту, CRFsuite очень простая и интересная часть всего этого. Во время написания материала, я обнаружил, что у него есть библиотека для Python, но сейчас мы не будем всё усложнять и будем пользоваться исполняемым файлом с помощью командной строки.</p> <p>(я планирую обновить модель, когда следующая книга, «Ветра зимы», увидит свет. Но у меня ведь есть еще пару лет пока это случится)</p> <p>Всё, что нужно CRFsuite это текст с некоторыми свойствами разделенными табуляцией, как эти например: </p> <pre> FN 0 Graf Sent Len=4 FN 1=True FN -2=True FN 0=True NN 1=True </pre><p> <br />Это формат для обучающих данных. Первый атрибут это правильный ответ. Все последующие это свойства. Они могут выглядеть как вам захочется, но не используйте двоеточие — это для взвешенных свойств, и поэтому может привести к ложной интерпретации.</p> <p>Вам нужно открыть командную строку где бы crfsuite.exe не находился и там набрать следующее: <br /></p> <pre> <code class="bash">crfsuite learn -m asoiaf.model train.txt</code> </pre><p> <br />Это создаст модель, что и является мозгом всего. Можете назвать её как угодно, я назвал свою asoiaf. Чтобы посмотреть на точность работы модели, наберите это: </p> <pre> <code class="bash">crfsuite tag -qt -m asoiaf.model test.txt</code> </pre><p> <br />Чтобы собственно запустить модель для пометки наберите</p> <pre> <code class="bash">crfsuite tag -m asoiaf.model untagged.txt </code> </pre><p> <br /><strong>untagged.txt</strong> должен выглядеть так же как и <strong>train.txt</strong>, но без атрибута правильного ответа в начале, т.е. приблизительно так: </p> <pre> NN -1=True FN 0=True FN 2=True FN -1=True NN 0=True </pre><p> <br />Тут можно узнать про это больше.</p> <p>Давайте теперь поиграемся со множеством свойств, которые могут повысить точность работы модели. Мы начнём с самого простого: с булевых значений, которые определяют расположение позиционных меток в и возле параграфа.</p> <p>И снова наш класс для извлечения свойств, только теперь с несколькими новыми функциями в начале.<br /></p> <pre> <code class="python">class feature_extractor: """Analyze dialogue features of a paragraph. Paragraph should be an lxml node.""" def __init__(self, paragraph_node, particles, tag_distance=0): self.paragraph = paragraph_node self.particles = set(particles) self.tag_distance = tag_distance self.raw = ''.join(t for t in self.paragraph.itertext()) self.tokens = self.tokenize(self.raw) self.speaker = self.xpath_find_speaker() def features(self): features = {} features.update(self.pre_speak()) features.update(self.dur_speak()) features.update(self.post_speak()) return features def local_features(self): #Разнообразные свойства живут в этой функции как в комуналке features = [] if self.tokens.count(u"\u201c") == 0: features.append("NoQuotes=True") prior = self.paragraph.getprevious() try: last_dialogue = list(prior.itertext("dialogue", with_tail=False))[-1].lower() hits = [w for w in ['who', 'you', 'name', '?'] if w in last_dialogue] if len(hits) > 2: features.append("Who Are You?=True:10.0") except (AttributeError, IndexError): pass try: dialogue = list(self.paragraph.itertext("dialogue", with_tail=False))[0].lower() for token in ['name', 'i am', u'i\u2019m']: if token in dialogue: features.append("My Name=True:10.0") break except (AttributeError, IndexError): pass if self.tokens[0] in self.particles: features.append("FirstSpeakerIndex0=True") if self.paragraph.text is not None: name_precount = len(self.find_speakers(self.tokenize(self.paragraph.text))) if name_precount > 2: features.append("Many Names Before=True") conjunctions = set([w.lower() for w in self.tokenize(self.paragraph.text)]).intersection(set(['and', 'but', 'while', 'then'])) if len(conjunctions) > 0 and self.paragraph.find("dialogue") is not None: features.append("Conjunction in Head=True") short_threshold = 10 if len(self.tokens) <= short_threshold: features.append("Short Graf=True") dialogue_length = sum(map(len, self.paragraph.xpath(".//dialogue/text()"))) dialogue_ratio = dialogue_length / len(self.raw) if dialogue_ratio == 1: features.append("All Talk=True") elif dialogue_ratio >= 0.7: features.append("Mostly Talk=True") elif dialogue_ratio < 0.3 and not self.tokens < short_threshold: features.append("Little Talk=True") return features def feature_booleans(self): bool_features = [] for tag in ["PS", "FN", "NN", "ADR", ]: label = "{} {}".format(tag, self.tag_distance) if label in self.features().keys(): bool_features.append("{}=True".format(label)) else: bool_features.append("{}=False".format(label)) return bool_features def tokenize(self, string): return nltk.wordpunct_tokenize(string) def find_speakers(self, tokens): speakers = {} particle_indices = [i for (i, w) in enumerate(tokens) if w in self.particles] for k, g in itertools.groupby(enumerate(particle_indices), lambda (i,x): i-x): index_run = map(itemgetter(1), g) speaker_name = ' '.join(tokens[i] for i in index_run) speakers[min(index_run)] = speaker_name return speakers def xpath_find_speaker(self): speakers = self.paragraph.xpath(".//@speaker") if speakers == []: return "NULL" else: return speakers[0] def pre_speak(self, prior_tag="FN", near_tag="NN"): # Имена перед диалогом features = {} if self.paragraph.text is not None: speakers = self.find_speakers(self.tokenize(self.paragraph.text)) if len(speakers) > 0: features.update({"{} {}".format(prior_tag,self.tag_distance): speakers.values()[0]}) <p class="copyrights"><span class="source">© <a target="_blank" rel="nofollow" href="https://habrahabr.ru/post/304230/">Habrahabr.ru</a></span></p> </div> <br> <!--<div align="left"> <script type="text/topadvert"> load_event: page_load feed_id: 12105 pattern_id: 8187 tech_model: </script><script type="text/javascript" charset="utf-8" defer="defer" async="async" src="//loader.topadvert.ru/load.js"></script> </div> <br>--> <div style="padding-left: 20px;"> <script async src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js?client=ca-pub-2514821055276660" crossorigin="anonymous"></script> <!-- PCNews 336x280 --> <ins class="adsbygoogle" style="display:block" data-ad-client="ca-pub-2514821055276660" data-ad-slot="1200562049" data-ad-format="auto"></ins> <script> (adsbygoogle = window.adsbygoogle || []).push({}); </script> </div> <!-- comments --> <noindex> <div style="margin: 25px;" id="disqus_thread"></div> <script type="text/javascript"> var disqus_shortname = 'pcnewsru'; var disqus_identifier = '707811'; var disqus_title = '[Перевод] Игра Престолов. Поиск авторов диалогов в книгах'; var disqus_url = 'http://pcnews.ru/blogs/%5Bperevod%5D_igra_prestolov_poisk_avtorov_dialogov_v_knigah-707811.html'; (function() { var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true; dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js'; (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq); })(); </script> <!--<noscript>Please enable JavaScript to view the <a rel="nofollow" href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>--> <!--<a href="http://disqus.com" rel="nofollow" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>--> </noindex> </div> <br class="clearer"/> </div> <br class="clearer"/> <div id="footer-2nd"></div> <div id="footer"> <br/><br/> <ul class="horz-menu"> <li class="about"><a href="/info/about.html" title="О проекте">О проекте</a></li> <li class="additional-menu"><a href="/archive.html" title="Архив материалов">Архив</a> </li> <li class="additional-menu"><a href="/info/reklama.html" title="Реклама" class="menu-item"><strong>Реклама</strong></a> <a href="/info/partners.html" title="Партнёры" class="menu-item">Партнёры</a> <a href="/info/legal.html" title="Правовая информация" class="menu-item">Правовая информация</a> <a href="/info/contacts.html" title="Контакты" class="menu-item">Контакты</a> <a href="/feedback.html" title="Обратная связь" class="menu-item">Обратная связь</a></li> <li class="email"><a href="mailto:pcnews@pcnews.ru" title="Пишите нам на pcnews@pcnews.ru"><img src="/media/i/email.gif" alt="e-mail"/></a></li> <li style="visibility: hidden"> <noindex> <!-- Rating@Mail.ru counter --> <script type="text/javascript"> var _tmr = window._tmr || (window._tmr = []); _tmr.push({id: "93125", type: "pageView", start: (new Date()).getTime()}); (function (d, w, id) { if (d.getElementById(id)) return; var ts = d.createElement("script"); ts.type = "text/javascript"; ts.async = true; ts.id = id; ts.src = (d.location.protocol == "https:" ? "https:" : "http:") + "//top-fwz1.mail.ru/js/code.js"; var f = function () { var s = d.getElementsByTagName("script")[0]; s.parentNode.insertBefore(ts, s); }; if (w.opera == "[object Opera]") { d.addEventListener("DOMContentLoaded", f, false); } else { f(); } })(document, window, "topmailru-code"); </script> <noscript> <div style="position:absolute;left:-10000px;"> <img src="//top-fwz1.mail.ru/counter?id=93125;js=na" style="border:0;" height="1" width="1" alt="Рейтинг@Mail.ru"/> </div> </noscript> <!-- //Rating@Mail.ru counter --> </noindex> </li> </ul> </div> <!--[if lte IE 7]> <iframe id="popup-iframe" frameborder="0" scrolling="no"></iframe> <![endif]--> <!--<div id="robot-image"><img class="rbimg" src="i/robot-img.png" alt="" width="182" height="305" /></div>--> <!--[if IE 6]> <script>DD_belatedPNG.fix('#robot-image, .rbimg');</script><![endif]--> </div> <!--[if lte IE 7]> <iframe id="ie-popup-iframe" frameborder="0" scrolling="no"></iframe> <![endif]--> <div id="footer-adlinks"></div> <noindex> <!--LiveInternet counter--><script type="text/javascript"> document.write("<a rel='nofollow' href='//www.liveinternet.ru/click' "+ "target=_blank><img src='//counter.yadro.ru/hit?t45.6;r"+ escape(document.referrer)+((typeof(screen)=="undefined")?"": ";s"+screen.width+"*"+screen.height+"*"+(screen.colorDepth? screen.colorDepth:screen.pixelDepth))+";u"+escape(document.URL)+ ";"+Math.random()+ "' alt='' title='LiveInternet' "+ "border='0' width='1' height='1'><\/a>") </script><!--/LiveInternet--> <!-- Rating@Mail.ru counter --> <script type="text/javascript"> var _tmr = window._tmr || (window._tmr = []); _tmr.push({id: "93125", type: "pageView", start: (new Date()).getTime()}); (function (d, w, id) { if (d.getElementById(id)) return; var ts = d.createElement("script"); ts.type = "text/javascript"; ts.async = true; ts.id = id; ts.src = "https://top-fwz1.mail.ru/js/code.js"; var f = function () {var s = d.getElementsByTagName("script")[0]; s.parentNode.insertBefore(ts, s);}; if (w.opera == "[object Opera]") { d.addEventListener("DOMContentLoaded", f, false); } else { f(); } })(document, window, "topmailru-code"); </script><noscript><div> <img src="https://top-fwz1.mail.ru/counter?id=93125;js=na" style="border:0;position:absolute;left:-9999px;" alt="Top.Mail.Ru" /> </div></noscript> <!-- //Rating@Mail.ru counter --> <!-- Yandex.Metrika counter --> <script type="text/javascript"> (function (d, w, c) { (w[c] = w[c] || []).push(function () { try { w.yaCounter23235610 = new Ya.Metrika({ id: 23235610, clickmap: true, trackLinks: true, accurateTrackBounce: true, webvisor: true, trackHash: true }); } catch (e) { } }); var n = d.getElementsByTagName("script")[0], s = d.createElement("script"), f = function () { n.parentNode.insertBefore(s, n); }; s.type = "text/javascript"; s.async = true; s.src = "https://mc.yandex.ru/metrika/watch.js"; if (w.opera == "[object Opera]") { d.addEventListener("DOMContentLoaded", f, false); } else { f(); } })(document, window, "yandex_metrika_callbacks"); </script> <noscript> <div><img src="https://mc.yandex.ru/watch/23235610" style="position:absolute; left:-9999px;" alt=""/> </div> </noscript> <!-- /Yandex.Metrika counter --> <!-- Default Statcounter code for PCNews.ru http://pcnews.ru--> <script type="text/javascript"> var sc_project=9446204; var sc_invisible=1; var sc_security="14d6509a"; </script> <script type="text/javascript" src="https://www.statcounter.com/counter/counter.js" async></script> <!-- End of Statcounter Code --> <script> (function (i, s, o, g, r, a, m) { i['GoogleAnalyticsObject'] = r; i[r] = i[r] || function () { (i[r].q = i[r].q || []).push(arguments) }, i[r].l = 1 * new Date(); a = s.createElement(o), m = s.getElementsByTagName(o)[0]; a.async = 1; a.src = g; m.parentNode.insertBefore(a, m) })(window, document, 'script', '//www.google-analytics.com/analytics.js', 'ga'); ga('create', 'UA-46280051-1', 'pcnews.ru'); ga('send', 'pageview'); </script> <script async="async" src="/assets/uptolike.js?pid=49295"></script> </noindex> <!--<div id="AdwolfBanner40x200_842695" ></div>--> <!--AdWolf Asynchronous Code Start --> <script type="text/javascript" src="https://pcnews.ru/js/blockAdblock.js"></script> <script type="text/javascript" src="/assets/jquery.min.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/jquery/jquery.json.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/jquery/jquery.form.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/jquery/jquery.easing.1.2.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/jquery/effects.core.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/js/browser-sniff.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/js/scripts.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/js/pcnews-utils.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/js/pcnews-auth.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/js/pcnews-fiximg.js"></script> <script type="text/javascript" src="/assets/a70a9c7f/js/pcnews-infobox.js"></script> </body> </html>