lecture2-2015 (1126921)

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

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

Обработка текстовОбработка текстовЛекция 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,> и в о• Знак ^: [^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.

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

Тип файла PDF

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

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

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