Added a new set of exercises (regular expressions).

author: Martin Možina <martin.mozina@fri.uni-lj.si> 2016-12-05 11:51:58 +0100
committer: Martin Možina <martin.mozina@fri.uni-lj.si> 2016-12-05 11:51:58 +0100
commit: 236001ec7563804f87a40c924681461bc8b2d764 (patch)
tree: 534a9ba942e6f6906d751439dff8864130a370ea /python/problems/re/re_sl.html
parent: 413bb73adaee77e8c1ab1c5721b13d9b6f756a7a (diff)
1 files changed, 371 insertions, 0 deletions
diff --git a/python/problems/re/re_sl.html b/python/problems/re/re_sl.html
new file mode 100644
index 0000000..4432336
--- /dev/null
+++ b/python/problems/re/re_sl.html
@@ -0,0 +1,371 @@
+<!DOCTYPE html>
+<html lang="sl">
+<head>
+<meta charset="utf-8" />
+<title></title>
+<link rel="stylesheet" type="text/css" href="/css/codeq.css" />
+<link rel="stylesheet" type="text/css" href="../../style.css" />
+</head>
+<body>
+
+<h2>Regularni izrazi</h2>
+
+<p>Ena najbolj uporabnih stvari v skriptnih jezikih so "regularni izrazi". Če jih boste znali, boste glavni frajerji in boste lahko delali odlične reči. Po drugi strani pa niso prav nič zapleteni, čisto enostavno se jih je naučiti ... in, no, priznam, kar zoprno sestavljati. Ko sestavljamo kaj bolj zapletenega, se tudi stari mački nekoliko zafrkavamo, preden jih spravimo v delujoče stanje.</p>
+
+<h3>Regularni izraz</h3>
+
+<p>Če bi hoteli teoretizirati, bi rekli, da opisujejo <em>jezik</em>, pri čemer z "jezikom" mislimo nekakšno množico nizov. So tudi v tesnem sorodu s končnimi avtomati, ki vam morda niso več neznani, če kaj sledite Uvodu v računalništvo.) A pustimo teorijo in uvode. Naučili se bomo pisati nize, s katerimi opišemo nekakšne vzorce. Recimo, da imamo na voljo naslednje oznake, ki jih lahko tlačimo v nize:
+<dl>
+<dt>.</dt><dd>katerikoli znak</dd>
+<dt>\w</dt><dd>katerakoli črka ali števka</dd>
+<dt>\W</dt><dd>katerikoli znak, ki ni črka ali števka</dd>
+<dt>\d</dt><dd>katerakoli števka</dd>
+<dt>\D</dt><dd>katerakoli znak, ki ni števka</dd>
+<dt>\s</dt><dd>beli prostor (presledek, tabulator, nova vrstica...)</dd>
+<dt>\S</dt><dd>karkoli, kar ni beli prostor</dd>
+<dt>^</dt><dd>začetek niza</dd>
+<dt>$</dt><dd>konec niza</dd><
+<dt>\</dt><dd>vzvratno poševnico uporabimo, ko bi radi v vzorec vpisali, recimo, piko. Znak <code>.</code> ima namreč poseben pomen (glej zgoraj), zato takrat, kadar v resnici želimo piko, napišemo <code>\.</code>. Enako velja za zvezdico, vprašaj, plus... in tudi vzvratno poševnico.</dd>
+<dt>oglati oklepaji</dt><dd>mednje napišemo seznam znakov in opisujejo katerikoli znak s tega seznama; če je prvi znak <code>^</code>, pa to pomeni katerikoli znak, ki ni na tem seznamu. Znotraj oglatih oklepajev je pika samo pika in celo vzvratna poševnica samo vzvratna poševnica.</dd>
+</dl>
+Poglejmo nekaj preprostih primerov vzorcev
+<dl>
+<dt>l.pa</dt><dd>Ta izraz opisuje "l", ki mu sledi karkoli in nato "pa". To je lahko "lipa", "lepa" ali "lopa", pa tudi "lrpa", "lmpa", "lgpa". In celo "l3pa", "l/pa" in "l pa". Vzorcu pa ne ustrezata, recimo, "sipa", saj se ne začne z "l" ali "lotupa", saj ima med "l" in "pa" več kot eno samo črko.</dd>
+<dt>l.p.</dt><dd>Tole pa je lahko tudi "lipi" ali "lopi" ali "lspt" ali "l1p4" ali "l-p)"... Torej vse besede s štirimi znaki, pri čemer mora biti prvi znak "l", tretji pa "p".</dd>
+<dt>l\wp\w</dt><dd>Ta vzorec je podoben prejšnjemu, le da zahteva, da sta drugi in četrti znak črki ali številki. "lipa" in "l1p4" sta še vedno spremenljivi, "l-p)" pa ne več.</dd>
+<dt>lip[aieo]</dt><dd>Tole pa je lahko "lipa", "lipi", "lipe" ali "lipo". Ne pa "lipu" ali "lipm".</dd>
+<dt>lip[^u t]</dt><dd>Ta vzorec opisuje "lip", ki mu sledi katerikoli znak, razen u-ja, presledka ali t-ja.</dd>
+<dt>s[tpr]anje</dt><dd>"stanje", "spanje" in nekatere druge reči.</dd>
+</dl>
+Zdaj pa še par posebnih znakov.
+<dl>
+<dt>okrogli oklepaji</dt><dd>Z okroglimi oklepaji označimo skupino</dd>
+<dt>*</dt><dd>Z zvezdico označimo, da se sme prejšnji znak ali prejšnja skupina (ki smo jo zaprli v okrogle oklepaje) poljubnokrat ponoviti - lahko tudi ničkrat.</dd>
+<dt>+</dt><dd>Plus pomeni isto kot zvezdica, le da zahteva, da se prejšnja skupina ali znak pojavi vsaj enkrat.</dd>
+<dt>?</dt><dd>Z vprašajem povemo, naj se prejšnja skupina pojavi enkrat ali nobenkrat.</dd>
+</dl>
+Spet si oglejmo nekaj primerov.
+<dl>
+<dt>Go*l!</dt><dd>Ta vzorec opisuje nize, kot so "Gol!", "Gooooooool!" in "Goooooooooooooooool!". Žal pa tudi "Gl!". :)</dd>
+<dt>Go+l!</dt><dd>Popravljena verzija gornjega: zahteva, da se "o" pojavi vsaj enkrat.</dd>
+<dt>Go+l?!</dt><dd>Tole pa je podobno kot zgoraj, le da se črka <code>l</code> lahko pojavi ali pa tudi ne. To je torej lahko karkoli od tega, kar smo našteli zgoraj, poleg tega pa tudi "Go!" ali "Gooooooooooo!"  </dd>
+</dl>
+Pa še par bolj zapletenih.
+<dl>
+<dt>(brm)+</dt><dd>Opisuje motor, ki dela "brmbrmbrmbrmbrmbrm" ali "brmbrmbrmbrmbrmbrmbrmbrm" ali vsaj "brm".</dd>
+<dt>ra(ta)*</dt><dd>Opisuje mitraljez (ki je lahko tudi pokvarjen in reče samo "ra" in razpade)</dd>
+<dt>tr([aeiou]l)*[aeiou]</dt><dd>Opisuje prepevanje, ko ne poznamo besedila ("tralalelalalalilolololu")</dd>
+<dt>jodl(dodl)*dii</dt><dd>Jodlanje (in jodldodlanje in jodldodldodldodldodlanje).</dd>
+<dt>jodl(dodl)?dii</dt><dd>Tole pa je samo jodlanje in jodldodlanje, ne pa tudi jodldodldodldodldodlanje.</dd>
+</dl>
+Pri plusu, zvezdici in vprašaju nas včasih zmoti, da požrejo preveč. Če hočemo, da požrejo čim manj, jim dodamo vprašaj.
+<dl>
+<dt>*?, +?, ??</dt><dd>Če k zvezdici, plusu ali vprašaju dodamo še en vprašaj, zahtevamo, naj ta zvezdica, plus ali vprašaj "požre" čim manj znakov. Tole je na prvi pogled zelo praktično; v resnici bo začetnik, ko odkrije te vprašaje, naredil veliko naivnih napak, zato se jim, vsaj v začetku, raje izognite in poskusite to, kar želite povedati, povedati brez njih.</dd>
+</dl>
+Vzemimo stavek "Ta nas Janez je en dolgocasnez, prav res". Če poskusimo v tem stavku poiskati podniz, ki ustreza vzorcu "J.*nez", bomo izvedeli, da "Janez je en dolgocasnez", kar ni ne lepo ne prav in nikakor ni tisto, kar smo hoteli. Težava je v tem, da je zvezdica požrla "nez je en dolgocas"; izraz namreč pravi, da hočemo "Ja", potem (karseda veliko) drugih črk in potem "nez". Če pa poiščemo "J.*?nez", bomo dobili samo "Janez", saj bo ".*" požrlo le toliko znakov, kolikor jih potrebujemo, da je iskanje uspešno, torej, v tem primeru, le črko "a".</p>
+
+<h3>Funkcije za uporabo regularnih izrazov</h3>
+
+<p>Naučili smo se opisovati vzorce. Kaj pa lahko s temi opisi počnemo?</p>
+
+<p>Regularni izrazi, ki smo jih spoznali, so bolj ali manj enaki v vseh jezikih. Jeziki, ki imajo veliko opraviti z iskanjem po besedilih, na primer php in javascript, imajo regularne izraze tesno vdelane v jezik - tako kot ima Python vdelana števila in nize (za nize nimamo "posebnega modula", ki bi ga morali uvoziti, preden lahko delamo z njimi), imajo ti jeziki vdelane tudi regularne izraze. Ne da bi potrebovali poseben modul, lahko preverimo, ali ima določen niz določeno obliko, podano z regularnim izrazom. Python je splošnejši jezik, zato regularnih izrazov ne sili v ospredju, temveč so lepo v posebnem modulu. Imenuje se <code>re</code>, kar je okrajšava za <em>regular expression</em>.</p>
+
+<p>Za primer uporabimo rdečo nit predavanj izpred nekaj let: v besedilu iščemo imena potencialnih teroristov, pri čemer so nam sumljive kar vse besede, ki se začnejo z veliko črko. Besedilo nekega prestreženega elektronskega sporočila je bilo takšno:
+<pre>msg = """Dragi Ahmed,
+
+kako si kaj? Upam, da so otroci ze zdravi.
+
+Mustafa, Osama in jaz smo se sli danes malo razgledat in
+kaze kar dobro. Abdulah pa ni mogel zraven, je sel v Pesavar
+prodat se tri kamele. Osama sicer pravi, da se mu to pred
+zimo ne splaca, ampak saj ves, kaksen je Abdulah. Harun in
+on, nic jima ne dopoves, se Osama ne. Jibril me klice,
+moram iti; oglasi se kaj na Skype!
+
+tvoj Husein
+
+"""</pre>
+
+<p>Vzorec, ki bo predstavljal ime - nekaj, kar se začne z veliko črko in nadaljuje s vsaj eno črko, je <code>[A-Z]\w+</code>.</p>
+
+<p>Najpreprostejša za uporabo (a ne tudi najbolj uporabna) funkcija, na kateri lahko poženemo ta izraz, je <code>findall</code>, ki, kot bi bili ob imenu nemara presenečeni (posebej, če ne bi znali angleško) poišče vse (neprekrivajoče se) podnize, ki jim ustreza izraz.  Če imamo sporočilo shranjeno v nizu <code>msg</code>, bomo seznam imen dobili z
+<pre>>>> re.findall(r"[A-Z]\w+", msg)
+['Dragi', 'Ahmed', 'Upam', 'Mustafa', 'Osama', 'Abdulah', 'Pesavar', 'Osama', 'Abdulah', 'Harun', 'Osama', 'Jibril', 'Skype', 'Husein', 'PS', 'Python']</pre></p>
+
+<p>Opazka: pred narekovaj sem dodal <code>r</code>. Iz davnega začetka semestra se morda spomnite, kakšne posledice ima to: vse vzvratne poševnice (po domače: <em>backslashi</em>) po tem pomenijo le vzvratne poševnice, ne ubežnih zaporedij (torej, <code>\n</code> pomeni vzvratno poševnico in <code>n</code>, ne pa prehoda v novo vrsto). V regularnih izrazih se bo vedno trlo vzvrtanih poševnic, medtem ko bodo nove vrste in tabulatorji strašno redki, zato bomo skoraj vedno uporabljali nize z <code>r</code>-jem pred narekovaji.</p>
+
+<p>Metoda <code>findall</code> je najpreprostejša, ker vrne kar (pod)nize, ki ustrezajo vzorcu. Druge funkcije vračajo objekt, iz katerega lahko razberemo še kaj več. Vzemimo <code>search</code>, ki poišče prvo pojavitev vzorca.</p>
+
+<pre>>>> mo_ime = re.search(r"[A-Z]\w+", msg)
+>>> mo_ime
+<_sre.SRE_Match object at 0x045812F8></pre>
+
+<p><code>mo_ime</code> ni niz, tako kot prej, temveč objekt, ki vsebuje podatke o podnizu, ki se ujema z izrazom. (Ker gre za "<code>Match object</code>", zato sem mu pripel <code>mo_</code>. To spet spominja na madžarsko notacijo, ki sem jo omenil pri Qtju in tudi tu izvira iz (mojih) izkušenj: če imaš spremenljivko, ki predstavlja objekt, ki se nanaša na najdeno ime, boš imel najbrž tudi spremenljivko, ki bo vsebovala niz z najdenim imenom in imeli bosta tendenco, da se bosta enaki. Če prvemu vedno pripnemo <code>mo_</code>, je problem rešen.</p>)
+
+<pre>>>> mo_ime.group()
+'Dragi'
+>>> mo_ime.start()
+0
+>>> mo_ime.end()
+5
+>>> mo_ime.span()
+(0, 5)</pre>
+
+<p>Tule <code>start</code> pove indeks črke v nizu, kjer se ujemanje začne in <code>end</code> indeks črke za ujetim podnizom; <code>span</code> pove oboje hkrati. Najdeni niz se torej nahaja v <code>msg[0:5]</code>. Razlog, da se metoda, ki vrne celotni podniz, imenuje <code>group()</code>, pa bo postal jasen malo kasneje, ko se bomo pogovarjali o skupinah.</p>
+
+<p>Če želimo poiskati vse pojavitve vzorca in jih obdelati v zanki, bomo uporabili <code>finditer</code>, kot recimo tule:
+<pre>for s in re.finditer(r"[A-Z]\w+", msg):
+    print(s.group())</pre></p>
+	
+<p>Metoda <code>sub</code> je podobna metodi <code>replace</code>, ki smo jo spoznali pri nizih: z njo lahko zamenjamo vse pojavitve danega vzorca s čim drugim.</p>
+
+<pre>>>> print(re.sub(r"[A-Z]\w+", "XXX", msg))
+XXX XXX,
+
+kako si kaj? XXX, da so otroci ze zdravi.
+
+XXX, XXX in jaz smo se sli danes malo razgledat in
+kaze kar dobro. XXX pa ni mogel zraven, je sel v XXX
+prodat se tri kamele. XXX sicer pravi, da se mu to pred
+zimo ne splaca, ampak saj ves, kaksen je XXX. XXX in
+on, nic jima ne dopoves, se XXX ne. XXX me klice,
+moram iti; oglasi se kaj na XXX!
+
+tvoj XXX
+</pre>
+
+<p>V zvezi s <code>sub</code> lahko opazimo, da so argumenti funkcije obrnjeni nekoliko drugače kot pri <code>replace</code>: <code>replace</code> je metoda razreda <code>str</code>, torej je niz, katerega podnize želimo spreminjati že implicitno podan (kot <code>self</code>), povedati je potrebno le, kakšen podniz zamenjamo s katerim. Za primer: na nekaterih operacijskih sistemih so presledki v imenih datotek precej tečna reč. Kako bi se jih znebili? Če bi poznali le nize, bi rekli
+
+<pre>fname = fname.replace(" ", "_")</pre>
+
+Metodi <code>sub</code> pa kot argument povemo vzorec, niz, po katerem naj išče in s čim naj zamenjuje. Če bi želeli gornjo zamenjavo opraviti z regularnimi izrazi, bi napisali:
+<pre>fname = re.sub(" ", "_", fname)</pre>
+</p>
+
+<p>Regularni izrazi so za tako preprosto zamenjavo prevelik kanon. <code>sub</code> namreč zmore še veliko več; namesto niza, s katerim naj zamenja ujemajoči se podniz, ji lahko podamo kar funkcijo, ki naj jo pokliče ob vsakem ujemanju: funkcija bo kot argument dobila <code>Match object</code>, kot rezultat mora vrniti niz, ki naj zamenja ujemajoči se podniz. Podniz lahko zamenjamo z, recimo, enakim podnizom, vendar zapisanim z velikimi črkami.</p>
+
+<pre>>>> def velike_crke(mo):
+... 	return mo.group().upper()
+... 
+>>> print re.sub(r"[A-Z]\w+", velike_crke, msg)
+DRAGI AHMED,
+
+kako si kaj? UPAM, da so otroci ze zdravi.
+
+MUSTAFA, OSAMA in jaz smo se sli danes malo razgledat in
+kaze kar dobro. ABDULAH pa ni mogel zraven, je sel v PESAVAR
+prodat se tri kamele. OSAMA sicer pravi, da se mu to pred
+zimo ne splaca, ampak saj ves, kaksen je ABDULAH. HARUN in
+on, nic jima ne dopoves, se OSAMA ne. JIBRIL me klice,
+moram iti; oglasi se kaj na SKYPE!
+
+tvoj HUSEIN
+
+</pre>>
+
+<p>Da ne definiramo brez potrebe takšnih kratkih funkcij, si lahko pomagamo z lambda-funkcijami. O njih se pri Programiranju 1 nismo pogovarjali; primeren trenutek je bil kvečjemu prejšnji teden, saj je njihovo naravno mesto funkcijsko programiranje. Tule jih bomo samo uporabili, v izziv radovednim:
+<pre>print(re_ime.sub(lambda mo: mo.group().upper(), msg))</pre>
+Za primer obrnimo vsa imena po arabsko, z desne na levo:
+
+<pre>>>> print(re.sub(r"[A-Z]\w+", lambda mo: "".join(reversed(mo.group())), msg))
+...
+igarD demhA,
+
+kako si kaj? mapU, da so otroci ze zdravi.
+
+afatsuM, amasO in jaz smo se sli danes malo razgledat in
+kaze kar dobro. haludbA pa ni mogel zraven, je sel v ravaseP
+prodat se tri kamele. amasO sicer pravi, da se mu to pred
+zimo ne splaca, ampak saj ves, kaksen je haludbA. nuraH in
+on, nic jima ne dopoves, se amasO ne. lirbiJ me klice,
+moram iti; oglasi se kaj na epykS!
+
+tvoj niesuH
+</pre></p>
+
+<p>Še ena (in zadnja, za danes) zanimiva funkcija, ki jo nudijo regularni izrazi, je <code>split</code>. Tej  smo doslej podajali točen podniz, po katerem naj deli. Tako bo tudi poslej, modul za regularne izraze pa ima še eno, drugo funkcijo <code>split</code>, ki ji povemo vzorec, po katerem naj deli. Lahko, recimo, rečemo, naj sporočilo razdeli ob vsakem imenu (kar ni posebej uporaben zgled, je pa preprost).</p>
+
+<pre>
+>>> re.split(r"[A-Z]\w+", msg)<br/>
+['', ' ', ',\n\nkako si kaj? ', ', da so otroci ze zdravi.\n\n', ', ', 
+' in jaz smo se sli danes malo razgledat in\nkaze kar dobro. ', 
+' pa ni mogel zraven, je sel v ', '\nprodat se tri kamele. ', 
+' sicer pravi, da se mu to pred\nzimo ne splaca, ampak saj ves, kaksen je ', 
+'. ', ' in\non, nic jima ne dopoves, se ', ' ne. ', 
+' me klice,\nmoram iti; oglasi se kaj na ', '!\n\ntvoj ', '\n\n']
+</pre>
+
+<p>V zvezi z <code>Match objecti</code> so nam ostale še skupine. Kaj so in kaj počnemo z njimi, pa bomo videli na primerih.</p>
+
+<h2>Prevedeni regularni izrazi</h2>
+
+<p>V davnih časih smo se pri predmetih, kot je Uvod v računalništvo, učili Moorevoih in Mealyjevih avtomatov. Danes so menda iz mode, zato bo moral ta, ki ga zanima, kako delujejo regularni izrazi, najbrž počakati do Prevajalnikov in navideznih strojev, ki si jih lahko izbere v tretjem letniku. Za zdaj vam lahko povem le, da se izraz, preden lahko računalnik v resnici naredi karkoli z njim, prevede v nekaj, čemur se reče <em>končni avtomat</em>, ta pa je neke vrste usmerjen graf. (Tako da boste vsaj vedeli, čemu služi to, kar počnete pri Diskretnih strukturah.)</p>
+
+<p>Za razumevanje tega, kar je pomembno tu, je bistveno le: regularni izraz se mora v nekaj <em>prevesti</em>. Če napišete program, ki vsebuje nekaj takšnega:
+<pre>for i in range(10000):
+    re.findall(r"[A-Z]\w+", msg[i])
+	# in potem še kaj naprej</pre>
+bo moral nesrečni računalnik deset tisočkrat prevesti regularni izraz <code>[A-Z]\w+</code> v tisto, v kar ga pač prevaja. Pri tako kratkem in preprostem izrazu še gre, pri čem bolj zapletenem pa bi program tekel bistveno hitreje, če bi ga lahko prevedli enkrat za vselej. In res ga lahko.</p>
+
+<p><pre>re_ime = re.compile(r"[A-Z]\w+")
+for i in range(10000):
+    re_ime.findall(msg[i])
+	# in potem še kaj naprej</pre>
+Spremenljivka <code>re_ime</code> (spet madžarska notacija!) zdaj predstavlja prevedeni izraz. Objekt <code>re_ime</code> ima vse funkcije, ki smo jih poznali prej, le da gre zdaj pač za metode objekta in ne funkcije modula: namesto <code>re.findall</code>, <code>re.finditer</code>, <code>re.sub</code>, <code>re.split</code>, zdaj pišemo <code>re_ime.findall</code>, <code>re_ime.finditer</code>, <code>re_ime.sub</code>, <code>re_ime.split</code>. Poleg tega pa še izpustimo prvi argument, vzorec, saj je izraz že pripravljen.</p>
+	
+<p>Sam vedno eksplicitno pokličem prevajanje izraza, preden ga uporabim; tako sem se navadil in škoditi ne more. Tule pa bomo počeli, kakor bo naneslo.</p>
+
+<h2>Primeri</h2>
+
+<h3>Primer: teroristi</h3>
+
+<p>Rešimo, za začetek, kar staro nalogo, ki je zahtevala, da izpišemo, kolikokrat se v sporočilu pojavi posamezno ime.</p>
+
+<pre>import re
+
+imena = {}
+for ime in re.findall(r"[A-Z]\w+", msg):
+    imena.setdefault(ime, 0)
+    imena[ime] += 1
+
+for ime, stevec in imena.items():
+    print("{} {}".format(ime, stevec))</pre>
+	
+<p>Gre pa, jasno, tudi hitreje: modul <code>collections</code> ima razred <code>Counter</code>, ki prešteje število ponovitev v poslanem seznamu, slovarju, množici... Takole:
+
+<pre>>>> collections.Counter(re.findall(r"[A-Z]\w+", msg))
+Counter({'Osama': 3, 'Abdulah': 2, 'PS': 1, 'Ahmed': 1, 'Mustafa': 1, 'Python': 1,
+'Pesavar': 1, 'Upam': 1, 'Dragi': 1, 'Harun': 1, 'Husein': 1, 'Skype': 1,
+'Jibril': 1})</pre>
+
+<p>To naš program precej poenostavi, saj nas odreši glavnega opravila, štetja.</p>
+
+
+<pre>import re, collections
+for ime, stevec in collections.Counter(re.findall(r"[A-Z]\w+", msg)).items():
+    print("{} {}".format(ime, stevec))</pre>
+
+
+<h3>Primer: branje vseh slik z določene strani</h3>
+
+<p>Tisti, ki vsaj malo poznate HTML, veste, da so slike na spletnih straneh praviloma postavljene tako, da HTML vsebuje značko IMG, ki videti nekako tako:
+<xmp><img src="ime_slike.gif"/></xmp>
+Z malo potencialnimi komplikacijami, seveda. Oklepaju sicer vedno sledi najprej <code>img</code>, a poleg <code>src</code> lahko naletimo še na kaj drugega. Lepo vzgojen HTML ima poleg <code>src</code> vsaj še <code>alt</code>, slabo vzgojen pa tudi <code>onclick</code> ali kaj hujšega. Poleg tega so lahko kjerkoli, razen sredi besed, tudi presledki.</p>
+
+<p>Kar iščemo, lahko z besedami opišemo kot oklepaj (namreč tale: <code>&lt;</code>), ki mu lahko sledi kaj praznega prostora, nato pa <code>img</code>. Potem sme biti čisto karkoli razen zaklepaja, <code>&gt;</code> in nekoč mora priti na vrsto <code>src</code>, pred njim pa mora biti kak znak, ki ni črka (če bi, recimo, pisalo <code>mesrc</code>, to ni OK, če je pred <code>src</code> presledek, tabulator, nova vrsta ali, zaradi mene tudi narekovaj ali vejica (čeprav to ni povsem po predpisih) pa je OK. Besedi <code>src</code> mora slediti enačaj, pred in za njim sme biti bel prostor. Nato pa narekovaj, za katerim pride tisto, kar nas v resnici zanima: URL slike. Ta je sestavljen iz poljubnih znakov razen narekovajev... in na koncu pride še narekovaj.</p>
+
+<p>Z regularnim izrazom taisto povemo tako:
+<pre><\s*img[^>]*\Wsrc\s*=\s*"([^"]*)"</pre>
+Se pravi
+<table>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>&lt;</code></td><td>oklepaj, &lt;</td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>\s*</code></td><td>poljubno praznega prostora (lahko tudi nič)</td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>img</code></td><td>beseda <code>img</code></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>[^&gt]*</code></td><td>poljubno dolga poljubna šara, razen zaključnega oklepaja</td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>\W</code></td><td>karkoli, kar ni črka</td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>src</code></td><td>beseda <code>src</code></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>\s*</code></td><td>poljubno praznega prostora (lahko tudi nič)</td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>=</code></td><td>enačaj</td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>\s*</code></td><td>poljubno praznega prostora (lahko tudi nič)</td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>"</code></td><td>narekovaj</td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>([^"]*)</code></td><td>poljubne reči razen narekovaja; čemu oklepaji, bomo še videli</td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>"</code></td><td>narekovaj</td></tr>
+</table>
+
+Ko smo rekli <em>poljubno dolga poljubna šara, razen zaključnega zaklepaja</em>: kdo nam jamči, da ta "poljubna šara" ne bo požrla tudi <code>src</code>ja in URLja? To nam jamči sam regularni izraz! Če bi <code>[^&gt]*</code> požrl <code>src</code>, potem se regularni izraz ne bi mogel ujemati s sicer pravilno vstavljeno sliko. Regularni izraz (oziroma knjižnica, ki ga poganja) pa vedno naredi vse, da bi se izraz ujemal, torej tudi ukroti požrešne dele.</p>
+
+<p>Podobno, a ravno obratno vprašanje je, kdo zagotavlja, da bo <code>([^"]*)</code>, to so, <em>poljubne reči razen narekovaja</em>, res požrle ves URL in ne odnehale, tako, za hec, po treh znakih? Tako kot prej, nam tudi to zagotavlja preostanek izraza. V opisu regularnega izraza delu <code>([^"]*)</code> namreč sledi <code>"</code>; če <code>([^"]*)</code> ne požre vsega do narekovaja, se tisto, kar sledi, ne bo ujemalo z narekovajem, kot zahteva izraz.</p>
+
+<p>Je kdo opazil, da nikjer ne lovimo zaključnega zaklepaja, <code>&gt;</code>. Res je, ne omenjamo ga. Z razlogom. Vseeno nam je zanj. Ko ulovimo URL, nam je za vse, kar se dogaja naprej, vseeno. Da bo še jasneje, pripnimo h gornji tabeli še en preprost in en zapleten podniz, ki se ujame v izraz. Najprej<code>&lt;img src="ime_slike.gif"/&gt;</code></p>
+
+<table>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>&lt;</code></td><td><code>&lt;</code></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>\s*</code></td><td></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>img</code></td><td><code>img</code></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>[^&gt]*</code></td><td></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>\W</code></td><td><em>(presledek med <code>img</code> in <code>src</code>)</em></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>src</code></td><td><code>src</code></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>\s*</code></td><td></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>=</code></td><td><code>=</code></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>\s*</code></td><td></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>"</code></td><td><code>"</code></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>([^"]*)</code></td><td><code>ime_slike.gif</code></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>"</code></td><td><code>"</code></td></tr>
+</table>
+
+<p>Pa še bolj zapleten primer: kako regularni izraz zgrabi <code>&lt;   img alt="Tvoj brskalnik ne kaže slik" onclick="http://www.fri.uni-lj.si"   src=  "x.gif" class="psl" &gt;</code></p>
+
+<table>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>&lt;</code></td><td><code>&lt;</code></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>\s*</code></td><td><em>(presledka pred <code>img</code>)</em></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>img</code></td><td><code>img</code></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>[^&gt]*</code></td><td><code> alt="Tvoj brskalnik ne kaže slik" onclick="http://www.fri.uni-lj.si"  </code> <em>(pred <code>src</code> so trije presledki; "šara" pograbi prva dva)</em></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>\W</code></td><td><em>(tretji presledek pred <code>src</code>)</em></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>src</code></td><td><code>src</code></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>\s*</code></td><td></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>=</code></td><td><code>=</code></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>\s*</code></td><td><em>(presledek)</em></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>"</code></td><td><code>"</code></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>([^"]*)</code></td><td><code>x.gif</code></td></tr>
+<tr><td style="background-color: #cccccc; text-align: right; padding: 2px"><code>"</code></td><td><code>"</code></td></tr>
+</table>
+
+<p>Zdaj pa uporabimo izraz v funkciji <code>download_images</code>, ki bo kot argument sprejela URL strani in ciljni direktorij. Prebrala bo s stran, nato pa z nje snela vse slike in jih shranila v ciljni direktorij.</p>
+
+<pre>import re
+import urllib.request
+import os
+
+re_img = re.compile(r'<\s*img[^>]*\Wsrc\s*=\s*"([^"]*)"', re.DOTALL + re.IGNORECASE)
+
+def download_images(url, target_dir):
+    if not os.path.exists(target_dir):
+        os.mkdir(target_dir)
+    elif not os.path.isdir(target_dir):
+        raise IOError("'%s' is not a directory" % target_dir)
+
+    page = urllib.request.urlopen(url).read().decode("utf-8")
+    for mo in re_img.finditer(page):
+        img_url = mo.group(1)
+        img = urllib.request.urlopen(img_url).read()
+        img_name = os.path.split(img_url)[1]
+        target_name = os.path.join(target_dir, img_name)
+        open(target_name, "wb").write(img)</pre>
+        
+
+<p>Regularni izraz smo tokrat enkrat za vselej prevedli pred funkcijo in ga shranili v <code>re_img</code>. Dodali smo še en argument, zastavice, s katerimi povemo, naj vzorec <code>.</code> požira tudi znake za novo vrstico,  <code>\n</code> (<code>re.DOTALL</code>) in da nam je vseeno za male in velike črke (<code>re.IGNORECASE</code>), tako da se bo, denimo, <code>img</code> ujemal tudi z <code>IMG</code>, <code>Img</code> in <code>iMg</code>...
+
+<p>Funkcija nato preveri ali ciljni direktorij obstaja; če ga ni, ga naredi, če je, pa preveri, ali je v resnici direktorij in v nasprotnem primeru - kot znamo od prejšnjič - sproži izjemo.</p>
+
+<p>Sledi pravo delo: poberemo podano stran. Kar dobimo z <code>read</code>, ni niz (<code>str</code>) temveč bajti (<code>bytes</code>). Ker regularni izrazi brskajo le po nizih, pretvorimo bajte v niz. Če bi hoteli narediti, kot se šika, bi ugotovili, kako je stran v resnici kodirana, tule pa bomo predpostavili, da gre za utf-8 in poklicali <code>decode("utf-8")</code>
+
+Potem poiščemo vse pojavitve značke <code>img</code>. Zdaj pride, kar sem zamolčal: <code>group</code>. Ko smo v prejšnjih primerih želeli iz <code>match object</code>a dobiti podniz, ki se je prilegal regularnemu izrazu, smo poklicali <code>group()</code>. Zdaj bi želeli priti do podniza, ki se prilega URLju slike, torej tistemu med narekovaji za <code>src</code>em. Zato smo ta del zaprli v oklepaje in s tem naredili novo skupino. Do njene vsebine pridemo z <code>group(1)</code>. Čemu <code>1</code>? Zato pač, ker gre za prvo skupino. Če bi jih imeli več, bi jih lepo prešteli in povedali, ali želimo vsebino tretje ali šeste.</p>
+
+<p>"Lepo prešteli"? Tole štetje ni prav nič lepo in prikladno. Regularni izrazi so zapleteni in kaj lahko se uštejemo. Še huje: ko izraz spremenimo, bomo morda dodali novo skupino in vse bo treba preštevilčiti. Zato je skupine bolj praktično poimenovati. Namesto
+<pre>re_img = re.compile(r'<\s*img[^>]*\Wsrc\s*=\s*"([^"]*)"', re.DOTALL + re.IGNORECASE)</pre>
+napišemo
+<pre>re_img = re.compile(r'<\s*img[^>]*\Wsrc\s*=\s*"(?P<url>[^"]*)"', re.DOTALL + re.IGNORECASE)</pre>
+in skupina je dobila ime, <code>url</code>. Do vsebine te skupine potem pridemo z <code>mo.group("url").</code></p>
+
+<p>Sliko poberemo v niz z <code>urllib.request.urlopen</code>. Zdaj pa jo je potrebno še shraniti. URL slike bo, recimo, takšen: <code>http://i1.nyt.com/images/2011/01/01/arts/design/01moth_costa/01moth_costa-moth.jpg</code> in takšno sliko želimo shraniti pod imenom <code>01moth_costa-moth.jpg</code>. Da pridemo do njega, lahko za prvi približek posilimo kar funkcijo <code>os.path.split(p)</code>, ki kot argument (običajno) prejme datoteko skupaj s potjo do nje, na primer, <code>c:\Users\Janez\Desktop\desktop.ini</code>, kot rezultat pa vrne terko s potjo in datoteko, na primer <code>("c:\Users\Janez\Desktop", "desktop.ini")</code>. URL je dovolj podobna reč, da ga bo <code>os.path.split</code> pravilno razcepil.</p>
+
+<p>Funkcija deluje, lahko jo preskusimo. Ker vaje ni nikoli preveč, pa poskusimo spremeniti izraz tako, da se izognemo klicu <code>os.path.join</code>. Pot vodi prek razmisleka, da je URL sestavljen iz dveh delov; prvi del je pot, drugi ime datoteke in slednji ne vsebuje poševnic, <code>/</code>. (Tole je le zmerno res: pri, denimo, slikah, ki se generirajo sproti, URL navadno ne bo vseboval imena datoteke. Ta detajl za zdaj pozabimo.) Ime, torej tisto med narekovaji, bi zato spremenili iz <code>[^"]*</code>, karkoli razen narekovaja, v <code>[^"]*[^"/]*</code>, to je, karkoli razen narekovaja, ki mu sledi karkoli razen narekovaja in poševnice. No, tole še ne bo povsem dobro, saj prvemu delu nič ne preprečuje, da ne bi kar vedno požrl celotnega imena in za drugi del ne bi ostalo nič. Prva rešitev, ki nam pride na misel, je <code>[^"]*/[^"/]*</code>, torej, karkoli razen narekovaja, ki mu sledi poševnica in potem karkoli razen narekovaja in poševnice. Tudi to ne bo povsem dobro, saj zdaj zahtevamo, da URL vsebuje poševnico in zdaj ne bomo več prepoznali povsem legalne slike <code>&lt;img src="ime_slike.gif"/&gt;</code>. Prava rešitev je, da prvemu delu pač zapovemo, naj požre čim manj, tako da zvezdici dodamo vprašaj, <code>[^"]*?[^"/]*</code>. Zdaj vse deluje, kot mora: prvi del lahko požira karkoli (vendar čim manj), drugi pa ne mara poševnic. Če obstaja (vsaj ena) poševnica, bo prvi del požrl vse do (zadnje) poševnice in tako omogočil drugemu, da se ujame (a požrl ne bo nič več, kot je nujno treba, saj požira čim manj). Če pa poševnice sploh ni, bo vse požrl drugi del, saj prvemu ni potrebno požreti ničesar.</p>
+
+<p>In zdaj določimo in poimenujmo še skupine. Dve bosta in ena bo del druge. Najprej poskrbimo za ime datoteke, se pravi to, kar sledi poševnici: <code>[^"]*?(?P<fname>[^"/]*)</code>. Vse skupaj pa zapremo še enkrat, saj celoten URL vsebuje tako prvi del kot tudi ime: <code>(?P<url>[^"]*?(?P<fname>[^"/]*))</code>. Funkcija s takšnim regularnim izrazom je taka:</p>
+
+<pre>re_img = re.compile(r'<\s*img[^>]*\Wsrc\s*=\s*"(?P<url>[^"]*?(?P<fname>[^"/]*))"', re.DOTALL+re.IGNORECASE)
+
+def download_images(url, target_dir):
+    if not os.path.exists(target_dir):
+        os.mkdir(target_dir)
+    elif not os.path.isdir(target_dir):
+        raise IOError("{}' is not a directory".format(target_dir))
+    page = urllib.request.urlopen(url).read().decode("utf-8")
+    for mo in re_img.finditer(page):
+        img_url, img_name = mo.group("url", "fname")
+        img = urllib.request.urlopen(img_url).read()
+        target_name = os.path.join(target_dir, img_name)
+        open(target_name, "wb").write(img) </pre>
+
+</body>
+</html>
author	Martin Možina <martin.mozina@fri.uni-lj.si>	2016-12-05 11:51:58 +0100
committer	Martin Možina <martin.mozina@fri.uni-lj.si>	2016-12-05 11:51:58 +0100
commit	236001ec7563804f87a40c924681461bc8b2d764 (patch)
tree	534a9ba942e6f6906d751439dff8864130a370ea /python/problems/re/re_sl.html
parent	413bb73adaee77e8c1ab1c5721b13d9b6f756a7a (diff)