IB113 Radek Pelánek
2019
1/68
1950 1960 1970 1960 1990 2000 2010
Rok
JAN, JAROSLAV, JIŘÍ, MAREK, MATĚJ, NIKOLA,
ONDŘEJ, RADEK, TOMÁŠ, VALDEMAR, D > <ff>      <s> -s 0„c
2/68
Dnešní prednáška
Příklady a techniky relevantní k situaci
• mám data (text, tabulková data)
• chci získat vhled, informace
Regulární výrazy: motivace
• vyhledání e-mailových adres v textu
• vyhledání odkazů v HTML dokumentu
• náhrada „jméno příjmení" za „příjmení jméno"
• změna formátu datumů
• odstranění bílých znaků
4/68
nástroj pro hledání „vzorů" v textu
• programování
• textové editory
• príkazová řádka: např. grep
• teorie: formální jazyky, konečné automaty
obecně používaný nástroj
syntax velmi podobná ve většině jazyků, prostredí bohatá syntax
následuje „ochutnávka", ukázky základního využití v Pythonu
NíľW SKíLL 1 CdKďCT (scenarios were [T
OH Nö! THE kU[£R HER ON VACATION!
s
But to find them wfd have to seto Though 2od hb of Míľ wokm m
(evejvboc^ STWO SAX
			4
& ür			e jí
http://xkcd.com/208/
•<□►  < [SP ►  < -ž ►  < ►
7/68
Ukázka
Naivní způsob hledání e-mailových adres v textovém souboru import re
f = open(Mtestovaci-soubor.txt") for line in f.readlines():
if re.search(r1[a-z]+@[a-z]+\.cz1, line): print(line) f. closeO
-
Znaky a speciální znaky
• základní znak „vyhoví" právě sám sobě
• speciální znaky: .~$* + ?{}[]\l
• umožňují konstrukci složitějších výrazů
• chceme, aby odpovídaly příslušnému symbolu
c)
prefix \
[abc]	=jeden ze znaků a, b, c		
[~abc]	= cokoliv jiného než a, b, c		
\d	Čísla: [0-9]		
\D	Cokoliv kromě čísel: ["0-9]		
\s	Bílé znaky: [ \t\n\r\f\v]		
\S	Cokoliv kromě bílých znaků:		\t\n\r\f\v]
\w	Alfanumerické znaky: [a-zA-	-zo	-9_]
\W	Nealfanumerické znaky: [~a-	-zA-	-Z0-9J
10/68
Speciální symboly
libovolný znak začátek řetězce $        konec řetězce
I alternativa - výběr jedné ze dvou možností
11/68
Příklady
Jaký je význam následujících výraz
• kocka|pes
• ~[Pp]rase$
• \d[A-Z]\d \d\d\d\d
Ooakovánŕ
* nula a více opakování
+ jedno a více opakování
? nula nebo jeden výskyt
{m5n} m až n opakování
Pozn. *, + jsou „hladové", pro co nejmenší počet opakování *?, +?
13/68
Jaký je význam následujících výrazů?
• ~\s*Nadpis
• ~a.+a$
• \d{3}\s?\d{3}\s?\d{3}
• [a-z]+@[a-z]+\.cz
• ~To:\s*(fi|kit)(-int)?@fi\.muni\.cz
14/68
Která z následujících slov vyhoví jednotlivým výrazům?
	p[ars]e	p[ars]*e	p["ars]e
ps			
pes			
pse			
poe			
prase			
poklice			
15/68
Která z následujících slov vyhoví jednotlivým výrazům?
	p[ars]e	p[ars]*e	p["ars]e
ps	X	X	X
pes	X	/	X
pse	/	/	X
poe	X	X	/
prase	X	/	X
poklice	X	X	X
16/68
Kontrola tabulky v Pythonu
import re
texts = [MpsM,"pes","pse","poe","prase","poklice"] regexps = [ r'p[ars]e', r'p[ars]*e', r'p[~ars]e' ]
for text in texts:
print (text, end=" 11) for regexp in regexps:
if re.search(regexp, text):
print (1, end=" 11) else:
print (0, end=" 11)
print()
17/68
Backreference
• „odkaz" na předchozí část textu
• pomocí \1, \2, \3, ...
• příklad: slova, která obsahují opakovaně stejnou trojici písmen (jinde než) na začátku a konci
• starosta
• periferie
• jak zapsat regulární výraz?
• jaká další slova splňují?
18/68
Backreference a trojice písmen
• seznam slov, např.
https://wiki.korpus.cz/doku.php/seznamy:srovnavaci_seznamy
• regulární výrazy:
• ~(. . .).*\1$
• .(...).*\l.
• výstupy např.:
• ostrost
• skaliska
• bramborami
• multikulturní
19/68
Bez regulárních výrazů
Varianta „uvnitř slova":
def triple_match(word):
for i in ranged, len(word)-3) :
for j in range(i+l, len(word)-3): if word[i:i+3] == word [j: j +3] return True
return False Je to ekvivalentní?
< □ ► * gi ► 4
Detekce opakovaných trojic
• regulární výraz: .(...). *\1.
• kontrola podmínky: word[i:i+3] == word[j:j
• rozdílné chování: skleneného, kovovou, kocicich
Co je správně?
Nejasná specifikace problému...
Regulární výrazy: xkcd
r[REGEX GOLF:
YOO TKVTo Wíttf ONE
grdup eur notthe: dm£
/tí | Difl|B/ IWCHE5 CDOL
501UROTE ň PROGPAM
...euri ípstwcdoe;
50 Xh GREPPlNG FĎR FiLEB THfíT tJXXC ÍJKE rtgex golf 50wer5.
/rra^-)*R£jGEXGDLF/ NOU W UME
http://xkcd.com/1313/ http://www.explainxkcd.com/wiki/index.php/1313:_Regex_Golf
https://regex.alf.nu/
22/68
ulárnŕ výrazy v Pythonu
• knihovna re (import re)
• re.match - hledá shodu na začátku řetězce
• re.search - hledá shodu kdekoliv v řetězci
• (re. compile - pro větší efektivitu)
• re. sub - nahrazení
• „raw string" - r'vyraz' - nedochází k interpretaci speciálních znaků jako u běžných řetězců v Pythonu
23/68
Regi
uiarni výrazy
prace s výs
led ke
m
match/search vrací „MatchObject" pomocí kterého můžeme s výsledkem pracovat
pomocí kulatých závorek () označíme, co nás zajímá
3       vT) Q^O
24/68
»> m = re.match(r' (\w+)  (\w+) ' , \
'Isaac Newton, fyzik')
»> m.group(0) 1 Isaac Newton1 »> m.group(1) 1 Isaac 1
»> m.group(2) 1 Newton1
4  □  ►   4 [SP ► 4
Regulární výrazy v Pythonu: nahrazení
import re
text = 'Petr Novák, 329714, FI B-AP BcAP1 print(re.sub(r'(\w*)  (\w*),  (\d*)1,
r'\2 \1, UC0=\3',
text))
# 'Novák Petr, UC0=329714, FI B-AP BcAP'
26/68
27/68
Kahoot: program 1
import re
def filter_list(regexp, alist): output = [] for word in alist:
if re.search(regexp, word): output.append(word) return output
fruits = ['apple',   'banana',  'pear', 'blackberry',
1fig',  'peach']
print(filter_list(r'a.*e', fruits))
28/68
Kahoot: program 2
import re
def filter_list(regexp, alist): output = [] for word in alist:
if re.search(regexp, word): output.append(word) return output
nums = [11.21,  '3',  '5.832',  '428', '1.55']
print(len(filter_list(r'\d.\d', nums)))
•<□►   4 ^ t   <  -z  ►   4 S ►
29/68
Kahoot: program 3
import re
def filter_list(regexp, alist): output = [] for word in alist:
if re.search(regexp, word): output.append(word) return output
names = ['Kremilek a Vochomurka',  'Maxipes Fik
1Rakosnicek1,  'Mala čarodejnice 1, 1 Tom a Jerry1]
print(len(filter_list(r1~\w*\s\w*$1, names)))
Kahoot: program 4
import re
def decide(regex, string):
if re.search(regex, string)
return 1Y1 return 1N1
for regex in [r'A.I', r'A.*I', r'A.*I$']:
print(decide(regex,  'PARDUBICE'), end=IMI)
<  □  ►   4 ^ t   <  -z  ►   4 S ►
31/68
Kahoot: program 5
import re
text = 'FI MU, Botanická 68a, 602 00 Brno'
m = re.match(r'.*,  (\w*).*, [\s\d]*(\w*)$', text)
print(m.group(l)+ 1   1 + m.group(2))
32/68
Kahoot: program 6
import re
text = 'Petr /vykopal#sloveso/ dim.
text =
re.sub(r'/(.*)#(.*)/' ,
r'<span cat=M\2M>\l</span>', text)
print(text)
•<□►   4 ^ t   <  -z  ►   4 S ►
33/68
Kahoot: program 7
text = 1 one two   three 1 text split('e') print(len(text))
34/68
Kahoot: program 8
def process(alist): output = [] for x in alist:
if isinstance(x, str): output.append(x) return output
alist = [3,  '2.4',  '1', 8.2, '2
print (11 +11. join (process (alist)))
Kahoot: program 9
def magic(alist):
for i in range(len(alist)):
alist [i] = alist[i].count(1 a1)
fruits = [1 apple 1, magic(fruits) print(fruits)
banana', 'fig']
•<□►   4 ^ t   <  -z  ►   4 S ►
36/68
Analýza textu
vstup: text (v textovém souboru) výstup: zajímavé statistiky
• délka vět, slov
• nejčastější slova (určité minimální délky) o frekvence písmen, digramy, trigramy
cvičení
37/68
Analýza textu
statistiky délky slov a vět:
• x - průměr
• s - směrodatná odchylka (míra variability)
slova věty
x       s        x s
Starý zákon	4.3	2.3	14.9	7.8
Čapek	4.5	2.5	14.9	13.3
Pelánek	5.9	3.6	13.5	6.9
Wikipedie	5.6	3.0	14.8	8.3
Analýza textu - dekompozice problému
text —seznam délek slov (vět) O seznam délek —>► statistiky O statistiky —>► výpis
•<□►   4 ^ t   <  -Ž  ►   4 S ►
39/68
• vstup: rozsáhlý text
• výstup: náhodně generovaný text, který má „podobné charakteristiky" jako vstupní text
• imitace na úrovni písmen nebo slov
40/68
Náhodnostnŕ imitace vstupního textu
I špiské to pole kavodali parnas ne nebo kdy v Dejný Odm sem uvalini se zabijí s Pan stěží re, a silobe lo v ne rečekovících blova v nadrá těly jakvěmutelaji rohnutkohonebout anej Fravinci V A pěk fine houty. zal Jírakočítencej ské žil, kdDo jak a to Lorskríže si tomůžu schno mí, kto.
Kterak král kočku kupoval V zemi Taškářů panoval král a zapřísáhl se velikou přísahou že bude pochválena První pán si jí ani nevšimnul zato druhý se rychle shýbl a Juru pohladil Aha řekl sultán a bohatě obdaroval pana Lustiga koupil od něho telegram z Bombaje v Indii není o nic horší člověk nežli někdo z mých hraček Kdepak mávl Vašek rukou
-
Základní prístup
O vstupní text ^> statistiky textu
Q statistiky =^ generování náhodného textu
Co jsou vhodné statistiky?
•<□►   4 ^ t   <  -ž  ►   <  -E ►
42/68
Statistiky textu
• základ: frekvence písmen (slov)
• rozšíření: korelace mezi písmeny (slovy)
příklad: pokud poslední písmeno bylo a: a e velmi nepravděpodobné (méně než obvykle)
• 1, k hodně pravděpodobná (více než obvykle)
< □ ► * s ► 4
Implementace
• základní frekvenční analýza - datová struktura seznam nebo slovník
písmeno frekvence
• rozšírená analýza - seznam seznamů nebo slovník slovníků písmeno     { písmeno     frekvence }
generovaní
• podle aktuálního písmene získám frekvence
• vyberu náhodné písmeno podle těchto frekvencí „vážená ruleta"
44/68
• seznam seznamů - tabulka 26 x 26, pouze pro malá písmena anglické abecedy
• slovník slovníků - pro libovolné symboly
•<□►   4 ^ t   <  -ž  ►   <  -š ►
45/68
def
def
ce písmen: seznamy
letter_ord(char):
return ord(char) - ord('a')
letter_correlations(text): counts = [[0 for a in range(26)]
for i in range(len(text)-1): a = letter_ord(text [i]) b = letter_ord(text [i+1]) if 0 <= a <= 26 and 0 <= b <= 26:
for b in range(26)]
counts[a][b] += 1
return counts
46/68
Výpis nejčastějších následujících písmen
def most_common_after(letter, counts, top_n=5): i = letter_ord(letter)
letter_counts = [(counts [i] [j], chr(ord('a')+j))
for j in range(26)] letter_counts.sort(reverse=True) for count, other_letter in letter_counts [:top_n] print(other_letter, count)
47/68
Korelace písmen: slovníky
def symbol_correlation(text): counts = {} last = 11 11 for symbol in text:
if last not in counts:
counts [last] = {} counts[last][symbol] = counts[last].get(symbol, 0)+l last = symbol return counts
Tip pro kratší kód: def aultdict
48/68
Výpis nejčastějších následujících písmen
def most_common_after_symbol(symbol, counts, top_n=5) print(sorted(counts [symbol].keys(),
key=lambda s:
-counts[symbol] [s]) [:top_n])
49/68
def get_next_letter(current, counts):
total = sum(counts[current].values()) r = random.randint(0, total-1) for symbol in counts [current].keys(): r -= counts [current][symbol] if r < 0:
return symbol return 11 11
def imitate(counts, length=100): current = 11 11 for _ in range(length):
print (current, end=M 11)
current = get_next_letter(current, counts)
50/68
v A/
mitace textu: rozšířeni
nebrat v potaz pouze předcházející písmeno, ale k předcházejících písmen
doporučené cvičení
51/68
mitace sofistikovaněji
• Recurrent Neural Networks - dokáží postihnout i složitější aspekty jazyka
• básně, recepty, Wikipedia články, zdrojové kódy, ...
http://karpathy.github.io/2015/05/21/rnn-effectiveness/
PANDARU5:
Alas, I think he shall be come approached and the day When little srain would be attain'd into being never fed, And who is but a chain and subjects of his death, I should not sleep.
Second Senator:
They are away this miseries, produced upon my soul, Breaking and strongly should be buried, when I perish The earth and thoughts of many states.
DUKE VINCENTIO:
Well, your wit is in the care of side and that. Second Lord:
They would be ruled after this chamber, and
my fair nues begun out of the fact, to be conveyed,
Whose noble souls I'll have the heart of the wars.
•<□►   4 ^ t   < -ž ►   < -š ►
52/68
Statistiky jmen
o data: četnosti jmen, příjmení podle roků, krajů, ...
• zdroj: Ministerstvo vnitra CR
Akt. stav: „Ministerstvo vnitra není oprávněno ke zveřejňování statistik / přehledů s charakterem statistik. Proto bylo zveřejňování těchto přehledů zrušeno."
• profiltrovaná data (nejčastější jména):
docs.google.com/spreadsheets/d/ltbhl-sHEnDOUnbxXOBXf9CaWJb50tyy0abp0HX6gioc
• doporučené cvičení
• snadno zpracovatelné
• zajímavá data
• cvičení na vymýšlení otázek
• následuje několik ukázek pro inspiraci ...
53/68
_1				□	E	F	G	H				L	M	N
1	JMÉNO 1950		1951	1952	1953	1954	1955	1956	1957	1956	1959	1960	1961	1962
2	ADAM	15	10	17	17	7	10	9	11	9	11	7	B	10
3	ADÉLA	13	16	23	30	19	28	19	22	21	8	12	15	~»
4	ADRIANA	2		3	3	2	3	5	2	7	8	10	B	11
5	ALENA	2304	3041	3033	3337	3431	361 ■	3560	3290	2£73	2743	2600	2651	2474
6	ALEŠ	100	164	170	222	222	231	255	271	251	280	302	317	397
7	ALEXANDR	66	65	72	67	57	70	47	54	62	57	57	90	56
8	ALEXANDRA	90	107	76	102	80	87	70	63	58	54	70	60	69
9	ALICE	72	76	72	95	91	89	109	86	96	91	103	100	95
10	ALOIS	332	312	271	303	232	283	229	215	216	195	146	163	144
11	ALŽBĚTA	126	131	112	110	89	83	75	77	73	55	45	43	34
12	AMÁLIE	6	4	4	2	0	1	2	1	1	1	1	3	0
13	ANDREA	11	7	9	9	12	13	4	14	11	10	25	16	26
14	ANETA	0	0	2	1	0	3	0	2	1	2	1	1	1
15	ANEŽKA	271	232	220	170	186	157	128	127	106	91	77	52	52
16	ANNA	3163	2993	2812	2534	2352	2184	2114	1993	1832	1489	1377	1156	1024
17	ANTONIE	131	156	124	127	114	122	106	74	74	63	51	41	32
15	ANTONÍN	1355	1306	1254	1163	1114	1054	1066	1010	881	771	748	790	690
19	BARBORA	22	31	30	23	31	30	22	25	32	39	35	56	91
20	BEDŘICH	157	153	170	146	136	130	144	155	99	106	93	99	86
21	BLANKA	592	635	TO'	704	734	692	718	761	675	575	615	635	674
22	BLAŽENA	176	199	172	152	156	124	114	116	112	65	60	65	56
25	BOHUMIL	552	575	547	479	437	441	424	449	374	299	327	259	234
24	BOHUMILA	262	236	269	265	216	216	190	138	171	159	127	113	93
25	BOHUSLAV	415	362	360	357	332	357	316	342	266	245	236	195	177
26	BOŽENA	1364	1173	1080	990	946	964	871	756	681	534	492	420	366
54/68
Poznámky ke zpracování
• načtení CSV
• funkce split —> seznam hodnot
• použití knihovny pro práci s CSV (pro složitější data)
• normalizace (relativní výskyty jmen) - podělit součtem (pro daný rok)
• různě velké ročníky
• neúplná data u starých ročníků
Reprezentace dat
slovník mapující jména na seznam počtů výskytů
{'Alois':   [332, 131, 112],  'Adam':   [15, 10, 17]} print(data[name][year-1950])
slovník mapující jména na slovníky mapující roky na počty
{'Adam': {1950: 15, 1951: 10},
'Alois': {1950: 332, 1951: 131}} print(data[name][year])
slovník mapující dvojici jméno+rok na počet výskytů
{('Alois', 1951): 131,  ('Adam', 1950): 15, ('Alois', 1950): 332,  ('Adam', 1951): 10} print(data[name, year])
56/68
1950 1960 1970 1960 1990 2000 2010
Rok
JAN, JAROSLAV, JIŘÍ, MAREK, MATĚJ, NIKOLA,
ONDŘEJ, RADEK, TOMÁŠ, VALDEMAR, D > <ff>      <s> -s 0„c
57/68
5
58/68
30
Prvni písmena
59/68
Co zajímavého můžeme z dat zjistit?
Kladení otázek - důležitá dovednost hodná tréninku.
Computers are useless. They can only give you answers. (Pablo Picasso)
60/68
Identifikace trendů
U kterých jmen nejvíce roste/klesá popularita?
• co to vlastně znamená?
• jak formalizovat?
•<□►   4 ^ t   <  -ž  ►   <  -š ►
61/68
Kolik let v radě roste popularita jména:
• Tobiáš - 14
• Viktorie, Ella, Sofie - 9
• Elen, Tobias - 8
Kolik let v radě klesá popularita jména:
• Jana - 26
• Martin - 21
• Petra - 11
• Zdeněk - 9
62/68
Největší skok v popularitě za 10 let
• alespoň desetinásobný nárůst popularity: Sofie, Elen, Amálie, El la 7 Nicol, Nella, Tobias
• pokles alespoň o 60 %: Petra, Pavlína, Martina
63/68
150
Počet jmen s frekvenci > 0.1%
64/68
využití existujících knihoven:
• načítání dat ve standardních formátech: HTML, XML, JSON, CSV, ...
• operace s daty: numpy, pandas
• vizualizace: matplotlib
• interaktivní prozkoumávání dat: ipython, jupyter
65/68
Doporučené procvičování
https://www.umimeprogramovat.cz/regularni-výrazy
66/68
Kontrolní otázky
• K čemu slouží regulární výrazy?
• Jaký je v regulárních výrazech význam + , *,  ., \s, \d, \w,  [ab], $?
• Jak používáme regulární výrazy v Pythonu?
• Pokud mám tabulku číselných údajů, jak ji mohu načíst, reprezentovat a zpracovat?
regulární výrazy práce s textem, daty využití datových struktur
68/68