Pedmluva I kdy pota byl vytvoen pedevm jako stroj na provdn v pot , postupn se do program vkldaly sti, kter pracovaly s textov mi etzci. Nejdve lo jen o pidvn textov ch informac do v stupnch dat, kter slouily pro jejich lep itelnost. Dalm krokem byla monost ten textov ch etzc , kter byly do v stupnch dat ze stejn ch d vod pidvny bu beze zmny nebo jen s mal mi zmnami. Pozdji bylo mono vstupn text uchovat jako hodnotu promnn , co pmo vedlo k monosti zpracovn textu. Tento v voj je mono pozorovat na zmnch v monostech programovacch jazyk . Nejl pe je tato skutenost patrn z v voje jazyka FORTRAN. Typick m jevem pro prostedky v poetn techniky je pevn formt dat, a proto se v zatcch zpracovn textu pouvaly pedevm etzce pevn d lky, tabulky, formule. V ad ppad se textov informace pro zpracovn na potai kdovaly pomoc sel. Tomuto jevu odpovdal i v voj databzov ch syst m . Databzov syst my se zaaly pouvat pedevm pro prci s seln mi daji a s formtovan mi textov mi daji. Vechny zkladn modely databzov ch syst m (relan, sov , hierarchick ) jsou orientovny na prci s formtovan mi daty. Zpracovn neformtovan ch textov ch informac na potach se vyvjelo pomrn pomalu, i kdy je zejm , e vtina text , se kter mi se v ivot setkvme, m voln neformtovan tvar. Tento tvar vyhovuje ten m. Jedn se o knihy, asopisy, noviny, edn spisy, zkony, pkazy a podobn dokumenty. Souasn doba je charakterizovna jako obdob informan exploze, co pedevm znamen prudk nr st vytven textov ch materil . V poetn technika se v t to oblasti uplatuje v mnoha smrech: pi pprav textu se pouvaj textov editory a syst my pro kontrolu jazykov sprvnosti textu, pi uchovn textu se pouvaj nejr znj zp soby organizace textu tak, aby potebn prostor pro uchovn textu byl co nejmen a (nebo) aby bylo mono v textu co nejrychleji nal zt potebnou informaci, pi penosu textu se pouvaj metody zabezpeujc text proti chybm a metody komprese textu, pi vyhledvn informac v textu se pouvaj postupy umoujc rychl nalezen poadovan informace, pi v stupu textu pro prezentaci se pouvaj formtovac syst my umoujc pipravit pehledn a estetick v stupn dokument. Tento uebn text je uren jako uebn pom cka pro studium pedmtu Textov informan syst my. Vzhledem k tomu, e pojem informan syst m je velice irok , bylo nutno zamen tohoto textu zit. V textu jsou podrobn rozebrny z algoritmick ho hlediska zejm na tyto ti probl my: 1. vyhledvn v textu, 2. komprese textu, 3. kontrola sprvnosti textu. Krom tchto zkladnch skupin probl m textov ch syst m jsou dle zmnny otzky zkladnch princip organizace a pouit informanch syst m . 3
Na druh stran je teba uv st, e v textu nejsou uvedeny kapitoly pojednvajc o piblin m vyhledvn a o hypertextov ch syst mech. Ob tyto oblasti se rychle rozvjej a pprava pslun ch kapitol si vyd del dobu. Podkladem pro tento uebn text byl pedevm uebn text pro postgraduln kurz Inen rsk informatika (Melichar,B.: Informan syst my, ES VUT Praha, 1991) a pehledov zprva vydan na katede pota (Melichar,B., Pokorn ,J.: Data Compression, Survey Report DC-92-04, April 1992). Na pprav pedlohy pro tisk v syst mu LATEX se podleli studenti v rmci cvien z pedmtu Textov informan syst my ve kolnm roce 1993/94. Jim dkuji za ppravu prvn verze uebnho textu. Dle dkuji RNDr. Alen Balvnov a Ing. Martinu Blochovi, CSc. za peliv peten pracovn verze textu a za jejich cenn nmty, kter byly vyuity pi pprav nln verze textu. M j dk pat tak RNDr. Alen Balvnov , Olze Vrtikov a Jan Hanzlkov za ppravu konen verze pedlohy pro tisk. Mnek pod Brdy, ervenec 1994
Boivoj Melichar
Za prvn rok po vydn tohoto uebnho textu byl cel nklad rozebrn. Proto byl pipraven dotisk, ve kter m jsou opraveny chyby, kter byly nalezeny. Dkuji vem student m, kte mi pi tom vydatn pomhali. Mnek pod Brdy, kvten 1996
Boivoj Melichar
4
Obsah 1 Zkladn pojmy informanch systm
7
2 Klasi kace informanch systm
8
3 Vyhledvac systmy
10
4 Vyhledvac algoritmy
11
4.1 Elementrn algoritmus : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.2 Vyhledvac metody s pedzpracovnm vzork : : : : : : : : : : : : : : : : : : 4.2.1 Vyhledvac metody s pedzpracovnm vzork se sousmrn m vyhledvnm : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.2.1.1 Vyhledvac stroj : : : : : : : : : : : : : : : : : : : : : : : : : 4.2.1.2 Knuth-Morris-Pratt v algoritmus : : : : : : : : : : : : : : : : 4.2.1.3 Algoritmus Aho-Corasickov : : : : : : : : : : : : : : : : : : : 4.2.1.4 Vyhledvac konen automaty : : : : : : : : : : : : : : : : : : 4.2.1.5 Vyhledvn nekonen mnoiny vzork : : : : : : : : : : : : : 4.2.2 Vyhledvac metody s pedzpracovnm vzork s protismrn m vyhledvnm : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.2.2.1 Boyer-Moore v algoritmus : : : : : : : : : : : : : : : : : : : : 4.2.2.2 Algoritmus Commentz-Walterov : : : : : : : : : : : : : : : : 4.2.2.3 Protismrn vyhledvn nekonen mnoiny vzork : : : : : : 4.2.2.4 Dvoucestn automat se skokem : : : : : : : : : : : : : : : : : : 4.2.3 Shrnut : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.3 Vyhledvac metody s pedzpracovnm textu { indexov metody : : : : : : : : 4.3.1 Implementace indexov ch syst m : : : : : : : : : : : : : : : : : : : : : 4.3.1.1 Pouit invertovan ho souboru : : : : : : : : : : : : : : : : : : 4.3.1.2 Pouit seznamu dokument : : : : : : : : : : : : : : : : : : : 4.3.1.3 Souadnicov syst m s ukazateli : : : : : : : : : : : : : : : : : 4.3.2 Metody indexovn : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.3.2.1 Anal za textu : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.3.2.2 Jednoduch metoda automatick ho indexovn : : : : : : : : : 4.3.2.3 $zen indexovn : : : : : : : : : : : : : : : : : : : : : : : : : 4.3.2.4 Konstrukce tezauru : : : : : : : : : : : : : : : : : : : : : : : : 4.3.2.5 Vyhledvn vzork pomoc fragmentov ch index : : : : : : : 4.4 Vyhledvac metody s pedzpracovnm textu a vzork { signaturov metody : 4.4.1 $etzen a vrstven kdovn : : : : : : : : : : : : : : : : : : : : : : : : 4.4.2 Metody tvorby signatur : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.4.3 Vyhledvn vzorku pomoc signatury a indexu : : : : : : : : : : : : : : 4.5 Vyhledvn vzork pomoc dvojit ho slovnku : : : : : : : : : : : : : : : : : : 5
12 13
13 13 14 16 19 23 34 34 36 39 41 43 44 45 45 45 45 47 47 49 49 50 51 51 52 53 54 54
5 Jazyky pro vyhledvn
56
6 Komprese dat
60
6.1 Zkladn pojmy komprese dat : : : : : : : : : : : : : : : : : : : 6.1.1 Kdovn a dekdovn : : : : : : : : : : : : : : : : : : 6.1.2 Entropie a redundance : : : : : : : : : : : : : : : : : : : 6.2 Predikce a modelovn : : : : : : : : : : : : : : : : : : : : : : : 6.3 Reprezentace cel ch sel : : : : : : : : : : : : : : : : : : : : : : 6.3.1 Fibonacciho kdy : : : : : : : : : : : : : : : : : : : : : : 6.3.2 Eliasovy kdy : : : : : : : : : : : : : : : : : : : : : : : : 6.4 Statistick metody komprese dat : : : : : : : : : : : : : : : : : 6.4.1 Shannon-Fanovo kdovn : : : : : : : : : : : : : : : : : 6.4.2 Hu%manovo kdovn : : : : : : : : : : : : : : : : : : : 6.4.2.1 Statick Hu%manovo kdovn : : : : : : : : : 6.4.2.2 Vlastnosti Hu%manov ch strom : : : : : : : : 6.4.2.3 Adaptivn Hu%manovo kdovn : : : : : : : : 6.4.2.4 Implementan poznmky : : : : : : : : : : : : 6.4.3 Aritmetick kdovn : : : : : : : : : : : : : : : : : : : 6.5 Slovnkov metody komprese dat : : : : : : : : : : : : : : : : : 6.5.1 Statick slovnkov metody : : : : : : : : : : : : : : : : 6.5.2 Semiadaptivn slovnkov metody : : : : : : : : : : : : : 6.5.3 Adaptivn slovnkov metody : : : : : : : : : : : : : : : 6.5.3.1 Metoda posuvn ho okna : : : : : : : : : : : : 6.5.3.2 Metody s rostoucm slovnkem : : : : : : : : : 6.5.3.3 Slovnkov metody s restrukturalizac slovnku 6.6 Syntaktick metody : : : : : : : : : : : : : : : : : : : : : : : : 6.6.1 Derivan kdovn : : : : : : : : : : : : : : : : : : : : : 6.6.2 Analytick kdovn : : : : : : : : : : : : : : : : : : : : 6.7 Kontextov modelovn : : : : : : : : : : : : : : : : : : : : : : 6.7.1 Konen kontextov modely : : : : : : : : : : : : : : : : 6.7.2 Modely zaloen na konen ch automatech : : : : : : : 6.7.2.1 Automaty s konen m kontextem : : : : : : : 6.7.2.2 Dynamick Markovovo modelovn : : : : : : :
7 Kontrola sprvnosti textu 7.1 7.2 7.3 7.4
Kontrola textu pomoc frekvennho slovnku Kontrola textu pomoc dvojit ho slovnku : : Interaktivn kontrola textu : : : : : : : : : : : Kontrola textu zaloen na pravidelnosti slov
Literatura
: : : :
: : : :
: : : :
: : : :
: : : :
: : : :
: : : :
: : : :
: : : :
: : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
60 60 62 62 64 64 65 67 67 68 69 70 72 74 76 78 79 79 80 80 82 87 89 89 90 91 91 92 92 93
95 96 96 97 98
99 6
1 Zkladn pojmy informanch systm Informan systm (informan soustava) je syst m, kter umouje eln uspodn sbru, uchovn, zpracovn a poskytovn informac. Informace je odraz poznan ho nebo pedpokldn ho obsahu skutenost. Informaci lze de novat vdy jen ve vztahu k syst mu, pro kter je urena. Informace je mono posuzovat z tchto t hledisek:
1. Kvantitativnho { jako mitelnou veliinu, kter seln vyjaduje mnostv informace obsaen v dan zprv. Toto hledisko studuje teorie informace. 1. Kvalitativnho { (v znamov ho, s matick ho) jako zprvu, kter zmenuje u pjemce neznalost jist ch skutenost, tj. zvtuje jeho informovanost. 2. Pragmatick ho { jako zprvu, kter m pro pjemce uritou hodnotu. Pi uren pragmatick (hodnotov ) strnky informac vychzme z tchto vlastnost: a) v znam pro een urit ho probl mu, b) uitenost { vyjaduje podl asti na een probl mu, c) upotebitelnost { vyjaduje monost jednorzov ho nebo vcensobn ho pouit, d) periodicita { vyjaduje etnost pouit, e) okruh pouit pro een r zn ch probl m , f) aktulnost podle rychlosti strnut informace, g) hodnovrnost. Krom uveden ch vlastnost se dle u informace posuzuje pohotovost, podrobnost, plnost, jednoznanost, dostupnost a nklady na jej zskn. daj (datum) je konkr tn vyjden zprvy ve form posloupnosti symbol njak abecedy. Z uveden ch de nic pojm daj a informace je zejm , e tyto pojmy nelze zamovat. Jist si m eme pedstavit daj, kter nenese dnou informaci. Informanm procesem rozumme proces vzniku informac, jejich zobrazen ve form daj , uchovn, zpracovn, poskytovn a vyuit. Tomuto procesu odpovdaj urit operace nad informacemi.
7
2 Klasi kace informanch systm Automatizovan informan syst my m eme klasi kovat podle pevldajc funkce, kterou pln. Nejd leitj typy informanch syst m jsou: 1. databzov syst my (data base management systems), 2. dokumentogra ck vyhledvac syst my (information retrieval systems), 3. faktogra ck syst my pro zen (management information systems), 4. syst my pro podporu rozhodovn (decision support systems), 5. expertn syst my (expert systems, question-answering systems).
Databzov systmy
Jak koliv automatizovan informan syst m je zaloen na databzi, tj. souboru poloek uloen ch v njak pamti, ke kter m m pstup. V databzov ch syst mech jsou jednotliv poloky uloeny jako zznamy, kter se skldaj ze sloek. Kad sloka obsahuje hodnotu urit ho typu. Pi vyhledvn informac je nutno stanovit speci ck hodnoty sloek zznam , kter je teba vyhledat. V sledkem vyhledvn je mnoina tch zznam , jejich pslun sloky maj hodnoty, kter pesn odpovdaj zadan mu poadavku. D se tedy ci, e informace uloen v databzi databzov ho syst mu je psn strukturovan a vyhledvn je na t to struktue zaloeno.
Dokumentogra ck vyhledvc systmy
V dokumentogra ck m vyhledvcm syst mu jsou jednotliv poloky uloeny ve form zznam (dokument ) obsahujcch textov informace obvykle v pirozen m jazyce. Pi vyhledvn informac je obvykle zadn vyhledvac v raz obsahujc slova, slovn spojen nebo sti slov. V sledkem vyhledvn je mnoina zznam , kter piblin odpovdaj vyhledvacmu v razu. Na rozdl od databzov ch syst m , je informace uloena v databzi vyhledvacho syst mu nestrukturovan nebo jen mlo strukturovan a pi vyhledvn se nen tedy mono opt o strukturu zznam .
Faktogra ck systmy pro zen
Informan syst m pro zen je databzov syst m pizp soben potebm dcho pracovnka (manaera). Je to syst m, kter navc m nkter funkce, kter nejsou bn u databzov ch syst m . Jedn se nap. o monost provdn proces s informacemi vybran mi z databze.
Systmy pro podporu rozhodovn
Syst m pro podporu rozhodovn je informan syst m, ve kter m jsou integrovny funkce databzov ho syst mu, vyhledvacho syst mu a syst mu pro zen. Obvykle je v tomto syst mu mono pout gra ky a prezentovat v sledky v bru informac nebo r zn ch v pot
v gra ck podob. 8
Expertn systmy
Expertn syst m se skld z databze a odvozovacho mechanismu. Uivatel zadv dotazy v jazyce, kter se podob pirozen mu jazyku. Syst m dotazy analyzuje a na zklad znalost uloen ch v databzi vytv odpov. Obr. 2.1 shrnuje vztahy mezi r zn mi typy informanch syst m . Vyhledv textov informace Uchovv text v pirozen m jazyce Zpracovv piblin dotazy @ I @ @ @
Vyhledv speci ck informace Uchovv fakta z urit oblasti a obecn znalosti Zpracovv dotazy z dan oblasti
vyhledvac syst m
expertn syst m
; ;
; ;
databze
; ; ; ;
databzov syst m
syst m pro zen
@ @
@ R @
Vyhledv uloen informace Uchovv strukturovan informace Zpracovv pesn dotazy
Pidv k databzov mu syst mu zpracovn vyhledan informace
Obr. 2.1: Vztahy r zn ch typ informanch syst m
Databzov syst my a syst my pro zen maj mnoho spolen ho. To se u ned ci o ostatnch typech informanch syst m . Databzov syst my a syst my pro zen zpracovvaj strukturovan daje asto ve form tabulek seln ch daj . Vyhledvac syst my a expertn syst my zpracovvaj daje v pirozen m jazyce. Vyhledvac syst my vyhledvaj dokumenty a expertn syst my vyhledvaj fakta potebn k odpovdi na zadan dotaz. Spolen m znakem vech typ automatizovan ch informanch syst m je existence databze pro uloen informac.
9
3 Vyhledvac systmy Existuje mnoho r zn ch typ vyhledvacch syst m . Abychom mohli posoudit v hody a nev hody r zn ch syst m , podvme se na vyhledvac syst m z hlediska jeho funkce. Databze vyhledvacho syst mu obsahuje mnoinu zznam (dokument ). Uivatel syst mu mohou zadvat poadavky (dotazy) na v br dokument . Vyhledvac syst m na zklad dotazu ur, kter dokumenty odpovdaj zadan mu dotazu. Tuto situaci znzoruje obr. 3.1. Nkter vyhledvac syst my jsou dodvny s databz a umouj jen vyhledvn dokument . Existuj vak tzv. przdn vyhledvac syst my, kter umouj doplovn databze s tm, e je mono de novat tvar a strukturu dokument , zp sob ppravy vstupnch dokument , zp sob v bru dokument a zp sob prezentace vybran ch dokument . Princip takov ho syst mu je znzornn na obr. 3.2.
datab'aze 6 ?
dotaz
-
Mechanismus pro uren'), kter'e dokumenty vyhovuj') dotazu
mnoina vybran'ych dokument(u
-
Obr. 3.1: Princip vyhledvn dokumentu
De nice dokument
6 ?
-
Vyhledvac
De nice formtu v stupnch dokument -
syst m
De nice zp sobu vyhledvn dokument Obsah dokument
databze
7
Mnoina vybran ch dokument v pedepsan m formtu-
6
dotazy
Obr. 3.2: Vyhledvac syst m s monost de nice a doplovn databze V dalch kapitolch se budeme podrobnji zab vat metodami uloen dokument , monostmi de nice jejich struktury, algoritmy pro v br dokument , monostmi organizace databze z hlediska rychlosti vyhledvn, jazyky pro zpis dotaz a metodami popisu formtu vystupujcch dokument . 10
4 Vyhledvac algoritmy Vyhledvn je operace, pi kter se zjituje, zda zadan text obsahuje hledan slova { vzorky. V ppad, e zadan text obsahuje hledan vzorky, zajm ns i informace o tom, kde se v zadan m textu vzorky vyskytuj. Budeme pedpokldat, e loha na vyhledvn vzork v textu je formulovna jednm z tchto zp sob :
a) Vyhledej vzorek v v textu.
V sledkem je informace o tom, kde se v textu vzorek v vyskytuje.
b) Vyhledej konenou mnoinu vzork p = fv1 v2 : : : vk g.
V sledkem je informace o tom, kde se v textu vyskytuje nkter ze zadan ch vzork .
c) Vyhledej nekonenou mnoinu vzork zadanou regulrnm v razem R. Regulrn v raz R
de nuje mnoinu L(R), kter m e b t nekonen. V sledkem je informace o tom, kde se v textu vyskytuje nkter ze vzork z mnoiny L(R).
Ve vech ppadech m eme lohu na vyhledvn vzork formulovat tak, e vyhledvme bu prvn v skyt nebo vechny v skyty njak ho vzorku. Ve druh m ppad ns zajm i ppad, kdy se vyhledvan vzorky pekr vaj. Napklad pi vyhledvn vzorku abab v textu aaabababa m eme zjistit, e vzorek se objevuje dvakrt a to od pozice tet a pt . Metody vyhledvn m eme rozdlit do dvou skupin: a) Do prvn skupiny pat postupy, pi kter ch se prohl samotn text. b) Do druh skupiny pat postupy, pi kter ch je nejdve prohl dnuta pedem pipraven +nhraka, textu, kter charakterizuje p vodn text. Takov nhraka m e b t
{ index, tj. uspodan seznam v znamn ch prvk s odkazy do p vodnho textu, { signatura, tj. etzec pznak indikujc ptomnost v znamn ch prvk v textu. Co do kvality hledn je nejlep metoda, kter prohl samotn text. Tento pm pstup m e vak b t znan asov nron . Metoda pouvajc +nhraky, umouje hrub vyhledn rychleji, avak v sledek nemus b t kvalitn. Oba pstupy lze spolu kombinovat pi dvoustupov m vyhledvn. Nejdve se pouije rychl metoda nhraek, m se vylou vtina textu, ve kter se zadan vzorky v bec nevyskytuj. Na zbyl menin textu se pak pouije pm prohledn, kter vede k pesn m v sledk m. Metoda nhraek vyaduje pedchoz ppravu textu, kter m e b t dosti nkladn. Aby se tato investice vyplatila, mus b t vyhledvan ch vzork dostaten poet. Na druh stran nkter metody vyaduj pedzpracovn hledan ch vzork . Metody vyhledvn m eme klasi kovat podle toho, zda vyaduj pedzpracovn text
nebo pedzpracovn vzork nebo oboj, do ty kategori podle tabulky 4.1. Do skupiny I pat elementrn algoritmus, kter nevyaduje ani pedzpracovn textu ani pedzpracovn vzorku. 11
Metoda vyaduje
Pedzpracovn textu ne ano Pedzpracovn ne I III vzork
ano II IV Tabulka 4.1: Klasi kace vyhledvacch metod Do skupiny II pat metody, kter pro dan vzorek nebo mnoinu vzork vytvo nejdve vyhledvac stroj, kter potom provd vyhledvn. Do skupiny III pat indexov metody, kter pro text, ve kter m se m vyhledvat, vytvo index. Index je uspodan seznam slov s odkazy na jejich umstn v textu. Do skupiny IV pat signaturov metody, kter vytvo pro vzorek nebo mnoinu vzork a prohledvan text etzce bit (signatury), kter jak vzorky tak text charakterizuj, a vyhledvn se provd porovnvnm signatur. Druh m krit riem pro klasi kaci vyhledvacch metod je odpov na otzku, zda metoda umouje vyhledn pouze jedin ho vzorku nebo souasn vyhledvn konen nebo nekonen mnoiny vzork . Tetm kriteriem pro klasi kaci vyhledvacch metod je smr porovnvn vzork a smr pr chodu textem. Text se obvykle prohledv smrem zleva doprava. Sousmrn metody porovnvaj vzorky tak ve smru zleva doprava. Protismrn metody provdj porovnn vzork
v opan m smru, t.j. zprava doleva.
4.1 Elementrn algoritmus Elementrn algoritmus postupn pikld a porovnv jedin vzorek ve vech pozicch textu. Prohledvan text a zadan vzorek se nijak nepedzpracovv. Princip tohoto algoritmu m eme znzornit fragmentem programu v Pascalu takto: var TEXT : array1..T] of char VZOREK : array1..V] of char I,J : integer NALEZEN, SHODA : boolean ... NALEZEN := false I := 0 while not NALEZEN and (I <= T - V) do begin I := I + 1 J := 0 SHODA := true while SHODA and (J < V) do if TEXTI+J] = VZOREKJ+1] then J:=J + 1 else SHODA := false NALEZEN:= J = V end ...
12
Poznmka: Promnn I ukazuje v ppad nalezen vzorku na prvn znak prvnho v skytu vzorku v textu.
Budeme-li povaovat za mru asov sloitosti algoritmu poet porovnn jednotliv ch znak
vzorku a textu (viz v raz TEXT -I + J ] = V ZOREK -J + 1]), pak poet tchto porovnn je pinejhorm V (T ; V + 1), tedy asymptoticky lep ne O(V T ). Tento ppad nastane napklad, kdy vzorek m tvar aV ;1 b a text m tvar aT ;1 b. U pirozen ch jazyk vak dochz k neshod znak textu a vzorku vtinou velmi brzy (u prvnho i druh ho porovnvan ho znaku). Poet porovnn se tedy sn na CE (T ;V +1), kde CE je empiricky zjitn konstanta. Pro anglitinu m hodnotu 1.07, pro etinu zjitna nen. Je tedy praktick asymptotick sloitost elementrnho algoritmu rovna O(CE T ), tj. algoritmus se chov prakticky jako linern. Implementace elementrnho algoritmu je velmi jednoduch. Elementrn algoritmus umouje sousmrn vyhledvn jednoho vzorku. V ppad konen mnoiny vzork je nutno jej pout opakovan pro kad vzorek. Pro vyhledvn nekonen mnoiny vzork je nepouiteln .
4.2 Vyhledvac metody s pedzpracovnm vzork V tomto odstavci se budeme zab vat metodami vyhledvn, kter provd pedzpracovn vzork ped vlastnm vyhledvnm. V sledkem tohoto pedzpracovn vzork je vyhledvac stroj, kter je potom pouit pro vyhledvn. Popisovan metody rozdlme na metody pro sousmrn vyhledvn a protismrn vyhledvn.
4.2.1 Vyhledvac metody s pedzpracovnm vzork se sousmrnm vyhledvnm Do skupiny metod, kter vytv vyhledvac stroj, kter provd sousmrn vyhledvn pat: 1. Knuth-Morris-Pratt v algoritmus pro vyhledvn jednoho vzorku, 2. algoritmus Aho-Corasickov pro vyhledvn konen mnoiny vzork , 3. konen automat pro vyhledvn nekonen mnoiny vzork .
4.2.1.1 Vyhledvac stroj Vyhledvac stroj pro sousmrn vyhledvn je de novn takto: Vyhledvac stroj A = (Q T g h q0 F ), kde Q je konen mnoina stav , T je konen vstupn abeceda, g Q T ! Q ffailg je dopedn pechodov funkce, h (Q ; q0 ) ! Q je zptn pechodov funkce, q0 je poten stav, F je mnoina koncov ch stav . V dalch odstavcch uvedeme konstrukci vyhledvacch stroj pro jednotliv metody. Kon gurace vyhledvacho stroje je dvojice (q w), kde q 2 Q je stav, ve kter m se stroj nachz a w 2 T je dosud neprohledan st textu. Poten kon gurace je dvojice (q0 w), kde w je cel prohledvan text. Kon gurace, ve kter dolo k nalezen vzorku, je dvojice (q w), kde 13
q
2 F je koncov stav a w neprohledan st textu. Nalezen vzorek je bezprostedn ped textem w. Vyhledvac stroj pro sousmrn vyhledvn provd dopedn a zptn pechody. Pechod vyhledvacho stroje je relace ` (Q T ) (Q T ) de novan takto:
a) je-li g(q a) = p, pak (q aw) ` (p w) je dopedn pechod pro vechna w 2 T , b) je-li h(q) = p, pak (q w) ` (p w) je zptn pechod pro vechna w 2 T . Pi dopedn m pechodu (q aw) ` (p w) pro g(q a) = p je peten jeden vstupn symbol a stroj pechz do nsledujcho stavu p. Je-li g(q a) = fail, provede se zptn pechod s pouitm zptn pechodov funkce h. Pro g(q a) = fail a h(q) = p, pak (q w) ` (p w). Pi tomto pechodu se nete dn vstupn symbol. Funkce g a h maj tyto vlastnosti: 1. g(q0 a) 6= fail pro vechna a v T . 2. Jestlie h(q) = p, pak hloubka p je men ne hloubka q, kde hloubkou stavu q je mnna d lka nejkrat dopedn posloupnosti pechod ze stavu q0 do stavu q. Prvn podmnka zajiuje, e se neprovd dn zptn pechod v potenm stavu. Druh podmnka zajiuje, e celkov poet zptn ch pechod pi zpracovn vstupnho etzce bude men ne celkov poet dopedn ch pechod . Protoe pro kad vstupn symbol se provd jeden dopedn pechod, bude celkov poet pechod men ne dvojnsobek d lky textu. Vyhledvn m tedy sloitost O(T ).
4.2.1.2 Knuth-Morris-Prattv algoritmus Knuth, Morris a Pratt navrhli vyhledvac algoritmus, kter m asymptotickou asovou sloitost O(T + V ). Tento algoritmus konstruuje nejdve pro zadan vzorek zptnou pechodovou funkci h, co znamen pedzpracovn vzorku, a potom pouije nsledujc postup pro vyhledn vzorku v textu: var TEXT:array1..T] of char VZOREK:array1..V] of char I,J : integer NALEZEN : boolean ...
I:=1 J:=1 while (I <= T) and (J <= V) do begin while (TEXTI] <> VZOREKJ]) and (J > 0) do J:=hJ] J := J + 1 I := I + 1 end NALEZEN := J > V ...
Vyhledvac algoritmus porovnv postupn znaky vzorku se znaky textu. Jeho zkladn mylenka je zaloena na pozorovn, e v okamiku, kdy je porovnna pedpona vzorku 14
v1 v2 : : : vj;1 s podetzcem textu ti;j +1ti;j +2 : : : ti;1 a vj <> ti, nen teba znovu porovnvat znaky ti;j +1 ti;j +2 : : : ti;1 , protoe je znmo, jak st porovnvan ho textu je rovna pedpon vzorku. Msto toho se ve vnitnm cyklu posouv vzorek o j ; h(j ) pozic doprava a do j se ukld h(j ) tak dlouho, dokud j nen nula (v tomto ppad pedpona vzorku nen v prohledvan m textu obsaena) nebo ti = vj (v tomto ppad v1 v2 : : : vj ;1 vj souhlas s podetzcem textu ti;j +1ti;j +2 : : : ti;1 ti ). Aby mohl uveden algoritmus sprvn pracovat, mus h(j ) mt hodnotu rovnou nejvtmu k < j takovou, e v1 v2 : : : vk;1 je pponou v1 v2 : : : vj;1 (tj. v1 v2 : : : vk;1 = vj ;k+1 vj ;k+2 : : : vj ;1 ) a vj <> vk . Jestlie takov k neexistuje, pak h(j ) = 0. Hodnoty funkce h pot nsledujc algoritmus, kter se npadn podob v e uveden mu vyhledvacmu algoritmu.
I := 1 J := 0 h1] := 0 while I < V do begin while (J>0) and (VZOREKI]<>VZOREKJ]) do J := hJ] I := I+1 J := J+1 if VZOREKI]=VZOREKJ] then hI] := J else hI] := hJ] end
Funkce h je zptn pechodov funkce vyhledvacho stroje pro Knuth-Morris-Pratt v algoritmus (KMP vyhledvacho stroje). KMP vyhledvac stroj zkonstruujeme pomoc tohoto postupu:
Algoritmus 4.1:
Konstrukce KMP vyhledvacho stroje. Vstup: Vzorek v1 v2 : : : vV . V stup: KMP vyhledvac stroj. Metoda: 1. Poten stav bude q0 . 2. Kad stav q vyhledvacho stroje odpovd pedpon v1 v2 : : : vj zadan ho vzorku. De nujme g(q vj +1 ) = q0 , kde q0 odpovd pedpon v1 v2 : : : vj vj +1 . 3. Pro stav q0 de nujme g(q0 a) = q0 pro vechna a, pro kter g(q0 a) nebylo de novno v kroku 2. 4. g(q a) = fail pro vechna q a a, pro kter g(q a) nebylo de novno v kroku 2 nebo 3. 5. Stav, kter odpovd pln mu vzorku, je koncov stav. 6. Funkce h je zptn pechodov funkce.
Pklad 4.1:
Konstrukci KMP vyhledvacho stroje provedeme pro vzorek ababa nad abecedou T = fa bg. Dopedn pechodov funkce g a zptn pechodov funkce h maj hodnoty podle nsledujc tabulky:
g
0 1 2 3 4 5
a
1 fail 3 fail 5
b
0 2 fail 4 fail 15
h
nede novno 0 0 1 2
Pechodov diagram KMP vyhledvacho stroje je na obr. 4.1. Dopedn pechody jsou oznaeny symboly, pro kter se provd, zptn pechody oznaeny nejsou.
Obr. 4.1: KMP vyhledvac stroj pro vzorek ababa Pouijme KMP vyhledvac stroj pro vzorek ababa na vyhledvn v textu abaababab: (0,abaababab)
` ` ` ` ` ` ` ` ` `
(1, baababab) (2, aababab) (3, ababab) (1, ababab) (0, ababab) (1, babab) (2, abab) (3, bab) (4, ab) (5, b)
fail fail
vzorek nalezen
Postup zde uveden je specilnm ppadem dle uveden ho AC vyhledvacho stroje.
4.2.1.3 Algoritmus Aho-Corasickov Algoritmus Aho-Corasickov vede na AC vyhledvac stroj, kter je schopen vyhledvat souasn konenou mnoinu vzork . Je zadna mnoina vzork p = fv1 v2 : : : vk g. Na zklad t to mnoiny je sestrojen AC vyhledvac stroj a pak vyhledvn probh podle nsledujcho algoritmu: var TEXT:array1..T] of char I : integer NALEZEN : boolean STATE: TSTATE g: array1..MAXSTATE,1..MAXSYMBOL] of TSTATE h: array1..MAXSTATE] of TSTATE F: set of TSTATE ... begin NALEZEN:=false STATE:=q0 I:=0 while (I<=T) and not NALEZEN do begin I:=I+1 while gSTATE,TEXTI]]=fail do STATE:=hSTATE]
16
STATE:=gSTATE,TEXTI]] NALEZEN:=STATE in F end end
Vyhledvac stroj postupn prochz text a v ppad, e g-STATE TEXT -I ]] m hodnotu fail, provd zptn pechody tak dlouho, dokud g m hodnotu fail. Potom provede dopedn pechod. Stroj kon vyhledvn v okamiku, kdy dojde do nkter ho koncov ho stavu. Nyn uveme postup konstrukce funkc g a h. Dopedn pechodov funkce bude konstruovna pomoc Algoritmu 4.2:
Algoritmus 4.2:
Konstrukce dopedn pechodov funkce AC vyhledvacho stroje. Vstup: Mnoina vzork p = fv1 v2 : : : vk g. V stup: Dopedn pechodov funkce g AC vyhledvacho stroje. Metoda: 1. Poten stav bude q0 . 2. Kad stav q vyhledvacho stroje odpovd pedpon b1 b2 bj njak ho vzorku vi v mnoin p. De nujme g(q bj +1 ) = q0 , kde q0 odpovd pedpon b1 b2 bj bj +1 vzorku vi . 3. Pro stav q0 de nujme g(q0 a) = q0 pro vechna a pro kter g(q0 a) nebylo de novno v kroku 2. 4. g(q a) = fail pro vechna q a a, pro kter g(q a) nebylo de novno v kroku 2 nebo 3. 5. Kad stav odpovdajc pln mu vzorku bude koncov stav. Dve ne budeme konstruovat zptnou pechodovou funkci h, de nujeme chybovou funkci f takto: 1. Pro vechny stavy q hloubky 1 bude f (q) = q0 . 2. Pedpokldejme , e funkce f byla de novna pro vechny stavy hloubky d a men. Nech qd je stav hloubky d a g(qd a) = q0 , pak f (q0 ) vypotme takto: q:=fqd] while gq,a]=fail do q:=fq] fq']:=gq,a]
Protoe g(q0 a) 6= fail, cyklus vdy skon. Na obrzku 4.2 je sch maticky znzornn v poet funkce f (q0 ). Jednotliv hrany jsou ohodnoceny symboly, pro kter se provdj dopedn pechody. Chybov funkce f m tuto vlastnost: Jestlie stavy q a r reprezentuj pedpony u a v njak ch vzork z p, pak f (q) = r prv tehdy, jestlie v je nejdel vlastn pedpona u. Chybov funkce m e b t pmo pouita jako zptn pechodov funkce, avak m e zp sobovat zbyten zptn pechody. Efektivnj zptn pechodov funkce h vyluujc tyto zbyten zptn pechody m e b t zkonstruovna pomoc Algoritmu 4.3:
Algoritmus 4.3:
Konstrukce zptn pechodov funkce AC vyhledvacho stroje. Vstup: Dopedn pechodov funkce g AC vyhledvacho stroje. V stup: Zptn pechodov funkce h AC vyhledvacho stroje. Metoda: 17
Obr. 4.2: V poet f (q0 ) 1. h(q) = q0 pro vechny stavy hloubky jedna. 2. Pedpokldejme, e funkce h byla de novna pro vechny stavy hloubky d a men. Nech q je stav hloubky d +1. Jestlie mnoina znak , pro kter je ve stavu f (q) hodnota funkce g jin hodnota ne fail, je podmnoinou mnoiny znak , pro kter je hodnota funkce g ve stavu q jin ne fail, pak h(q) := h(f (q)), jinak h(q) := f (q). Na obr. 4.3 je schematicky znzornn v poet funkce h(q).
Obr. 4.3: V poet h(q)
Pklad 4.2:
Je zadna mnoina vzork p = fhe she herg nad abecedou T = fh e r s xg. Symbol x zastupuje vechny znaky krom h e r s. Sestrojme AC vyhledvac stroj. Funkce g, f a h jsou uvedeny v nsledujc tabulce.
q0 h1 e1 r s
h2 e2
g f h e r s x h1 q0 q0 s q0 { e1 q0 r q0 q0 h2 q0 e2 h1 e1 18
h {
q0 q0 q0 q0 q0 e1
'$ '$ '$ &% &% &% e
h1
'$ &%
h
>
A K A A
? START- qo
Q
x,r,e
Q Q Q
s
-
r
e1
-
r
A K A A
A A A A A A
A A
A A A A
'$ '$ '$ &% &% &%
Q Q Q s Q
s
h
A A A A A -
A A
A
h2
e
A A
-
e2
Obr. 4.4: AC vyhledvac stroj pro p = fhe she herg
Na obr. 4.4 je uveden pechodov diagram AC vyhledvacho stroje. Ohodnocen hrany pat dopedn pechodov funkci g. Neohodnocen hrany pat chybov funkci f . Funkce h se li od funkce f jen ve stavu h2 . Ve stavu h2 je mon dopedn pechod jen pro symbol e stejn jako ve stavu h1 . To znamen, e po zptn m pechodu ze stavu h2 do stavu h1 , kter se provede jen pro jin symboly ne e, je nutno vdy prov st dal zptn pechod do stavu q0 . Je proto mon ve stavu h2 prov st zptn pechod pmo do stavu q0 .
4.2.1.4 Vyhledvac konen automaty V tomto odstavci uvedeme pojmy deterministick a nedeterministick konen automat a ukeme jejich pouit pi vyhledvn. Deterministick konen automat M je ptice M = (K T q0 F ), kde K je konen mnoina vnitnch stav , T je konen vstupn abeceda, je zobrazen z K T do K, q0 2 K je poten stav, F K je mnoina koncov ch stav . Deterministick konen automat pracuje tak, e provd posloupnost pechod . Pechod je uren stavem, ve kter m se automat nachz, a symbolem, kter je ten ze vstupnho etzce. Pi pechodu pejde automat do nov ho stavu a pete jeden vstupn symbol. ten vstupnch symbol se provd zleva doprava ponaje nejlevjm symbolem vstupnho etzce. Pokud je zobrazen de novno pro kadou dvojici (q a) z K T , kme, e automat je pln uren . V opan m ppad se jedn o nepln uren automat. Abychom mohli urit budouc chovn deterministick ho konen ho automatu, potebujeme znt: a) stav, ve kter m se automat prv nachz, 19
b) zbylou st vstupnho etzce, kterou dosud automat nepeetl. Tuto dvojici (q w) 2 K T nazveme kongurac konen ho automatu M . Kon guraci (q0 w) nazveme poten kon gurac konen ho automatu M , kon guraci (q "), kde q 2 F , nazveme koncovou kon gurac konen ho automatu. Relaci ` (K T ) (K T ) nazveme p echodem automatu M . Jestlie (q a) = p, pak (q aw) ` (p w) pro vechna w 2 T . Symbolem ` k ozname k-tou mocninu relace `. Symboly ` + a ` budou oznaovat tranzitivn a tranzitivn re0exivn uzvr relace `. $etzec w je pijat konen m deterministick m automatem M = (K T q0 F ), jestlie (q0 w) ` (q ") pro njak q 2 F . L(M ) = fw : w 2 T (q0 w) ` (q ") pro njak q 2 F g je jazyk pijman konen m automatem M . $etz w 2 L(M ), jestlie se skld pouze ze symbol
vstupn abecedy a existuje posloupnost pechod takov, kter z poten kon gurace (q0 w) vede do koncov kon gurace (q "). Dle uvedeme vyhledvac algoritmus zaloen na principu konen ho automatu, kter pouv tabulku pechod g, kter odpovd zobrazen . var TEXT:array1..T] of char STATE: TSTATE g:array1..MAXSTATE,1..MAXSYMB] of TSTATE I: integer NALEZEN : boolean F: set of TSTATE ... begin NALEZEN:=FALSE STATE:=q0 I:=0 while (I<=T) and not NALEZEN do begin I:=I+1 STATE:=gSTATE,TEXTI]] NALEZEN:=STATE in F end end ...
Pi konstrukci vyhledvacho konen ho automatu je v hodn sestrojit nejdve nedeterministick konen automat a ten transformovat na deterministick . Nedeterministick konen automat M je ptice M = (K T q0 F ), kde K je konen mnoina vnitnch stav , T je konen vstupn abeceda, je zobrazen z K T do mnoiny podmnoin K , q0 2 K je poten stav, F K je mnoina koncov ch stav . Z porovnn de nic plyne, e podstatn rodl nedeterministick ho konen ho automatu oproti deterministick mu konen mu automatu spov v tom, e (q a) je u nedeterministick ho automatu mnoina stav , zatmco (q a) je u deterministick ho automatu jeden stav. Pojmy kon gurace, poten a koncov kon gurace podle de nice m eme pout i pro nedeterministick konen automat. De nici pechodu musme rozit. 20
Relaci ` (K T ) (K T ) nazveme pechodem v automatu M. Jestlie p 2 (q a), pak (q aw) ` (p w) pro vechna w 2 T . $etzec w je pijat konen m nedeterministick m automatem M = (K T q0 F ), jestlie existuje posloupnost pechod (q0 w) ` (q ") pro njak q 2 F . Potom L(M ) = fw : w 2 T (q0 w) ` (q ") pro njak q 2 F g je jazyk pijman nedeterministick m konen m automatem M . Pro kad nedeterministick konen automat M m eme sestrojit deterministick konen automat M 0 , pro kter plat, e L(M ) = L(M 0 ). Pevod nedeterministick ho konen ho automatu na ekvivalentn deterministick provedeme takto:
Algoritmus 4.4:
Vstup: Nedeterministick konen automat M = (K T q0 F ) V stup: Deterministick konen automat M 0 = (K 0 T 0 q00 F 0 ), pro kter plat, e L(M ) = L(M 0 ). Metoda: 1. De nujeme K 0 = ffq0 gg, stav fq0 g budeme povaovat za neoznaen . 2. Jestlie v K 0 jsou vechny stavy oznaeny, pokrauj krokem (4). 3. Vybereme z K 0 neoznaen stav q0 a provedeme tyto operace: S (a) Urme 0 (q0 a) = (p a) pro vechna p 2 q0 a pro vechna a 2 T , (b) K 0 = K 0 0 (q0 a) pro vechna a 2 T , (c) stav q0 2 K 0 ozname, (d) pokraujeme krokem (2) 4. q0 = q00 . 5. F 0 = fq0 : q0 2 K 0 q0 \ F 6= g.
Poznmka: Z d vodu pehlednosti a itelnosti budeme pro oznaen stav v K 0 pouvat hranat ch msto sloen ch zvorek.
Nyn uvedeme postup konstrukce pechodov tabulky g pro zadanou mnoinu vzork p = Nejdve sestrojme pechodovou tabulku g0 pro nedeterministick konen 0 automat M , kter pijm vechny etzce s pponami z mnoiny p takto: 1. Poten stav bude q0 a g0 (q0 a) = q0 pro vechna a ze vstupn abecedy automatu. 2. Kad stav q automatu odpovd pedpon b1 b2 : : : bj njak ho vzorku vi v mnoin p. De nujeme g0 (q bj +1 ) = q0 , kde q0 odpovd pedpon b1 b2 : : : bj bj +1 vzorku vi . 3. Kad stav, kter odpovd pln mu vzorku bude koncov stav. Dle sestrojme deterministick automat M s pechodovou tabulkou g. fv1 v2 : : : vk g.
Pklad 4.3:
Cel postup nvrhu automatu ukeme na pklad. Mjme zadnu lohu takto: Naleznte, zda v dan m etzci nad abecedou T = fh e r s xg se vyskytuj podetzce z mnoiny p = fhe she her g. Symbol x zastupuje vechna psmena krom h e r s. Cel probl m budeme eit takto: 1. Sestrojme nedeterministick konen automat M 0 , kter pijm vechny etzce nad abecedou fh e r s xg s pponami z mnoiny p. Pechodov diagram automatu M 0 je na obr. 4.5. Poten stav je stav q0 , koncov stavy jsou stavy e2 e5 e7 a r8 a znamenaj situace, kdy byly peteny ppony he, he nebo she, he a her. 2. Zskan nedeterministick konen automat M 0 pevedeme na deterministick . Pechodov tabulka nedeterministick ho automatu m tvar: 21
h,e,r,s,x START- ? q0 h h1 e- e2 A@ s A@ R A h@ h- h4 e- e5 A s3 A A U A
h6 e- e7 r- r8
Obr. 4.5: Nedeterministick automat M 0 pro vyhledvn mnoiny vzork p = fhe she herg
g0
h
e
s
r
x
q0 q0,h1,h6 q0 q0,s3 q0 q0 h1 e2 e2 s3 h4 h4 e5 e5 h6 e7 e7 r8 r8 Po pevodu automatu M 0 na deterministick automat zskme automat M , jeho pechodov tabulka m tvar:
g
-q0] -q0,h1,h6] -q0,s3] -q0,e2,e7] -q0,h1,h4,h6] -q0,r8] -q0,e2,e5,e7]
h
-q0,h1,h6] -q0,h1,h6] -q0,h1,h4,h6] -q0,h1,h6] -q0,h1,h6] -q0,h1,h6] -q0,h1,h6]
e
-q0] -q0,e2,e7] -q0] -q0] -q0,e2,e5,e7] -q0] -q0]
s
-q0,s3] -q0,s3] -q0,s3] -q0,s3] -q0,s3] -q0,s3] -q0,s3]
r
-q0] -q0] -q0] -q0,r8] -q0] -q0] -q0,r8]
x
-q0] -q0] -q0] -q0] -q0] -q0] -q0]
3. Zskan deterministick automat M 0 implementujeme jako program. Vzhledem k tomu, e automat M 0 je pln uren , co znamen, e zobrazen g0 je de novno vdy, je vhodn jej implementovat tak, e tabulku pechod budeme reprezentovat jako celoselnou matici, kterou pouv univerzln algoritmus. Ptomnost hledan ch etzc se zjist tak, e pi pechodu do koncov ho stavu m eme identi kovat konec jist ho vzorku podle t to tabulky: hledan vzorek he she her
koncov stavy -q0,e2,e7],-q0,e2,e5,e7] -q0,e2,e5,e7] -q0,r8]
22
4.2.1.5 Vyhledvn nekonen mnoiny vzork Vhodn m prostedkem pro popis nekonen mnoiny vzork je regulrn v raz.
De nice:
Regulrn v raz V nad abecedou A je de novn takto: 1. " a jsou regulrn v razy pro vechna a 2 A. 2. Jsou-li x y regulrn v razy nad A, pak: a) (x + y) (sjednocen) b) (x : y) (zetzen) c) (x) (iterace) jsou regulrn v razy nad A. Hodnota h(x) regulrnho v razu x je de novna takto: 1. h( ) = h(") = f"g h(a) = fag, 2. h(x + y) = h(x) h(y), h(x : y) = h(x) : h(y), h(x ) = (h(x)) . Hodnotu h(x ) m eme vyjdit tak takto: h(x ) = " + x + x:x + x:x:x + : : :, co znamen, e h(x ) obsahuje przdn etz a dle vechny etzy, kter vzniknou zetzenm libovoln ho potu etz x. Hodnotou libovoln ho regulrnho v razu je regulrn jazyk. Naopak kad regulrn jazyk lze reprezentovat njak m regulrnm v razem. Pro zpis regulrnch v raz se obvykle zavd konvence o priorit regulrnch operac a pak je mono vynechvat pebyten zvorky. Nejvy prioritu m operace iterace, nejni pak operace sjednocen. Pro regulrn v razy jsou de novny tyto axiomy (Salomaa 1966): A1: x + (y + z ) = (x + y) + z (asociativnost sjednocen) A2: x:(y:z ) = (x:y):z (asociativnost zetzen) A3: x + y = y + x (komutativnost sjednocen) A4: (x + y):z = x:z + y:z (distributivnost zprava) A5: x:(y + z ) = x:y + x:z (distributivnost zleva) A6: x + x = x (idenpotence sjednocen) A7: " : x = x (" je jednotkov prvek pro zetzen) ( je nulov prvek pro zetzen) A8: : x = A9: x + = x ( je nulov prvek pro sjednocen) A10: x = " + x x A11: x = (" + x) Je dokzno, e vechny ostatn rovnosti mezi regulrnmi v razy lze odvodit z tchto axiom . Pro kad regulrn v raz V je mono sestrojit konen automat M takov , e h(V ) = L(M ). Nejdve uvedeme klasick zp sob konstrukce zobecnn ho nedeterministick ho konen ho automatu pro dan regulrn v raz. Zobecnn konen automat dovoluje "-pechody, tj. pechody bez ten vstupnho symbolu. Nsledujc rekurzivn procedura sestroj pro dan regulrn v raz V automat M . 23
1. Jestlie v raz V je tvoen jedin m symbolem a, sestrojme automat majc dva stavy a pechod z potenho do koncov ho stavu pro symbol a. a 2. Jestlie v raz V = V1 + V2 , M1 a M2 jsou automaty pro v razy V1 a V2 , pak sestrojme pro v raz V automat:
* "
M1
HH
H " HH
HH H
HH" HH H j H
"
H j H
M2
*
Vytvoili jsme nov poten a nov koncov stav. Z potenho stavu vedou "-pechody do potench stav automat M1 a M2 . Dle jsou zde "-pechody z koncov ch stav
automat M1 a M2 do nov vytvoen ho koncov ho stavu. 3. Jestlie v raz V = V1 V2 , M1 a M2 jsou automaty pro v razy V1 a V2 , pak sestrojme pro v raz V automat M tak, e ztotonme koncov stav automatu M1 s potenm stavem automatu M2 . Poten stav automatu M1 , je potenm stavem automatu M a koncov stav automatu M2 je koncov m stavem automatu M .
' $ & %
4. Jestlie v raz V = V1 a M1 je automat pro v raz V1 , pak sestrojme automat:
"
"
-
/
M1
"-
*
"
Vytvoili jsme nov poten a nov koncov stav. V automatu M jsou tyi nov "-pechody:
-
z vytvoen ho potenho stavu do potenho stavu automatu M1 , z vytvoen ho potenho stavu do vytvoen ho koncov ho stavu, z koncov ho stavu automatu M1 do jeho potenho stavu, z koncov ho stavu automatu M1 do nov vytvoen ho koncov ho stavu.
Takto vytvoen nedeterministick konen automat m tyto zajmav a uiten vlastnosti:
a) poet stav automatu M je nejv e roven dvojnsobku d lky v razu V , b) ze dn ho stavu nevychz vce jak dv hrany do dalch stav , c) z koncov ho stavu nevychz dn hrana. D lka d regulrnho v razu V je de novna takto: 24
Obr. 4.6: Odstrann "-pechod
d(V ) = 1, jestlie V je tvoen jedin m symbolem, d(V1 + V2) = d(V1 ) + d(V2 ) + 1, d(V1 V2 ) = d(V1 ) + d(V2 ) + 1, d(V ) = d(V ) + 1, d((V )) = d(V ) + 2. Tyto vlastnosti umouj efektivn simulovat chovn automatu. Nech d je d lka v razu V a T d lka textu. Pi simulaci se pouv mnoina stav automatu M , do kter automat m e pejt po peten etzce a1 a2 : : : ai;1 . Z t to mnoiny m eme urit v ase O(d) mnoinu stav , do kter ch se automat m e dostat po peten symbolu ai , protoe z kad ho stavu jsou mon nejv e dva pechody. Tmto zp sobem je mono simulovat chovn automatu M v ase O (dT ) a v pamti O (d). Proto se nyn budeme zab vat metodami implementace nedeterministick ch konen ch automat . Uvedeme dv metody. Prvn metoda je zaloena na pouit tabulky pechod . Druh metoda se opr o implementaci automatu ve form programu. V obou ppadech jsou stavy automatu reprezentovny stavov m vektorem. Kad mu stavu nedeterministick ho konen ho automatu odpovd jeden prvek tohoto vektoru. Jestlie se automat nachz v urit m stavu, bude mt odpovdajc prvek stavov ho vektoru hodnotu true, jinak bude mt hodnotu false. Nedeterministick konen automat budeme implementovat tak, e souasn budeme prochzet vemi mon mi cestami. To znamen, e ve stavov m vektoru m e mt vce prvk hodnotu true, co odpovd tomu, e automat se m e nachzet ve vce stavech. Pro nsledujc metody simulace nedeterministick ch konen ch automat je teba odstranit "-pechody. Tuto transformaci je mono prov st tmto postupem: 1. Jestlie "-pechod q0 2 (q ") vede do stavu, ze kter ho existuj dal pechody, pak tento "-pechod nahradme nov mi pechody tak, aby (q a) = (q0 a) pro vechna a 2 T . Tato transformace je znzornna na obr. 4.6. 2. Jestlie "-pechod vede ze stavu q do koncov ho stavu qf , do kter ho dn dal pechod nevede, vynechme jej a q bude dal koncov stav. Nejdve uvedeme program simulujc nedeterministick konen automat tak, e stav je reprezentovn Booleovsk m vektorem. 25
program type
var
NKA(INPUT,OUTPUT) TYPSTAV = (Q0,Q1,...,QN) TYPSYMBOL = 1 .. |T|
SYMBOL:TYPSYMBOL STAV,NSTAV: array QO..QN] of BOOLEAN TABULKAPECHOD: array Q0..QN,TYPSYMBOL] of set of TYPSTAV PIJAT, DEFINOVN: BOOLEAN PECHODY, F : set of TYPSTAV I,J: TYPSTAV
procedure DALSYMBOL(var X:TYPSYMBOL) external procedure TENTABULKYPECHOD external begin TENTABULKYPECHOD F := QF1,QF2,...,QFK] STAVQ0] := TRUE for I := Q1 to QN do STAVI] := FALSE DEFINOVN :=TRUE while not EOF(INPUT) and DEFINOVN do begin DALSYMBOL(SYMBOL) for I := Q0 to QN do NSTAVI] := FALSE for I := Q0 to QN do if STAVI] then begin PECHODY := TABULKAPECHODI,SYMBOL] for J := Q0 to QN do if J in PECHODY then NSTAVJ] := TRUE end DEFINOVN := FALSE for I := Q0 to QN do DEFINOVN := DEFINOVN or NSTAVI] STAV := NSTAV end PIJAT := FALSE for I := Q0 to QN do PIJAT := PIJAT or (I in F) if PIJAT then WRITE(OUTPUT,'VSTUP PIJAT') else WRITE(OUTPUT,'VSTUP NEPIJAT') end.
V uveden m programu jsou pouity dva stavov vektory STAV a NSTAV. D vodem k tomu je skutenost, e pi v potu nov hodnoty stavov ho vektoru je po celou dobu nutno uchovat hodnotu star ho stavov ho vektoru. innost automatu m e skonit ze dvou d vod . Ukonen vstupnho etzu je d vod k normlnmu ukonen prce automatu. Ukonen pi nede novan m stavu znamen, e automat neumouje pechod do dn ho stavu, t.j. stavov vektor m vechny hodnoty false. Uveden program pedstavuje univerzln implementaci pro libovoln konen automat. Druh metoda implementace nedeterministick ho konen ho automatu, pi kter je automat implementovn jako program bez pouit tabulky pechod vede samozejm na r zn programy pro r zn automaty. Proto uvedeme implementaci nsledujcho automatu: 26
NKA= (f1 2 3 4 5g fa bg 1 f1g), kde zobrazen je de novno tabulkou:
1 2 3 4 5
a
f2g f3g f4g f5g f1g
b
f1,2g f1,3g f1,4g f1,5g
program NKA(INPUT,OUTPUT) type TYPSTAV = (JEDNA,DV,TI,TYI,PT) TYPSYMBOL = (A,B) var
SYMBOL: TYPSYMBOL STAV, NSTAV: array TYPSTAV of BOOLEAN I: TYPSTAV DEFINOVN: BOOLEAN
procedure DALSYMBOL(var X: TYPSYMBOL) external begin STAVJEDNA] := TRUE for I := DV to PT do STAVI] := FALSE DEFINOVN := TRUE while not EOF(INPUT) and DEFINOVN do begin DALSYMBOL(SYMBOL) for I := JEDNA to PT do NSTAV := FALSE if STAVJEDNA] then case SYMBOL of A : NSTAVDV] := TRUE B : end if STAVDV] then case SYMBOL of A : NSTAVTI] := TRUE B : begin NSTAVJEDNA] := TRUE NSTAVDV] := TRUE end end if STAVTI] then case SYMBOL of A : NSTAVTYI] := TRUE B : begin NSTAVJEDNA] := TRUE NSTAVTI] := TRUE end end
27
(*)
(*)
if STAVTYI] then case SYMBOL of A : NSTAVPT] := TRUE B : begin NSTAVJEDNA] := TRUE NSTAVTYI] := TRUE end end if STAVPT] then case SYMBOL of A : NSTAVJEDNA] := TRUE B : begin NSTAVJEDNA] := TRUE NSTAVPT] := TRUE end end
(*)
(*)
DEFINOVN := NSTAVJEDNA] or NSTAVDV] or NSTAVTI] or NSTAVTYI] or NSTAVPT] STAV := NSTAV end if STAVJEDNA] then WRITE (OUTPUT,'ETZ PIJAT') else WRITE (OUTPUT,'ETZ NEPIJAT') end.
Poznmka: Pkazy na dcch oznaen ch () je mono vynechat. Jin klasick zp sob vyhledvn vzorku generovan ho regulrnm v razem je pouit deterministick ho konen ho automatu. Pro regulrn v raz je mono sestrojit deterministick konen automat nkolika zp soby. Jeden z nich je sestrojen deterministick ho automatu ekvivalentnho nedeterministick mu, jeho konstrukce byla popsna v e. Jednodu a pm cesta spov v pm m sestrojen deterministick ho konen ho automatu. Uveme dva zp soby. Nejdve uvedeme postup, kter je zaloen na pojmu sousednch symbol .
Algoritmus 4.5:
Konstrukce ekvivalentnho konen ho automatu pro dan regulrn v raz. Vstup: Regulrn v raz V . V stup: Konen automat M = (K T q0 F ) takov , e h(V ) = L(M ). Metoda: Nech abeceda, nad kterou je de novn v raz V je T . 1. Oslujeme sly 1,2,: : : ,n vechny v skyty symbol z T ve v razu V tak, aby kad dva v skyty t ho symbolu byly oslovny r zn mi sly. Vznikl regulrn v raz ozname V 0. 2. Sestrojme mnoinu zatench symbol
Z = fxi : x 2 T , symbolem xi m e zanat njak etzec z h(V 0 )g. 3. Sestrojme mnoinu soused P takto: P = fxi yj : symboly xi a yj mohou b t vedle sebe v njak m etzci z h(V 0 )g. 28
4. Sestrojme mnoinu koncov ch symbol F takto: F = fxi: symbolem xi m e konit njak slovo z h(V )g. 5. Mnoina stav konen ho automatu K = fq0 g fxi : x 2 T i 2 h1 nig. 6. Zobrazen sestrojme takto: a) (q0 x) obsahuje xi pro vechna xi 2 Z vznikl oslovnm x. b) (xi y) obsahuje yj pro vechny dvojice xi yj 2 P takov , e yj vzniklo oslovnm y. 7. Mnoina F je mnoinou koncov ch stav .
Pklad 4.4:
Sestrojme konen automat pro v raz V = ab a + ac + b ab . T = fa b cg Po oslovn symbol m v raz V tvar: V = a1 b2 a3 + a4 c5 + b6 a7 b8 Mnoina zatench symbol : Z = fa1 a4 b6 a7g Mnoina soused : P = fa1 b2 a1 a3 b2 b2 b2 a3 a4 c5 b6 b6 b6 a7 a7 b8 b8 b8 g Mnoina koncov ch symbol : F = fa3 c5 a7 b8 g Konen automat M = (fq0 a1 b2 a3 a4 c5 b6 a7 b8 g fa b cg q0 fa3 c5 a7 b8 g) a zobrazen je znzornno pechodov m diagramem na obr. 4.7. Z uveden ho pkladu je vidt, e v sledn automat m e b t nedeterministick .
b
a
START- q0 b
b
a1 a
-
a4
-
b2 a
c
H S HH b SSw HaHH H j H b6 a - a7
a
?
-
b
- a3 *
c5
-
b
?
b8
Obr. 4.7: Pechodov diagram konen ho automatu z pkladu 4.4 Dal postup, kter umouje vdy sestrojen deterministick ho konen ho automatu pro zadan regulrn v raz, je zaloen na pojmu derivace regulrnch v raz . Pro regulrn v razy je de novn pojem derivace regulrnho v razu takto: Derivace dV dx regulrnho v razu V podle etzce x 2 T je de novna takto: 1. dV d" = V . 29
2. Pro a 2 T plat:
d" = d = da da ( db = jestlie a 6= b " jestlie a = b da d(U + V ) = dU + dV da da da d(U:V ) = dU :V + f dV : " 2 h(U )g da da da d(V ) = dV :V da da 3. Pro x = a1 a2 : : : an ai 2 T plat dV = dV ( dV (: : : dV ( dV ) : : :)) dx dan dan;1 da2 da1
Pklad 4.5:
Je dn regulrn v raz y = (0 + 1) :1 . Urme nkolik derivac v razu y.
dy = (0 + 1) :1 d" dy = d(0 + 1) :1 + d1 = d(0 + 1) :(0 + 1) :1 + " d1 d1 d1 d1 = ( dd01 + dd11 )(0 + 1) :1 + " = ( + "):(0 + 1) :1 + " dy = d(0 + 1) :1 + d1 = d(0 + 1) :(0 + 1) :1 + = (" + ):(0 + 1) :1 + : d0 d0 d0 d0 Z pravidel pro derivaci regulrnho v razu V podle etzce x se d lehce odvodit, e plat: dV = fy : xy 2 h(V )g: dx To znamen, e m eme ci, e derivac v razu V podle x je v raz U takov , e h(U ) obsahuje etzce, kter vzniknou odtrenm pedpony x v etzcch z h(V ).
Dle uvedeme zp sob konstrukce konen ho automatu pro zadan regulrn v raz. Tato metoda je zaloena na tom, e regulrn v raz m konen poet derivac, kter nejsou podobn . Regulrn v razy x y jsou podobn , kdy jeden z nich m e b t transformovn na druh pomoc tchto rovnost:
x+x=x x+y =y+x (x + y) + z = x + (y + z ) x+ =x x: = :x = x:" = ":x = x 30
Algoritmus 4.6:
Konstrukce ekvivalentnho konen ho automatu pro dan regulrn v raz. Vstup: Regulrn v raz V nad abecedou T . V stup: Konen automat M = (K T q0 F ) takov , e h(V ) = L(M ). Metoda: 1. Polome Q = fV g Q0 = fV g i := 1. 2. Vytvome derivace vech v raz z Qi;1 podle vech symbol z abecedy T . Do mnoiny Qi vlome vechny v razy vznikl derivac v raz z Qi;1 , kter nejsou podobn v raz m z Q. 3. Jestlie Qi 6= , pidme Qi do Q, polome i := i + 1 a pejdeme na krok 2. V ppad, e Qi = , pak vytvome automat M = (Q T V F ), kde zobrazen je vytvoeno takto: dU dU dU ( dU dx a) = dx v ppad, e v raz dx je podobn v razu d(xa) . dU Mnoina F = f dU dx : " 2 h( dx )g . 0
0
Pklad 4.6:
Sestrojme pomoc Algoritmu 4.2 konen automat, kter pijm jazyk de novan regulrnm v razem (0 + 1) 1 . 1. Polome Q = f(0 + 1) 1g Q0 = f(0 + 1) 1g: 2. Vypoteme Q1 :
d ((0 + 1) 1) = ( + ")(0 + 1) 1 + " = (0 + 1) 1 + " d1 d ((0 + 1) 1) = (" + )(0 + 1) 1 + = (0 + 1) 1 d0 Protoe
d ((0 + 1) 1) = (0 + 1) 1 d0 bude
Q1 = f(0 + 1) 1 + "g a Q = f(0 + 1) 1 (0 + 1) 1 + "g 3. Vypoteme Q2 :
d ((0 + 1) 1 + ") = ( + ")(0 + 1) 1 + " + = (0 + 1) 1 + " d1 d ((0 + 1) 1 + ") = (" + )(0 + 1) 1 + = (0 + 1) 1: d0 Protoe oba v razy ji jsou v mnoin Q, je mnoina Q2 przdn. 4. V sledn automat bude mt dva stavy: stav x odpovdajc v razu (0 + 1) 1 a stav y odpovdajc v razu (0 + 1) 1 + ". Poten stav bude x, koncov stav bude y, protoe " 2 h((0 + 1) 1 + ") . 31
0
? START - x
H Y HH
1
1
HH j H
0
y
?
Obr. 4.8: Pechodov diagram konen ho automatu z pkladu 4.6 Protoe plat:
dx = y dx = x dy = y dy = x d1 d0 d1 d0
bude v sledn automat mt pechodov diagram podle obr. 4.8. Dle uvedeme konstrukci derivace regulrnho v razu pomoc pozinho vektoru. Pozin vektor je mnoina sel, kter odpovdaj pozicm takov ch symbol abecedy, kter se mohou vyskytnout na zatku zbytku etzu, kter je soust hodnoty dan ho regulrnho v razu. innost pi vytven nov ho pozinho vektoru m eme shrnout do tchto bod : 1. Ke kad syntaktick konstrukci se vytvo seznam potench pozic na zatcch len . 2. Je-li symbol v konstrukci roven symbolu podle kter ho se provd derivace a je-li na oznaen pozici, pak se oznaen posouv ped nsledujc pozici. 3. Je-li za konstrukc opertor iterace a oznaen je na konci konstrukce, pak se do v sledn ho seznamu pipoj tak seznam zatench pozic nleejc t to konstrukci. 4. Je-li oznaen ped njakou konstrukc, pak se do v sledn ho seznamu pipoj seznam potench pozic t to konstrukce. 5. Je-li oznaen ped konstrukc, kter generuje tak przdn etz, pak se do v sledn ho seznamu pipoj tak seznam potench pozic konstrukce nsledujc. 6. M-li se oznait konstrukce v zvorce, pak je teba oznait zatky vech len v zvorce.
Pklad 4.7:
Postup pi derivaci pomoc pozinho vektoru objasnme na jednoduch m pklad. Mjme regulrn v raz: (1) a . b . c K oznaen pozic budeme pouvat ipky. Na zatku bude tedy v raz (1) oznaen takto: a . b . c (2)
^
Derivac oznaen ho regulrnho v razu dostaneme nov oznaen regulrn v raz. Zkladn pravidlo pro derivaci je toto: 1. Je-li oznaen operand, podle kter ho se derivuje, pak se ozna msta nsledujc za tmto operandem. Jeho oznaen se ru. To znamen, e derivac v razu (2) podle operandu a dostaneme: a . b . c (3a)
^
2. Protoe je oznaena konstrukce, kter generuje tak przdn etzec, ozname tak konstrukci nsledujc: (3b) a . b . c
^ ^
Nyn derivac podle operandu b v razu (3b) dostaneme: a . b . c (4a)
^
32
3. Protoe je oznaena konstrukce nsledujc za konstrukc v iteraci mus se oznait i pedchoz konstrukce. a . b . c (4b)
^ ^
Derivac v razu (4b) podle operandu c dostaneme: a . b . c (5)
^
Takto oznaen regulrn v raz odpovd przdn mu regulrnmu v razu ". asov sloitost vyhledvn pomoc deterministick ho konen ho automatu je O(T ) a pomoc nedeterministick ho konen ho automatu je O(ST ), kde T je d lka textu a S je poet stav nedeterministick ho konen ho automatu. Pamov sloitost nedeterministick ho konen ho automatu je O(S ) a ekvivalentnho deterministick ho konen ho automatu je O(2S ). Pokud pro dan nedeterministick konen automat konstruujeme jemu ekvivalentn deterministick konen automat, pak asov sloitost t to konstrukce a vyhledvn je O(2S + T ) a pamov sloitost deterministick ho konen ho automatu je O(2S ). Linern pamov sloitost nedeterministick ho konen ho automatu a linern asov sloitost deterministick ho konen ho automatu nabz monost pouit hybridnho deterministicky-nedeterministick ho pstupu. V takov m ppad sestrojme nedeterministick konen automat pro dan regulrn v raz. Potom nejastji navtvovan stavy tohoto automatu pevedeme na deterministick . Tyto stavy implementujeme pomoc celoseln matice, co vede ke konstantn asov sloitosti proveden pechodu. Tento pstup zatm nebyl teoreticky prozkoumn a nen znma jeho pr mrn asov a pamov sloitost.
33
4.2.2 Vyhledvac metody s pedzpracovnm vzork s protismrnm vyhledvnm Do skupiny metod, kter vytv vyhledvac stroj provdjc protismrn vyhledvn pat: 1. Boyer-Moore v algoritmus pro vyhledvn jednoho vzorku, 2. algoritmus Commentz-Walterov pro vyhledvn konen mnoiny vzork , 3. konen automat sestrojen pro reverzovan regulrn v raz.
4.2.2.1 Boyer-Moorev algoritmus Boyer a Moore navrhli d mysln a zajmav algoritmus pro vyhledn vzorku v textu, kter peskakuje seky prohledvan ho textu, ve kter ch nem e b t vzorek obsaen. Pro abecedu s vt mohutnost m algoritmus pr mrnou asovou sloitost O(T=V ). Zkladn mylenka algoritmu spov v posouvn vzorku po textu a srovnvn znak vzorku a textu zprava doleva. Na zatku se srovnv znak VZOREKV] se znakem TEXTV]. Jestlie se znak TEXTV] nevyskytuje ve vzorku, pak je mono posunout vzorek o V znak doprava a srovnvat znak VZOREKV] se znakem TEXT2*V]. Jestlie se srovnvan znaky rovnaj, pokrauje se ve srovnvn znaku vzorku se znaky textu zprava doleva dokud nen cel vzorek srovnn nebo dojde k neshod. V ppad neshody je mono pout r zn postupy na uren, jak daleko posunout vzorek doprava. Vyhledvac Boyer-Moore v algoritmus m tvar: var TEXT:array1..T] of char VZOREK:array1..V] of char I,J : integer NALEZEN : boolean ... begin NALEZEN:=false I:=V while(I<=T) and not NALEZEN do begin J:=0 while (J
Tento algoritmus pouv funkci SHIFT , kter uruje, jak daleko posunout vzorek doprava, kdy VZOREKV-J] <> TEXTI-J]. Existuje cel ada zp sob , jak de novat funkci SHIFT. Uvedeme jeden z nich. Jestlie znak textu TEXTI-J] nen ve vzorku obsaen, pak se vzorek posouv o celou dosud nepouitou st vzorku, t.j. o V-J, doprava. V ppad, e k neshod dolo pro posledn znak vzorku, provede se posun o celou d lku vzorku, protoe v tom okamiku J=0. V ppad, e znak textu TEXTI-J] je ve vzorku obsaen v jeho dosud nepouit sti, t.j. na pozici J+K (potno odzadu), posune se vzorek o K pozic doprava tak, aby J+K -t prvek vzorku odpovdal znaku TEXTI-J]. M eme tedy napsat: 34
SHIFT(A,J)
= if A se nevyskytuje ve vzorku then V-J else nejmen K takov , e VZOREKV-(J+K)]=A = min{K:K=V, 0 K
Pklad 4.8:
Ukame hledn vzorku BANANA v textu I-WANT-TO-FLAVOR-NATURAL-BANANAS. V nsledujc tabulce jsou uvedeny hodnoty funkce SHIFT(ZNAK,J) pro vzorek BANANA. Symbol X zastupuje vechny znaky, kter se ve vzorku nevyskytuj. 0 1 2 3 4 5
A B 5 1 4 3 1 2 1 1
N X 1 6 5 1 4 3 2 2 1 1
Hodnoty funkce SHIFT pro vzorek BANANA. Na obr. 4.9 je znzornn Boyer-Moore v (BM) vyhledvac stroj. Hrany oznaen znaky v krouku ukazuj, jak se m vzorek posunout pro jednotliv ppady.
Obr. 4.9: BM vyhledvac stroj pro vzorek BANANA Vyhledvn probh takto (znaka oznauje srovnvan znak v textu): BANANA I-WANT-TO-FLAVOR-NATURAL-BANANAS ^
(1) T <> A a T se nevyskytuje ve vzorku, posun o d lku vzorku (V=6, SHIFT=6). 35
BANANA I-WANT-TO-FLAVOR-NATURAL-BANANAS ^
(2) L <> A a L se nevyskytuje ve vzorku, posun o d lku vzorku (SHIFT=6). BANANA I-WANT-TO-FLAVOR-NATURAL-BANANAS ^
(3) N <> A, ale N se vyskytuje ve vzorku, posun vzorku doprava je SHIFT=1, aby se srovnaly symboly N. BANANA I-WANT-TO-FLAVOR-NATURAL-BANANAS ^..
(4) Protoe { <> A, { se ve vzorku nevyskytuje, je mono posunout vzorek za {, tj. SHIFT=4. BANANA I-WANT-TO-FLAVOR-NATURAL-BANANAS ^.
(5) A = A, ale R <> N, SHIFT=5 vzhledem k tomu, e R se ve vzorku nevyskytuje. BANANA I-WANT-TO-FLAVOR-NATURAL-BANANAS ^
(6) N <> A, SHIFT=1, protoe N se vyskytuje ve vzorku BANANA I-WANT-TO-FLAVOR-NATURAL-BANANAS ^...
(7) ANA = ANA, ale B <> N1 SHIFT=2, protoe B se vyskytuje ve vzorku o 2 znaky vlevo. BANANA I-WANT-TO-FLAVOR-NATURAL-BANANAS ......
(8) Vzorek nalezen.
4.2.2.2 Algoritmus Commentz-Walterov Commentz-Walterov navrhla algoritmus, kter je zaloen na kombinaci Boyer-Mooreova algoritmu a algoritmu Aho-Corasickov . Tento algoritmus je uren pro vyhledvn konen mnoiny vzork protismrn m vyhledvnm. Pedzpracovnm konen mnoiny vzork p = fv1 v2 : : : vk g vznikne CW vyhledvac stroj a pak vyhledvn probh podle nsledujcho algoritmu: const LMIN = /d lka nejkrat!"ho vzorku/ var TEXT : array 1..T] of char I,J : integer NALEZEN : boolean
36
STATE : TSTATE g : array1..MAXSTATE,1..MAXSYMBOL] of TSTATE F : set of TSTATE ... begin NALEZEN:=FALSE STATE:=q0 I:=LMIN J:=0 while (I<=T) and not NALEZEN do begin if gSTATE,TEXTI-J]]=fail then begin I:=I+SHIFTSTATE,TEXTI-J]] STATE:=q0 J:=0 end else begin STATE:=gSTATE,TEXTI-J]] J:=J+1 end: NALEZEN:=STATE in F end end
CW vyhledvac stroj postupn porovnv text a vzorek zprava doleva a v ppad, e gSTATE, TEXTI-J]] m hodnotu fail, posune se cel vyhledvac stroj doprava o hodnotu SHIFT , kter zvis na stavu a prv srovnvan m znaku v textu. Pak opt zan vyhledvn a CW vyhledvac stroj vychz z potenho stavu. CW vyhledvac stroj zkonstruujeme pomoc algoritmu 4.7. Sestrojme funkci g a zavedeme ohodnocen w jednotliv ch stav :
Algoritmus 4.7:
Konstrukce CW vyhledvacho stroje. Vstup: Mnoina vzork p=fv1 v2 : : : vk g V stup: CW vyhledvac stroj Metoda: 1. Poten stav bude q0 1 w(q0 ) = ". 2. Kad stav vyhledvacho stroje odpovd ppon bm bm+1 : : : bn njak ho vzorku vi z mnoiny p. De nujeme g(q bm;1 ) = q0 , kde q0 odpovd ppon bm;1 bm bm+1 : : : bn vzorku vi . w(q) = bn : : : bm+1 bm , w(q0 ) = w(q)bm;1 3. g(q a) = fail pro vechna q a a, pro kter g(q a) nebylo de novno v kroku 2. 4. Kad stav, kter odpovd pln mu vzorku bude koncov stav.
Pklad 4.9:
Sestrojme CW vyhledvac stroj pro mnoinu vzork p = fcacbaa aba acb acbab ccbabg. V sledek je uveden na obr. 4.10. Jednotliv stavy CW stroje jsou ohodnoceny symboly, pi kter ch se do nich pechz. Poten stav je oznaen ipkou. Posledn otzkou, kterou je teba vyeit, je v poet funkce SHIFT . Je opt nkolik monost, jak tuto funkci de novat. Zde uvedeme nvrh autorky: 37
Obr. 4.10: CW vyhledvac stroj pro mnoinu vzork p = fcacbaa aba acb acbab ccbabg
SHIFT -STATE TEXT -I ; J ]] = min(max(shift1(STATE ) char(TEXT -I ; J ]) ; J ; 1) shift2(STATE )):
Jednotliv funkce jsou de novny takto:
1. char(a) je de novna pro vechny symboly z abecedy T jako nejmen hloubka stavu, do kter ho se v CW vyhledvacm stroji pechz pi symbolu a. Pokud symbol a nen v dn m vzorku, je char(a) = LMIN + 1, kde LMIN je d lka nejkratho vzorku. Formln: char(a) = min(fd(q) : w(q) = xag LMIN + 1): 2. Funkce shift1(q) m hodnotu shift1(q0 ) = 1. Pro ostatn stavy m hodnotu shift1(q) = min(k : fk = d(q0 ) ; d(q) w(q0 ) = w(q)u pro njak neprzdn slovo ug LMIN ): Stav q0 m vt hloubku ne q a w(q) je vlastn pponou w(q0 ). 3. Funkce shift2 m hodnotu shift2(q0 ) = LMIN . Pro ostatn stavy m hodnotu shift2(q) = min(k : fk = d(q0 ) ; d(q) w(q0 ) = w(q)u pro njak neprzdn slovo u q0 je koncov stavg fshift2(q 0 ) : q 0 je pedch dce q g): 38
Pklad 4.10:
CW vyhledvac stroj pro mnoinu vzork p = fcacbaa aba acb acbab ccbabg z pkladu 4.9 bude mt jednotliv funkce de novny takto:
a b c x
char 1 1 2 4
Poznmka: x zastupuje ostatn symboly abecedy. Funkce shift1 je naznaena na obr. 4.11 jako ohodnocen jednotliv ch uzl a rkovan jsou pro pslun stavy q uvedeny jim odpovdajc stavy q0 , kter byly pi v potu funkce shift1 vzaty v vahu. Na obr. 4.12 je tot provedeno pro funkci shift2.
Obr. 4.11: V poet funkce shift1
4.2.2.3 Protismrn vyhledvn nekonen mnoiny vzork Podobn jako pi sousmrn m vyhledvn je mono pout konen automat i pi protismrn m vyhledvn. V tomto ppad sestrojme konen automat pro reverzovan regulrn v raz popisujc mnoinu vzork (konenou i nekonenou). Potom pro jednotliv stavy a vstupn symboly urme velikosti posuv . Tento postup navrhl Buczilowski. 39
Obr. 4.12: V poet funkce shift2
Pklad 4.11:
Je dn regulrn v raz RV = bc(a + a bc). Reverzovan v raz m tvar RV R = (a + cba )cb. Pro tento v raz sestrojme konen automat, jeho pechodov diagram je na obr. 4.13.
'$ # "! &% c
4
b
3
+
H Y HH
a
HH
?
HH
c
2
HH HH
b
1
5
Q k Q
Qc Q
Q
Q Q
0
a
Obr. 4.13: Konen automat pro reverzovan regulrn v raz RV R = (a + cba )cb V nsledujc tabulce jsou uvedeny velikosti posuv (shift-STAV SY MBOL]) pro ppad, kdy v automatu nen mon sprvn pechod. Symbol x zastupuje ostatn symboly abecedy. 40
symboly a b 0 1 1 1 stavy 2 1 3 1 4 1 1 5 2 2
c x 3 1 2 1 1 1 1 1 2
Hodnoty funkce shift z pkladu 4.11 V tabulce jsou d leit zejm na ppady, kdy posuv je vt ne jedna. Rozebereme tyto ppady podrobnji: shift-0 x] = 3 Symbol x nen soust dn ho ze vzork a proto posuv se provede o d lku nejkratho vzorku, kter je 3. shift-1 x] = 2 Plat tot co v pedchozm ppad s tm, e pedchoz symbol byl c a je tedy mono prov st posuv o 2, protoe symbol c se vyskytuje jet pi pechodu ze stavu 2. shift-5 a] = 2 Symbol a se nevyskytuje jako ppona dn ho vzorku zanajc ve stavu 5. Posuv se provede o 2, protoe symbol a se vyskytuje pi pechodu ze stavu 2. shift-5 b] = 2 shift-5 x] = 2 Ped symbolem b nebo x byl nalezen symbol a. Posuv se provede o 2, protoe symbol a se vyskytuje pi pechodu ze stavu 2.
4.2.2.4 Dvoucestn automat se skokem Krom pouit konen ho automatu pro protismrn vyhledvn navrhl Buczilowski tak dvoucestn konen automat se skokem jako zobecnn vech vyhledvcch stroj pro sousmrn a protismrn vyhledvn. Dvoucestn deterministick konen automat se skokem (2DFJA) je M = (Q T q0 k " F ), kde Q je mnoina stav , T je vstupn abeceda, q0 2 Q je poten stav, je zobrazen z Q T do Q f;1 1 : : : kg, k2N je maximln d lka skoku, "62 Q T je znaka skoku, F Q je mnoina koncov ch stav . Kongurace dvoucestn ho deterministick ho konen ho automatu M je etzec z mnoiny T QT " T . Napklad etzec
a1 a2 : : : ai;1 qai : : : aj ;1 " aj : : : an
je kon gurace. V znam t to kon gurace je znzornn na obr. 4.14. Mnoinu kon gurac automatu M ozname K (M ). P echod je relace, kterou ozname `, a je podmnoinou K (M ) K (M ) de novanou takto: 41
a1 : : : ai;1 q ai : : : aj;1 "aj : : : an tec hlava
6
6
znaka skoku
-
q
Obr. 4.14: V znam kon gurace 2DFJA
a1 : : : ai;1 qai : : : aj ;1 " aj : : : an ` a1 : : : ai;2q0 ai;1 ai : : : aj ;1 " aj : : : an pro i > 1 (q ai ) = (q0 ;1) a1 : : : ai;1 qai : : : aj ;1 " aj : : : an ` a1 : : : ai;1ai : : : at;1 q0 " at : : : an pro (q ai ) = (q0 m) m 1 t = min(j + m n + 1): k
+
Symboly ` ` ` pouijeme pro oznaen k-t mocniny, transitivnho, transitivnho a re0exivnho uzvru relace `. Jazyk pijman automatem M = (Q T q0 k " F ) je mnoina L(M ) = fw 2 T : q0 " w ` wf " f 2 F g: Je dokzno, e dvoucestn deterministick konen automat se skokem je formln syst m pro speci kaci regulrnch jazyk . To znamen, e pro kad 2DFJA existuje ekvivaletn klasick konen automat. Pro sousmrn vyhledvn m eme pslun vyhledvc stroje simulovat pomoc 2DFJA tak, e v kad kon guraci bude oznaen stavu a znaka skoku bezprostedn za sebou.
Pklad 4.12:
Sestrojme 2DFJA pro BM vyhledvc stroj z pkladu 4.8. M = (fstart q0 q1 q2 q3 q4 q5 q6 g fA B N X g start 6 " fq6 g) Pechodov tabulka m tvar:
start
q0 q1 q2 q3 q4 q5 q6
A
B
N
(q0 5) (q0 5) (q0 5) (q1 ;1) (q0 5) (q0 1) (q0 1) (q0 4) (q2 ;1) (q3 ;1) (q0 3) (q0 1) (q0 1) (q0 2) (q4 ;1) (q5 ;1) (q0 1) (q0 2) (q0 1) (q6 ;1) (q0 1)
X (q0 5) (q0 6) (q0 5) (q0 4) (q0 3) (q0 2) (q0 1)
Pro text z pkladu 4.8 provede automat M tuto posloupnost pechod : 42
start " I-WANT-TO-FLAVOR-NATURAL-BANANAS ` I-WANq0 "T-TO-FLAVOR-NATURAL-BANANAS ` I-WANT-TO-Fq0 "LAVOR-NATURAL-BANANAS ` I-WANT-TO-FLAVOR-q0 "NATURAL-BANANAS ` I-WANT-TO-FLAVOR-Nq0 "ATURAL-BANANAS ` I-WANT-TO-FLAVOR-q1N "ATURAL-BANANAS ` I-WANT-TO-FLAVORq2-N "ATURAL-BANANAS ` I-WANT-TO-FLAVOR-NATURq0 "AL-BANANAS ` I-WANT-TO-FLAVOR-NATUq1R "AL-BANANAS ` I-WANT-TO-FLAVOR-NATURAL-BAq0 "NANAS ` I-WANT-TO-FLAVOR-NATURAL-BANq0 "ANAS ` I-WANT-TO-FLAVOR-NATURAL-BAq1N "ANAS ` I-WANT-TO-FLAVOR-NATURAL-Bq2AN "ANAS ` I-WANT-TO-FLAVOR-NATURAL-q3BAN "ANAS ` I-WANT-TO-FLAVOR-NATURAL-BANANq0 "AS ` I-WANT-TO-FLAVOR-NATURAL-BANAq1 N "AS ` I-WANT-TO-FLAVOR-NATURAL-BANq2 AN "AS ` I-WANT-TO-FLAVOR-NATURAL-BAq3NAN "AS ` I-WANT-TO-FLAVOR-NATURAL-Bq4ANAN "AS ` I-WANT-TO-FLAVOR-NATURAL-q5BANAN "AS ` I-WANT-TO-FLAVOR-NATURALq6 -BANAN "AS
4.2.3 Shrnut Metody sousmrn ho a protismrn ho vyhledvn je mono uspodat podle toho, jak velkou mnoinu vzork vyhledvj. Toto uspodn je na obr. 4.15. 2 DFJA DFA
B
1
AC
CW
k
KMP
BM
1
-
Obr. 4.15: Shrnut metod sousmrn ho a protismrn ho vyhledvn v textu Jednotliv zkratky maj tento v znam: KMP { KNUTH-MORRIS-PRATT AC { AHO-CORASICKOV DFA { DETERMINISTICK KONEN AUTOMAT BM { BOYER-MOORE CW { COMMENTZ-WALTEROV B { BUCZILOWSKI 2DFJA { DVOUCESTN DETERMINISTICK KONEN AUTOMAT SE SKOKEM
43
4.3 Vyhledvac metody s pedzpracovnm textu { indexov metody Metoda, kterou se budeme zab vat v t to kapitole, pat do skupiny III, pi kter se provd pedzpracovn textu a neprovd se pedzpracovn vzork . Zkladnmi pojmy t to metody jsou pojmy index a indexov soubor. Pojem index je velmi irok , ale ve vyhledvacch syst mech je to obvykle uspodan mnoina slov, kter jsou obsaena v textu. U kad ho slova v indexu jsou uvedeny odkazy do textu, kter ukazuj, kde se pslun slovo vyskytuje. Je to obdobn zp sob, jak se pouv v kvalitnjch odborn ch knihch pi konstrukci rejstku. Indexov soubor pak obsahuje slova tvoc index s identi kac jejich v skytu v textu. Tak se pouv pojmu indexsekvenn soubor, m se mn indexov soubor a sekvenn soubor obsahujc text. Index je mono implementovat mnoha zp soby. Nejnzornj je implementace indexu ve form invertovan ho souboru. Tento princip ukeme na pklad. Rozshl text b v zpravidla hierarchicky rozlenn na rovn. Napklad text { dokument { odstavec { vta { slovo. Odkazy v indexu lokalizuj v skyty dan ho slova v textu. Pedpokldejme, e text je rozlenn na dokumenty, kter jsou pr bn oslovny. Nsledujc tabulka popisuje v skyty jednotliv ch slov v dokumentech uloen ch v sekvennm souboru. slovo1 slovo2 slovo3 slovo4 dokument1 1 1 0 1 dokument2 0 1 1 1 dokument3 1 0 1 1 Jednika znamen, e slovo se vyskytuje v dokumentu, nula znamen, e slovo se nevyskytuje v dokumentu. Invertovan soubor vznikne z t to tabulky operac transpozice matice. slovo1 slovo2 slovo3 slovo4
dokument1 dokument2 dokument3 1 0 1 1 1 0 0 1 1 1 1 1
Hledme-li nap. dokument, kter obsahuje slovo3, je zejm , e je obsaeno v dokumentu2 a dokumentu3. Pitom vyhledvn vzorku v indexu je mono prov st binrnm p lenm, protoe slova mohou b t v indexu uspodna. asov sloitost nalezen dokument pro jeden vzorek pi binrnm p len je O(V log(i)), kde V je d lka vzorku a i je d lka indexu. Pro mnoinu vzork p = fv1 v2 vk g m eme pout dv metody. Jestlie poet vzork je mnohem men ne d lka indexu (k << i), pak je v hodn pout opakovan vyhledvn binrnm p lenm. V tomto ppad je asov sloitost nalezen dokument , ve kter ch se vyskytuje mnoina vzork p = fv1 v2 vk g, rovna O (s k log (i)), kde i je d lka indexu, s je pr mrn d lka vzorku. V opan m ppad je v hodn pout vyhledn vzork metodou dvojit ho slovnku. Metoda vyhledvn vzork pomoc dvojit ho slovnku je bn pouvan metoda pi porovnvn dvou uspodan ch mnoin. V naem ppad se jedn o mnoiny slov. Nejdve je teba uspodat mnoinu vzork a vytvoit uspodan index. Podstata vyhledvacho algoritmu pak spov v porovnvn dvou uspodan ch mnoin slov. Poet porovnn nen vt ne souet potu slov v obou seznamech. Vyhledvn m tedy sloitost O((k + i) s), kde i je poet slov v indexu, k je poet vzork a s je pr mrn d lka vzorku. Probl mem, kter se nevyskytl v metodch nepouvajcch pedzpracovn textu, je pidn dokumentu do souboru. Pi pidn dokumentu do souboru je nutno upravit invertovan soubor, 44
co znamen pidn sloupce pro nov dokument a ppadn pidn nov ch slov. Pitom je nutno stle udrovat index uspodan .
4.3.1 Implementace indexovch systm Indexov syst m se skld z indexov ho souboru, ve kter m jsou uloeny informace o pstupu k jednotliv m dokument m, a sekvennho souboru, ve kter m jsou uloeny vlastn dokumenty. Z mnoha implementac vybereme ti: 1. pm pouit invertovan ho souboru, 2. pouit seznamu dokument ke kad mu klov mu slovu, 3. souadnicov syst m s ukazateli.
4.3.1.1 Pouit invertovanho souboru Nejjednodu zp sob implementace indexov ho syst mu je piazen bitov ho vektoru ke kad mu klov mu slovu. Pozice jedniek v tomto vektoru udvaj sla dokument , ve kter ch se klov slovo vyskytuje. Dokumenty jsou tedy oslovny. Tento princip je naznaen na obr. 4.16. slovo1 slovo2 slovo3 slovo4
1 1 0 1
0 1 1 1
1 0 1 1
Obr. 4.16: Indexov soubor s bitov m vektorem Z tohoto obrzku je zejm , e napklad slovo3 se vyskytuje v dokumentech slo 2 a 3.
4.3.1.2 Pouit seznamu dokument Stejn jako v pedchozm ppad jsou jednotliv dokumenty oslovny a ke kad mu klov mu slovu je piazen seznam sel dokument , ve kter ch se toto slovo vyskytuje. Indexov soubor je uveden na obr. 4.17. slovo1 slovo2 slovo3 slovo4
1, 3 1, 2 2, 3 1, 2, 3
Obr. 4.17: Indexov soubor se seznamem sel dokument
4.3.1.3 Souadnicov systm s ukazateli V tomto ppad se nepracuje s sly dokument , ale indexov soubor je rozdlen na dv sti: slovnk s ukazateli do seznamu dokument , seznam dokument s ukazateli na dokumenty. Cel uspodn je znzornno na obr. 4.18. 45
Obr. 4.18: Souadnicov syst m s ukazateli 46
4.3.2 Metody indexovn Ze vech operac v oblasti indexov ch metod je nejsloitj een probl mu nalezen vhodn ch slov, kter maj b t soust indexu. Slova, kter jsou soust indexu, mus b t vybrna tak, aby dostaten pesn reprezentovala obsah jednotliv ch dokument . Je zejm , e slovo, kter se vyskytuje ve vech dokumentech nem z hlediska vyhledvn dn v znam. Mal v znam m i slovo, kter se vyskytne jen v jednom dokumentu. 2loha nalezen vhodn ch slov do indexu se naz v indexovn. Zp soby, jak se indexovn provd, m eme rozdlit na run, automatick . Run indexovn provd zkuen experti zejm na pi zpracovn bibliogra ck ch dokument . Je to prce nron, a proto je snaha tento kol algoritmizovat. Uvedeme dle jednoduchou metodu automatick ho indexovn zaloenou na frekvenci v skytu slov v jednotliv ch dokumentech. Pi vech metodch se obvykle de nuje urit mnoina slov, kter se pi indexovn pouvat nebudou. Jsou to slova, kter maj v jazykov ch textech jen gramatick v znam. Pat sem slovn druhy jako pedloky, spojky, zjmena, dle pak pomocn a zp sobov slovesa, leny a podobn. Seznam tchto slov (stop seznam, angl. stop list) se obvykle vytv run. Pi tvorb tohoto seznamu je mon vyut v sledk anal zy textu, protoe slova ve stop seznamu jsou hodn frekventovan a krtk. Dalm kriteriem pro klasi kaci indexovacch metod je otzka, zda je indexovn nezen nebo zen . Pi zen m indexovn je pouvn speciln slovnk slov, kter se pouvaj pro indexovn. Existuj dva pstupy k tvorb takov ho slovnku. Prvn pstup je zaloen na seznamu slov, kter nen nijak vnitn strukturovn (angl. pass list). Druh pstup je zaloen na slovnku, kter je specilnm zp sobem strukturovn. Tento slovnk se naz v tezaurus. V dalm textu se budeme zejm na zab vat otzkou automatick ho indexovn a otzkou struktury a tvorby tezauru. V br slov do indexu se provd tak, aby byly splnny tyto poadavky: 1. Nal zt dokumenty, kter se t kaj oblasti zjm uivatele. 2. Dt do souvislosti dokumenty, kter se t kaj podobn ch a souvisejcch oblast. 3. Ut slova s dobe de novan m v znamem tak, aby dobe charakterizovala jednotliv dokumenty. Dve ne se budeme zab vat metodami automatick ho indexovn, shrneme strun nkter principy pouvan pi runm indexovn. Pi nezen m runm indexovn je teba vzt v vahu pro kad slovo jeho synonyma a pbuzn slova a pokud mono vechna pout pro indexovn. Pi zen m runm indexovn je tato operace usnadnna tm, e v tezauru jsou seznamy synonym a pbuzn ch slov uvedeny.
4.3.2.1 Analza textu 2kolem indexovn je nalezen slov, kter charakterizuj obsah urit ho dokumentu a uren vhy nebo hodnoty tchto slov vzhledem k jejich d leitosti k identi kaci dokumentu. Lze oekvat, e takov slova jsou pedevm soust uvaovan ho dokumentu. Proto se budeme zab vat otzkou anal zy textu vedouc k v bru slov do indexu. 47
Vtina automatick ch indexovacch metod vychz ze skutenosti, e frekvence v skytu jednotliv ch slov m pmou souvislost s jejich v znamnost pi identi kaci dokumentu. Pokud by se jednotliv slova vyskytovala ve vech dokumentech se stejnou frekvenc, nebylo by mon vybrat dn z nich jako vhodn pro identi kaci jednotliv ch dokument . Skutenost je, e jednotliv slova se vyskytuj v textu s r znou frekvenc. Jestlie vytvome seznam slov a setdme jej podle klesajc frekvence jejich v skyt , dostaneme frekvenn slovnk. Zatek takov ho frekvennho slovnku pro anglitinu je uveden v tab. 4.2. Tento slovnk byl vytvoen ze souboru dokument obsahujcch 1 000 000 slov. poad 1 2 3 4 5 6 7 8 9 10
slovo frekvence poad frekvence the 69971 0.070 of 36411 0.073 and 28852 0.086 to 26149 0.104 a 23237 0.116 in 21341 0.128 that 10595 0.074 is 10099 0.081 was 9816 0.088 he 9543 0.095
Tabulka 4.2: Zatek frekvennho slovnku Frekvenn slovnk lze charakterizovat empirick m Zipfov m zkonem: po ad frekvence = konstanta
Tento zkon je vysvtlovn pomoc obecn ho +principu nejmenho odporu,. V tomto ppad to znamen, e mluv i pisatel radji nkter slova astji opakuje msto pouvn nov ch a r zn ch slov. Dle je vidt, e slova s vysokou frekvenc jsou obvykle velmi krtk.
Obr. 4.19: Kumulativn podl pouvan ch slov
48
Dal charakteristikou frekvennho slovnku je graf ukazujc zvislost kumulativnho podlu pouvan ch slov (KPS) na procentu slov z frekvennho slovnku.
KPS =
PN
po ad=1 frekvencepo ad
poet slov textu
Z grafu na obr. 4.19 je vidt, e 20% nejfrekventovanjch slov tvo 70% textu.
4.3.2.2 Jednoduch metoda automatickho indexovn Frekvenn slovnk, Zipf v zkon a jeho d sledky m eme pout jako v chodisko pro jednoduchou metodu odvozen v znamnosti slov pro identi kaci dokument . Nech je dn soubor n dokument . Pak provedeme tyto operace: 1. Vypoteme frekvenci FREQik pro kad dokument i 2 h1 ni a kad slovo k 2 h1 K i, kde K je poet r zn ch slov pouit ch v cel m souboru dokument . 2. Vypoteme frekvenci TOTFREQk pro kad slovo ve vech dokumentech dohromady:
TOTFREQk =
n X i=1
FREQik
3. Vytvome frekvenn slovnk pro vechna slova k 2 h1 K i. Stanovme prh pro vylouen velmi frekventovan ch slov ze zatku frekvennho slovnku. Tm vyloume velmi frekventovan slova, kter maj bu dn nebo mal v znam pro identi kaci dokument . 4. Podobn m zp sobem vyloume slova s velmi nzkou frekvenc. 5. Zb vajc slova se stedn frekvenc jsou vhodn pro zaazen do indexu. Tato metoda se opr o empiricky zjitnou skutenost, e slova s nzkou a vysokou frekvenc maj mal v znam pro vyhledvn. Na obr. 4.20 je uveden graf ukazujc v znam slova pro vyhledvn v zvislosti na frekvenci jeho v skytu.
Obr. 4.20: V znam slov pro vyhledvn v zvislosti na jejich frekvenci
4.3.2.3 zen indexovn Zkladnm prostedkem pro zen procesu indexovn je stanoven indexovacho jazyka, kter obsahuje omezen v br termn (slov) pro indexovn. Takov slovnk se naz v tezaurus. Tezaurus je slovnk, kter obsahuje hierarchick a asociativn vztahy a vztahy ekvivalence mezi jednotliv mi termny. Tyto vztahy m eme rozdlit do ty skupin: 49
Obr. 4.21: Pklad hierarchick struktury tezauru 1. Vazba na standardn termn (See : : : ). Pro kadou mnoinu ekvivalentnch termn (synonym) je stanoven standardn (preferovan ) termn. Pi indexovn je vdy vybrn standardn termn bez ohledu na to, jak termn je pouit v dokumentu nebo v dotazu. Jen standardn termn je pouit v indexu. 2. Vazba na pbuzn termny (See also : : : , related terms, RT). Mezi jednotliv mi pbuzn mi termny jsou uvedeny vzjemn vazby. Tyto termny pak tvo skupiny pbuzn ch termn . 3. Vazba na obecnj (ir) termny (broader terms, BT). 4. Vazba na u termn (narrower terms, NT). Tezaurus je pouvn nejen pro zen indexovacho procesu, ale tak pi vlastnm vyhledvn. Pi zpracovn dotazu se pouit termny uprav na standardn termny a dle je mono na zklad poadavk uivatele pidat pro vyhledvn pbuzn , obecnj i u termny. Tezaurus m eme znzornit ve form stromu. Tento strom znzoruje vazby mezi umi a irmi termny a mezi pbuzn mi termny. Na obr. 4.21 je pklad hierarchick struktury tezauru pro vyhledvn v oblasti publikac. Z obrzku je vidt, e publikace je obecnj termn pro termny kniha, broura a asopis. asopis m u termny vdeck , technick a propagan. Kniha, broura a asopis jsou pbuzn termny. Vazba mezi ekvivalentnmi termny zde nen vyjdena, protoe v tezauru jsou pouity jen standardn termny.
4.3.2.4 Konstrukce tezauru Tezaurus m e b t konstruovn run nebo automatizovan. Bez ohledu na zp sob konstrukce je teba prov st: rozhodnut o tom, kter termny maj b t do tezauru vloeny, vytvoit skupiny podobn ch termn . Rozhodnut o tom, jak termny do tezauru vloit, m eme odvodit z vahy o vhodnosti urit ho termnu pi indexovn. Z toho, co bylo uvedeno v e, plyne, e termny se stedn frekvenc jsou nejlepmi kandidty na vloen do tezauru. Tak termny s ni frekvenc je 50
mono pout, ale ty je teba sdruit do skupin tak, aby souet frekvenc jednotliv ch termn
ve skupin byl dostaten vysok . Tezaurus se obvykle vytv pro zen indexovn v urit m oboru. Z toho vypl vaj experimentln potvrzen pravidla o jeho tvorb: 1. Tezaurus m obsahovat jen termny, kter pat do dan ho oboru. 2. V ad ppad se jako odborn termny pouvaj termny z jin ch obor . V tomto ppad je nutno jim v tezauru pisoudit s mantiku obvyklou v dan m oboru. Pkladem mohou b t termny POLE a STROM v oblasti informatiky. 3. Pi tvorb skupin pbuzn ch termn je dobe sdruovat termny s podobnou frekvenc. Souet frekvenc termn by ml b t pro vechny skupiny piblin stejn . 4. Je teba z tezauru vylouit termny s vysokou frekvenc, kter maj mal nebo dokonce nulov v znam pro rozlien jednotliv ch dokument .
4.3.2.5 Vyhledvn vzork pomoc fragmentovch index Metoda, kter pouv fragmentov ch index , pat mezi metody, kter vyaduj jak pedzpracovn vzork , tak pedzpracovn textu. Fragmentov index je zaloen na mylence, e v znam slova je soustedn jen v jeho sti. Hledme-li nap. molybden, sta najt podetzec (fragment) "ybd". Pro uritou zkou t matickou oblast se d sestrojit mnoina fragment , kter ch je dov tisc. Slovnk fragment m e b t pevn , m odpadaj probl my s jeho aktualizac pi doplovn souboru dokument . Nev hodou t to metody je zvislost na jazyce a t matick oblasti a dle snen pesnost vyhledvn vzhledem k vyhledvn fragment msto cel ch slov.
4.4 Vyhledvac metody s pedzpracovnm textu a vzork { signaturov metody Signatura Sx je bitov etzec d lky m, kter je piazen textov mu etzci x zobrazenm h : x ! Sx Sx 2 f0 1gm . Kad bit signatury Sx vyjaduje njakou vlastnost textov ho etzce x. Zvolme-li vhodn zobrazen h, pak je mono porovnnm signatury textu St a signatury vzorku Sv zjistit, zda text m e i nem e vzorek obsahovat. M e-li ho obsahovat, pak je teba njak m pesn m algoritmem ovit, zda jej skuten obsahuje. Zejm, kdy St and Sv Sv , pak text spluje vechny vlastnosti poadovan vzorkem a je nutno provit, zda text vzorek skuten obsahuje. Pro praktickou implementaci je mono pout vztahu: (St and Sv 6 Sv ) (not St and Sv ), kter vede na jednodu v raz. Zb v otzka volby h. V t to souvislosti se budeme zab vat tmito otzkami: jak vytvoit signatury jednotliv ch termn , jak ze signatur jednotliv ch termn vytvoit signaturu dokumentu, jak rozdlit rozshl dokumenty na bloky vzhledem k vlastnostem signatur. Signatury jednotliv ch termn m eme vytvoit tmito zp soby: 1. Kad mu termnu piadme jeden bit v signatue. 2. Signaturu termnu vytvome pomoc njak haovac funkce. Ze signatur jednotliv ch termn vytvome signaturu dokument
etzen m kdovnm, vrstven m kdovnm. 51
4.4.1 etzen a vrstven k dovn Pi etzen m kdovn jsou signatury jednotliv ch termn zetzeny. Tento pstup se hod jen pro ppady, kdy text je njak m zp sobem strukturovn a jednotliv sloky jsou uspodany. Mjme zznam, kter m tvar z = (a1 a2 : : : an ): Signatura zznamu h(z ) = h(a1 ) h(a2 ) : : : h(an ). Pi vyhledvn je teba urit hodnotu pslun ch prvk zznamu.
Pklad 4.13:
Zznam m tvar z = (ISBN, AUTOR, TITUL). Konkr tn zznam pro jednu knihu bude napklad z = (72345, KAREL APEK, KRAKATIT). Signatury jsou zvoleny takto: h(72345) = 10001001, h(KAREL APEK) = 01011000, h(KRAKATIT) = 10010001. Signatura zznamu vznikne zetzenm signatur jednotliv ch prvk : h(z ) = 10001001 01011000 10010001 Pi vyhledvn knih KARLA APKA bude mt signatura dotazu tvar: ???????? 01011000 ???????? Otaznky v signatue dotazu znamenaj, e v tomto mst m e mt signatura libovolnou hodnotu. Pi vrstven m kdovn jsou signatury jednotliv ch termn pouit ch v dokumentu logicky stny bit po bitu. Jestlie v dokumentu d jsou pouita slova a1 a2 : : : an , pak h(d) = h(a1 ) or h(a2 ) or : : : or h(an ).
Pklad 4.14:
Pi pouit vrstven ho kdovn pro dokumenty o knihch z pedchozho ppadu bude signatura urena takto: hodnota 7345 KAREL APEK KRAKATIT signatura dokumentu
signatura 10001001 01011000 10010001 11011001
Pi vrstven m kdovn dochz k tomu, e poet jedniek v signatue se zvtuje s potem termn pouit ch v dokumentu. Pokud poet jedniek vzroste natolik, e t m vechny bity signatury jsou jedniky, m to negativn d sledek na vyhledvn. Takov dokumenty pak vyhovuj t m vem dotaz m a pi pesn m prohledvn je nutno prohledvat velmi mnoho dokument . Experimentln bylo zjitno, e z hlediska vyhledvn je nejvhodnj signatura, ve kter je 50% jedniek. Z tohoto d vodu je teba rozshl dokumenty rozdlit na bloky tak, aby poet jedniek v jejich signaturch nebyl vysok . Jsou dv monosti: 1. rozdlit dokument na bloky stejn d lky (FSB { Fixed Size Blocks), 2. rozdlit dokument na bloky o stejn vze (FWB { Fixed Weight Blocks). Pi metod FWB se signatura vytv postupn pidvnm jednotliv ch termn . Blok se ukon tehdy, kdy poet jedniek je piblin 50%. 52
4.4.2 Metody tvorby signatur Vhodnou kombinac uveden ch princip vznikaj jednotliv metody tvorby signatur. Nejjednodu je metoda zaloen na vektoru vskytu slov. Tato metoda piazuje kad mu termnu jeden bit v signatue a signatura dokumentu vznik vrstven m kdovnm. To znamen, e pro kad dokument je vytvoen binrn etzec, kde kad bit odpovd jednomu z mon ch termn . Bity odpovdajc termn m, kter se v dokumentu vyskytuj jsou nastaveny na jedniku, ostatn jsou nastaveny na nulu. V nsledujc tabulce je uveden pklad piazen signatur jednotliv m termn m. termn signatura data 000001 disc 000010 le 000100 information 001000 storage 010000 tape 100000 Dokument obsahujc termny data le storage bude mt signaturu 010101. Tato metoda vede na pesn vyhledvn, co znamen, e pro kad vzorek jsou vybrny prv ty dokumenty, kter jej obsahuj. Tato v hoda ovem pin dva zkladn probl my: signatura je velice dlouh, protoe jej d lka je dna potem mon ch termn , metoda vyaduje pevn seznam termn , protoe pi zmn potu termn se mn d lka signatury. Tuto nev hodu odstrauje pouit haovacch funkc pro v poet signatur jednotliv ch termn . V tomto ppad je signatura termnu bitov etzec s konstantn d lkou a vrsven m kdovnm zskme signaturu dokumentu.
Pklad 4.15:
V nsledujc tabulce je uveden pklad signatur nkolika termn . termn signatura data 0001 disc 0101 le 1001 information 0110 storage 0011 tape 1010 Signatura dokumentu obsahujcho "data le storage" bude 1011. Jestlie polome dotaz na dokumenty obsahujc termn " le", bude jeho signatura 1001. Pkladem, jak volit haovac funkce, je pouit haovan ch k-signatur. Vechny podetzce d lky k (k ; gramy) se pouij jako argumenty haovac funkce hash. Jej hodnotou je slo v intervalu < 1 m >, kter udv poad pznaku v signatue. Tento pznak (bit) je v signatue nastaven na jedniku. Nzorn je tento v poet naznaen na obrzku 4.22. V ppad pouit haovacch funkc pro v poet signatur a vrstven ho kdovn je signatura dokumentu vlastn jeho komprimovan verze, ale se ztrtou informace. To znamen, e pi v bru se stv, e nastane tzv. falen v br (false drop), tj. v br dokumentu, kter neodpovd dotazu. Pitom signatura dokumentu dotazu odpovd signatue dotazu. V pedchozm pklad dokument obsahujc "data le storage" (1011) odpovd dotazu "tape" (1010). Toto je d vod k tomu, aby vybran dokumenty byly dle prozkoumny pesn m ovovacm algoritmem. Na obr. 4.23 je naznaen zp sob pouit metody vyhledvn vzorku pomoc signatury. 53
hash
-
etzec x
0 1 0 1 0 0 1 0 0 signatura SX
hash
-
?
6
hash
-
Obr. 4.22: V poet signatury text T vzorek V
-
-
?
Ovovac algoritmus
h h
6
m
not
ST
-
m SV
-
@
XXX XXX nen je XXX XXX ? X
je obsaen
m
not ST
-
@ R @
not ST and SV
9 =0 (m e)
X z X
6=0
(nem e)
?
nen obsaen
Obr. 4.23: Vyhledvn vzorku pomoc signatury
4.4.3 Vyhledvn vzorku pomoc signatury a indexu V sledkem porovnn signatur je zjitn, zda text m e vzorek obsahovat, ale nen ureno kde. Je tedy mon zkombinovat signaturu s indexem, tj. pipojit k signatue seznamy ukazatel
do textov ho etzce. Pznakem v signatue u pak nen jedin bit, ale ukazatel na zatek etzce ukazatel nebo nic, kdy tento etzec neexistuje. Nev hodou t to metody je znan pamov sloitost a pitom i tato metoda m asovou sloitost O(p t), kde p je poet vzork
a t je poet text .
4.5 Vyhledvn vzork pomoc dvojit ho slovnku Metoda vyhledvn vzork pomoc dvojit ho slovnku je bn pouvan metoda pi porovnvn dvou uspodan ch mnoin. V naem ppad se jedn o mnoiny slov. Nejdve je teba uspodat mnoinu vzork a vytvoit uspodan index slov, kter se vyskytuj v textu. Podstata vyhledvacho algoritmu pak spov v porovnvn dvou uspodan ch mnoin slov. Poet porovnn nen vt ne souet potu slov v obou seznamech. Vyhledvn je tedy linern se sloitost 0(n + m), kde n je poet slov v indexu a m je poet vzork . Jestlie n << m, pak je v hodnj hledat v indexu metodou binrnho p len pro kad vzorek zvl a celkov sloitost je 0(m log n), m dostaneme vlastn metodu vyhledvn v indexu. Z toho plyne, 54
e metoda vyhledvn vzork pomoc dvojit ho slovnku je v hodn pedevm tehdy, kdy mnoina vzork m mohutnost srovnatelnou s indexem. Nsledujc tabulka shrnuje zkladn vlastnosti probran ch algoritm na vyhledvn v textu. pedzpracovn pedzpracovn poet textu vzork
vzork
ne ne 1 ano 1 1 konen konen nekonen ano ne konen ano 1 konen
algoritmus elementrn Knuth-Morris-Pratt Boyer-Moore Aho-Corasickov Commentz-Walterov konen automat slovn index signatura signatura s indexem fragmentov index dvojit slovnk
Pehled metod vyhledvn vzork v textu
55
5 Jazyky pro vyhledvn Jen zdka se vyskytuje situace, kdy vyhledvme dokumenty, kter obsahuj jedno klov slovo. V jimen m e jedno klov slovo stait jako dotaz pro vyhledvac syst m, ale jen v ppad, e toto slovo je nov nebo zvl jedinen . Pkladem takov ch slov mohou b t specializovan odborn termny jako napklad +tezaurus,. Pokud napklad v informanm syst mu o potach se doteme na +computation,, dostaneme jako odpov t m celou databzi. Tato odpov m piblin stejnou cenu jako dn odpov. Obvykle se uivatel pi pprav dotazu pro vyhledvn sna omezit poet vyhledvan ch dokument tak, aby jich nebylo pli mnoho a aby zskal vechny potebn informace. Toho se dosahuje tm, e dotaz b v sloitj a krom klov ch slov obsahuje opertory. Opertory v dotazech m eme rozdlit na booleovsk a pozin. Booleovsk opertory bn pouvan jsou and, or, xor a not. Jejich interpretace je ovem ponkud jin, ne v logice. V znam tchto opertor je uveden v nsledujc tabulce. v raz v znam A and B vyber dokumenty, ve kter ch se vyskytuje jak slovo A, tak i slovo B A or B vyber dokumenty, ve kter ch se vyskytuje slovo A nebo slovo B nebo ob. A xor B vyber dokumenty, ve kter ch se vyskytuje slovo A nebo B, ale ne ob. A not B vyber dokumenty, ve kter ch se vyskytuje slovo A a nevyskytuje slovo B. Z t to tabulky je zejm , e opertory and, or a not budou implementovny pomoc mnoinov ch operac pr nik, sjednocen a mnoinov ho rozdlu. Vimnme si, e opertor not je binrn. Ve sloitjch v razech je nutno de novat prioritu opertor . V tomto smru se jednotliv syst my velmi li. Ve vtin syst m je mono pouvat zvorky. Pokud nejsou zvorky uvedeny, jsou pouvny tyto de nice poad provdn ch operac: a) b) c) d)
zleva doprava, zprava doleva, and, (or, xor), not, (or, xor), and, not.
Priorita opertor or a xor b v stejn. Protoe opertor not nen komutativn, je teba dle de novat poad, v jak m se provd stejn opertory. Obvykle b v pouita konvence lev asociativity, tj. operace se provd zleva doprava. Druhou skupinou opertor jsou pozin opertory, kter pedepisuj, v jak m poad mus b t klov slova v hledan m dokumentu. Zkladn pozin opertory jsou adj (adjacent), (n)words, with, same, syn. V znam tchto opertor je uveden v nsledujc tabulce. Opertory sentence a paragraf jsou ekvivalentn s opertory with a same. 56
v raz A adj B
v znam vyber dokumenty, ve kter ch se vyskytuje slovo A nsledovan slovem B A (n)words B vyber dokumenty, ve kter ch se vyskytuje slovo A a nejdle o n slov za nm je slovo B A with B vyber dokumenty, ve kter ch se vyskytuje A sentence B slovo A a B ve stejn vt A same B vyber dokumenty, ve kter ch se vyskytuje A paragraph B slovo A a B ve stejn m odstavci A syn B de nuje, e slovo A a B jsou synonyma Pokud se t e priority pozinch opertor , plat o nich podobn jako o booleovsk ch opertorech, e v r zn ch syst mech jsou pouvny r zn typy priorit. Ve vtin ppad vak maj pozin opertory vy prioritu ne booleovsk opertory. Mezi uveden mi pozinmi opertory se pouvaj priority v tomto poad: adj, (n)words, syn, with, same. Dalm rysem vyhledvacch jazyk je monost popisu mnoiny klov ch slov zkrcen m zp sobem. Napklad zpisem PSYCH jsme popsali mnoinu slov, kter obsahuje nap. slova: PSYCHIATRIST PSYCHIATRY PSYCHOLOGICAL PSYCHOLOGY PSYCHOLOGIST Hvzdika se pouv jako zstupce libovoln ho etzce znak . Dle se pouv otaznk jako zstupce jednoho znaku, kter m e, nebo nemus b t ptomen. Nap. DOCUMENT?? popisuje mnoinu, kter obsahuje slova: DOCUMENT DOCUMENTS DOCUMENTED ale neobsahuje nap. slovo DOCUMENTATION. Symboly a ? mohou b t pouity na zatku, uvnit a na konci slova. To je v znamn zejm na u ohebn ch jazyk , kde je mon zmna kmenov ch hlsek pi skloovn a asovn, co jsou napklad v etin dosti ast jevy. U syst m , kter pracuj s tezaurem, je mono pout pi vyhledvn tezauru a tm se dostvme k monosti vyhledvn s pouitm t matu (concept, topic). V tchto syst mech se pouvaj operace uveden v nsledujc tabulce. 57
BT (A) BROADER TERM NT (A) NARROWER TERMS PT (A) PREFERRED TERM SYN (A) SYNONYMS RT (A) RELATED TERMS TT (A) TOP TERM
vybere z tezauru r termn k termnu A vybere z tezauru u termny k termnu A vybere z tezauru preferovan termn k termnu A vybere z tezauru vechna synonyma k termnu A vybere z tezauru vechny pbuzn termny k termnu A vybere z tezauru nejir termn
U operac BT, NT je mono jet speci kovat, o kolik rovn v e nebo ne se vybraj termny z tezauru. Jako pklad pouit uveden ch vlastnost jazyk pro vyhledvn v textov ch syst mech uveme rozen jazyka SQL pro vyhledvn v textu tak, jak je de novn v syst mu ORACLE SQL*TextRetrieval. Toto rozen se t k pedevm pkazu SELECT. Zde uvedeme rozen pkazu SELECT ve zjednoduen podob. Podrobn popis je uveden ve remn dokumentaci. Zjednoduen pkaz SELECT pro vyhledvn v textu m tvar: SELECT speci kace poloek FROM speci kace tabulek WHERE poloka CONTAINS textov v raz Napklad: SELECT TITLE FROM BOOK WHERE ABSTRACT CONTAINS 'text retrieval' Textov v raz m e obsahovat opertory AND, OR a NOT a tm, e NOT je obvykl unrn logick opertor. Dle m e obsahovat kulat zvorky v obvykl m v znamu. Operandy, kter m e obsahovat textov v raz jsou shrnuty v nsledujc tabulce. 58
operand jednoduch etz etz s prav m rozenm etz s lev m rozenm etz s oboustrann m rozenm etz s libovoln m znakem msto ? etz s libovoln m podetzem msto % pozin v raz, 'etzb' m e b t m slov za 'etza' nebo 'etza' m e b t n slov za 'etzb' frze ir termn o jednu rove ir termny o n rovn r termny vech rovn u termny o jednu rove u termny o n rovn u termny vech rovn synonyma preferovan termn pbuzn termny nejir termn
zpis v textov m v razu 'etz' 'etz' 'etz' 'etz' 'e?z' 'e%z' 'etza' (m,n) 'etzb' 'hledm tuto frzi' BT ('etz') BT ('etz', n) BT ('etz', *) NT ('etz') NT ('etz', n) NT ('etz', *) SYN ('etz') PT ('etz') RT ('etz') TT ('etz')
Hodnotou sprvn ho textov ho v razu je vdy neprzdn konen mnoina slov.
Pklad 5.1: SELECT JM8NO FROM ZAM9STNANEC WHERE VZD9L:N; CONTAINS RT(UNIVERSITA) AND JAZYKY CONSTAINS 'ANGLITINA' AND 'N9MINA' AND PUBLIKACE CONTAINS 'KNIHA' OR NT('KNIHA',*) Tento pkaz zp sob v br jmen zamstnanc , kte maj vysokokolsk vzdln, ovldaj nminu a anglitinu a napsali knihu, pruku, monogra i, nvod nebo uebnici, jestlie byl pouit tezaurus z obr.4.21 a pbuzn termny k termnu universita jsou oznaen vysok ch kol.
59
6 Komprese dat Pi uchovvn znan ho mnostv dat se dve nebo pozdji naraz na fyzick omezen pamtov ho prostoru. Jednou z monost, jak tento probl m eit, je zvten pamtov ho prostoru. Zde se budeme zab vat druhou monost, kterou je lep vyuit existujcho pamtov ho prostoru. Uvedeme metody, kter jsou zaazovny do oblasti naz van komprese dat. A. Shannon ji v padest ch letech poukzal na to, e entropie, tj. informace obsaen ve znaku v rmci textu, je podstatn men, ne by se oekvalo. Obecn eeno, veker data obsahuj njakou nadbytenou informaci. Clem algoritm pro kompresi dat je transformace dat do tvaru, kter bude men, ale ponese stle stejn informace. V literatue je tzv. Shannon-Fano metoda povaovna za nejstar. Shanonn s Weaverem a Fano ji vyvinuli v roce 1949 nezvisle na sob. Po tech letech publikoval Hu%mann svou nejznmj prci, t kajc se metody konstrukce minimln redundantnho kdu. Musme si uvdomit, e clem vech tchto snah nebyla ani tak komprese dat, ale spe kdovn informace pro komunikan ely. Nen to ovem nic nov ho. V roce 1838 Morse navrhl sv j velmi dobe znm kd pro vysln zprv elektrick m telegrafem. Podobn jako ve v e zmnn ch kompresnch metodch, znaky s velkou pravdpodobnost v skytu maj krat kdov slova, ne ty, kter se vyskytuj m n asto. Na druh stran probl my, kter pin komprese pi zpracovn dat se v jedn d leit vci li od tradinch studi v teorii komunikac: nen zde jednoznan de novan statistick informan zdroj, na jeho zklad by se dal kd doladit. Mnoh dve vyvinut metody tedy pouze velmi tko umouj podrobnou anal zu, kter by teprve zajistila skuten dobrou kompresi. Modern kompresn metody pouvaj model dat, kter obsahuje: 1. strukturu, kter je vlastn sadou jednotek, kter mme komprimovat, a kontextu, ve kter m se vyskytuj, 2. parametry, kter vyjaduj pravdpodobnosti v skytu jednotliv ch jednotek. Kad algoritmus, kter komprimuje data, m eme chpat tak, jako by pracoval ve dvou krocch: vytvoen modelu dat a vlastn kdovn. Tyto dva aspekty komprese dat otevraj cestu k pochopen model , odrejc l pe strukturu dat, kter se maj komprimovat.
6.1 Zkladn pojmy komprese dat 6.1.1 K dovn a dek dovn Abeceda A je konen neprzdn mnoina symbol . Njak posloupnost symbol z A je etzec (slovo, zprva) nad A. Przdn posloupnost se naz v przdn etzec a budeme ji znait ". Mnoina vech etzc nad abecedou A bez przdn ho etzce se zna A+ . Kd K je trojice K = (S C f ), kde S je konen mnoina zdrojovch jednotek, C je konen mnoina kdovch jednotek, f je zobrazen z S do C +. Zobrazen f piazuje kad zdrojov jednotce z S prv jedno kdov slovo (sekvenci kdov ch jednotek) z C + . Zobrazen f mus b t injektivn. To znamen, e nikdy nezobrazuje dv r zn zdrojov jednotky na stejn kdov slova. Zobrazen f m e b t rozeno pro konenou posloupnost zdrojov ch jednotek (zdrojovou zprvu) takto:
60
f (S1 S2 Sk ) = f (S1)f (S2 ) f (Sk ):
Pojem kd se nkdy pouv pro obor hodnot (kdov ch slov) zobrazen f . $etz x 2 C + je jednoznan dekdovateln vzhledem k f , jestlie existuje maximln jedna posloupnost y 2 S + takov, e f (y) = x. $kme, e kd K = (S C f ) je jednoznan dekdovateln , jestlie jsou vzhledem k f jednoznan dekdovateln vechny etzy v C +. Kd K se naz v prexov kd, jestlie dn kdov slovo nen pre xem jin ho. Pre xov kdy se pouvaj velmi asto, protoe prv ty jednoznan dekduj zprvu bhem jejho ten zleva doprava. Blokov kd d lky n je takov kd, pi kter m vechna kdov slova maj d lku n. Kad blokov kd je jednoznan dekdovateln . Kad blokov kd je pre xov . Pre xov kd nemus b t blokov .
Pklad 6.1:
Chceme sestrojit binrn pre xov kd pro destkov slice (A = f1 2 : : : 9g C = f0 1g ) vhodn pro slova, kde se asto vyskytuj slice 3 a 4, ale zdka se vyskytuj slice 5 a 6. To znamen, e slicm 3 a 4 chceme piadit kd co nejkrat. Pro jejich zakdovn ale nem eme pout kdy 0 a 1, protoe pro dal slice bychom nenalezli kdov slova tak, aby kd byl pre xov , protoe kad binrn slovo m pre x 0 nebo 1. Zvolme tedy f (3) = 00 f (4) = 01. Potom dn dal kdov slovo nem e zanat nulou. Pro dal slice musme zvolit kdov slova zanajc jednikou. Pro slice 5 a 6 zvolme nejdel kdov slova. Poet slov d lky 3, kter zanaj jednikou, je pouze 4. Nem eme tedy zakdovat slice 0 1 2 7 8 9 kdov mi slovy d lky 3. Zvolme proto kdov slova o d lce 4 a potom m eme nal zt napklad tento kd: a 0 1 2 3 4 5 6 7 8 9 f (a) 1000 1001 1010 00 01 1101 1110 1111 1011 1100 Jak je vidt na obr. 6.1, p vodn data jsou transformovna na data koprimovan (zakdovan). -
KOMPRESE (K DOV N!)
-
pvodn data
komprimovan data DEKOMPRESE (DEK DOV N!)
Obr. 6.1: Komprese a dekomprese dat Tento proces oznaujeme jako kdovn. Opan proces, dekdovn, je transformace, kdy komprimovan data jsou dekdovna zpt na p vodn data. Odpovdajc algoritmy jsou naz vny kodr a dekodr. Stupe redukce dat zskan ch jako v sledek kdovn oznaujeme kompresn pomr. Tento pomr m velikost komprimovan ch dat vzhledem k velikosti p vodnch dat. komprimovanch dat Kompresn pomr= Dlka Dlka pvodnch dat Napklad kompresn technika, kde jeden znak komprimovan ch dat odpovd tem znak m p vodnch dat, m kompresn pomr 0,33. 61
6.1.2 Entropie a redundance Entropie je mra mnostv informace. Mjme zdrojov jednotky S = fx1 x2 xn g. Jestlie pravdpodobnost v skytu zdrojov jednotky xi je pi , 1 i n, pak entropie informanho obsahu jednotky xi je Ei = ;log2 pi bit : To znamen, e zdrojov jednotky s vt pravdpodobnost obsahuj m n informace ne jednotky s men pravdpodobnost. Prmrn entropie zdrojov jednotky z S je AE = Pni=1 piEi = ; Pni=1 pilog2 pi bit : Entropie zdrojov zprvy X = xi1 xi2 xi z S + je pak E (X ) = ; Pkj=1 pi log2 pi bit : Pouijeme-li pro zakdovn zdrojov jednotky P xi 1 i n, kdov slovo f (xi) d lky di bit , pak dlka zakdovan zprvy X je l(X ) = kj=1 di bit : Z teorie informace plyne, e l(X ) E (X ). Rozdl R(X ) = l(X ) ; E (X ) = Pkj=1(di + pi log2 pi ) bit
je redundance kdu K pro zprvu X. Prmrn dlka kdovho slova K je AL(K ) = Pni=1 dipi bit : Prmrn redundance kdu K je AR(K ) = AL(K ) ; AE (S ) = Pni=1 pi(di + log2 pi) bit : Kd K je optimln, kdy m minimln redundanci. Kd K je asymptoticky optimln, kdy plat, e pro dan rozloen pravdpodobnost se pomr AL(K )=AE (S ) bl k jednice, kdy se entropie bl k nekonenu. k
j
j
j
j
j
j
6.2 Predikce a modelovn Komprese dat je mon proto, e v datech je velk mnostv redundace zp soben : opakovnm symbol , skupin symbol a slov, nestejnomrnou pravdpodobnost v skytu symbol , zvislostmi mezi sousednmi symboly. Pouit t to redundance znamen pedpovdt, jak bude nsledujc symbol a pout tuto znalost pro kompresi. Predikce nsledujcho symbolu znamen odhadnut pravdpodobnosti v skytu nsledujcho symbolu. Z tohoto d vodu je pouit model dat obsahujc rozloen pravdpodobnost. Obr. 6.2 ukazuje, jak je model pouit pro kdovn a dekdovn.
MODEL
MODEL
data
?
-
KOD"R
-
Pam#, komunikan linka
?
-
DEKOD"R
data
-
Obr. 6.2: Pouit modelu pro kompresi dat Kod r i dekod r mus mt stejn model. Existuj ti zp soby, jak kod r a dekod r mohou pracovat se stejn m modelem: statick , semiadaptivn a adaptivn modelovn. 62
Statick modelovn znamen, e kod r a dekod r pouvaj t model pipraven pedem, bez ohledu na data, kter jsou komprimovna. Protoe statick model nebere v vahu vstupn data, m e b t kompresn pomr daleko hor ne optimln. Semiadaptivn modelovn je postup, kter umouje vytvoen modelu, odpovdajcho charakteru komprimovan ch dat. Vstupn data jsou nejdve petna a z nich je odvozen model. Potom je model uloen spolen se zakdovan mi daty. Nev hodou tohoto postupu je skutenost, e model mus b t uchovn s komprimovan mi daty a m e se stt, e celkov mnostv informace je vt ne bez komprese. Navc mus kod r mt vechna komprimovan data k dispozici a mus prov st dva pr chody: vytvoen modelu a zakdovn. Adaptivn modelovn znamen, e kod r odvozuje model ze vstupnch dat a dekod r odvozuje t model z komprimovan ch dat. Takto vytvoen model dobe odpovd komprimovan m dat m, model nen soust komprimovan ch dat a kod r provd pouze jeden pr chod. Existuje nkolik typ model . Nejjednodu model piazuje kad zdrojov jednotce uritou pravdpodobnost jejho v skytu bez ohledu na jej pozici v datech. V tomto modelu pravdpodobnost P(a) je pravdpodobnost izolovan zdrojov jednotky a. Tento model pouil Morse pro znmou Morseovu abecedu. V t to abeced jsou nejastj psmena v anglitin (e,t) zakdovna pomoc nejkratch kdov ch slov. Lep modely jsou zaloeny na mylence, e pravdpodobnost zdrojov jednotky zvis na nkolika pedchozch zdrojov ch jednotkch. Takov modely s konenm kontextem se naz vaj Markovovy modely. Jestlie prv n pedchozch zdrojov ch jednotek je pouito pro uren pravdpodobnosti nsledujc zdrojov jednotky, pak se jedn o model du n. Nejjednodu model je du 0, protoe nepouv dnou pedchoz zdrojovou jednotku pi uren pravdpodobnosti. Je to model zmnn v e. Modely zaloen na konen ch automatech jsou mnohem obecnj ne modely s konen m kontextem. Tyto modely pedpokldaj, e komprimovan data jsou prvky regulrnho jazyka. Specilnm ppadem konen ch automat jsou automaty s konenm kontextem. Vysvtleme, jakou vlastnost maj automaty s konen m kontextem.
De nice 6.1
Je dn konen automat M = (K T q0 F ): Mnoinu synchronizanch etz automatu M de nujeme takto: S (M ) = fx 2 T : (qi x) ` (qk ") (qj x) ` (ql ") qk = ql pro vechny stavy qi qj 2 K g Synchronizan etzy maj tu vlastnost, e kad synchronizan etz donut pejt automat z libovoln ho stavu do uren ho stavu. Mnoina nesynchronizanch etz je pak de novna takto: N (M ) = fx 2 T : (qi x) ` (qk ") (qj x) ` (ql ") qk 6= ql pro njak qi qj 2 K g:
De nice 6.2
Automat s konen m kontextem je konen automat M , kter m mnoinu nesynchronizanch etz N (M ) konenou. Pravdpodobnost zdrojov jednotky a v modelu s konen m kontextem du n je podmnn pravdpodobnost P (ajx1 x2 : : : xn ), kter zvis na etzu n pedchzejcch zdrojov ch jednotek x1 x2 : : : xn: Pravdpodobnost zdrojov jednotky v modelu zaloen m na konen m automatu je podmnn pravdpodobnost P (ajqi ), kter zvis na stavu qi , ve kter m se automat nachz. V ppad, e modelovan etzy pat do regulrnho jazyka, jsou modely s konen m kontextem a modely pouvajc konen automaty velmi uiten . V ppad, e modelovan etzy pat do bezkontextov ho jazyka, nejsou tyto modely vhodn a je l pe pout bezkontextov ch 63
gramatik. Jedn se zejm na o ppady, kdy se v modelov ch etzech vyskytuj symetrick zvorkov struktury. Bezkontextov gramatika je tveice G = (N T P S ), kde N je konen mnoina neterminlnch symbol , T je konen mnoina terminlnch symbol , P je konen mnoina pravidel tvaru: A ! A 2 N 2 (N T ) a S 2 N je startovac symbol. Derivace v gramatice G, oznaen ), je relace na etzech de novan takto: x1 Ax2 ) x1 x2 kdy A ! 2 P x1 x2 2 (N T ): Tranzitivn a re0exivn uzvr relace ) ozname ) . $etz x 2 T je generovn gramatikou G kdy S ) x. Syntaktick anal za etzu x generovan ho gramatikou G je konstrukce derivace x 2 L(G).
6.3 Reprezentace celch sel Kd je univerzln, jestlie zdrojov jednotky zobraz na kdov slova tak, e pr mrn d lka kdov ho slova je omezena hodnotou c1 AE + c2 , kde c1 a c2 jsou konstanty a AE je pr mrn entropie zdrojov jednotky. Univerzln kd je asymptoticky optimln, kdy c1 = 1. Nyn uvedeme nkter univerzln kdy pro kdovn cel ch sel. Tyto kdy umouj kdovat cel slo x na posloupnost bit Sx a pitom d lka Sx je mrn hodnot sla x. Tyto kdy jsou pouvny pro zakdovn sel vznikajcch pi kompresi pomoc slovnkov ch a syntaktick ch metod.
6.3.1 Fibonacciho k dy Posloupnost Fibonacciho kd je zaloena na Fibonacciho slech du m 2. Fibonacciho sla du m jsou de novna rekurzvn:
F0 = F;1 = : : : = F;m+1 = 1 Fn = Fn;m + Fn;m+1 + : : : + Fn;1 pro n 1: Napklad Fibanocciho sla du 2 jsou: 1,1,2,3,5,8,13,21,.... Kad nezporn cel slo N m binrn reprezentaci tvaru: R(N ) = Pki=0 di Fi kde di 2 f0 1g k N , a Fi (0 i k) jsou Fibonacciho sla du 2. Zajmavou vlastnost reprezentace R(N) je skutenost, e neobsahuje dv jedniky bezprostedn vedle sebe. Fibonacciho kd du 2 pro N je de novn jako F (N ) = d0 d1 d2 dk 1, kde di 0 i k je de novno v e. To znamen, e Fibonacciho reprezentace je reverzovan a je pidna jednika. V sledn binrn kdov slova tvo pre xov kd, protoe kad kdov slovo kon dvma po sob nsledujcmi jednikami, kter se neobjev nikde jinde v kdov m slov. Fibonacciho reprezentace R(N ) pro nkter cel sla jsou uvedeny na obr. 6.3. Doln dek obsahuje hodnotu Fi bitu na i ; t pozici v obvykl m uspodn od vych d k nim. Prav sloupec obsahuje odpovdajc Fibonacciho kdy F (N ). Je dokzno, e Fibonacciho kd du 2 je univerzln pro c1 = 2 a c2 = 3. Nen asymptoticky optimln, protoe c1 > 1. Fibonacciho kdy vych d komprimuj l pe ne kd du 2, ale 64
N
R (N )
F (N ) 1 11 10 011 100 0011 101 1011 1000 00011 1001 10011 1010 01011 10000 000011 100100 0010011 1010100 00101011 21 13 8 5 3 2 1
1 2 3 4 5 6 7 8 16 32
Obr. 6.3: Pklad Fibonacciho reprezentace cel ch sel dn Fibonacciho kd nen asymptoticky optimln. Dle uvedeme Eliasovy kdy, kter jsou asymptoticky optimln. Avak Fibonacciho kdov slova jsou krat ve velk m potenm intervalu (a do N=514228). Tedy Fibonacciho kdy dvaj lep kompresi ne Eliasovy kdy uveden dle, dokud hodnota cel ch sel nen velk.
6.3.2 Eliasovy k dy Elias de noval posloupnost kd , kter zobrazuj cel sla na binrn kdov slova. Nkter z nich jsou universln. Nejjednodu binrn reprezentace cel ch sel se naz v unrn kd a je de novn takto: (N ) = 00 : : : 0} 1 | {z N ;1 Standardn binrn reprezentace je de novna induktivn takto (1) = 1 (N ) = (M )j kde N = 2M + j: Nanetst kd nen jednoznan dekdovateln , protoe nen pre xov . Napklad (5) = 101 = (2) (1) ukazuje tento probl m. Abychom vytvoili kd jednoznan dekdovateln , je teba pidat znak konec slova (#). Pak dostaneme reprezentaci:
(N ) = (N )#: Avak reprezentace je ternrn a ne binrn kd. Existuje modi kace reprezentace oznaovan 0 , kter vznikne nsledujcm postupem. Protoe binrn kd (N ) vdy zan jednikou, m eme ji vynechat a dostaneme : (1) = " (przdn posloupnost) (2N ) = (N )0 (2N + 1) = (N )1: Pak (N ) = (N )#. Elias v kd je kompozice unrnho a binrnho kdu. Kad bit binrnho kdu (N ) je nsledovn bitem unrnho kdu d lky (N ). Protoe prvn bit (N ) je vdy jednika, je mono jej vynechat. V sledkem je kd , ve kter m kad bit (N ) je vloen mezi dvojici bit
z (j (N )j). 0
0
0 0
0
0
0
0
0
65
(1) = 1 (3) = 011 (5) = 00011 (2) = 001 (4) = 00001 (6) = 01001: Bity s pruhem jsou z (N ) a ostatn bity jsou z (j (N )j). Mnoina C = f (N ) : N > 0g = (0f0 1g) 1 je regulrn a proto m e b t dekdovna konen m automatem. Permutace bit v (N ) dv kd (N ) = (j (N )j) (N ) stejn d lky, ale itelnj: 0
0
0
(1) = 1 (3) = 011 (5) = 00101 (2) = 010 (4) = 00100 (6) = 00110. 0
0
0
0
0
0
Protoe posledn bit (j (N )j) je vdy jednika, m e b t pouit jako prvn bit posloupnosti (N ) = 1 (N ). Kd zobrazuje tedy cel slo N na binrn kd, ped kter m pedchz blog2 (N )c nul. Tento kd je jednoznan dekdovateln , protoe celkov d lka kdov ho slova je o jednu vt ne dvojnsobek potu vedoucch nul. Mnoina C = f0k 1f0 1gk : k 0g nen regulrn a dekod r potebuje ta. Kdov slova pro kdy a 0 jsou dlouh pro velk N . D lku (N ) je mon reprezentovat jako (j (N )j) msto (j (N )j). Tento kd je krat pro vt N: Nech (N ) = (j (N )j) (N ). 0
0
0
(1) = (1) = 1 (3) = (2)1 = 0011 (2) = (2)0 = 0010 (4) = (3)00 = 01100: Symboly s pruhem jsou (N ). Dekdovac algoritmus pro (N ) pouv dekod r pro (j (N )j), aby vypoetl j (N )j a pak dv na v stup jedniku nsledovanou poslednmi j (N )j ; 1 symboly, t.j. (N ). Jin representace je kd !. Kdovac procedura m tvar: K := 01 while blog2 (N )c > 0 do begin K := (N )K 1 N := blog2 (N )c end. Pklady v sledk t to procedury:
!(1) = 0 !(4) = 10 100 0 !(15) = 11 1111 0 !(2) = 10 0 !(7) = 10 111 0 !(16) = 10 100 10000 0 !(3) = 11 0 !(8) = 11 1000 0 !(32) = 10 101 100000 0: Prav skupina slic s pruhem je (N ) s v jimkou ppadu, kdy N = 1. Kad pedchzejc skupina je binrn kd d lky nsledujc skupiny zmenen o jedniku. Prvn skupina m d lku 2. Dekod r je podobn jako pro kd . Kd !0 je variantou kdu ! s tm, e prvn skupina m d lku 3.
66
6.4 Statistick metody komprese dat Nejstar statick metoda komprese dat byla navrena v roce 1949 Shannomem, Weaverem a Fanem. Vychz se zadan ho statistick ho rozloen pravdpodobnost zdrojov ch jednotek zaloen m na modelu du 0. Hu%man v roce 1952 vyel ze stejn ho pedpokladu a jeho kd je nejznmj metodou pre xov ho kdovn, kter je minimln v tom smyslu, e dosahuje nejlep kompresn pomr mezi pre xov mi kdy pi pevn zadan ch pravdpodobnostech. V tomto odstavci se budeme zab vat obma metodami a ukeme, jak Hu%manovou statickou metodu lze pev st na adaptivn verzi (algoritmy FGK a V).
6.4.1 Shannon-Fanovo k dovn Algoritmus je zaloen na rekurzivn procedue pidvajc ke kdov mu slovu v kad m kroku jeden bit.
Algoritmus 6.1:
Shannon-Fanovo kdovn Vstup: Posloupnost n zdrojov ch jednotek S -i], 1 i n. V stup: n binrnch kodov ch slov.
begin uspodej zdrojov jednotky v poad neklesajc pravdpodobnosti1 pia vem kdov m slov m przdn etz1 SF-SPLIT(S )
end procedure SF-SPLIT(S )1 begin if jS j 2 then begin rozdl S do posloupnost S 1 a S 2 tak, e ob posloupnosti
end
end
maj piblin stejnou celkovou pravdpodobnost1 pidej ke vem kdov m slov m z S 1 nulu1 pidej ke vem kdov m slov m z S 2 jedniku1 SF-SPLIT(S 1)1 SF-SPLIT(S 2)
Algoritmus kon a vytv pre xov kd.
Pklad 6.2:
Nech (1,1,1,1,3,3,3,3,7) je posloupnost vyjadujc frekvence zdrojov ch jednotek v textu nad abecedou o velikosti n = 9. Piazen pravdpodobnosti jsou (1=23 1=23 1=23 1=23 3=23 3=23 3=23 3=23 7=23): Obrzek 6.4 ilustruje postupnou aplikaci procedury SF-SPLIT Algoritmu 6.1 a v sledn zobrazen f . Kad pre xov kd m eme reprezentovat binrnm stromem. Tyto stromy budeme naz vat kdov stromy. Kdov strom odpovdajc kdu z pkladu 6.2 je na obr. 6.5. D lka kad ho kdov ho slova v Shannon-Fanov kdovn je bu ;log2 pi nebo ;log2 pi + 1, t.j. Algoritmus 6.1 vytv kdov slova splujc podmnku: AE AL AE + 1: Obecn Shannon-Fanovo kdovn nezaruuje, e v sledn kd je optimln. Dal nev hodou je skutenost, e algoritmus vyaduje rozloen pravdpodobnost zdrojov ch jednotek a proto kod r mus st kdovan data dvakrt. 67
zdrojov jednotka pravdpodobnost kdov slovo krok S -1] 1/23 1111 8 S -2] 1/23 1110 6 S -3] 1/23 1101 7 S -4] 1/23 1100 4 S -5] 3/23 101 5 S -6] 3/23 100 1 S -7] 3/23 011 3 S -8] 3/23 010 2 S -9] 7/23 00 Obr. 6.4: Shannon-Fanovo kdovn
u
00 010 011 100 101 1100 1101
u
k dov strom
k dov slova
b
H H
u
1 ;@ 1;; @ 0 @ ; ; @ @ A A A A 1 A 0 1 A0 A AA A
u
1
u
u u u u
1110
S-1]
S-2]
S-3]
S-4]
1111 frekvence
1
1
1
1
HH0 H
b
b 0 b b
u
HH H \ 1 \0 \ \ \
u
b b b
u
u u uu u
Q A 1 AQQQ 0 A Q Q A A 1 A 0 S-9] A AA
S-5]
S-6] S-7]
3
3
3
S-8]
3 7
Obr. 6.5: Shannon-Fan v kd a kdov strom
6.4.2 Hu%manovo k dovn Hu%man navrhl v roce 1952 optimln kdovn pomoc pre xov ho kdu. Navren algoritmus je statick a vyaduje pevn dan statistick charakteristiky v skytu jednotliv ch zdrojov ch jednotek. Originln algoritmus vytv kdov strom, naz van Humanv strom. Podobn jako Shannon-Fan v algoritmus vyaduje i Hu%man v algoritmus dva pr chody. Nov varianty Hu%manova algoritmu jsou adaptivn, co umouje, aby se pravdpodobnosti v skytu zdrojov ch jednotek mnily pi pr chodu daty a odpovdajcm zp sobem se mnil i poten Hu%man v strom. To znamen, e se provd kdovn souasn s rekonstrukc kdov ho stromu. Okamit je zejm , jak tato varianta zlepuje p vodn algoritmus. Nen teba uchovvat kdov strom pro ely dekdovn. Dekod r se +u, charakteristiky zdrojov ch dat pi jejich dekdovn. Je zejm , e jak kod r, tak dekod r mus zat se stejn m potenm stromem. Jednopr chodov metoda m e b t efektivn, protoe poet bit
nutn ch pro zakdovn m e b t men. Dle uvedeme dv verze adaptivnch Hu%manov ch algoritm . 68
6.4.2.1 Statick Hu%manovo k dovn Nejdve uvedeme Hu%man v originln algoritmus zaloen na konstrukci Hu%manova stromu.
Algoritmus 6.2:
Statick Hu%manovo kdovn Vstup: n zdrojov ch jednotek a posloupnost jejich pravdpodobnost p-i], 1 i n, V stup: posloupnost n binrnch kdov ch slov.
begin /* konstrukce Hu%manova stromu */
vytvo list o(p-i]) binrnho stromu pro kadou zdrojovou jednotku i1 /* uzel o jednotky i je ohodnocen pravdpodobnost p-i] */ k := n1 while k 2 do begin najdi dv nejmen nenulov pravdpodobnosti p-r] a p-s], kde r 6= s1 q := p-r] + p-s]1 vytvo uzel o ohodnocen q a hrany -o(q) o(p-r])] a -o(q) o(p-s])] ohodnocen 0 a 11 p-r] := 01 p-s] := 01 k := k ; 1
end end
/* konstrukce kdov ch slov */ ohodnocen hran nulami a jednikami na cest z koene do listu pia zdrojov jednotce i, 1 i n.
Pr mrn d lka kdov ch slov AL zskan ch Hu%manov m algoritmem je stejn jako ven d lka cesty AEPL = Pni=1 d-i] p-i] kde d-i] je d lka cesty z koene do listu i. Je dokzno, e AEPL je minimln pro vechny mon binrn stromy se zadan mi listy. Hu%man v algoritmus tedy vytv pre xov kd s minimln pr mrnou d lkou. Existuj vak optimln pre xov kdy, kter nejsou Hu%manovy (viz pklad 6.4). Uveme nkter poznmky: Nen nutn normalizovat frekvence na pravdpodobnosti, tj. sla z intervalu < 0 1 >. Stejn v sledky dostaneme, pouijeme-li frekvence zdrojov ch jednotek. Ohodnocen hran nulami a jednikami v poad uveden m v algoritmu je jen jedno z mon ch. Obrcen poad vede t na optimln kd. Pouze d lka kdov ch slov je podstatn. Jak Hu%man v, tak Shannon-Fan v kd m e b t generovn v ase O(n) za pedpokladu, e posloupnost zdrojov ch jednotek je uspodan podle jejich pravdpodobnost. Poet uzl v Hu%manov stromu je 2n ; 1.
Pklad 6.3:
Nech posloupnost frekvenc (1,1,1,1,3,3,3,3,7) je stejn jako v pkladu 6.2. Algoritmus 6.2 vytv Hu%man v strom a Hu%man v kd, kter je uveden na obr. 6.6. Pr mrn entropie zdrojov jednotky je 2,869 bit a pr mrn d lka kdov ho slova je 2,840 bit . Hlavn probl m statick ho Hu%manova kdovn spov v tom, e je nutno znt rozloen frekvenc (pravdpodobnost) zdrojov ch jednotek ve vstupnch datech. Toto rozloen je asto 69
11 010 011 100 101 0000 0001 0010 0011
u
k dov strom
k dov slova
b root b b b b b b q16 10 Hq15 13 b LZZ H H L Z HH Z L H HH LL q ZZ q q 4 ;@ 11 6 A 12 6 A 13 A ; @ A A ; @ A ; @ A ; q7 A q8 q9 AA q10 2 A q 5 2@A q6 A A A A A AA q q1 A q2 q3 4
u
u
u
u
u u u u
1
1
1
1
23
u
u u u u u u u
3
3
3
q14
3 7
Obr. 6.6: Hu%man v kd a kdov strom znmo a je pozoruhodn stabiln (nap. v etin nebo v anglitin). Jestlie jsme schopni zskat takov rozloen pro dostaten velk tdy dat, m eme vytvoit tak zvan kdov tabulky s nkolika zobrazenmi. V takov m ppad je mon vytvoit Hu%manovy kdy pedem a uetit as na jejich konstrukci.
6.4.2.2 Vlastnosti Hu%manovch strom Hu%manovy stromy maj nkter zajmav vlastnosti. Existuje-li vce monost pro v br p-r] a p-s], je mono vybrat libovolnou z nich. To znamen, e Hu%man v kd m e b t reprezentovn nkolika binrnmi stromy. Maximln poet takov ch strom je 2n ; 1. Pitom vak jsou nkter kdy jen permutacemi jin ch kd a proto je maximln poet r zn ch Hu%manov ch strom men. V znamnou vlastnost Hu%manov ch strom je tzv. sourozeneck vlastnost. Binrn strom m sourozeneckou vlastnost, kdy 1. kad uzel krom koene m sourozence, 2. uzly mohou b t seazeny v poad neklesajc pravdpodobnosti tak, e kad uzel sousedc v seznamu s njak m uzlem je jeho sourozenec (lev synov budou na lich ch mstech v seznamu a prav synov na sud ch mstech). Napklad strom na obr. 6.6 m uspodn dan posloupnost uzl q1 q2 : : : q16 . Je dokzno, e binrn pre xov kd je Hu%man v kd prv tehdy, kdy jeho kdov strom m sourozeneckou vlastnost. Uveden uspodn pouijeme dle v algoritmu pro adaptivn Hu%manovo kdovn. Hu%man v algoritmus nen jedinou monost konstrukce optimlnho kdu. Libovoln pre xov kd, kter m stejn d lky kdov ch slov, je stejn dobr jako Hu%man v kd. Pro dan seznam frekvenc posloupnost
, kde ni je poet kdov ch slov d lky i, oznauje tdu kd se stejnou d lkou jako Hu%manovy kdy. Uveme optimln kd, kter nen Hu%man v. 70
u
k dov strom
k dov slova
1010
u u u u u u u u u u u u u u u u
1011
3
01 000 100 110 111 0010 0011
0
0;
0
; @
Z
Z
Z
;@ ; @
@1 @ @
@ @1 @ @ A 0 AA1 AA
1
1
Z
0;
; ; @
0
1 7 3
Z Z ;c c ;
@
c1 c
@1 @ @ A 0 AA1 AA
1
c c A A 0 A1 AA
1 3
3
Obr. 6.7: Pre xov kd, kter nen Hu%man v
Pklad 6.4:
Uvaujme opt seznam frekvenc (1,1,1,1,3,3,3,3,7) z pkladu 6.2. Jeden z mon ch pre xov ch kd a jemu odpovdajc kdov strom je na obr. 6.7. Tento kd nen Hu%man v kd, protoe listy kdov ho stromu s frekvenc 1 nejsou ve spolen m podstromu. Tato skutenost odporuje sourozeneck vlastnosti. Kd je vak optimln a pat do tdy < 0 1 4 4 >, co je t tda, do kter pat kd z pkladu 6.2. Shannon-Fan v kd na obr. 6.5 je tak Hu%man v kd. Dal zajmavou skutenost je odhad horn meze redundance Hu%manova kdu. Nech X je zprva a pn je nejvy pravdpodobnost zdrojov jednotky ve zprv X. Pak pro redundanci R(X ) Hu%manova kdu plat R(X ) pn + 0 086: Nkdy je eln vyadovat dal vlastnosti Hu%manov ch kd . Jednou z nich je vlastnost b ti suxovm kdem, co dovoluje dekdovn zprvy opan m smrem. Pre xov kdy majc tuto vlastnost se naz vaj axov kdy. Je zejm , e kad kd s pevnou d lkou kdov ho slova je a xov . Tyto kdy jsou triviln a xov kdy. Netriviln a xov kd je uveden v pkladu 6.4. Je dokzno, e existuje neomezen poet netrivilnch a xov ch kd . Napklad, kdy rozme strom na obr. 6.7. tak, e pidme dva nov syny k listu a ohodnotme hrany nulou a jednikou, dostaneme opt kdov strom a xov ho kdu. Tdy kd obsahujc kdov slova o d lce 1 neobsahuj a xov kdy. A xov kdy maj adu praktick ch aplikac KWIC index. Indexovn textu v textov m vyhledvacm syst mu se provd pro kad slovo K. Nadto je douc, aby lev a prav kontext slova K mohl b t vyhledvn spolen se slovem K. V ppad komprese textu je poadovno, aby se zpracovval zakdovan text od slova K pozptku. vyhledvn vzorku X . Zpracovn vzork tohoto typu se pi vyhledvn asto vyaduje. Dal vlastnost kdu je jeho plnost. Kd je pln , kdy po pidn libovoln ho dalho kdov ho slova vznikne kd, kter nen jednoznan dekdovateln . Hu%manovy kdy jsou 71
pln . 2pln kdy jsou nev hodn v situaci, kdy dojde pi penosu k chyb. Kdy se jeden bit ztrat, pak nejsme schopni v mnoha ppadech se zotavit z chyby pi omezen m zpodn. Pi pouit pln ho a xov ho kdu je mon zpracovat zakdovanou zprvu ve zptn m smru a zskat alespo sten uspokojiv v sledek.
6.4.2.3 Adaptivn Hu%manovo k dovn Nev hodou statick ho Hu%manova kdovn je nutnost ukldn kdov ho stromu spolen s komprimovan mi daty. R zn modi kace vedly na dv v znamn adaptivn verze Hu%manova kdovn naz van FGK a V algoritmy. as na kdovn a dekdovn zdrojov jednotky je u tchto algoritm mrn d lce kdov ho slova. Proto m e kdovn a dekdovn probhat v reln m ase. V obou uveden ch algoritmech se pedpokld, e nen na zatku kdovacho procesu nic znmo o pravdpodobnostech zdrojov ch jednotek. Zkladn mylenka je zaloena na monosti adaptace kdov ho stromu podle zmn pravdpodobnost bhem kdovn. To znamen, e k-t zdrojov jednotka je zakdovna podle informac o k-1 pedchozch zdrojov ch jednotkch. Algoritmus FGK byl navren Fallerem, Gallagerem a Knuthem. Odhadovn pravdpodobnost je nahrazeno potnm frekvenc zdrojov ch jednotek. Algoritmus pouv tae frekvenc a inkrementuje je o hodnotu INCR (obvykle INCR = 1). Tyto hodnoty se pouvaj pro reorganizaci Hu%manova stromu. Zmny ve stromu zp soben zvtenm frekvence v listu se dj ve dvou fzch: 1. Nech T1 je dan Hu%man v strom. Postupn, ponaje od listu, kter odpovd prv zakdovan zdrojov jednotce, a po koen stromu, vymnme podstromy tak, aby kad uzel o, kter m prochzme, byl v uspodn uzl se stejnou frekvenc na poslednm mst. Jestlie takov uzly jsou ok ok+1 : : : ok+m , pak o = ok+m . V sledn strom ozname T2 . 2. Zvtme frekvence v jednotliv ch uzlech od zpracovan ho listu ke koenu o hodnotu INCR. Vzhledem ke zp sobu konstrukce stromu T2 je zachovna sourozeneck vlastnost stromu na konci 2. fze. Sloitj 1. fzi zapeme ve form algoritmu (predcessor(x) je rodi uzlu x ).
Algoritmus 6.3:
Adaptivn Hu%manovo kdovn (jdro FGK) Vstup: Dan Hu%man v strom T 1. V stup: Hu%man v strom T 2.
begin /* prv zpracovvan uzel je v promnn current */ current := o1 while current 6= root do
begin
vym uzel v current (vetn odpovdajcho podstromu) s uzlem o , kter m nejvy poad mezi uzly se stejnou frekvenc1 /* current obsahuje o */ current := predcessor(current) 0
0
end
end
72
s s s s s s s s s s s s s s s s s s s s s s s s s s ss s s ss s , HH HH 21 , HH 11 ,, ,Z Z , d Z , , 10A 11Z A A A A 5 5 5 6A c AA a b A 2 3
11
10
9
7
3
4
1
e
32
a)
11
;@ ; @ 21 11; @ A A 5 AA 6 10 AA11 A b AA d A 3A 5 5A
9
5
2 1 e
f
2 3 c
7
a
5
f
6
2
33
11
;@ ; @ 21 12; @ A A 6 AA6 10 AA11 A b AA d A 4A 5 5A
9
10
6
8
8
5
2 1 e
4
b)
10
6
f
7
2 3 c
8
4
a
c)
Obr. 6.8: Adaptovn Hu%manova stromu
Pklad 6.5:
Je dna mnoina zdrojov ch jednotek fa,b,c,d,e,fg. Hu%man v strom T1 je na obrzku 6.8 a) a byl vytvoen FGK algoritmem (sla oznauj frekvence, tun sla oznauj uspodn). Nsledujc kdovan jednotka je f . f bude zakdovno pomoc stromu T1 jako 1011. Po proveden 1. fze bude v sledn strom T2 podle obr. 6.8 b). 2. fze zp sob zvten frekvenc podle obr. 6.8 c) (INCR = 1). Pi dalm v skytu bude jednotka f zakdovan jako 001. Poznamenejme, e na zatku kdovn dokonce nen znmo, jak zdrojov jednotky budeme kdovat. Tento probl m je mono eit tak, e zavedeme zvltn uzel s frekvenc 0 naz van 0-uzel pro reprezentaci dosud nepouit ch jednotek. Pokud se objev nov jednotka, 0-uzel se rozdl na nov 0-uzel a list pro novou jednotku. Star 0-uzel se stane rodiem obou nov vznikl ch uzl a jeho frekvence bude 1. Ostatn uzly v T2 jsou peslovny. Pi kompresi +nehomogennch, dat nen toto schema pli vhodn , protoe pi kolsajc frekvenci zdrojov ch jednotek se pli vyuv +star ch, informac o jejich frekvenci. Tento probl m m vak jednoduch een: Vynsobit vechny tae koe cientem r < 1 po zpracovn N jednotek. Tento pstup dovoluje vyut loklnch vlastnost kdovan ch dat.
Pklad 6.6:
Jsou dny zdrojov jednotky fa,b,cg a hodnoty odpovdajcch ta 10, 20, 30. Nech N = 30 a po zpracovn N jednotek budou mt tae hodnoty 10 40 40. Jestlie vynsobme tyto hodnoty ta slem r = 0:2, pak budou mt tae hodnoty 2 8 8. Po dalch N krocch budou mt v prvnm ppad hodnoty 30 50 40, ve druh m ppad 22 18 8 (tj. inkrementy jsou 20 10 0). Odpovdajc Hu%manovy kdy jsou: 73
1.ppad a 10 b 0 c 11
2.ppad 0 11 10
Je vidt, e ve druh m ppad pi vtm potu v skytu jednotek a pro tuto jednotku dostaneme krat kdov slovo ne pi pouit globlnch frekvenc. Metoda nsoben frekvenc koe cientem m jednu nev hodu. Vzhledem k nutnosti zaokrouhlovn po nsoben je teba prov st reorganizaci kdov ho stromu. Tuto nev hodu je mono obejt tm, e hodnota INCR se bude postupn zvtovat podle posloupnosti 1 r r2 : : : rn, kde r > 1. V okamiku, kdy nastane peplnn nkter ho z ta , provede se dlen hodnotou rn . Je dokzno, e FGK algoritmus nen nikdy hor ne dvakrt optimln. Kdy ALHS a ALHD jsou po ad pr mrn d lky kdov ch slov pro statick a dynamick Hu%manovo kdovn, pak ALHD 2ALHS : Knuth dokzal, e as potebn jak pro kdovn, tak pro dekdovn, je O(d), kde d je d lka kdov ho slova. Vitter navrhl pravu FGK algoritmu, kter je znma jako V algoritmus. Tento algoritmus m tyto vlastnosti: (1) Poet v mn v 1. fzi algoritmu je nejv e 1. (2) Minimalizuje nejen n X
n X d-i] p-i] ale i d-i] a maxi d-i]: i=1 i=1 (3) ALHD ALHS + 1, a to je optimum mezi vemi dynamick mi Hu%manov mi metodami.
6.4.2.4 Implementan poznmky Reorganizace stromu vyaduje vhodnou datovou strukturu pro jednoduchou implementaci. Jedna z monost je zaveden ukazatel na rodie ze vech uzl krom koene. Uspodn dan sourozeneckou vlastnost vyaduje obousmrn zetzen seznam, kde kad uzel obsahuje dopedn a zptn ukazatel. Pstup k uzl m je mon napklad pomoc indexov tabulky. Tato pm reprezentace Hu%manova stromu vede na velmi sloitou strukturu. Existuje daleko jednodu reprezentace pomoc tabulky, kter dovoluje pm dekdovn kdov ho slova bit po bitu jednm pr chodem v ase O(n).
Pklad 6.7:
Pedpokldejme kdovou tabulku na obr. 6.9 a) a kdov strom na obr. 6.9 b). Odpovdajc dekdovac tabulka je na obr. 6.9 c). Pro kad uzel Hu%manova stromu krom koene je v tabulce jeden dek. Tabulka m proto 2(n ; 1) dk . Prvn sloupec kad ho dku obsahuje bit kdov ho slova. Ve druh m sloupci je pro koncov uzly stromu uvedena zdrojov jednotka. Pro vnitn uzly je ve druh m sloupci uvedeno slo, kter udv, o kolik dk ne je dek pro nsledujc uzel. Hu%manovo kdovn je mono pout tak pro zdrojov jednotky, kter mi jsou slova nad njakou abecedou. Uvedeme metodu, kter je rozenm v e uveden ho postupu. Kdov strom je reprezentovn pre xov m zpisem ve tvaru: (koen, lev podstrom v pre xov m zpisu, prav podstrom v pre xov m zpisu). Kad uzel stromu obsahuje jedniku oznaujc uzel jako list nebo nulu pro vnitn uzel. 74
u
u u u u 0
A0 B 10 C 11
J
A
J 1 J JJ J 0 JJ1 JJ
B
a)
12 0A 0B 1C
C
c)
b) Obr. 6.9: Stromov reprezentace kdov tabulky
Kad vnitn uzel obsahuje adresu prav ho podstromu. Celkem potebujeme nC + (n ; 1)A byt a pam pro n kdovan ch slov. Typicky C =1 byte na d lku slova a A=2 byty na adresu.
Pklad 6.8:
Je dn slovnk podle obr. 6.10. kdov strom:
u
1
u u u u u u u u u u u u
3
0
HH H
@ 0 @1 @ @ c c1 0 c c
5
7
H1 HH H
16
12
22
24
0
0
20
HH HH
@
@1 @ @ %@ 0 % @1 % @
big 001
the 01
on 100
35
HH
27
29
zdroj. jednotka: near kdov slovo: 000
H1 HH
at 1010
32
in 1011
over 11
Obr. 6.10: Hu%manovo kdovn slov Strom v pre xov m zpisu m tvar: adresa: obsah: adresa: obsah:
1 (0,20) 20 (0,35)
3 (0,16) 22 (0,27)
5 7 (0,12) (1,4,near) 24 27 (1,2,on)(0,32)
12 (1,3,big) 29 (1,2,at)
16 (1,3,the) 32 (1,2,in)
35 (1,4,over)
Kdov slova nejsou v t to reprezentaci obsaena. Algoritmus 6.4 pedstavuje dekod r pro pre xovou reprezentaci.
Algoritmus 6.4:
Dekod r pro pre xovou reprezentaci dekdovac tabulky Vstup: Zakdovan data po pedchozm dekdovan m kdov m slovu. V stup: Dekdovan slovo. 75
/* pedpokldejme, e kad uzel je reprezentovn zznamem P -i] s polokami ag a address a i je jeho adresa, A je poet byt potebn ch pro uloen adresy*/
begin k := 11 repeat receive bit1 if bit = 0 then k := k + A else k := P -k] . address1 0ag . value := P -k] . 0ag1 until 0ag . value = 11 Pidej obsah adres k : : : k + P -k] . length { 1 k dekdovan mu v stupu end 6.4.3 Aritmetick k dovn Hu%manovo kdovn je specilnm ppadem aritmetick ho kdovn. Hu%manovo kdovn dv v sledky rovn entropii E (X ), jestlie pravdpodobnosti zdrojov ch jednotek jsou zporn mocniny dvou. V opan m ppad Hu%manovo kdovn je daleko od optima a obsahuje uritou redundanci. Kdy rozdlen pravdpodobnost je velmi nepzniv , pak pr mrn d lka kdu generovan ho Hu%manov m kdovnm m e b t mnohem vt ne optimum dan entropi E (X ). Pi aritmetick m kdovn jsou kdovan data reprezentovna intervalem < 0 1) na ose reln ch sel. Kad zdrojov jednotka zuuje tento interval. Jak se interval zmenuje, tak se poet bit potebn ch pro jeho uren zvtuje. Vysoce pravdpodobn jednotky zmenuj tento interval m n ne mlo pravdpodobn jednotky. To znamen, e vysoce pravdpodobn jednotky pispvaj m n bity do kdov ho etzu. Tato metoda pouv seznam zdrojov ch jednotek a jejich pravdpodobnost. seln osa je rozdlena na subintervaly na zklad kumulativnch pravdpodobnost. Kumulativn pravdpodobnost je de novna tmto zp sobem:
De nice 6.3
Nech a1 a2 : : : an je uspodan posloupnost zdrojov ch jednotek s pravdpodobnost p1 p2 : : : pn . Kumulativn pravdpodobnost cpi zdrojov jednotky ai je souet:
cpi =
i;1 X
j =1
pj :
Pklad 6.9:
Na obr. 6.11 jsou uvedeny pravdpodobnosti zdrojov ch jednotek, jejich kumulativn pravdpodobnosti a subintervaly pro dan zdrojov jednotky. zdrojov jednotka pravdpodobnost pi kumulativn pravdpodobnost cpi d 0,001 0,000 b 0,010 0,001 a 0,100 0,011 c 0,001 0,111
subinterval
<0.000,0.001) <0.001,0.011) <0.011,0.111) <0.111,1.000)
Obr. 6.11: Pravdpodobnosti pro aritmetick kdovn Zmenovn intervalu pi aritmetick m kdovn je gra cky znzornno na obr. 6.12 pro poslopnost aabc. Tato posloupnost je kdovna takto: 76
Vstup:
1.000 c 0.111
a 0.111
" "
" "
a 0.1101
b 0.10101
a
0.011 b 0.001 d 0.000
" "
A
B B
A A A A
AA
0.011
" " "
" " " " "
" B B B BB
0.1001
c 0.1010100 D D D D D D D D D
D D D
@ @ @
0.10011
D D D
0.1010011
Obr. 6.12: Aritmetick kdovn Na zatku mme interval < 0 1). Tento interval je rozdlen na subintervaly podle kumulativnch pravdpodobnost zdrojov ch jednotek. Pro prvn vstupn symbol a je vybrn subinterval < 0:011 0:111). Tento interval se dle rozdl na subintervaly stejn m zp sobem. Pro druh vstupn symbol a je vybrn podinterval < 0:1001 0:1101), jako nov interval. Pokraujeme stejn m zp sobem, pro tet symbol b se vybere podinterval < 0:10011 0:10101), a pro posledn symbol c vstupn posloupnosti se vybere podinterval < 0:1010011 0:1010100). Posloupnost aabc je zakdovna tmto intervalem a jak koliv slo v tomto intervalu ji m e reprezentovat. slo 0:1010011 je vhodn , protoe je nejkratm reprezentantem uveden ho intervalu. Vstupn etz aabc je zakdovn pomoc bitov ho etzce 1010011. Interval m eme reprezentovat jako dvojici (L S ), kde L je doln mez intervalu a S je jeho d lka. Poten hodnoty tchto promnn ch jsou L = 0 S = 1. Bhem kdovn vstupn jednotky se potaj nov hodnoty promnn ch L a S takto:
L := L + (S cpi ) S := S pi kde cpi je kumulativn pravdpodobnost i;t zdrojov jednotky a pi je pravdpodobnost i;t
zdrojov jednotky. Jednm z potencilnch probl m je skutenost, e kd m e b t po chvli pli dlouh na to, aby se s nm mohlo dle pracovat. Natst je mon prov st v stup a zruit st vytvoen ho kdu tak, jak kdovn pokrauje. Napklad po zakdovn druh ho symbolu (a) z pkladu 6.9 je vytvoen interval < 0:1001 0:1101). Bez ohledu na dal zuovn tohoto intervalu, mus v stup zanat jednikou a proto tato st m e b t pedna na v stup a zapomenuta. Tot plat pro druh bit, kter m je nula, po zakdovn tetho symbolu b. Bhem dekdovn se provd opan operace ne pi kdovn. Dekdovn probh ve tech krocch: 1. Zjitn, do kter ho intervalu pat slo N reprezentujc zakdovan etz. 2. Odetn doln meze nalezen ho intervalu od sla N . 3. Dlen v sledku 2. kroku d lkou nalezen ho intervalu.
77
Pklad 6.10:
Nyn ukeme dekdovn kdu 1010011 v pkladu 6.9. Protoe toto slo pat do intervalu < 0:011 0:111), prvn znak mus b t a. Pak odeteme doln mez intervalu 0:1010011 ; 0:011 = 0:0100011 a vydlme v sledek d lkou intervalu pro a: 0:0100011=0:1 = 0:100011: Toto slo pat opt do intervalu < 0:011 0:111): Druh symbol je opt a a proces pokrauje: 0:100011 ; 0:011 = 0:001011 0:001011=0:1 = 0:01011: Toto slo pat do intervalu < 0:001 0:011), a dal symbol je tedy b. 0:01011 ; 0:001 = 0:00111 0:00111=0:01 = 0:111: Toto slo pat do intervalu < 0:111 1:0) a proto dal symbol mus b t c. 0:111 ; 0:111 = 0:0 0:0=0:001 = 0:0: V tomto okamiku je kd dekdovn, ale dekod r m e pokraovat, protoe nula je kd pro libovoln dlouhou posloupnost symbol d. Proto je nutn pout speciln koncov symbol, kter ur konec vstupnch dat. Aritmetick kdovn m tyto hlavn vlastnosti: Zakduje dan data tak, e kd je libovoln blzk entropii AE = ; P p(xi )log2 p(xi ) kde x1 x2 : : : xn jsou zdrojov jednotky. Rozloen pravdpodobnost se m e mnit pi kdovn kad zdrojov jednotky a tedy adaptivn aritmetick kdovn je mon . Je rychl , protoe je nutno pout pouze nkolik operac celoseln aritmetiky pro zakdovn zdrojov jednotky a je k tomu poteba pouze nkolik registr . Cel proces komprese je jasn rozdlen na dv sti: model pouit pro rozloen pravdpodobnost a aritmetick kod r.
6.5 Slovnkov metody komprese dat Slovnkov metody komprese dat jsou zaloeny na pozorovn, e se zejm na v textu nkter slova opakuj. Napklad v t to kapitole se asto opakuj slova jako kdovn, komprese, data. Slovnkov metody kduj slova (podetzy, frze) pomoc ukazatel do slovnku.
De nice 6.4
Slovnk je dvojice D = (M C ), kde M je konen mnoina slov, C je zobrazen, kter zobrazuje M na mnoinu kdov ch slov. L(m) bude oznaovat d lku kdov ho slova C (m), m 2 M ,
v bitech. $etzy v urit m slovnku budou zdrojov mi jednotkami podle na dosavadn terminologie. V br etz do slovnku je mono provdt statick m, semiadaptivnm a adaptivnm zp sobem. 78
6.5.1 Statick slovnkov metody Statick slovnkov metoda pouv slovnk, kter je pedem pipraven. Pro ppravu takov ch slovnk je mono pout dv zkladn metody: Prvn metoda pouv slovnk obsahujc etzy pevn d lky. Tyto etzy d lky n jsme naz vali n ; gramy. Nejastj je pouit digram , tj. dvojic sousednch symbol . V kad m kroku je ve slovnku digram hledna dvojice nsledujcch symbol . Jestlie je nalezena, je zakdovna. V opan m ppad je prvn symbol zakdovn samostatn. Druh pstup k vytven slovnku pouv slova promnn d lky a to takov, kter maj nejvt frekvenci. Toto je zaloeno na zjitn, e asi 50% anglick ho textu je tvoeno asi 150 nejfrekventovanjmi slovy. (Tuto skutenost vyuijeme dle pro implementaci interaktivn metody kontroly sprvnosti textu). Statick slovnkov metody maj nev hody vech statick ch metod. Nejsou schopny reagovat pesn na rozdlen pravdpodobnost v skytu slov v komprimovan ch datech a proto dosaen kompresn pomr nemus b t pli dobr .
6.5.2 Semiadaptivn slovnkov metody Hlavn nev hodu statick ch slovnkov ch metod je mono pekonat vytvoenm slovnku, kter odpovd komprimovan m dat m. Nev hodou tohoto pstupu je skutenost, e slovnk mus b t soust komprimovan ch dat. Dle budeme pedpokldat, e ukazatele do slovnku jsou dvojice (n d), kde n je pozice prvnho symbolu slova ve slovnku a d je d lka slova. Existuj dv monosti implementace semiadaptivn slovnkov komprese dat: 1. Slovnk je prvn st komprimovan ch dat a sm nen komprimovn. Tuto situaci ukazuje obr. 6.13. Komprimovan data jsou tvoena ukazateli do slovnku. P vodn data zskme tak, e v komprimovan ch datech nahradme kad ukazatel pslunou polokou ze slovnku.
SLOVNK
KOMPRIMOVAN DATA
Obr. 6.13: Semiadaptivn slovnkov komprese (1. metoda) 2. Slovnk je prvn st komprimovan ch dat a je sm komprimovn. Tuto situaci znzoruje obr. 6.14. Komprimovan data jsou opt tvoena ukazateli do p vodnho (nekomprimovan ho) slovnku. P vodn data zskme ve dvou krocch: - dekomprese slovnku, - nahrazenm kad ho ukazatele z komprimovan ch dat polokou ze slovnku. Semiadaptivn slovnkov metody jsou v hodn zejm na pro rozshl data, protoe v takov m ppad tvo slovnk jen malou st cel ch komprimovan ch dat. Kompresn pomr m e
KOMPRIMOVAN& SLOVN!K
KOMPRIMOVAN DATA
Obr. 6.14: Semiadaptivn slovnkov komprese (2. metoda) 79
b t lep ne pro statick a adaptivn slovnkov metody. To ovem zle na metod tvorby slovnku. Typick postup pro vytvoen t m optimlnho slovnku je tento: Nejdve se ur frekvence jednotliv ch symbol , dle pak digram , trigram , : : : n-gram
pro urit n. Potom se slovnk inicializuje vloenm jednotliv ch symbol . Dle jsou do slovnku postupn vkldny digramy, trigramy, : : : n-gramy tak, e se vdy zan nejfrekventovanjmi k-gramy (k = 2 3 : : : n). Pi vloen k-gramu do slovnku se sniuje frekvence jeho sloek (dvou(k-1)-gram , t (k-2)-gram , : : : , n samostatn ch symbol ). Jestlie dky sniovn frekvenc se frekvence njak poloky ve slovnku +velmi sn,, pak je tato poloka ze slovnku vylouena. Tento proces pokrauje, dokud nen slovnk pln .
6.5.3 Adaptivn slovnkov metody Velk st adaptivnch slovnkov ch metod komprese dat je zaloena na dvou zkladnch principech, kter popsali Lempel a Ziv ve dvou lncch v letech 1977 a 1978. Tyto metody jsou oznaovny jako LZ77 a LZ78. Metoda LZ77 je oznaovna dle jako metoda posuvn ho okna, metoda LZ78 pouv rostouc slovnk.
6.5.3.1 Metoda posuvnho okna Metoda LZ77 pouv ukazatele do okna pevn d lky, kter pedchz mstu, kter se prv kduje. Existuje ada variant t to metody a dle jsou uvedeny principy nejd leitjch z nich. Nejdve popeme originln verzi metody LZ77.
Metoda LZ77
Na obr. 6.15 je uvedeno posuvn okno, kter je rozdleno na st ji zakdovan ho etzu a na st dosud nezakdovanou. Typick velikost okna je N 8192 byt a velikost sti okna
a b c b a b b a b b a a b a b a c b
zak dovan st
nezak dovan st
Obr. 6.15: Posuvn okno pro nezakdovanou st B se pohybuje v rozmez 10 a 20 byt . Na zatku je prvnch N ; B pozic okna obsazeno mezerami a prvnch B znak textu uloeno v mst pro nazakdovanou st. Jeden krok kdovn probh takto: V okn je vyhledna nejdel pedpona p etzu, kter je v dosud nezakdovan sti. Pokud je takov etz s nalezen s tm, e jeho zatek je v zakdovan sti, pak pedpona p je zakdovna pomoc trojice (i j a), kde i je vzdlenost prvnho znaku podetzu s od hranice mezi zakdovanou a nezakdovanou st okna, j je d lka etzu s a a je prvn znak za pedponou p. Okno je potom v textu posunuto o j + 1 znak doprava. Jestlie dn podetz odpovdajc pedpon nazakdovan sti nebyl nalezen, pak je vytvoena trojice (0 0 a), kde a je prvn znak nezakdovan sti. $etz s m e pesahovat i do dosud nezakdovan sti.
Pklad 6.11:
Na obr. 6.15 je nalezen etz s = aba a ten zan dva znaky ped hranic obou st okna. 80
To znamen, e nejdel pedpona je zakdovna trojic (2 3 c). Okno je posunuto o 3 + 1 = 4 znaky. Dekdovn se provd podobn m zp sobem jako kdovn. Dekod r m stejn okno jako kod r rozdlen na dekdovanou a nedekdovanou st, ale msto hledn nejdel pedpony kopruje st textu odpovdajc pslun trojici z dekdovan sti do nedekdovan sti. Za slovnk lze v tomto ppad povaovat okamit obsah okna. Poet poloek slovnku je jM j = (N ; B ) B t, kde t je velikost abecedy T . Poet bit pro zakdovn ukazatele na poloku ve slovnku je L(m) = dlog2 (N ; B )e + dlog2 B e + dlog2 te: Hlavn nev hodou metody LZ77 je, e bhem kad ho kdovacho kroku mus b t vyhledvna nejdel pedpona dosud nezakdovan ho etzu. Pro tuto operaci je mono pout KMP algoritmus (viz odst. 4.2.1.2).
Metoda LZR
Metodu LZR navrhl Rodeh. Tato metoda je velmi podobn metod LZ77 a na tyto rozdly: 1. LZR pouv strom obsahujc vechny pedpony v dosud zakdovan sti. 2. Je pouita cel dosud zakdovan st jako slovnk. 3. Protoe hodnoty i v trojici (i j a) mohou b t libovoln velk , je pouit kd !0 pro zakdovn cel ch sel (viz odst. 6.3.2). Nev hodou metody LZR je skutenost, e velikost pouit ho stromu m e r st bez omezen. Obvykle je po vyerpn vymezen pamti strom vymazn a jeho konstrukce zan od zatku.
Metoda LZSS
Metodu LZSS navrhl Bell na zklad mylenky Storera a Szymanskiho. V stupem je pi t to metod posloupnost ukazatel a znak . Ukazatel jsou dvojice (i j ), kde i a j maj stejn v znam jako pi metod LZ77. Pedpokldejme, e ukazatel potebuje stejnou pam jako p znak . To znamen, e m smysl vytvet ukazatele jen na podetzy del ne p znak , jinak jsou do v stupu koprovny jednotliv znaky. V stup je tedy sms ukazatel a nazakdovan ch znak , co znamen, e je nutno pout zvltn bit na rozlien, zda se jedn o ukazatel nebo znak. Poet poloek ve slovnku je jM j = t (N ; B ) (B ; p), protoe se uvauj pouze podetzy del ne p. Poet bit pro zakdovn je ( dlog2 te kdy m 2 T L(m) = 11 + + dlog2 N e + dlog2 (B ; p)e jinak protoe d lku d podetzu (druh prvek ukazatele) m eme reprezentovat jako B ; p.
Metoda LZB
Metodu LZB navrhl rovn Bell a je podobn metod LZSS. Rozdl je v kdovn ukazatel . Ukazatele jsou dvojice (i j ), kde i je ukazatel do okna na zatek podetzce, kter se rovn pedpon nezakdovan sti. V nsledujcch dvou situacch je pl tvnm pouit log2 N byt
pro zakdovn i: 1. Okno nen pln . Tato situace nastv na zatku komprese dlouh ho etzu. 2. Komprimovan text je krat ne N . V obou ppadech je mono pout krat kd pro i. Metoda LZB pouv fzovn pi binrnm kdovn. To znamen, e je pouit pre xov kd s rostoucm potem bit pro rostouc hodnoty sel. Pklad tohoto kdovn pro sla od 0 do 8 je uveden v nsledujc tabulce: 81
slo 0 1 2 3 4 5 6 7 8
kd 000 001 010 011 100 101 110 1110 1111
Pouit standardn binrn reprezentace sel v intervalu < 0 8 > vede na tybitov kd. V tomto ppad jsou kdy sel od 0 do 6 tbitov . Pro druhou komponentu ukazatele pouv metoda LZB kd .
Metoda LZH
Metoda LZH byla navrena Brentem jako varianta metody LZSS, ve kter je pro kdovn ukazatel pouito Hu%manovo kdovn. Zatmco metoda LZB pouv jednoduch kdovn pro reprezentaci obou komponent ukazatele, metoda LZH pouv kdovn ukazatel odvozen od rozloen jejich pravdpodobnost. Tento postup vede na lep kompresi, ale pin urit komplikace. Kdovn probh ve dvou pr chodech. Pi prvnm pr chodu je pouita metoda LZSS, ke kter je pidn v poet statistick ch charakteristik. Druh pr chod probh jako statick Hu%manovo kdovn. Hu%man v kd mus b t st komprimovan zprvy.
6.5.3.2 Metody s rostoucm slovnkem Tyto metody zaloen opt na mylence Lempela a Ziva vytv slovnk tak, e do nho vkldaj frze z textu, kter je komprimovn. Opt existuje nkolik variant a nejdve uvedeme metodu LZ78.
Metoda LZ78
Metoda LZ78 rozdluje text na frze. Kad nov frze pidvan do slovnku je vytvoena tak, e ji ve slovnku existujc frze je rozena o jeden symbol. Kad frze je zakdovna indexem jej pedpony a pidan m symbolem. Tato frze je pidna do slovnku a je mono se na ni odvolvat pomoc pslun ho indexu.
Pklad 6.12: vstupn etz a index frze v stup
b
ab
c
ba
bab aa
aaa aaaa
1 2 3 4 5 6 7 8 9 (0 a) (0 b) (1 b) (0 c) (2 a) (5 b) (1 a) (7 a) (8 a)
Bhem komprese je vytven nsledujc slovnk. 82
s s s s s s s s s s 0
1
a
7 8
a
a
Q
b QQ c
2 a 5 b 6
b
3
a
Q
QQ
4
9 Obr. 6.16: Stromov struktura pro metodu LZ78 frze index a 1 b 2 ab 3 c 4 ba 5 bab 6 aa 7 aaa 8 aaaa 9
zakdovan frze
a b 1b c 2a 5b 1a 7a 8a
V stup se skld ze dvou st (index frze, symbol). Frze obsahujc pouze jeden symbol jsou kdovny tak, e prvn st je rovna nule. asov nejnronj st t to metody je vyhledvn ve slovnku. Toto vyhledvn je mono realizovat s pouitm stromov struktury. Strom pro lohu z pkladu 6.12 je uveden na obr. 6.16. Pro kadou frzi je zde uzel obsahujc index. Frze odpovd cest z koene do odpovdajcho uzlu. Dekod r vytv stejnou tabulku jako kod r. Kdy je pamov prostor pro slovnk vyerpn, je slovnk vymazn a proces kdovn a dekdovn zan od zatku.
Metoda LZW
Metoda LZW navrena Welchem je jedna z variant metody LZ78. Jejm v stupem jsou pouze indexy. Vynechn symbol z dvojic v LZ78 je mon dky tmto dvma princip m: Slovnk je inicializovn polokami pro vechny vstupn symboly. Posledn symbol kad frze je prvnm symbolem nsledujc frze.
Pklad 6.13: vstupn etz a b a b c b a b a b a a index frze v stup
4 5 6 7 8 1 2 4 3 5
Bhem komprese je vytvoen tento slovnk: 83
a
a a a
9 10 11 8 1 10
11
frze index a 1 b 2 c 3 ab 4 ba 5 abc 6 cb 7 bab 8 baba 9 aa 10 aaa 11
zakdovan frze
a b c 1b 2a 4c 3b 5b 8a 1a 10a
Dekod r nahrazuje indexy frzemi ze slovnku a vytv stejn slovnk. Probl m, kter se m e vyskytnout, je ppad, kdy vstupn etz obsahuje posloupnost axaxa, kde a je jeden symbol, x je njak etz symbol a frze ax je ji ve slovnku. Kod r najde frzi ax, pid jej index do v stupu a frzi axa vlo do slovnku, nsledujc frze vloen do v stupu bude axa. Dekod r pi dekdovn tohoto kdu nebude mt tento kd jet ve slovnku, protoe nezn dal symbol pro pedchoz frzi. Tento probl m m e b t vyeen, protoe prvn a posledn symbol takov +neznm , frze mus b t stejn a frze je rozenm posledn dekdovan frze. Popsan situace se vyskytuje v pkladu 6.13, kdy je generovn index 8. V tomto okamiku dekod r m ve slovnku pouze index 7. Probl m je vyeen vytvoenm frze 5b=bab=8. Situace +peplnn slovnk, se e statick m zp sobem. To znamen, e v okamiku peplnn slovnku dn dal frze nen pidvna a kdovn pokrauje staticky.
LZC metoda
Metoda LZC je pouita v programu +compress,, kter je soust UNIXov ch syst m . Je zaloena na metod LZW, kter je rozena o dva nov principy. Prvn spov v tom, e ukazatele jsou kdovny pomoc kd s prodluujc se d lkou podle potu frz ve slovnku. Druh princip se uplatn v ppad peplnn slovnku. LZC monitoruje kompresn pomr a jakmile se ten zane sniovat, slovnk se vymae a zan se znovu od potenho nastaven.
LZT metoda
Metoda LZT byla navrena Tischerem a je zaloena na metod LZC. Metoda LZT se li od LZC eenm probl mu peplnn slovnku. Jakmile je slovnk pln , metoda LZT vyluuje ze slovnku frze, kter byly v nedvn minulosti nejm n pouity. Slovnk je organizovn jako samoorganizujc se seznam. Kdy se nkter frze do slovnku vkld pi kdovn, vkld se na zatek seznamu a tm se stv nejposlednji pouitou frz. Bhem vkldn nov frze se posledn frze ze seznamu vyluuje. Navc metoda LZT pouv fzovn pi binrnm kdovn pro kdovn index frz.
LZMW metoda
Metoda LZMW navren Millerem a Wegmanem je zaloena na metod LZT. Hlavn rozdl oproti LZT metod spov v uren nov frze. Zatmco ostatn metody vytv novou frzi pidnm jednoho symbolu k existujc frzi, metoda LZMW konstruuje novou frzi zetzenm dvou posledn zakdovan ch frz.
84
PP P
# ## # #
a###
0
# ## ##
PP P
; b; ; 6
4
b
1
HH c HH H j
@ c @ R @
a;; ;
8
PP c PP
PP P
?
## )
b ? 3 b ? 5
b
10
7
@ b @ R @
13
Obr. 6.17: Strom pro etz abbbcabbcb.
PP q
a b
2
Q Q QQ s ?
9
12
?
11
LZJ metoda
Metoda LZJ navren Jakobssonem se li od vech ostatnch metod z rodiny LZ78 principem konstrukce slovnku. Tento slovnk obsahuje vechny podetzy ji zpracovan ho etzu do njak maximln d lky h. Na zatku jsou do slovnku vloeny jednotliv symboly stejn jako v metod LZW. Metoda LZJ pouv strom pro uloen slovnku. Poten strom se skld z koene pro przdn etz a nslednky pro vechny symboly abecedy. Na obr. 6.17 je uveden tento strom pro abecedu T = fa b cg h = 3 a etz S = abbbcabbcb. Nsledujc tabulka ukazuje, jak probh komprese a jak roste slovnk bhem komprese etzu S = abbbcabbcb. slo frze frze 0 a 1 b 2 c 3 ab 4 bb 5 abb Vstup ab b b c ab b c b 6 bbb V stup 0 1 1 1 2 5 2 1 7 bc 8 bbc 9 ca 10 bca 11 cab 12 cb 13 bcb Jakmile je slovnk pln , mohou b t pouity dv alternativy. Prvn spov v pokraovn komprese statick m zp sobem s vytvoen m slovnkem. Druh alternativa spov ve vynechvn uzl s frekvenc pouit men ne zadan konstanta. V tomto ppad mus uzly obsahovat ta frekvence pouit, kter je inkrementovn pi kad nvtv uzlu bhem vyhledvn frze.
85
LZFG metoda
Metoda LZFG navren Fialou a Greenem pouv tak stromovou strukturu pro uloen slovnku. V tomto stromu jsou hrany ohodnoceny etzy tvoen jednm nebo vce symboly. Tyto etzy jsou uloeny v okn a kad uzel stromu obsahuje ukazatel ukazujc do okna a identi kujc symboly na cest z koene do tohoto uzlu. Uzly jsou rozdleny do dvou typ : vnitn uzly a koncov uzly. Obr.6.18 ukazuje takov strom a okno pro 26 symbol , kter byly zakdovny touto posloupnost: (1,L0) (2,L1) (2,L2) (2,L3) (2,L4) (2,L5)
'$ &% '$ '$ '$ &% &% &% '$ '$ '$ '$ '$ &% &% &% &% &% '$ '$ &% &% (ab)
N2
17,2
(aa: : : )
%
%
L2 7
Q Q
N1
Q
(cc)
Q
Q Q
1,1
(ca: : : )
(ab: : : )
Q s Q
N4 23,2
A A
%
?
N3 17,4
(ab: : : )
Q
?
A (ca) A AU
3
Q
(b)
+
A A
L1
N0 23,0
L0
L3
1
13
(bb: : : )
A A
AU
L5 23
A A (ba: : : ) A A AU
L4 17
okno b c a b a a a b c a a b c c 1 2 3 4 5 6 7 8 9 10 11 12 13 14 okno a b a b c a b a c c b b 15 16 17 18 19 20 21 22 23 24 25 26 Obr. 6.18: Strom a okno v LZFG metod Kad frze je zakdovna pomoc dvojice (d,n), kde d je poet symbol shodn ch s etzem z ohodnocen hrany vedouc do uzlu n a n je identi kace uzlu. Jestlie nsledujc st vstupu je abcb : : :, pak frze abc bude zakdovna pomoc dvojice (N 3 1), protoe frze abc je shodn a do symbolu c s ohodnocenm hran na cest vedouc z koene ke hran mezi vnitnmi uzly N 2 a N 3. V tomto ppad je frze zakdovna dvojic (n d), kde n je identi kace uzlu na konci hrany, na kter dolo k neshod, a d je poet shodn ch symbol na t e hran. Jestlie nsledujc st vstupu je ccabac, pak frze bude ccaba a bude zakdovna pomoc dvojice 86
(3 L3), protoe tato frze se shoduje se symboly na hran (N 0 N 4) a s etzem abc na hran (N 4 L3) { etzec ohodnocujc tuto hranu je neomezen etzec zanajc v okn na pozici 13. Jestlie dal st vstupnho etzu je cacbca, pak prvn ti symboly cac tohoto etzu se neshoduj se dn m etzcem delm ne jeden symbol. V tomto ppad bude etz cac zakdovn jako literl ve tvaru (3 cac), kde prvn slo je d lka literlu. Jakmile je frze zakdovna, nsleduje prava stromu. Kad zakdovan frze se ukld do okna. Literl se vlo do stromu tak, e se vytvo nov list a hrana z koene do tohoto uzlu ohodnocen vkldan m literlem. Pokud byla frze zakdovna pomoc dvojice (d n), je hrana, na kter dolo k neshod rozdlena na dv v mst neshody a zde je vytvoen nov vnitn uzel a jeden nov list jako jeho nslednk. Hrana mezi nov m vnitnm uzlem a listem nen ohodnocena, ale ohodnocen bude vytvoeno a pidno do okna ped tm, ne bude jeho ukazatel pouit. Jestlie v okn nen msto pro novou frzi, pak jsou z okna vyloueny nejstar frze a odpovdajc listy jsou ve strom zrueny.
6.5.3.3 Slovnkov metody s restrukturalizac slovnku Ve vech v e uveden ch adaptivnch slovnkov ch metodch byl slovnk rozen pidnm nov ho slova na jeho konec. Nyn se podvme na metody, ve kter ch se slovnk bere jako seznam a poloky slovnku jsou tedy uspodn . Toto uspodn je zvl uiten , kdy nejvce pravdpodobn slova jsou blzko zatku seznamu. V tomto ppad je mon zakdovat jejich indexy (jsou to mal sla) krtkou posloupnost bit . Pro dosaen hlavnho cle, zejm na umstn nejvce pravdpodobn ch slov blzko zatku seznamu, se pouv nkolik heuristick ch metod pro organizaci seznam . Uvme nkolik z nich: Pesun na zatek. Kdy nalezneme slovo, pesuneme jej na zatek seznamu. Vym'ovn. Pi nalezen slova jej pesuneme o jedno ble k zatku seznamu tak, e jej vymnme s pedchzejcm. Pesun vped o k. Toto je kompromis mezi pesunem na zatek a vymovnm. Pi nalezen slova jej pesuneme dopedu o k pozic. (etnost. Pi nalezen slova je jeho etnost zv ena a je pesunuto na odpovdajc pozici ve slovnku, kter je sestupn setdn podle t to etnosti.
Metoda BSTW
Metoda BSTW je zaloena na heuristice p esun na zatek, kter je pouita pro restrukturalizaci slovnku, a na promnn d lce zakdovn sel. Probl m hledn slova ve vstupu nen popsn a m eme tedy pout mnoho r zn ch pstup . Slovnk je na zatku przdn . Pro zakdovn slova jej kod r hled ve slovnku. Je-li nalezeno na pozici i, je zakdovno jako i. Protoe dekod r m ten sam slovnk je schopen je dekdovat. Kod r i dekod r pesunou dan slovo na prvn pozici ve slovnku a odsunou slova na pozicch 1 2 : : : i ; 1 na pozice 2 3 : : : i. Jestlie slovo nen dosud ve slovnku je pidno na konec slovnku a je zakdovno jako slo n + 1 nsledovan vlastnm slovem (n je aktualn poet slov ve slovnku). Potom se provede p esun na zatek jako v pedchozm ppad.
87
Pklad 6.14:
Pedpokldejme, e chceme zakdovat nsledujc text: KA=D> SOFSEMISTA MUS; KA=D> DEN BD;T CEL> DEN Slovnk se bude mnit takto: KA=D> SOFSEMISTA KA=D> MUS; SOFSEMISTA KA=D> KA=D> MUS; SOFSEMISTA DEN KA=D> MUS; SOFSEMISTA BD;T DEN KA=D> MUS; SOFSEMISTA CEL> BD;T DEN KA=D> MUS; SOFSEMISTA DEN CEL> BD;T KA=D> MUS; SOFSEMISTA Cel zprva bude zakdovna takto: 1 KA=D> 2 SOFSEMISTA 3 MUS; 3 4 DEN 5 BD;T 6 CEL> 3 Je zejm , e se kad slovo v p vodn podob objev v zakdovan form textu pouze jednou. sla jsou kdovna pouitm kdu promnn d lky . Dle je mono pout Fibonacciho kdy pro zlepen komprese. Tato metoda je zejm na v hodn pi kompresi zprv s vtm potem stejn ch slov v loklnm kontextu. Jinak eeno, algoritmus odr lokalitu v skyt slov. Nedvno pouit slova jsou umstna blzko zatku seznamu a jsou tedy kdovna kratmi kdy. Je zejm , e nen jednoduch rozhodnout jak rozdlit text do slov. Napklad etzce jako jsou mnohoslovn v razy mohou b t brny jako slova ve slovnku. BSTW metoda m e b t mnohom lep ne statick Hu%manovo kdovn. Uvaujme slova f1 2 : : : ng a zprvu 1n 2n : : : nn , tj. kad z n slov m n za sebou jdoucch v skyt . Zatmco Hu%manovo kdovn vede ke kd m pevn d lky, tj. zprva vyaduje n2 log2 n bit , zde nm sta pouze mal konstantn mnostv bit na jedno slovo.
Koe cient nedvnosti a intervalov k dovn
Poet r zn ch slov mezi jejich dvmi nsledujcmi v skyty se naz v koe cient nedvnosti. Kdovn pomoc koe cientu nedvnosti je ekvivalentn BSTW metod. Heuristika +pesun na zatek, je jednoduchou implementanc v potu koe cientu nedvnosti. Dal metodou zaloenou na peuspodvn slovnku je intervalov kdovn. Intervalov kdovn reprezentuje slovo celkov m potem slov, kter se vyskytly od jeho poslednho v skytu. Pedpokldejme, e slovnk obsahuje slova a1 a2 : : : an . Ke kad mu slovu ai , je piazeno slo LAST (ai ), kter obsahuje +as, poslednho v skytu ai , 1 i m. Tato hodnota je inicializovna na nulu. Vstupn posloupnost je rozena doleva pidnm vech n frz v opan m poad. Nech vstupn posloupnost je x1 x2 : : : xt : : : xm . Potom intervalov kdovn m eme popsat nsledujcm fragmentem programu: for t := 1 to m do begin fxt = ai g if LAST(xt) = 0 then y(t) = t + i ; 1 else y(t) = t;LAST(xt)1 LAST(xt ) := t end. Poloupnost y1 y2 : : : ym je v stupem kod ru a m e b t dle zakdovna nkter m kdem promnn d lky. 88
D lka intervalu pouit ho v intervalov m kdovn nen men ne koe cient nedvnosti zakdovan ho slova. To znamen, e kdovn pouije m n bit na jedno slovo ne intervalov kdovn. Slov m objevujcm se v krtk m seku zprvy bude opt piazen krat kd. Navc nen nutn udrovat slovnk slov, sta seznam index jejich poslednch v skyt .
6.6 Syntaktick metody Syntaktick pstup ke kompresi dat je v hodn , kdy zprva nle k njak mu formlnmu jazyku a jestlie je mon vytvoit gramatiku popisujc tento jazyk. Pkladem takov ch jazyk
jsou programovac jazyky. Proto m e b t syntaktick pstup v hodn pro kompresi program . Program m e b t reprezentovn derivanm stromem a mnoinou identi ktor a konstant. Zamme se na kompresi derivanch strom . Pro kompresi identi ktor a konstant je mon pout napklad slovnkov metody. Existuj dv metody zakdovn derivanch strom : 1. derivan kdovn, 2. analytick kdovn.
6.6.1 Derivan k dovn Derivace etzu v dan gramatice se naz v levou (pravou), jestlie v kad m kroku derivace je neterminl stojc nejvce vlevo (vpravo) ve vtn form nahrazen pravou stranou gramatick ho pravidla. Derivan strom etzce w je mon reprezentovat v linern form levho rozkladu, co je posloupnost sel pravidel gramatiky pouit ch pi lev derivaci etzce w. Podobn prav rozklad w je pevrcen posloupnost sel gramatick ch pravidel pouit ch pi prav derivaci w. Pro dan w je prav rozklad permutac lev ho rozkladu a nikoliv pouh m pevrcenm posloupnosti sel. Standardn pstup k slovn pravidel je pouit globlnch sel pravidel, co znamen, e kad pravidlo gramatiky m sv uniktn slo. Avak nen nutn pout tchto globlnch sel pravidel v lev m nebo prav m rozkladu. Protoe neterminln symbol, kter je pepisovn v lev nebo prav derivaci, je znm pedem, sta identi kovat pouze pravidlo pouit pro tento neterminl. Toto slovn se naz v lokln slovn. Jestlie existuje pouze jedno pravidlo pro dan neterminl, nen teba ho kdovat v bec.
Pklad 6.15:
Nech G1 = (fS Ag fa bg P1 S ) je bezkontextov gramatika obsahujc nsledujc pravidla s globlnmi sly v hranat ch zvorkch a loklnmi sly v kulat ch zvorkch: -(0) ] (0) S ! AS -(1) ] (1) S ! -(2) ] (0) A ! a -(3) ] (1) A ! b Lev derivace etzce abab je
S ) AS ) aS ) aAS ) abS ) abAS ) abaS ) abaAS ) ababS ) abab:
Lev rozklad vyjden pomoc globlnch sel je 020302031. Tent lev rozklad vyjden pomoc loklnch sel je 000100011. Pi pouit globlnho slovn jedno slo m e b t zakdovno pomoc 2 bit a celkov poet bit je 18. Pi pouit loklnho slovn sta celkem 9 bit . Pro bezkontextovou gramatiku m eme nal zt mnoho ekvivalentnch gramatik. Ty mohou mt odlin vlastnosti vzhledem k zakdovvn derivanch strom . 89
Pklad 6.16:
Gramatika G2 = (fS g fa bg P2 S ) s pravidly -(0)] S ! aS -(1)] S ! bS -(2)] S ! je ekvivalentn gramatice G1 . $etzec abab m e b t zakdovn pomoc lev ho rozkladu 01012 v gramatice G2 .
6.6.2 Analytick k dovn Analytick kdovn znamen zaznamenn posloupnosti rozhodnut proveden ch syntaktick m analyztorem. Pedpokldme, e ten je seznmem s hlavnmi principy LR anal zy.
Pklad 6.17:
LR automat pro gramatiku G1 z pkladu 6.15 je na obr. 6.19.
#:
A
S ! :S S ! :AS S!: A ! :a A ! :b
A:
S1 :
0
?
A ?
S
-
a b
b-:
a:
A ! b:
S
0
6
b a
S
?
S2 :
?
A ! a:
6
S ! A:S S ! :AS S!: A ! :a A ! :b
! S:
S ! AS: Obr. 6.19: LR automat pro gramatiku G1
Analyztor je nsledujc: stav operace analyztoru v stupn kd # pro a:p esun a 0 pro b:p esun b 1 jinak :redukce pomoc S ! 2 S1 p ijet A pro a:p esun a 0 pro b:p esun b 1 jinak:redukce pomoc S ! 2 a redukce pomoc A ! a b redukce pomoc A ! b S2 redukce pomoc S ! AS 90
Pro etzec abab LR analyztor provede tuto posloupnost krok : zsobnk # #a #A #Ab #AA #AAa #AAA #AAAb #AAAA #AAAAS2 #AAAS2 #AAS2 #AS2 #S1
vstup operace v stupn kd abab p esun a 0 bab redukce A ! a bab p esun b 1 ab redukce A ! b ab p esun a 0 b redukce A ! a b p esun b 1 redukce A ! b redukce S ! 2 redukce S ! AS redukce S ! AS redukce S ! AS redukce S ! AS p ijet
Tato posloupnost krok m e b t zakdovna posloupnost stav navtven ch bhem rozkladu, co je #aA bA aA bA S2 S2 S2 S2 S1 . Stavy a b S1 S2 mohou b t vynechny, protoe v nich nen dn rozhodovn. Jen ve stavech # a A se provd njak rozhodovn a proto je v sledn zakdovn 01012.
6.7 Kontextov modelovn Komprese dat je tak dobr, jak dobr je pouit model dat. Model dat zaloen na pravdpodobnostech izolovan ch zdrojov ch jednotek je velmi jednoduch , ale nen pli vhodn , pokud poadujeme dobrou kompresi. Proto se pro lep modelovn dat pouvaj kontextov modely.
6.7.1 Konen kontextov modely Konen kontextov modely, uveden v odstavci 6.2.1, uruj pravdpodobnost zdrojov jednotky s pouitm nkolika pedchozch zdrojov ch jednotek. Jestlie je pouito prv n pedchozch zdrojov ch jednotek, potom se jedn o model du n. Typick d lka kontextu je v rozsahu od 1 do 10 zdrojov ch jednotek. Adaptivn modelovn s konen m kontextem spov v uren pravdpodobnost zdrojov ch jednotek dosud peten ch ze vstupu. Pro vechny zdrojov jednotky mus b t de novny njak poten pravdpodobnosti. Konstrukce modelu zan s potenmi pravdpodobnostmi, kter nejsou vzny na zdrojovou zprvu. Bhem ten zprvy je vytven model tak, e odr strukturu zdrojov zprvy. Existuj dva typy konen ch kontextov ch model . Prvn pouv kontext pevn d lky. Pokud pouijeme krtk kontext, potom komprese nebude dobr, protoe k odhadnut pravdpodobnosti bude pouita pouze mal st ze struktury zdrojov zprvy. Pokud pouijeme dlouh kontext, komprese bude lep, ale bude nutn zpracovat a uloit znan mnostv informac. Tento rozpor m e b t een pouitm tzv. kombinovanho p stupu, kde jsou kombinovny kontexty r zn ch d lek k pedpovzen pravdpodobnosti. Obecn mechanismus t to kombinace je zaloen na piazen vhy kad mu modelu du n. Potom celkov pravdpodobnost jednotky je urena jako ven pravdpodobnost.
91
Nech x je nsledujc zdrojov jednotka, pn(x ) pravdpodobnost x v konen m kontextov m modelu du n, wn je vha modelu n, m je d nejvyho modelu. Vha mus b t normalizovna takto: m X wn = 1: n=0
Pravdpodobnost zdrojov jednotky x v kombinovan m modelu je
p(x ) =
m X
n=0
wn pn (x ):
Jsou zde dva mon pstupy, jak de novat vhu. Prvn monost je piadit pevnou mnoinu vah model m r zn ch d . Druhou monost je potat vhy bhem urovn adaptivnho modelu. Existuje nkolik metod, jak pidlit pravdpodobnosti ke zdrojov m jednotkm, kter se poprv objev ve zdrojov zprv. Nejjednodu procedura je zaloena na mylence, e pravdpodobnosti vech dosud nepouit ch jednotek v konen m kontextu jsou stejn . Poten pravdpodobnost dosud nepouit jednotky m e b t urena nsledujcm vztahem: e = C 1+ 1 n kde n je d modelu a Cn uruje, kolikrt byl konen kontext pouit. Smen modely jsou velmi nron na as a pam.
6.7.2 Modely zaloen na konench automatech Konen kontextov modely jsou specilnm ppadem model zaloen ch na konen ch automatech. Podobn jako jin typy model , model zaloen na konen ch automatech m e b t optimalizovn nebo vytven bhem zpracovn zdrojov ch dat. Takov to modely jsou vytveny adaptivnm zp sobem a mohou mt v hody oproti ostatnm adaptivnm model m.
6.7.2.1 Automaty s konenm kontextem Nejdve uvedeme postup vytven konen ho automatu z k-tic. Nech mme mnoinu k-tic L = fp1 p2 : : : pm g: Pro kadou k-tici vytvome stav automatu. Potom nsledujcm zp sobem vytvome pechody. Kdy pi = ayi a pj = yib, kde a a b jsou zdrojov jednotky, potom pj 2 (pi b). Potom je ke kad mu pechodu pidna pravdpodobnost.
Pklad 6.18:
Mjme mnoinu L = faa ab ba bbg a k = 2. Konen stavov automat je na obr. 6.20. V sledn automat m e b t velmi sloit (m e mt velk mnostv stav ) v ppad, e mnoina L m mnoho prvk . Nicm n redukce potu stav m e b t provedena slouenm nkter ch stav . Dva stavy mohou b t sloueny, pokud maj pechody pro stejn symboly do stejn ch stav . V naem pkladu mohou b t sloueny pry stav (aa ba) a (ab bb). Redukovan automat je na obr. 6.21. Konen automat vytvoen touto metodou m e b t aktualizovn inkrementln. Pedpokldejme, e se na vstupu objev nov zdrojov jednotka. Ta vytvo novou k-tici s novou jednotkou na jeho konci. Pokud je k-tice nov, potom je vytvoen nov stav s pslun m pechodem do nho. Pechod z tohoto stavu je vytvoen bhem zpracovn nsledujc jednotky. Potom m e b t automat redukovn pouitm stejn ho principu popsan ho v e. 92
a
aa
b
ab
1 PP b#### PPb # PP # 6 ? PP ## q a iP P # b # a PP a # # ? PP ## PP ## )
bb
?
ba
Obr. 6.20: Konen automat pro mnoinu pr L = faa ab ba bbg b a b - ab aa - ba bb a Obr. 6.21: Redukovan konen automat
6.7.2.2 Dynamick Markovovo modelovn Dynamick Markovovo modelovn navrhl Horspool a Cormack a je kombinac Markovova modelu s aritmetick m kdovnm. Zan s jednoduch m potenm konen m automatem a pidv do nho nov stavy pomoc vytven kopi stav . K pechod m v konen m automatu jsou pidny tae frekvenc. Tyto tae ukazuj, kolikrt byl pslun pechod pouit. Ukame vytven kopi stav na pkladu.
Pklad 6.19:
Na obr. 6.22 je uveden fragment konen ho automatu. Pedpokldejme, e pechod ze stavu u do stavu t m vysokou hodnotu tae frekvenc. Pro stav t se vytvo jeho kopie t'. Pechod ze stavu u do stavu t je pesmrovn do stavu t' piem ostatn pechody do stavu t z stanou stejn .
u
PP P
v
w
PP PP P
# ## # #
##
P q P 1 # ##
t
0
XXX
XXX
1
x
XXX z X
y
Obr. 6.22: Fragment konen ho automatu u v
w
XXX X
XX z X
t'
XX z X :
t
XXX X
0
:
1 # # PP##0# #PP ## q P 1PP## PP P
1
x
y
Obr. 6.23: Konen automat pro vytvoen kopie stavu Dle se vytvo pechody ze stavu t' do stav x a y. V sledn automat je na obr. 6.23. 93
# " ! a,b,: : :
Obr. 6.24: Poten jednostavov model Posledn otzka se t k pravy ta frekvenc pro nov vytvoen pechody. ta frekvence pechodu ze stavu u do t' z stane stejn jako dve. tae frekvenc pechod ze stavu t' do stav x a y jsou proporciln rozdleny podle ta pechod ze stavu u do t' a ze stav v a w do stavu t. Jako iniciln modely mohou b t pouity r zn konen automaty. Nejjednodu z nich je jednostavov automat podle obr. 6.24. Existuj vak jin modely jako ady, stromy, pletence. Avak je dokzno, e bez ohledu na pouit iniciln model jsou vechny dynamick Markovovy modely modely s konen m kontextem.
94
7 Kontrola sprvnosti textu Pi pprav text v iv ch jazycch pomoc potae s pouitm nejr znjch textov ch syst m se velice brzy objevila otzka monosti automatick kontroly sprvnosti textu. Zaaly proto vznikat r zn syst my na takovou kontrolu. Probl m, kter kontroln syst m e, je velmi jednoduch . Je dn textov soubor a je teba urit slova, kter jsou nesprvn. Kad slovo je mono povaovat za bod ve vcerozmrn m prostoru posloupnost psmen. Ne kad posloupnost psmen je sprvn slovo a kontroln syst m mus urit, zda posloupnost psmen je nebo nen sprvn slovo. Pitom je teba minimalizovat tyto dva druhy chyb: 1. indikace, e sprvn slovo je nesprvn , 2. indikace, e nesprvn slovo je sprvn . Po nalezen nesprvn ho slova je mono v prostoru slov hledat nejbliho souseda, nejbli sprvn slovo. Pi implementaci tohoto syst mu je teba vyeit otzku: Co je slovo? Odpov se zd jednoduch: Je to posloupnost psmen oddlen omezovai. Omezovae jsou: mezery, rky, teky, dvojteky, stednky, vykinky, otaznky atd. Vtinou je zejm , co lze povaovat za psmeno a co za omezova. Musme vak uvit, kam zaadit slice, pomlky a apostrofy. Posloupnosti znak , kter obsahuj slice, se obvykle neuvauj. To se t k jak sel, tak posloupnost, ve kter ch se vyskytuj slice. Rozhodnut, zda takov posloupnosti jsou slova nebo ne, je nejl pe ponechat uivateli. Pomlky se obvykle povauj za omezovae. V mnoha jazycch se toti pouvaj k vytven sloen ch slov (nap. v anglitin context-free) nebo k oddlen stic (v etin -li) apod. Dle se pomlky pouvaj na rozdlovn slov na konci dku. Tento druh pouit pomlek je vhodn zakzat, protoe jej nen obecn mon rozliit od jin ch ppad pouit pomlek. Zaazen apostrof mezi psmena nebo omezovae je zvisl na pouit m jazyku. V anglitin se apostrofy pouvaj jako sousti slov (don't, I'd, King's, kids'). V etin se apostrofy v t to funkci nepouvaj. Z toho plyne, e pro anglitinu je apostrof psmeno, pro etinu omezova. Dal probl m je otzka mal ch a velk ch psmen. Vtina syst m automaticky pevd psmena na jeden typ (mal nebo velk). Tento postup m e ale narazit na nkter probl my. Jednm z probl mov ch ppad jsou jm na. Jestlie nap. jm no Richta pevedeme na mal psmena, dostaneme slovo richta, kter bude povaovno za chybn , a nejbli sprvn slovo bude rychta. Dalm probl mem jsou zejm na v potaov literatue, slova, kter se vdy p velk mi psmeny (nap. FORTRAN), a zkratky (nap. IBM). Jednou z monost een tohoto probl mu je vynechat tato slova pi kontrole, protoe jsou to jm na nebo obecn uvan zkratky. V zkum v t to oblasti byl zahjen piblin v roce 1957, ale prvn syst m na kontrolu textu byl syst m SPELL pro pota DEC-10 vytvoen v roce 1971. Tento syst m a jeho modi kace jsou pouvny dodnes.
95
7.1 Kontrola textu pomoc frekvennho slovnku Nejjednodu princip kontroly sprvnosti textu je zaloen na vytvoen jeho frekvennho slovnku. Postup je velice jednoduch : 1. Vytvome frekvenn slovnk, co je posloupnost dvojic (slovo, poet v skyt ). 2. Frekvenn slovnk seadme podle potu v skyt v poad od nejm n ast ch slov k nejastjm. 3. Na zatku takto setdn ho frekvennho slovnku najdeme slova: a) kter jsou nesprvn, b) kter jsou velice dk. Poten st frekvennho slovnku prohl dneme a urme nesprvn slova. Metoda kontroly textu pomoc frekvennho slovnku m dv zkladn nev hody: 1. vyaduje prohlen frekvennho slovnku, 2. vede k probl mu pi odhalovn systematick ch chyb. Pesto se v literatue uvd, e tento typ kontroly byl pouit pi pprav knihy Computer Organization and Assembly Language Programming (Academic Press, 1978). V t to knize bylo pouito 156134 slov (5649 r zn ch slov) a v sledkem bylo, e v n nen dn (znm) chyba.
7.2 Kontrola textu pomoc dvojit ho slovnku Pouit slovnku sprvn ch slov je dal stupe pi konstrukci kontrolnho syst mu. Je zejm , e takov slovnk je znan rozshl a proto nen mon postupovat tak, e by se kad slovo kontrolovan ho textu hledalo ve slovnku. Proto se postupuje takto: 1. Vytvome seznam vech r zn ch slov v kontrolovan m textu (slovnk textu). 2. Seadme tento seznam podle abecedy (pedpokldme, e tak je seazen i slovnk). 3. Kad slovo v setdn m seznamu hledme ve slovnku: a) jestlie je slovo nalezeno, je sprvn , b) jestlie nen slovo nalezeno, pak je vloeno do v stupnho seznamu. 4. Vytiskneme seznam slov, kter nebyla nalezena ve slovnku. Tento postup vyaduje pouze jeden pr chod slovnkem a proto je podstatn rychlej ne hledn kad ho kontrolovan ho slova ve slovnku. Nejvt st tohoto postupu je slovnk. Je zejm , e run vytvoen slovnku je nron a rozshl prce. Slovnk je mono vytvoit automaticky takto: 1. Zaneme provdt kontrolu s przdn m slovnkem. 2. Sprvn slova se objev jako soust v stupu (viz bod 4. kontrolnho algoritmu). 3. Z v stupnho seznamu vynechme chybn slova a vlastn jm na. 4. Pidme sprvn slova do slovnku. Tmto postupem je mono vytvoit slovnk, ani bychom napsali jedin slovo. V t to souvislosti je teba uvit rozsah slovnku. Pro jednoho uivatele nebo pro malou skupinu uivatel sta slovnk obsahujc 10 000 slov. Velk slovnk, eknme 100 000 slov, jednak zpomaluje kontrolu a pak tak svd ke vkldn archaick ch, nepli frekventovan ch a tak nesprvn ch slov. Pro vt skupinu uivatel je nutno zdit funkci administrtora slovnku, kter sm vkldat nov slova a vynechvat slova uvan velice zdka. Jednm z pstup , jak udret velikost slovnku v pijateln ch mezch i pro vt skupinu uivatel je vytvoen nkolika dlch slovnk . Jeden z nich tvo spolen zklad a ostatn speciln slovnky pokr vaj slovn zsobu v urit m oboru. Pi kontrole textov ho souboru se vytvo pracovn slovnk spojenm zkladnho slovnku a jednoho i nkolika specilnch slovnk . Speciln slovnky mohou b t udrovny administrtorem slovnku nebo pmo uivateli. 96
Prv popsan postup kontroly textu pomoc dvojit ho slovnku m dv nev hody. Pedn se jedn o operaci, kter je asov nron a nehod se pro interaktivn pouit. Druhou nev hodou je ztrta kontextu. V sledkem prce je seznam slov, kter nejsou ve slovnku, bez jak koliv informace o jejich umstn v kontrolovan m souboru. Proto je nutno chybn slova hledat v souboru pomoc editoru a pitom nen mono pout operaci nahra etzec etzcem, protoe v textov m souboru jsou slova zapsna s pouitm mal ch i velk ch psmen a dle chybn slovo m e b t st sprvn ch slov.
7.3 Interaktivn kontrola textu Pro interaktivn zp sob prce je nutno pout tento postup: 1. Zadn specilnch slovnk , kter budou pouvny. 2. Kad slovo souboru je hledno ve slovnku. Kdy nen nalezeno, uivatel dostane dotaz, co udlat. Tento syst m m e provdt napklad tyto operace: 1. Nahra): Neznm slovo je vynechno ze souboru a uivatel je dotazovn na sprvn slovo. 2. Nahra) a zapamatuj: Neznm slovo je nahrazeno sprvn m, kter zadal uivatel, a vechna dal pouit tohoto slova jsou tak nahrazena nov m slovem. 3. Ponech: Neznm slovo je povaovno za sprvn (v dan m kontextu) a je ponechno. 4. Ponech a zapamatuj: Neznm slovo je ponechno v textu a vechna jeho dal pouit jsou povaovna za sprvn. 5. Editace: Pechod do stavu, kdy je mono soubor editovat. Je zejm , e tento syst m umouje ukzat kontext a msto v souboru, kde se neznm slovo vyskytuje, a dovoluje prov st okamit ppadnou opravu. Probl m, kter nen een, je asov nronost operace vyhledvn kad ho slova ve slovnku. V tomto ppad jsou poadavky na syst m jet vt oproti principu zaloen m na dvojit m slovnku, protoe kad slovo kontrolovan ho textu je hledno ve slovnku. Proto je zkladnm poadavkem takov organizace slovnku, kter dovoluje velice rychl vyhledvn. Uveme nkter mon organizace slovnku. Rozptlen: Program SPELL pouv rozptylovou funkci
h(L1 L2 : : : LN ) = (L1 26 + L2 ) 10 + min(N ; 2 9) Tato funkce m stejnou hodnotu pro vechna slova, kter maj stejn prvn dv psmena a stejnou d lku. Stromy: Z koene stromu vychz 26 hran odpovdajcch jednotliv m psmen m do 26 uzl . Z kad ho uzlu pak vychz hrany podle mon ch druh ch psmen sprvn ch slov. Z dalch uzl vychz hrany podle tetch psmen atd. Zvltnm bitem v uzlu je oznaen mon konec sprvn ho slova. Tento zp sob vyaduje pro slovo o d lce N pr chod stromem o N rovn a test bitu "konec slova". Pouit hierarchickho slovnku: Tato metoda je zaloena na zjitn, e mal poet slov je v textu pouvn s velmi vysokou frekvenc. Pro anglitinu napklad plat, e slovnk o 134 slovech sta ke kontrole 50% slov v textu. Dle bylo zjitno, e v urit m textov m souboru nen pouita cel slovn zsoba, ale sta pomrn mal slovnk. Z tchto vah plyne v hodnost trovov ho syst mu podle obr. 7.1, kde jsou uvedeny rozsahy slovnk a frekvence slov vyhledvan ch v jednotliv ch slovncch. Hledn v tomto trovov m slovnku se provd takto: 1. Prohledvn mal ho slovnku velmi frekventovan ch slov. Jestlie slovo nen nalezeno, pejdi na 2., jinak konec. 97
2. Prohledvn slovnku slov, ji dve v textu pouit ch. Jestlie slovo nen nalezeno, pejdi na 3., jinak konec. 3. Prohledn kompletnho slovnku. Jestlie je slovo nalezeno, pidej ho do slovnku slov pouit ch v textu a konec. Jestlie slovo nen nalezeno, jedn se o chybn slovo. Kompletn slovnk (uloen nap. na disku) 20.000 slov Slovnk slov pouit ch v kontrolovan m textu 2.000 slov Slovnk velmi frekventovan ch slov 200 slov
5%
45%
50%
Obr. 7.1: Hierarchick uspodn slovnku Vzhledem k r zn frekvenci prohledvn jednotliv ch slovnk je mono volit vhodn datov struktury umoujc rychl vyhledvn pi pimen ch nrocch na pam.
7.4 Kontrola textu zaloen na pravidelnosti slov Metoda zaloen na pravidelnosti (regularit) slov vychz z v zkumu frekvence v skytu dvojic psmen (digram ) a trojic psmen (trigram ) v jazykov m textu. Jestlie mme abecedu o 28 znacch (psmena, mezera, pomlka), pak existuje 282 (=784) digram a 283 (=21952) trigram . Frekvence tchto skupin psmen je ovem men. V anglick m textu se pouv jen asi 70%(=550) digram a 25%(=5000) trigram , s velice r znou frekvenc. Jestlie slovo obsahuje nkolik velice dk ch digram nebo trigram , je pravdpodobn chybn . Na t to skutenosti je zaloena cel ada metod kontroly textu. Zde uvedeme metodu zaloenou na +koe cientu podivnosti,. Koe cient podivnosti trigramu xyz zvis na relativn frekvenci digram f (xy) a f (yz ) a trigramu f (xyz ) takto: KPT = -log(f (xy) ; 1) + log(f (yz) ; 1)]=2 ; log(f (xyz ) ; 1)
Poznmka: log(0) je de novn pro tuto funkci jako ;10. Pro slova se koe cient podivnosti spot jako
v u n uX KPS = t (KPTi ; SKPT )2 i=1
kde KPTi je koe cient podivnosti i-t ho trigramu a STPT je stedn hodnota koe cientu podivnosti vech trigram obsaen ch ve slov. Pro slova, kter jsou chybn, vychz tento koe cient vysok a proto sta setdit slova podle koe cientu podivnosti a na zatku budou slova s velkou pravdpodobnost chyb. 98
Literatura -Adam89] Admek, J.: Kdovn. SNTL { Sttn nakladatelstv technick literatury, Praha, 1989. -Aho74]
Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms. Addison-Wesley, 1974.
-Aho75]
Aho, A.V., Corasick, M.J.: E!cient string matching: an aid to bibliographic search. Communications of the ACM, Vol.18, No.6., June 1975, pp.333-340.
-Aho79]
Aho, A.: Pattern matching in strings. Proceeding of the Symposium on Formal Language Theory, University of Santa Barbara, December 1979, pp.325-347.
-Bell91]
Bell, T.C., Cleary, J.G., Witten, I.H.: Text compression. Prentice Hall, Englewood Cli%s, N.J., 1991.
-Bent86]
Bentley, J.L., Sleator, D.D., Tarjan, R.E., Wei,W.K.: A locally adaptive data compression scheme. Communications of the ACM, Vol.29, No.4, April 1986.
-Blo86]
Bloch, M., Scheber, A.: Textov bzy dt. Sbornk refert semine SOFSEM'86, Liptovsk Jn, 2VT UJEP Brno a JMF, 1986, pp.47-80.
-Book90]
Bookstein, A., Klein, S.T.: Compression, Information Theory, and Grammars: A Unied Approach. ACM Transactions on Information Systems, Vol.8, No.1, Jan. 1990, pp.27 { 49.
-Boye77]
Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Communications of the ACM, Vol.20, No.10, Oct.1977, pp.262-272.
-Comm79] Commentz-Walter, B.: A string matching algorithm fast on the average. Proceedings of the 6th International Colloquium on Automata, Languages and Programming, Springer-Verlag, 1979, pp.118-132. -Corm84]
Cormack, G.V., Horspool, R.N.S.: Algorithms for adaptive Human codes. Information Processing Letters, Vol.18, No.3, March 1984, pp.159 { 165.
-Corm87]
Cormack, G.V., Horspool, R.N.S.: Data Compression using dynamic Markov modelling. The Computer Journal, Vol.30, No.6, 1987, pp.541 { 550.
-Elia75]
Elias, P.: Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, Vol. IT{21, No.2, March 1975, pp.194 { 203.
-Elia87]
Elias, P.: Interval and recency rank source coding: two on-line adaptive variablelength schemes. IEEE Trans. Inf. Theory IT{33, 1, 1987, pp.3 { 10.
-Even78]
Even, S., Rodeh, M.: Economical encoding of commas between strings. Communications of the ACM, Vol.21, No.4, April 1978, pp.315 { 317.
-Fano49]
Fano, R.M.: The transmission of information. Tech. Rep. 65, Research Laboratory of Electronics,MIT, Cambridge, MA. 1949.
-Fial89]
Fiala, E.R., Greene, D.H.: Data compression with nite windows. Communications of the ACM, Vol.32, No.4, Apr.1989, pp.490 { 505.
-Gall78]
Gallager, R.G.: Variation on a theme by Human. IEEE Transactions on Information Theory, Vol.IT-24, No.6, Nov.1978, pp.668 { 674. 99
-Held83] -Hopk92]
Held, G.: Data compression. John Wiley & Sons, Chichester, 1983. Hopkins, L.: SQLText-Retrieval. Administrator's Guide, Version 2.0, Oracle Corporation, 1992. -Hu%52] Hu%man, D.A.: A method for the construction of minimum-redundancy codes. Proceedings of IRE, Vol.40, No.9, Sept.1952, pp.1098 { 1101. Also in: Davisson, L.D., Gray, R.M. ed.: Data compression. Dowden, Hutchinson, Strondsburg, Pennsylvania, USA, 1976. -Jak82] Jakobsson, M.: Evalutation of a hierarchical bit-vector compression technique. Information Processing Letters, Vol.14, No.4, June 1982, pp.147 { 149. -Jak85] Jakobsson, M.: Compression of character strings by an adaptive dictionary. BIT, Vol.25, 4, pp.593 { 603. -Knut85] Knuth, D.E.: Dynamic Human coding. Journal of Algorithms, Vol.6, 1985, pp.163 { 180. -Knut77] Knuth, D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM Journal of Computing, Vol.6, No.2, 1977, pp.323 { 350. -Lang84] Langdon, G.G.: An introduction to arithmetic coding. IBM Journal of Research and Developement, Vol.28, No.2, March 1984, pp.135 { 149. -Lel87] Lelewer, D.A., Hirschberg, D.S.: Data compression. ACM Computing Surveys, Vol.19, No.3, Sept.1987, pp. 261 { 296. -Lemp76] Lempel, A., Ziv, J.: On the complexity of nite sequences. IEEE Transactions on Information Theory, Vol. IT{22, No.1, Jan.1976, pp.75 { 81. -Mel91] Melichar, B.: Informan systmy. Edin stedisko VUT, Praha, 1991, 57 str. -Mel92] Melichar, B., Pokorn , J.: Data Compression. Survey Report DC{92{04, Czech Technical University, Department of Computers, Praha, 1992, 55 str. -Pelt91] Peltola, H., Tarhio, L.: On syntactical data compression. In: Symp. on Progr. Lang. and Software Tools, Pirkkala, 1991. -Pok87] Pokorn , J.: Komprese dat. Proc. of Sem. DATASEM'87, DT SVTS, Praha, 1987, pp.43 { 54. -Riss79] Rissanen, J., Langdon, G.G.: Arithmetic coding. IBM Journal of Research and Development, Vol.23, No.2, March 1979, pp.149 { 162. -Salt83] Salton, G., McGill, M.J.: Introduction to modern information retrieval. McGrawHill, Tokyo, 1983. -Stor88] Storer ,J.: Data Compression: Methods and Theory. Computer Science Press, Rockwille, 1988. -Vitt87] Vitter, J.S.: Design and analysis of dynamic Human codes. Journal of the ACM, Vol.34, No.4, Oct.1987, pp.825 { 845. -Vitt89] Vitter, J.S.: ALGORITHM 673: Dynamic Human coding. ACM Transactions on Mathematical Software, Vol.15, No.2, June 1989, pp.158 { 167. -Welc84] Welch, T.A.: A technique for high-performance data compression. COMPUTER, Vol.17, No.6, June 1984, pp.8 { 19. 100
-Witt87] -Ziv77] -Ziv78]
Witten, I.H., Neal, R.M., Cleary, J.G.: Arithmetic coding for data compression. Communications of the ACM, Vol.30, No.6, June 1987, pp.520 { 540. Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, Vol.IT{23, No.3, May 1977, pp.337 { 343. Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, Vol.IT{24, No.5, Sept.1978, pp.530 { 536.
101
