IB113 Radek Pelánek
2021
1/62
1950 1960 1970 1980 1990 2000 2010
Rok
JAN, JAROSLAV, JIŘÍ, MAREK, MATĚJ, NIKOLA,
ONDŘEJ, RADEK, TOMÁŠ, VALDEMAR, D > <ff>      <s> -s ^c
2/62
v
Šifra
Nechci se tím zabývat donekonečna. Oběhal jsem dvaadvacet ministerstev, schvalovala to i vláda. Požádali jsme o vyjádření rakouskou stranu a podložili návrh lamelami. Nechyběla tomu ostrost, jak potvrdil novinový článek i matematická analýza.
(šifrovací hra Sendvič, 2020)
Dnešní prednáška
Příklady a techniky relevantní k situaci
• mám data (text, tabulková data)
• chci získat:
• „vhled"
• konkrétní informace
• transformovaná data
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ů
5/62
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
WHENEVER I LE^KN S\ EVfcW SKILL I GONCOCT ELA&OJttTE ffiMTA^V SCENARIOS WERE (T LETS (Vt^ETHEDW
OH 1M0[ "THE (CILLER MSTHAVE RHCWED HER ON VACATION!
BUT TO Fir©THEM WFD HAVE TO 5EASCM THOUGH 2oo MB OF EMAILS LOOKiPJG FQK SOMETHING FWnTED LIKE AN *DC*E55l /
	,-^ ^
	EXPRESSIONS, /
	& fg
http://xkcd.com/208/
8/62
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 \
10/62
[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
11/62
Speciální symboly
libovolný znak začátek řetězce $        konec řetězce
I alternativa - výběr jedné ze dvou možností
12/62
?
Jaký je význam následujících výrazů'?
• kočka|pes
• ~[Pp]rase$
• \d[A-Z]\d \d\d\d\d
13/62
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í *?, +?
14/62
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
15/62
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			
16/62
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
17/62
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()
•<□►   4 ^ t   <  -ž  ►   <  -E ►
18/62
Nechci se tím zabývat donekonečna. Oběhal jsem dvaadvacet ministerstev, schvalovala to i vláda. Požádali jsme o vyjádření rakouskou stranu a podložili návrh lamelami. Nechyběla tomu ostrost, jak potvrdil novinový článek i matematická analýza.
(šifrovací hra Sendvič, 2020)
19/62
v
Řešení šifry
Nechci se tím zabývat dONEkONEčna. Oběhal jsem DVAaDVAcet miniSTErSTEv, schVALoVALa to i vláda. Požádali jsme o vyjádření raKOUsKOU stranu a podložili návrh LAMeLAMi. Nechyběla tomu OSTrOST, jak potvrdil NOViNOVý článek i MATeMATická analýza.
Jak hledat vhodná slova při vytváření šifry?
kreference
• „odkaz" na předchozí část textu
• pomocí \1, \2, \3, ...
• příklad: slova, která obsahují opakovaně stejnou trojici písmen
• starosta
• periferie
• jak zapsat regulární výraz?
21/62
Backreference a trojice písmen
• seznam slov, např.
https://wiki.korpus.cz/doku.php/seznamy:srovnavaci_seznamy
• regulární výrazy:
• ~(. . .).*\1$
• .(...).*\i.
• (...)A1
• výstupy např.:
• ostrost
• skaliska
• bramborami
• multikulturní
22/62
Bez regulárních výrazů
Varianta „uvnitr 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í?
23/62
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
[IREJGEX golf"
YOO TRT T& MATCH OWE GROUP eur HOTTriE ows^
/tí I Difl|B/ MATCHES
501UROTE ň PROGRAM "TKňT FWftS RB3EXG0LF U/TH P^ff^iRV LIST?..,
...eur i tpsfľíť code;
fiičdTtWLpOKUfE fífGEX GOLF
RESAU-X       Í5 ALL /{to--)*REj6EXGDLF/
http://xkcd.com/1313/ http://www.explainxkcd.com/wiki/index.php/1313:_Regex_Golf
https://regex.alf.nu/
Š      -f) C^O
25/62
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
26/62
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
27/62
ulárnř výrazy v Pythonu: práce s výsledkem
»> m = re.match(r' (\w+)  (\w+) ' , \
'Isaac Newton, fyzik')
»> m.group(0) 1 Isaac Newton' »> m.group(1) 'Isaac1
»> m.group(2) 'Newton1
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'
29/62
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í
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
O text —seznam délek slov (vět)
O seznam délek —>► statistiky
O statistiky (pro více textů) —>► výpis
32/62
• vstup: rozsáhlý text
• výstup: náhodně generovaný text, který má „podobné charakteristiky" jako vstupní text
• imitace na úrovni písmen nebo slov
33/62
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ěží ře, a silobe lo v ne řeč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 Lorskříž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
O statistiky =^ generování náhodného textu
Co jsou vhodné statistiky?
•<□►   4 ^ t   <  -ž  ►   4 >
35/62
Statistiky textu
9 základ: frekvence písmen (slov)
• rozšíření: korelace mezi písmeny (slovy)
příklad: pokud poslední písmeno bylo a:
• e velmi nepravděpodobné (méně než obvykle)
• 1, k hodně pravděpodobná (více než obvykle)
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"
37/62
• seznam seznamů - tabulka 26 x 26, pouze pro malá písmena anglické abecedy
• slovník slovníků - pro libovolné symboly
•<□►   4 ^ t   <  -ž  ►   <  -š ►
38/62
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
39/62
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)
40/62
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
41/62
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])
42/62
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)
43/62
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í
4 □ ►   < |SP ►   4 S ►   4 S ►
5 >r)(\(y 44/62
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/
PANDARUS:
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.
45/62
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 ...
46/62
_1 *			C	□	E	F	G	H	I	J	K	L	M	N
|jMÉNO 1350			1951	1952	1953	1954	1955	1956	1957	1956	1959	1960	1961	1962
2	ADAM	15	10	17	17	7	10	9	11	J9	11	~J_	B	10
3	ADÉLA	13	16	23	30	19	28	19	22	21	Q	12	15	Q
4	ADRIANA	2	1	3	3	2	3	5	2	7	Q	10	B	11
5	ALENA	2804	3041	3033	3387	3481	3611	3560	3290	2Ů73	2743	2600	2651	2474
6	ALEŠ	100	164	170	222	222	231	255	271	251	280	302	317	397
1	ALEXANDR	66	65	72	67	57	70	47	54	62	57	57	90	56
8	ALEXANDRA	90	107	76	102	80	87	70	63	56	54	70	60	69
9	ALICE	72	73	72	95	91	89	109	88	98	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	76	55	45	43	34
12	AMÁLIE 6		4	4	2	0	1	2		Ä.	Ä.	1	3	0
13	ANDREA	11	T	9	9	12	13	4	14	11	10	25	13	26
14	ANETA 0		0	2	1	0	3	0	2		~J	1	1	1
15	ANEŽKA	271	232	220	170	188	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	138	130	144	155	99	108	93	99	86
21	BLANKA	592	635	70'	704	704	692	718	761	675	575	615	635	674
22	BLAŽENA	176	199	172	152	156	124	114	116	112	65	60	65	58
23	BOHUMIL	552	576	547	479	437	441	424	449	374	299	327	259	234
24	BOHUMILA	262	236	269	265	216	216	190	188	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	758	681	534	492	420	366
47/62
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])
49/62
1950 1960 1970 1980 1990 2000 2010
Rok
JAN, JAROSLAV, JIŘÍ, MAREK, MATĚJ, NIKOLA,
ONDŘEJ, RADEK, TOMÁŠ, VALDEMAR, D > <ff>      <s> -s ^c
50/62
5
51/62
Prvni písmena
30
D J M
1950 1960 1970 1980 1990 2000 2010
Rok
52/62
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)
53/62
Identifikace trendů
U kterých jmen nejvíce roste/klesá popularita?
co to vlastně znamená?
• jak formalizovat?
54/62
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
55/62
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
56/62
150
Počet jmen s frekvenci > 0.1 %
57/62
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
58/62
Demo ukázka řešení problému
Formát dat pro cvičení z pravopisu:
Zb [i/y|01]něk se rád zab[í/ý I01]vá hrou na b [i/y110]cí. Tvář mu zdob[í/ý|10] vlasy barvy ob [i/y110]lí a vypadá trochu jako hob [i/y 110]t. 0b [i/y101]čejně hraje ve svém ob [i/y 101]dlí na B [i/y 101]stré ulici ....
U kol: Převod na čistý výpis (Zbyněk se rád zabývá hrou na
bicí...).
•<□►   4 ^ t   <  -ž  ►   4 >
59/62
Doporučené procvičování
https://www.umimeprogramovat.cz/regularni-výrazy
60/62
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
62/62