lecture2-2016 (1126933)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Обработка текстовОбработка текстовЛекция 2Регулярные выраженияБазовые задачи обработки текстовОбработка текстовМотивация• Обновить цену товара в прайс-листе:для конкретного товара за 1000р. сделать 999.99р.• Заменить все вхождения одного слова втексте на другое• для части слова (Википедия -> Энциклопедия)• с учетом контекста• Найти сообщения о терроризме• Фильтрация нецензурных высказыванийна форумахОбработка текстовРегулярные выражения• Regular Expressions(RegExp)• Языки программирования(Python, Perl, Ruby,Java, .Net)• Текстовые редакторы(Vim, EmEdit)• Утилиты (grep, sed)Обработка текстовРегулярные выражения• Регулярные выражения - алгебраическаянотация для записи множества строк• Функции Pythonimport rere.search("в","пиво").group(0) # вre.sub("о","ко","пиво") # пивкоre.findall("cd","abcdcde") # [“cd”,”cd”]Обработка текстовРегулярные выражения• Последовательность букв: abcd• Чувствительны к регистру: “Пиво”= “пиво”• Дизъюнкция: [П|п]иво,[abc],[1234567890]• Интервал: [A-Z], [0-9], [A-Za-z]for letter in re.findall("[а-о]","пиво"):print(letter, end=‘ ‘)> и в о• Знак ^: [^a] - все кроме “а”• “.” - любой символ, кроме \nОбработка текстовРегулярные выражения• ? - условие для 0 или 1 вхождениясимволаre.findall("пивк?о", "пиво или пивко")> [“пиво”,”пивко”]• Как найти “Gooooogle”?• Счетчики–Gooo*gle–Goo+gleprint(re.sub(“Goo+gle”,"Google","Gooooogle"))> GoogleОбработка текстовРегулярные выражения• Якоря^ - начало строки$ - конец строкиre.search("^cat(1|2)","cat1 cat2").group(0)> cat1re.search("cat(1|2)$","cat1 cat2").group(0)> cat 2Обработка текстовРегулярные выражения• Память (Memory)text="A conditional random field (CRF) is a ..."print(re.search(“\([^\)]+\)”,text).group(0))> (CRF)print(re.search(“\(([^\)]+)\)”,text).group(1))> CRFtext1 = "the faster they ran, the faster we ran"text2 = "the faster they ran, the faster we ate"re.search("the (.*)er they (.*), the \\1er we \\2", text1) # Matchre.search("the (.*)er they (.*), the \\1er we \\2", text2) # Not match• Приоритет операцийКруглые скобкиСчетчикиПоследовательности и якоряДизъюнкция()* + ? {}the ^my end$|Обработка текстовПрактические примеры• Найти все вхождения слова в тексте–слово the в тексте 6 разОбработка текстовПрактические примеры• ELIZAUser: Men are all alike.ELIZA: IN WHAT WAY?User: They’re always bugging us about something otherELIZA: CAN YOU THINK OF A SPECIFIC EXAMPLE?User: My boyfriend made me come hereELIZA: YOUR BOYFRIEND MADE YOU COME HEREUser: He says I’m depressed much of the timeELIZA: I AM SORRY TO HEAR YOU ARE DEPRESSEDsentence=re.sub("I’m","YOU ARE", sentence)...sentence=re.sub(".* YOU ARE (depressed|sad) .*","I'M SORRY TO HEAR YOU ARE \\1",sentence)sentence=re.sub(".* all .*","IN WHAT WAY?",sentence)sentence=re.sub(".* always .*","CAN YOU THINK OF A SPECIFIC EXAMPLE?",sentence)Обработка текстовКонечные автоматы• Finite-state automation (FSA)• Один из важнейших инструментов дляобработки текстов• Могут быть использованы для реализациирегулярных выраженийконечныеавтоматырегулярныеязыкирегулярныеграмматикирегулярныевыраженияОбработка текстовИспользование КА дляраспознавания языка• Научимся говорить с овцами–бээ!–бэээ!–бээээ!–бэээээ!–...• RE: “бээ+!”эбq0эq1эq2!q3q4Обработка текстовПредставление автоматов• Текст: лента с ячейкамиq0эбэ!б• Таблица переходов между состояниямиСостояние01234Входбэ!12334Обработка текстовФормальное определениеQ = q0 q1 q2 .

. . qN1конечное множество из N состоянийконечный входной алфавитq0начальное состояниеFмножество конечных состояний(q, i) : Q⇥Qфункция перехода или матрицаперехода между состояниямиОбработка текстовАлгоритм распознавания длядетерминированного КА#encoding=CP1251def recognize(tape, machine, acceptStates):index = 0 # Beginning of tape0currentState = 0 # Initial state of machinewhile True:1if index == len(tape):2if currentState in acceptStates:return True3else:4return Falseelif machine[currentState].has_key(tape[index]):currentState = machine[currentState][tape[index]]index+=1else:return FalseВходб1э!233machineSheep = {0:{"б":1}, 1:{"э":2}, 2:{"э":3}, 3:{"э":3,"!":4}, 4:{}}print(recognize(“бээээээ!",machineSheep, [4]))4Обработка текстовФормальные языкиэбq0эq1эq2!q3q4• формальный язык — это множествоконечных слов (строк, цепочек) надконечным алфавитом= {a, b, !}L(m) = {baa!, baaa!, baaaa!, .

. .}Обработка текстовПример формального языкаодиндватричетырепятьшестьсемьвосемьдевятьдесятьq0двадцатьтридцатьсорокпятьдесятпятнадцатьодиннадцатьшестнадцатьдвенадцатьсемнадцатьтринадцатьвосемнадцатьчетырнадцатьдевятнадцатьq1шестьдесятсемьдесятвосемьдесятдевяностоq2одиндватричетырепятьшестьсемьвосемьдевятьОбработка текстовНедетерминированные КА• Обобщение ДКА• Недетерминизм двух типовэбТип 1q0эq1бТип 2q0эq2q3ээq1!q2q4!q3q4Обработка текстовРаспознование для НКА• Подходы к решению проблемынедетерминизма–Сохранение состояний (backup)•поиск в глубину и ширину–Просмотр будующих состояний (look-ahead)–ПараллелизмСостояние01234б1Входэ!22,34Обработка текстовДКА и НКА• ДКА и НКА эквивалентны• Существует простой алгоритм дляпреобразования НКА в ДКА• Идея:–взять все параллельные ветки НКА–в них взять все состояния, в которыходновременно может находиться НКА–объединить их в новое состояние ДКА• В худшем случае НКА с N состояниямипреобразуется в ДКА с 2N состояниямиОбработка текстовРегулярные языки и ДКА1.2.- регулярный язык⇥a⇤ , {a} - регулярный язык3.

Для любых регулярных языков L1 и L2 , такими также являются:· L2 = {xy | x ⇥ L1 , y ⇥ L2 } , соединение L1 и L2(b) L1L2 , объединение или дизъюнкция L1 и L2(c) L1 , замыкание (Клини) языка L1(a) L1•.• регулярные языки также замкнутыотносительно операций• пересечения• разности• дополнения• инверсииОбработка текстовПостроение автомата длярегулярных выраженийq0qfr=q0qfr=qfr=aaq0Обработка текстовПостроение автомата длярегулярных выраженийqfq0qfq0КА 1КА 2Последовательное соединение двух конечных автоматовОбработка текстовПостроение автомата длярегулярных выраженийqfq0КА 1q0qfq0qfКА 2Объединение двух конечных автоматовОбработка текстовПостроение автомата длярегулярных выраженийq0q0qfКА 1Замыкание конечного автоматаqfОбработка текстовБазовые задачи• Токенизация• Стемминг и лемматизация• Определение границ предложений• Стоп-словаОбработка текстовТокенизация• Токенизация - разбиение текста наосмысленные элементы (слова, фразы,символы), называемые токенами>>> raw = """'When I'M a Duchess,' she said to herself, (not in a very hopeful tone ...

though), 'I won't have any pepper in my kitchen AT ALL. Soup does very... well without--Maybe it's always pepper that makes people hot-tempered,'...""">>> re.split(r' ', raw)["'When", "I'M", 'a', "Duchess,'", 'she', 'said', 'to', 'herself,', '(not', 'in','a', 'very', 'hopeful', 'tone\nthough),', "'I", "won't", 'have', 'any', 'pepper','in', 'my', 'kitchen', 'AT', 'ALL.', 'Soup', 'does', 'very\nwell', 'without--Maybe',"it's", 'always', 'pepper', 'that', 'makes', 'people', "hot-tempered,'..."]>>> re.split(r'[ \t\n]+', raw)["'When", "I'M", 'a', "Duchess,'", 'she', 'said', 'to', 'herself,', '(not', 'in','a', 'very', 'hopeful', 'tone', 'though),', "'I", "won't", 'have', 'any', 'pepper','in', 'my', 'kitchen', 'AT', 'ALL.', 'Soup', 'does', 'very', 'well', 'without--Maybe',"it's", 'always', 'pepper', 'that', 'makes', 'people', "hot-tempered,'..."]Обработка текстовТокенизация• Чтобы пунктуация не присоединялась к словам,можно попробовать оставить только символьныепоследовательности• (W - эквивалент [^a-zA-Z0-9_])• (w - эквивалент [a-zA-Z0-9_])>>> re.split(r'\W+', raw)['', 'When', 'I', 'M', 'a', 'Duchess', 'she', 'said', 'to', 'herself', 'not',‘in', 'a', 'very', 'hopeful', 'tone', 'though', 'I', 'won', 't', 'have','any', ‘pepper', 'in', 'my', 'kitchen', 'AT', 'ALL', 'Soup', 'does', 'very','well', ‘without', 'Maybe', 'it', 's', 'always', 'pepper', 'that', 'makes','people', 'hot', ‘tempered', '']• Но тогда появляются пустые токеныОбработка текстовТокенизация• Добавим границы• \S - эквивалент [^ \t\r\n\f]>>> re.findall(r'\w+|\S\w*', raw)["'When", 'I', "'M", 'a', 'Duchess', ',', "'", 'she', 'said', 'to', 'herself', ',','(not', 'in', 'a', 'very', 'hopeful', 'tone', 'though', ')', ',', "'I", 'won', "'t",'have', 'any', 'pepper', 'in', 'my', 'kitchen', 'AT', 'ALL', '.', 'Soup', 'does','very', 'well', 'without', '-', '-Maybe', 'it', "'s", 'always', 'pepper', 'that','makes', 'people', 'hot', '-tempered', ',', "'", '.', '.', '.']• Теперь нужно не разбивать слова натокены>>> re.findall(r"\w+(?:[-']\w+)*|'|[-.(]+|\S\w*", raw)["'", 'When', "I'M", 'a', 'Duchess', ',', "'", 'she', 'said', 'to', 'herself', ',','(', 'not', 'in', 'a', 'very', 'hopeful', 'tone', 'though', ')', ',', "'", 'I',"won't", 'have', 'any', 'pepper', 'in', 'my', 'kitchen', 'AT', 'ALL', '.', 'Soup','does', 'very', 'well', 'without', '--', 'Maybe', "it's", 'always', 'pepper','that', 'makes', 'people', 'hot-tempered', ',', "'", '...']Обработка текстовТокенизация• В NLTK есть regexp_tokenizer>>> text = 'That U.S.A.

poster-print costs $12.40...'>>> pattern = r'''(?x)# set flag to allow verbose regexps...([A-Z]\.)+# abbreviations, e.g. U.S.A....| \w+(-\w+)*# words with optional internal hyphens...| \$?\d+(\.\d+)?%? # currency and percentages, e.g. $12.40, 82% ...| \.\.\.# ellipsis...| [][.,;"'?():-_`] # these are separate tokens; includes ], [... '''>>> nltk.regexp_tokenize(text, pattern)['That', 'U.S.A.', 'poster-print', 'costs', '$12.40', '...']• Если нет специфичных требований можноиспользовать WordPunctTokenizer
from nltk import WordPunctTokenizer
raw = """'When I'M a Duchess,' she said to herself, (not in a very hopeful tone
though), 'I won't have any pepper in my kitchen AT ALL.

Soup does very
well without--Maybe it's always pepper that makes people hot-tempered,'..."""
tokens = WordPunctTokenizer().tokenize(raw)
print(tokens)
["'", 'When', 'I', "'", 'M', 'a', 'Duchess', ",'", 'she', 'said', 'to', 'herself', ',', '(', 
'not', 'in', 'a', 'very', 'hopeful', 'tone', 'though', '),', "'", 'I', 'won', "'", 't', 'have', 
'any', 'pepper', 'in', 'my', 'kitchen', 'AT', 'ALL', '.', 'Soup', 'does', 'very', 'well', 
'without', '--', 'Maybe', 'it', "'", 's', 'always', 'pepper', 'that', 'makes', 'people', 
'hot', '-', 'tempered', ",'..."]Обработка текстовТокенизация• Многозначность определения токена• хэштеги (#текст)• “I’m” - один токен?• “won’t” - один токен?• Dr.

- токен?• Зависит от задачиОбработка текстовТокенизация• В каком виде лучше представлять результаттокенизации?• список токенов• простая модель• что, если нужно сразу несколькотокенизаторов?• что если нужно понимать где в текстеоригинальное слово?• Более общий способ представлениярезультатов анализа текстов - модельаннотацийОбработка текстовАннотации• Аннотация - в общем случае тройка• начало• конец• значение (не обязательно)• Пример токенизации>>> [(0, 1), (1, 5), (6, 9), (10, 11), (12, 19), (19, 20), (20, 21), (22, 25), (26, 30), (31, 33), (34, 41), (41, 42), (43, 44),(44, 47), (48, 50), (51, 52), (53, 57), (58, 65), (66, 70), (82, 88), (88, 89), (89, 90), (91, 92), (92, 93), (94, 96), (96,99), (100, 104), (105, 108), (109, 115), (116, 118), (119, 121), (122, 129), (130, 132), (133, 137), (138, 142), (143,147), (148, 152), (164, 168), (169, 183), (184, 186), (186, 188), (189, 195), (196, 202), (203, 207), (208, 213), (214,220), (221, 233), (233, 234), (234, 238)]print(raw[109:115])>>> pepperОбработка текстовАннотации• Аннотации используются во многихпроектах по обработке текстов• Apache UIMA• Texterra - ISPRAS API(https://api.ispras.ru)from ispras import texterrat = texterra.API(‘API KEY')
tokens = t.tokenizationAnnotate(raw)
print([(token['start'], token['end']) for token in tokens])Обработка текстовСегментация• В китайском языке слова не разделяются проблемнымисимволами• 戴帽⼦子的貓 -> Thecatinthehat• Жадный алгоритм по словарю• Многозначность• thetabledownthere• the table down there• theta bled own there• Проблемы, если слова нет в словаре• Но в целом, алгоритм неплохо работает длякитайского языка, так как слова имеют схожую длинуОбработка текстовСегментация• Обозначим сегментацию через бинарныйвекторtext = "doyouseethekittyseethedoggydoyoulikethekittylikethedoggy"
seg1 = “0000000000000001000000000010000000000000000100000000000”
seg2 = “0100100100100001001001000010100100010010000100010010000"def segment(text, segs):
words = []
last = 0
for i in range(len(segs)):
if segs[i] == '1':
words.append(text[last:i+1])
last = i+1
words.append(text[last:])
return wordsprint(segment(text, seg2))
>>> ['do', 'you', 'see', 'the', 'kitty', 'see', 'the', 'doggy', 'do', 'you', 'like','the', 'kitty', 'like', 'the', 'doggy']*NLTK BookОбработка текстовСегментация• Придумаем функцию оценки качества сегментации• размер лексикона (длина слов плюс разделительныйсимвол для каждого слова)• количество информации, необходимое для реконструкцииисходного текста из лексиконаhttp://www.nltk.org/book/ch03.htmlОбработка текстовСегментация• Придумаем функцию оценки качества сегментации• размер лексикона (длина слов плюс разделительныйсимвол для каждого слова)• количество информации, необходимое для реконструкцииисходного текста из лексиконаtext = "doyouseethekittyseethedoggydoyoulikethekittylikethedoggy"
seg1 = “0000000000000001000000000010000000000000000100000000000”
seg2 = “0100100100100001001001000010100100010010000100010010000"def evaluate(text, segs):
words = segment(text, segs)
text_size = len(words)
lexicon_size = sum(len(word) + 1 for word in set(words))
return text_size + lexicon_sizeprint(evaluate(text, seg1))>>> 64
print(evaluate(text, seg2))>>> 48Обработка текстовСегментация• Найдем минимум функции алгоритмомимитации отжигаfrom random import randintdef flip(segs, pos):
return segs[:pos] + str(1-int(segs[pos])) + segs[pos+1:]

def flip_n(segs, n):
for i in range(n):
segs = flip(segs, randint(0, len(segs)-1))
return segs

def anneal(text, segs, iterations, cooling_rate):
temperature = float(len(segs))
while temperature > 0.5:
best_segs, best = segs, evaluate(text, segs)
for i in range(iterations):
guess = flip_n(segs, int(round(temperature)))
score = evaluate(text, guess)
if score < best:
best, best_segs = score, guess
score, segs = best, best_segs
temperature = temperature / cooling_rate
print(evaluate(text, segs), segment(text, segs))
return segsanneal(text, seg1, 5000, 1.2)Обработка текстовСегментация• Результат работы(64, ['doyouseethekitty', 'seethedoggy', 'doyoulikethekitty', 'likethedoggy'])(64, ['doyouseethekitty', 'seethedoggy', 'doyoulikethekitty', 'likethedoggy'])(64, ['doyouseethekitty', 'seethedoggy', 'doyoulikethekitty', 'likethedoggy'])(64, ['doyouseethekitty', 'seethedoggy', 'doyoulikethekitty', 'likethedoggy'])(64, ['doyouseethekitty', 'seethedoggy', 'doyoulikethekitty', 'likethedoggy'])(63, ['doyouse', 'et', 'hekitty', 'seethedoggydoyoulik', 'et', 'hekitty', 'likethe', 'd', 'oggy'])(62, ['doyouse', 'ethekitty', 'seethe', 'doggydoyoulik', 'ethekitty', 'l', 'ikethed', 'oggy'])(60, ['do', 'youse', 'ethekitty', 'seethedoggydoyoulik', 'ethekitty', 'l', 'ikethedoggy'])(60, ['do', 'youse', 'ethekitty', 'seethedoggydoyoulik', 'ethekitty', 'l', 'ikethedoggy'])(57, ['do', 'youse', 'ethekitty', 'see', 'thedoggy', 'doyoulik', 'ethekitty', 'l', 'ike', 'thedoggy'])(53, ['doyouse', 'ethekitty', 'see', 'thedoggy', 'doyoulik', 'ethekitty', 'like', 'thedoggy'])(51, ['doyou', 'se', 'ethekitty', 's', 'ee', 'thedoggy', 'doyou', 'lik', 'ethekitty', 'lik', 'e', 'thedoggy'])(49, ['doyou', 'se', 'ethekitty', 'see', 'thedoggy', 'doyou', 'lik', 'ethekitty', 'lik', 'e', 'thedoggy'])(49, ['doyou', 'se', 'ethekitty', 'see', 'thedoggy', 'doyou', 'lik', 'ethekitty', 'lik', 'e', 'thedoggy'])(46, ['doyou', 'se', 'ethekitty', 'se', 'e', 'thedoggy', 'doyou', 'lik', 'ethekitty', 'lik', 'e', 'thedoggy'])(46, ['doyou', 'se', 'ethekitty', 'se', 'e', 'thedoggy', 'doyou', 'lik', 'ethekitty', 'lik', 'e', 'thedoggy'])(46, ['doyou', 'se', 'ethekitty', 'se', 'e', 'thedoggy', 'doyou', 'lik', 'ethekitty', 'lik', 'e', 'thedoggy'])Обработка текстовСтемминг и лемматизация• Часто необходимо обрабатывать разныеформы слова одинаково.• Например, при поиске: по запросам“кошками” и “кошкам” ожидаютсяодинаковые ответы• Стемминг - это процесс нахожденияосновы слова, которая не обязательносовпадает с корнем слова• Лемматизация - приведение слова ксловарной формеОбработка текстовСтемминг• Стемминг - это процесс нахожденияосновы слова, которая не обязательносовпадает с корнем слова• Стемминг отбрасывает суффиксы иокончания до неизменяемой формыслова• Примеры:• кошка -> кошк• кошками -> кошк• пылесосы -> пылесосОбработка текстовСтемминг• Наиболее распространенный стеммер - Snowballиз проекта Apache Lucene• Работает для нескольких языков, включая русский#coding: utf-8

from nltk import SnowballStemmer

word = "пылесосы".decode("utf-8")
stem = SnowballStemmer("russian").stem(word)
print(stem)http://snowball.tartarus.org/algorithms/russian/stemmer.htmlОбработка текстовЛемматизация• У разных слов часто совпадает основа• пол : полу , пола , поле , полю , поля , пол ,полем , полях , полям• лев : левый, левая, лев• Увеличивается многозначность и ухудшаютсярезультаты работы приложений• Лемматизация - приведение слова к словарнойформе• Примеры:• Кошки -> кошка• Кошками -> кошкаОбработка текстовЛемматизация• Для английского языка можно использоватьnltk.WordNetLemmatizer()• Для русского языка:• Илья Сегалович, Михаил Маслов.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций