Презентации лекций (1126940), страница 2

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

Текст из файла (страница 2)

. .}Обработка текстовПример формального языкаодиндватричетырепятьшестьсемьвосемьдевятьдесять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()• Для русского языка:• Илья Сегалович, Михаил Маслов.

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

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