Daniel Jurafsky & James H. Martin. Speech and Language Processing

Regular expressions
A formal language for specifying text strings
How can we search for any of these?
самовар
вар
варежка
Варвара

Формальные языки (ФЯ)
RE описывают регулярные языки в теории формальных языков.
ФЯ состоит из слов, порождённых RE.
RE включают константы и операторы, которые задают:
множество строк,
и операций над ними

Константы, являющиеся RE
над конечным алфавитом Σ
(пустое множество) ∅
(пустая строка) ε — множество, содержащее только пустую строку
(символьный литерал) a∈Σ — множество, содержащее только символ a.

Операции, генерирующие RE 1
над конечным алфавитом Σ
R, S — это RE
(сцепление, конкатенация) RS
Пример: {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"}.
(дизъюнкция, чередование) R|S
{"ab", "c"}|{"ab", "d", "ef"} = {"ab", "c", "d", "ef"}.
(замыкание Клини, звезда Клини) R*

Операции, генерирующие RE 2
(замыкание Клини, звезда Клини) R*
минимальное надмножество множества R, которое содержит ε и замкнуто относительно конкатенации
{"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", … }.
{"0","1"}* =

Области применения RE
поиск по шаблону
замена
(pattern substitution)
chatbot (тест Тьюринга)
токенизация

Regular Expressions: Disjunctions
Letters inside square brackets []
Ranges [A-Z]

Regular Expressions: Negation in Disjunction
Negations [^Ss]
Carat means negation only when first in []

Regular Expressions: More Disjunction
Woodchucks is another name for groundhog!
The pipe | for disjunction

Regular Expressions: ? * + .
Stephen C Kleene
Kleene *, Kleene +

Regular Expressions: Anchors ^ $

Токенизация (две стратегии разбиения на слова)
Пробелы?
Слова?
Какие символы?

Разбиваем на слова (VIM):
(1) ищем границы слов
Но он не умер. Открыв слегка глаза, он увидел себя сидящим на чем-то каменном. Вокруг него что-то шумело. Когда он открыл, как следует, глаза, он увидел, что шумит море, и что даже больше того, — волна покачивается у самых его ног, и что, короче говоря, он сидит на самом конце мола, и что под ним голубое сверкающее море, а сзади — красивый город на горах.
[.!?]

VIM
Vi, Vim and Emacs

Miessler D. The Differences Between Vi, Vim, and Emacs.https://danielmiessler.com/blog/differences-vi-vim-emacs/

Miessler D. The Differences Between Vi, Vim, and Emacs.https://danielmiessler.com/blog/differences-vi-vim-emacs/

Vim, Emacs
Bill Joy
1976
Unix modularity
work like a language =>? intuitive
installed nearly everywhere
Richard Stallman
1976
power and configurability
live in the system as much as possible
Lisp

Just memorize this vi / vim cheat sheet and you're ready for lightning-quick editing.

http://www.viemu.com/vi-vim-cheat-sheet.gif

Разбиваем на слова (VIM):
(1) ищем границы слов
[.!?]

Разбиваем на слова (VIM)
[.!?]

Токенизация
Пробелы,
но не всегда:
Saint Petersburg
всё равно (частица)
?
Слова?
Поздравляю с 8 марта :) #весна

Токенизация
Пробелы,
но не всегда:
Saint Petersburg
всё равно (частица)
?
Слова?
Поздравляю с 8 марта :) #весна
+ смайлики,
+ хештеги
!Китайский язык: 1755年1月25日俄罗斯女沙皇伊丽莎白·彼得罗芙娜下令建立莫斯科大学，同年4月26日该大学开始授课。至今为止在俄罗斯1月25日是大学生节。

Разбиваем на слова:
(2) ищем сами слова

The detailed elaborations on the development of even a short program form a long story, indicating that careful programming is not a trivial subject. If this paper has helped to dispel the widespread belief that programming is easy as long as the programming language is powerful enough and the available computer is fast enough, then it has achieved one of its purposes. #NiklausWirth #programming
Niklaus Wirth. Program Development by Stepwise Refinement. 1995.
http://sunnyday.mit.edu/16.355/wirth-refinement.html

Разбиваем на слова (2):
ищем сами слова
ищем слова program и programming,
поиск по двум словам, какое раньше?
поиск слов с корнем program,
RE: Quantifiers, Greedy and Non-Greedy
*, *?, +? VIM: *, \+, \=, \{-}
замена (substitute) на WORD,

Жадные (ленивые) квантификаторы:
? * + .

Разбиваем на слова:
ищем сами слова
The detailed elaborations on the development of even a short program form a long story, indicating that careful programming is not a trivial subject. If this paper has helped to dispel the widespread belief that programming is easy as long as the programming language is powerful enough and the available computer is fast enough, then it has achieved one of its purposes. #NiklausWirth #programming

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

Example
Find me all instances of the word “the” in a text.
the
Misses capitalized examples
[tT]he
Incorrectly returns other or theology
[^a-zA-Z][tT]he[^a-zA-Z]

Errors
The process we just went through was based on fixing two kinds of errors
Matching strings that we should not have matched (there, then, other)
False positives (Type I)
Not matching things that we should have matched (The)
False negatives (Type II)

Errors cont.
In NLP we are always dealing with these kinds of errors.
Reducing the error rate for an application often involves two antagonistic efforts:
Increasing accuracy or precision (minimizing false positives)
Increasing coverage or recall (minimizing false negatives).

Summary
Regular expressions play a surprisingly large role
Sophisticated sequences of regular expressions are often the first model for any text processing text
For many hard tasks, we use machine learning classifiers
But regular expressions are used as features in the classifiers
Can be very useful in capturing generalizations

Литература
Фридл, Дж. Регулярные выражения. — СПб.: «Питер», 2001. — 352 с.
(Mastering Regular Expressions)
Miessler D. The Differences Between Vi, Vim, and Emacs. https://danielmiessler.com/blog/differences-vi-vim-emacs/

Ссылки
http://vimregex.com