Doplněk symbolua nad abecedou S je množina symbolů S-{a}.
Řetězec nad abecedou S je posloupnoust symbolů z množiny S.
Řetězec x je podřetězcem řetězce y, pokud y=uxv, kde u, x, v Î S*.
Délka řetězce w je počet symbolů v řetězci w Î S* a označuje se |w|.
Prázdný řetězec je řetězec délky 0 a označuje se Epsilon.
Vyhledávačem vzorku v textu (pattern matcher) míníme algoritmus, který v zadaném vstupním textu hledá výskyt požadovaného vzorku. Vzorek budeme nadále označovat jakožto pole znaků Vzorek[] a text v němž vyhledáváme jako pole Text[]. Nechť m je délka vzorku a nechť n a je délka textu. Dále zavedeme konvenci, kdy poziční ukazatele ve vzorku a textu označíme postupně i a j.
Algoritmy
Obvyklé členění
Na klasifikaci metod pro vyhledávání v textech můžeme nazírat z více stran. Jedním z možných pohledů je rozlišení, zda metoda vyžaduje předzpracování textu a/nebo předzpracování vzorku. Příkladem metody, která nevyžaduje ani jedno z uvedeného je například naivní algoritmus (brute force). Metody, které vyžadují pouze předzpracování vzorku, jsou ty, o kterých se zde budu převážně zmiňovat. Postup probíhá tak, že nejprve je na základě vstupního vzorku jednorázově vytvořen vyhledávací stroj, který poté provádí samotné vyhledávání. Tato konstrukce vyhledávacího stroje není obvykle příliš časově ani paměťově náročná, tudíž se jedná o metody velmi vhodné pro plnotextové vyhledávání v reálném čase. Mezi zástupce patří právě známé algoritmy KMP (Knuth-Morris-Pratt) či BM (Boyer-Moore).
Odlišný přístup volí metody, které pro zadaný text, v němž se má provádět vyhledávání, nejprve vytvoří index, což není nic jiného než seznam slov s odkazy na jejich umístění v textu. Označují se také pojmem indexové metody.
Poslední skupina je tvořena tzv. signaturovými metodami, vyžadujícími jak zpracování textu tak vzorku, kdy se pro vzorek a text konstruují charakteristické bitové vektory. V následujícím textu bude pozornost zaměřena na první a zejména druhou kategorii.
Další obvyklé členění algoritmů se řídí počtem zadaných vzorků specifikovaných na vstupu respektive počtem vzorků, který je vyhledávací stroj schopen současně vyhledávat. Pro jednoprvkovou množinu vzorků je možno použít například již zmiňované algoritmy KMP a BM. Pro konečnou víceprvkovou množinu se používaji například variace algoritmů AC (Aho-Corasicková) nebo CW (Commentz-Walterová). Nekonečný počet prvků je nejvhodnější zadat pomocí regulárního výrazu a vyhledávací stroj tedy může být založen na procházení konečného automatu.
Vyhledávací problém
Cílem všech vyhledávacích algoritmů, o kterých budeme nadále hovořit, je zjistit výskyt vzorků v textu. Existuje mnoho různých variant jak zadefinovat vyhledávací problém.
Zjisti, zda se zadaný vzorek vyskytuje v textu. Výsledkem je boolovská odpověď ano/ne.
Nalezni první výskyt zadaného vzorku a vrať jeho pozici v textu.
Nalezni poslední výskyt zadaného vzorku a vrať jeho pozici v textu.
Nalezni počet výskytů zadaného vzorku.
Nalezni všechny výskyty zadaného vzorku a vrať jejich pozici v textu a to i v případě, že se nalezené výskyty překrývají.
Vztah ke konečným automatům
Jelikož všechny jednorozměrné problémy vyhledávání vzorků v textu můžeme klasifikovat jakožto sekvenční problémy, je možné je řešit využitím teorie konečných automatů.
Pokud zadáváme vstupní hledané vzorky, specifikujeme tím v podstatě námi akceptovatelný jazyk (omezujeme se pouze na regulární). V tomto případě se pro specifikaci jazyka hodí využití definice pomocí analyzátorů. Pro regulární jazyk vystačíme s konečným automatem (KA). Protože při konstrukci nejprve vytváříme nedeterministický KA (NKA), ale při vizualizaci postupujeme deterministicky (DKA), je třeba provést převod. Platí, že ke každému NKA lze setrojit ekvivalentní DKA, který přijímá stejný jazyk.
Dále je třeba si uvědomit, že jazyky rozpoznatelné KA jsou právě tzv. regulární výrazy.
Definice
Třída RJ(A) všech regulárních jazyků nad abecedou A je nejmenší třída jazyků nad A splňující podmínky:
0 Î RJ(A), {a} Î RJ(A) pro všechna a Î A
M, N Î RJ(A) Ţ M Č N Î RJ(A)
M, N Î RJ(A) Ţ M · N Î RJ(A)
M Î RJ(A) Ţ M* Î RJ(A)
Operace sjednocení, násobení a iterace se nazývají také regulární operace nad jazykem. Regulární jazyky jsou tedy právě ty jazyky, které lze dostat z konečných jazyků aplikací konečně mnoha regulárních operací.
Definice
Množinu RV(A) regulárních výrazu nad abecedou A={x1, ..., xn} definujeme jako nejmenší množinu slov v abecedě x1, ..., xn, L, 0, +, ·, *, (, ), kde L, 0, +, ·, *, (, ) jsou symboly nepatřící do abecedy A a splňující podmínky:
0 Î RV(A), L Î RV(A), a Î RV(A) pro všechna a Î A
a,b Î RV(A) Ţ (a + b) Î RV(A), (a · b) Î RV(A), a* Î RV(A)
Definice
Pro libovolné a Î RV(A) definujeme [a] hodnotu regulárního výrazu a takto:
Hodnota libovolného regulárního výrazu je zřejmě regulární jazyk a naopak.
Tento přístup má značné výhody. Zásadní je zejména to, že teorie konečných automatů je již
velice dobře teoreticky rozpracována a můžeme se proto opírat o pevnou základnu. Máme možnost popsat všechny pro nás zajímavé problémy pomocí jednotného pohledu. V důsledku zavedení tohoto formalismu lze tvrdit, že pokud existuje způsob jak zkonstruovat konečný automat pro nějaký problém vyhledávání vzorků v textu, pak také pro něj existuje algoritmus s lineární časovou složitostí. Prostorová složitost se však liší případ od případu.
Prototypový systém
Cíle
Jelikož existuje nepřeberné množství různých algoritmů zaměřených na vyhledávání v plných textech, které se liší návrhem, časovou i pamětovou složitostí, bylo prvním úkolem pohlédnout na celý problém shora a nalézt jakýsi jednotný systém, který by umožňoval klasifikaci a porovnání maximální většiny dostupných a využívaných algoritmů. Při podrobnějším zkoumání zadané problematiky, se jakožto vhodný systém pro základ mé práce stal šestidimenzionální pohled na klasifikaci problému vyhledávání vzorků.
6-D model
Jedná se o jednotný pohled na vyhledávání vzorků za použití šesti kritérií a návrh konstrukce modelů pomocí nedeterministického konečného automatu.
Definice
Nechť P=p1, p2, ..., pm je hledaný vzorek (řetězec či posloupnost znaků), délka vzorku |P| = m, nechť T=t1, t2, ..., tn je prohledávaný text a délka textu |T|=n.
Při vyhledávání jednoduchého vzorku v textu definujeme:
Vyhledání řetězce (string matching): ověření, zda řetězec P je podřetězcem řetězce T.
Vyhledání posloupnosti znaků (sequence matching): ověření, zda posloupnost znaků vzorku P je podposloupností znaků textu T.
Vyhledání části vzorku (subpattern matching): ověření, zda se část vzorku P (řetězec či posloupnost znaků) vyskytuje v textu T.
Aproximativní vyhledání (aproximate pattern matching): ověření, zda se vzorek P vyskytuje v textu T tak, že rozdílová metrika D(P, X) < k pro dané k < m, kde X = ti ... tj, je částí textu T.
Vyhledání vzorku s don't care symboly (pattern matching with don't care): ověření, zda se vzorek P obsahující don't care symboly vyskytuje v textu T.
Definice
Nechť P1, P2, ..., Ps je uspořádaná sekvence hledaných vzorků (řetězec či posloupnost znaků), nechť T=t1, t2, ..., tn je prohledávaný text a délka textu |T|=n.
Při vyhledávání uspořádané sekvence vzorků v textu definujeme:
Vyhledání sekvence vzorků (matching of sequence of patterns): ověření, zda výskyt vzorku Pi v textu T je následován výskytem vzorku Pi+1, 1 Ł i<s.
Definice
Rozdílové metriky mezi dvěma vzorky X a Y definujeme jako minimální počet operací k přechodu od jednoho vzorku k druhému.
R (Hammingova metrika): jedinou možnou operací je zde přepis znaku, čímž zachovává délku na výstupu.
DIR (Levenshteinova metrika): povolenými operacemi jsou přepis, odebrání a vložení znaku.
DIRT (obecná Levenshteinova metrika): povolenými operacemi jsou přepis, odebrání, vložení a transpozice znaku.
Definice
Pro samotnou klasifikaci v modelu je použito několik hodnot uspořádaných do šesti dimenzí:
Spojitost vzorku: řetězec, posloupnost
Integrita vzorku: celý vzorek, část vzorku
Počet vzorků: jeden, konečný počet, nekonečný počet
Důležitost symbolů: záleží na všech znacích, na některých znacích nezáleží
Počet instancí vzorku: jedna, konečný počet
Implementace
Programovací jazyk
Prakticky již ze zadání problému bylo zřejmé, že pro implementaci budu muset využít objektově orientovaný programovací jazyk Java, který byl navržen tak, aby byl přenositelný mezi různými platformami a operačními systémy. Byl vyvinut firmou SUN Microsystems silně při tom čerpaje z programovacího jazyka C++. K řešení mé práce se ukázal vhodný zejména proto, že využívá moderní objektový přístup, což bylo pro tuto dynamickou aplikaci zásadní. Použití byte kódu na jednu stranu umožňuje onu senzační přenositelnost, ale na druhou stranu za to platíme krutou daň ve formě pomalého zavádění programu, než je proveden překlad z byte kódu do interního kódu dané platformy. V případě této aplikace se však nejedná o klíčový nedostatek, byl nepříjemný především ve fázi ladění programu.
Vývojové prostředí
Jakožto vývojové prostředí jsem si zvolil Netbeans, kompletně napsané v samotné Javě
s použitím rozšíření Java Foundation Classes, původně vytvořené v České republice. Svého času bylo
volně ke stažení z Internetu. V dnešní době je však produkt již odkoupen firmou SUN,
která jej nyní nabízí pod označení Forte (v základní verzi opět zdarma). Ovšem po
přepracování má prostředí mnohem vyšší nároky na hardware, především na velikost operační
paměti.
Sami autoři doporučují pro práci 256 MB RAM na platformě Windows/32.
Prostředí je poměrně intuitivní a nabízí zejména příjemné ladící techniky.
Dynamická reprezentace grafu
Provázanost datových struktur systému
Základními strukturami jsou objekty Uzel (Node) a Hrana (Edge).
Mezi položky objektu Uzel patří přesné celočíselné souřadnice umístění na ploše, dále vnitřní atributy udávající označení a barvu uzlu. Každý uzel taktéž obsahuje ukazatele na pomocný seznam vstupních a výstupních hran z uzlu a odkaz na další uzel v lineárně zřetězeném seznamu uzlů.
Hrana je charakterizována několika vnitřními atributy, které specifikují zejména označení (ohodnocení) hrany a její barvu. Neméně důležité jsou poziční parametry, které v nejjednodušším případě udávají počáteční a koncový bod hrany (pokud se jedná o úsečku), ve složitějším případě pak navíc pole řídících interpolačních bodů (pokud se jedná o křivku). Ke každé hraně také přísluší pole souřadnic pro směrovou šipku. A konečně, hrana obsahuje ukazatele na uzel z něhož vychází, na uzel do kterého směřuje a odkaz na další hranu v lineárně zřetězeném seznamu hran.
Pomocný seznam hran používám z toho důvodu, že potřebuji mít k dispozici snadno přístupné uzly a hrany (tedy ve formě lineárně zřetězených seznamů). Jelikož se však mezi uzlem a hranami jedná obecně o relaci 1:N, využívám pomocný seznam hran, respektive zřetězený seznam ukazatelů na konkrétní hrany.
Moduly
Z předchozí kapitoly o vizualizaci vyplývá, že bychom měli uživatelům svých produktů nabídnout maximální míru osobního nastavení (customization) a přizpůsobení vlastním potřebám. Z tohoto důvodu používám třídu globálních proměnných Vars pro nastavení nejrůznějších parametrů vykreslování i animace samotné. Pochopitelně je možné toto nastavení vyexportovat do externího souboru a při novém spuštění znovu načíst.
Validátor
Jedinou funkcí tohoto modulu je ověření správné syntaxe uživatelem zadaného regulárního výrazu na vstupu. Povoleny jsou pouze znaky definované abecedy A a řídící znaky abecedy C mezi jejíž prvky patří znaky levé a pravé závorky ( , ) uvozující či ukončující víceznakovou sekci určenou k iteraci, znak + (uvozuje nový vzorek), * (označuje iteraci předchozího znaku) a ? (používaný ve funkci don't care symbolu).
Parser
Tento modul přebírá na vstupu regulární výraz s ověřenou syntaxí a jeho podrobnou analýzou vytváří tři inicializační vektory nezbytné ke konstrukci grafu - konečného automatu. Konkrétně se jedná o množinu počátečních stavů, množinu sousedů a množinu koncových stavů.
Základní myšlenku přebírá z následujícího algoritmu:
Vstup: Regulární výraz RV Výstup: Konečný automat KA = (S, A, D, q0, F) takový, že hodnota regulárního výrazu h(RV)=L(KA), kde L(KA) je jazyk generovaný konečným automatem KA.
očíslujeme postupně všechny výskyty znaků z abecedy A v regulárním výrazu RV čísly 1,2 ... r. Upravený RV označíme URV.
sestrojíme množinu počátečních symbolů: Z={xi: x Î A, kdy znakem xi může začínat nějaký řetězec z h(URV)}
sestrojíme množinu sousedů: P={xiyj: xi, yj Î A, kdy xi a yj se mohou vyskytovat vedle sebe v nějakém řetězci z h(URV)}
sestrojíme množinu koncových symbolů: F={xi: xi Î A, kdy symbolem xi může končit nějaký řetězec z h(URV)}
množinu stavů KA konstruujeme takto: S={q0} Č {qi: qi Î A, i Î {1, 2, ... , r} }
přechodovou funkci D sestrojíme podle předpisu: a) D(q0, x) obsahuje xi pro všechna xi Î Z vzniklá očíslováním x b) D(xi, y) obsahuje yi pro všechny dvojice xi, yj Î P takové, že yj vzniklo očíslováním y.
množina F je množinou koncových symbolů.
Vzniklé tři množiny jsou předány k dalšímu zpracování modulu GraphMaker.
Modul Parser taktéž při analýze zadaného regulárního výrazu automaticky vyhodnotí kritéria počtu vzorků a don't care symbolu, takže tyto parametry 6D pohledu není nutno individuálně specifikovat při parametrizaci.
Konstruktor grafu
Konstruktor grafu (GraphMaker) přebírá množiny počátečních, sousedních a koncových symbolů a na základě těchto informací vytváří dynamický graf. Děje se tak přidáváním objektů typu Uzel (výchozí, prvky množiny počátečních symbolů a prvky množiny ještě neobsažených sousedů) a objektů typu Hrana (propojení výchozího uzlu s prvky množiny počátečních symbolů a vzájemné propojení sousedů). Nakonec se na základě množiny koncových symbolů nastaví příznak pro koncové akceptující stavy grafu.
Při tom zároveň nastavuje atributy objektů, které se získávají algoritmickým výpočtem, užitím defaultních hodnot nebo aplikací globálních parametrů z objektu typu Vars.
Modifikátor grafu
Modifikátor má za úkol vytvořený dynamický graf upravit dle přání uživatele. Ten má teoreticky k dispozici celkem šest kritérií, která nastavovat.
Spojitost vzorku
-- Defaultně je graf vytvořen pro hodnotu řetězec. Změnou na hodnotu posloupnost dochází k modifikaci, kdy přidáním smyček ohodnocených množinou symbolů z abecedy A s výjimkou symbolu následujícího v posloupnosti ke všem uzlům z nichž vychází alespoň jedna hrana, dosáhneme akceptace posloupnosti znaků s libovolným množstvím nezajímavých mezisymbolů.
Integrita vzorku
-- pro volbu část vzorku je třeba modifikovat graf na tzv. faktorový automat, akceptující všechny podřetězce.
Počet vzorků
-- tento parametr se automaticky určuje při analýze v modulu Parser podle obsažených řídících symbolů.
Benevolence
-- při použití některé z aproximačních technik je graf modifikován pro simulaci operací R (replace), D (delete), I (insert) a T (translate). Používám k tomu algoritmus pro konstrukci konečného automatu KA(Lk(P)) akceptujícího jazyk Lk(P) při toleranci k chyb na vzorku P.
Důležitost symbolů
-- při analýze vzorku je možno podle výskytu řídících znaků reprezentujících don't care symboly nastavit tento parametr automaticky.
Počet instancí vzorku
-- při konečném počtu instancí lze přidáním sběrného uzlu, do něhož vcházejí hrany ze všech akceptačních (konečných) uzlů, vyvolat další průchod automatem.
Vykreslovací modul
Hlavním požadavkem na vykreslovací modul bylo, aby vhodně rozmístil uzly a hrany na vykreslovací ploše. Rozmístění se kvůli urychlení propočítavá již ve fázi konstrukce grafu. Využívá se k tomu parametrů globálního nastavení. Uzly jsou rozmisťovány pravidelně do ortogonální mřížky. Pokud velikost grafu přeroste přes viditelnou plochu, umožní posuv pomocí okrajových lištiček.
Po vygenerování grafu, který odráží všechny požadované objekty a vzájemné vazby vyvstává problém, jak tento nepřehledný diagram vhodně zobrazit. Je třeba dodržet přesný postup při modifikaci grafu a šikovně označovat jednotlivé uzly v závislosti na příslušenství ke svému rodičovskému automatu od něhož je většína uzlů odvozena. Přesto však i při dobrém návrhu nastávají konfliktní situace, které je třeba řešit.
Mohou se objevit konflikty dvou uzlů (tomu zcela zamezuji), konflikty dvou hran (v aktuální verzi není prozatím ošetřeno) a konflikty uzlu s hranou. Snadno může nastat situace, kdy by hrana spojující dva uzly protínala také nějaký uzel na jejich přímé spojnici.
Problém řeším tak, že nejprve zjistím počet uzlů ležících ve výřezu daném příslušnými dvěma spojovanými uzly. Pokud jejich počet (potencionální překážky) je nulový, spojuji uzly pouze úsečkou. Pokud jsem detekoval možné překážky, vybírám postupně ty nejbližší od uzlu z něhož zkoumaná hrana vystupuje a testuji, zda jeho vzdálenost od přímé spojnice je dostatečná (zadáno v globálních parametrech). Pokud není, přidávám do seznamu další kontrolní bod pro interpolaci křivky, který již podmínku splňuje.
Podle směrnice spojující usečky, respektive podle posledního segmentu křivky počítám umístění a úhel otočení směrové šipky.
Vizualizace
Vizualizace jako taková je spuštěna výběrem volby ve složce Action. Musí být však splněny následující předpoklady: musí existovat dynamicky vytvořený graf (obecně nedeterministický konečný automat) a editovatelné textové pole (sekce 5) musí obsahovat text k prohledávání.
Poté je vytvořeno a spuštěno speciální vlákno ovládající celou animační sekvenci. Nejedná se o plynulou animaci, ale pouze o sekvenci klíčových snímků, které reprezentují měnící se stav našeho grafu. Pauzu mezi snímky je možno navolit podle potřeby.
Protože získaný dynamický graf je nedeterministickým konečným automatem (NKA), je třeba zvolit před samotným prohledáváním jednu z variant. První možností je převést NKA na DKA, což sebou ovšem nese problém teoretického nárustu počtu stavů až na O(2m). Obvykle sice v praxi nedochází k exponenciálnímu nárustu, ale přesto se dává často přednost druhé variantě -- simulaci NKA. V aktuální verzi systému se držím druhé varianty.
Na počátku se inicializuje nastavení barev, které hraje v dalším procesu zásadní roli a nastavuje ukazatel konečného automatu (aktuální uzel) na výchozí uzel Start a ukazatel prohledávaného textu (aktuální znak) na první znak textu.
Dále naleznu všechny následníky aktuálního uzlu, z těchto adeptů pak vyberu ty, do kterých je možno se dostat skutečně pod aktuálním znakem (provedu označení). Pokud jsem nic nenalezl, inicializuji automat do původního stavu a posouvám se v textu.
Pokud jsem ovšem získal neprázdnou množinu následníků, mám šanci na akceptaci. Pokud v množině následníků leží uzel s nastaveným příznakem konečného stavu, automat se dostal do akceptujícího stavu a vzorek byl tedy nalezen. Pokud v neprázdné množině následníků, žádný takový uzel neleží, zachovám stav automatu i prohledávaného textu a celý zde uvedený postup provádím pro všechny získané následníky. Po konečném počtu kroků se vždy dostanu do fáze akceptace vzorku nebo do fáze odmítnutí (z důvodu kolize přechodové funkce automatu s aktuálním znakem či proto, že jsme narazili na konec textového souboru v okamžiku pouze částečné akceptace).
Knuth, D.E., Morris, J.H., Pratt, V.R, Fast pattern matching in strings, SIAM Journal on Computing, Vol. 6, No. 2, Society for Industrial and Applied Mathematics, Philadelphia, 1977
Boyer, R.S., Moore, J.S, A fast string searching algorithm, Communications of the ACM, Vol. 20, No. 10, Association for Computing Machinery, Inc., 1977
Melichar,B., Holub, J., 6D classification of pattern matching problems, Proceedings of the Prague Stringology Club Workshop '97, Colaborative Report DC-97-03