Charakteristické slabiky Genetické algoritmy ve slabikové kompresi textů

Charakteristické slabiky

Genetické algoritmy ve slabikové kompresi textů

Tomáš Kuthan Univerzita Karlova v Praze Matematicko-fyzikální fakulta [email protected]

Osnova ●

Motivace

●

Slabiková komprese

●

●

–

Algoritmy pro dělení na slabiky

–

Slabikové kompresní algoritmy

–

Slovníky častých slabik

Genetický algoritmus –

Teoretický odhad délky komprimovaného textu

–

Parametry

Měření a výsledky

Motivace ●

●

Proč komprimovat texty po slabikách? –

Rychlejš í a efektivnějš í než po znacích

–

Menš í prostorová náročnost než u slov

–

Dobré výsledky u menš ích souborů

Proč používat slovníky častých slabik? –

●

Inicializace algoritmů, lepš í kompresní poměr

Proč genetickým algoritmem? –

Protože by to mohlo fungovat líp

Slabiková komprese ●

●

Struktura kódované zprávy –

text v přirozeném jazyce

–

bohatá vs. chudá morfologie

Definice slabiky –

●

řetězec písmen obsahující právě jeden maximální podřetězec samohlásek

Druhy slabik –

velké, malé, smíš ené, číselné, speciální

Dělení na slabiky ●

Obtížné –

●

kompikovaná pravidla, etymologie, sématika ●

Př: ne-u-ro-nit vs. neu-ron

●

ob-le-tět vs. o-bre-čet

Nejednoznačné –

více možností jak rozdělit slovo ●

●

Př: Os-tra-va vs. Ost-ra-va

Netřeba rozdělit vždy lingvisticky správně

Algoritmy dělení na slabiky ●

●

specifické –

využívají znalostí konkrétního jazyka

–

vysoká úspěš nost správného dělení

–

TeX, kancelářské programy

univerzální –

lze je využít pro vš echny jazyky

–

algoritmy třídy PU ●

left, right, midle-left, midle-right

Univerzální algoritmy dělení slov ● ●

podle přerozdělování skupiny souhlásek – – –

–

PUL vš e doleva

PUL odst-rč-en-ou

–

PUR vš e doprava

PUR o-dstr-če-nou

–

PUML a PUMR

PUML ods-tr-če-nou

–

PUMR od-str-čen-ou

půl na půl výjimka – PUML a jediná ●

●

Př: dělení odstrčenou

souhláska

Slabikové kompresní algoritmy ●

2 algoritmy Jana Lánského:

●

HuffSyllable

●

–

slabiková verze algoritmu HuffWord (Moffat)

–

statistická kompresní metoda

–

adaptivní Huffmanovy stromy

LZWL –

slabiková verze algoritmu LZW (Welsch)

–

slovníková kompresní metoda

–

překladový slovník - omegatrie

Kódování nové slabiky ●

stejné pro HuffSyllable i LWZL

●

kód nové slabiky

●

–

symbol ESCAPE

–

kód typu slabiky

–

kód délky slabiky

–

jednotlivé znaky

kódování slabik je „ drahé“ , prodlužuje kód –

rádi bychom se mu vyhnuli

HuffSyllable ●

překladový slovník –

●

5 Huffmanových stromů –

●

ostatní stromy až když se na slabiku narazí

odhadování typu následující slabiky –

●

pro každý typ slabiky jeden

strom malých slabik inicializován ze souboru –

●

slabice přiřadí číslo

případně ESCAPE sekvence pro kód typu

kód slabiky

LZWL ●

●

překladový slovník –

implementován jako omegatrie

–

inicializován z databáze častých slabik

–

kód slabiky = číslo, které ji přiřadí slovník

komprese –

maximální prefix vstupu, který je frází ze slovníku

–

na výstup kód

–

do slovníku přidat zretězení s následující slabikou

Význam slovníků častých slabik ●

●

Oba algoritmy jsou adaptibilní –

délka kódu slabiky závisí na její četnosti v již zpracované části vstupu

–

na začátku neefektivní - horš í kompresní poměr

Inicializace ze souboru –

časté slabiky rovnou v překladovém slovníku ●

–

není nutné je kódovat po znacích

inicialozovány i s odhadem četnosti

Slovníky častých slabik ●

Konstruovány analýzou textových korpusů

●

Které slabiky do slovníku vybrat? –

nevybereme-li častou, nejspíš se vyskytne ●

–

vybereme-li vzácnou, nemusí se vyskytnout ●

●

zakódovat po znacích + delš í kód zbytečně delší kód ostatních slabik a velký slovník

Těžká úloha –

desítky tisíc unikátních slabik

Slovníky častých slabik ●

2 přímočará kritéria:

●

četnostní (cummulative) –

slabiky, jejichž počet výskytů v celém korpusu přesahuje jistou mez ●

●

výskytové (apearance) –

slabiky, které se vyskytují v dostatečně mnoho souborech alespoň jednou ●

●

Př: slovník C65 - poměr vyš ší než 1/65000

Př: slovník A05 - v 5% alespoň jedenkrát

různé typy vhodné pro různé velikosti vstupu

Genetický algoritmus ●

spojuje výhody obou kritérii

●

bere v potaz i dalš í informace –

●

optimalizován pro HuffSyllable –

●

odhad ceny zakódování slabiky po znacích

kvůli snadné aproximaci jeho fungování

úloha svým charakterem přímo vybízí ke GA

Genetický algoritmus ●

kódování kandidátních řeš ení - přímočaré –

●

●

1 ... slabika charakteristická, zařadit do slovníku

●

0 ... slabika vzácná, nezařazovat

cross-over –

●

binární řetězec délky počtu unikátních slabik

vícebodový ●

vhodný pro relativně malé populace

●

počet míst zlomu: 10

mutace

Fitness ●

Počítá se ze vzorku souborů z learning set –

každou generaci z jiného vzorku

–

velikost vzorku: 5 ●

●

ovlivňuje rychlost, i tlak na výskytové kritérium

Odpovídá odhadu počtu bitů vzorku zakódované algoritmem HuffSyllable –

–

nejpřesnějš í - zkomprimovat a změřit ●

neúnosně časově náročné

●

vyžadovalo by konstrukci H.S. O(nlogn)

proto teoretická aproximace

Teoretická aproximace ●

Shannon: –

●

●

„ odhad kompresního koeficientu: μ = H / logm“ ●

H ... entropie

●

m ... počet unikátních symbolů v textu

Huffmanovo kódování je optimální Dohromady: ●

µ=−∑ pi log pi /log m

pi ... pravděpodobnost výskytu i-té slabiky

Teoretická aproximace ●

●

Z toho délka l komprimovaného textu:

l=n log n '−∑ n i log n ' i [bitů ]

●

ni ... počet výskytů i-té slabiky v tomto textu

●

n ... počet výskytů vše ch slabik v tomto textu

●

n'i ... počet výskytů i-té slabiky ve vše ch textech

●

n' ... počet výskytů vše ch slabik ve vše ch textech

příspěvek nové slabiky –

lineární část - delš í kód

–

konstantní část - režie na zakódování po znacích

Výpočet fitness ●

●

Kritické místo algoritmu –

přestože je lineární k počtu slabik

–

konzumuje větš inu výpočetního času

Možné vylepš ení - paralelizace –

–

lze spustit až na takovém počtu CPU (počítačů), jako je velikost populace ●

dokonce: |populace| * |vzorek|

●

zrychlení až 1500krát

úzké rozhraní

Parametry GA ●

velikost populace: 150 jedinců –

●

relativně málo vzhledem k velikosti problému

počet generací: 400 –

stačí, dále už bylo zlepš ení zanedbatelné ●

●

●

sotva setiny bpc

cross-over: provádí se vždy –

„ není čas na neproduktivní klony“

–

kombinace s elitismem

mutace: rovněž vždy, ale titěrný rozsah –

Dalš í vlastnosti GA ●

Selekce –

vzorec pro pravděpodobnost výběru jedince:

p x i = K − f  x i /nK −∑ f  x j 

●

Inicializace prvotní populace –

náhodně inicializovaní jedinci ●

–

heuristika ●

●

náhodně rozmístěni skoro po celém prostoru lehce se preferují 1 na místě slabik s vysokou četností

Elitismus: zhruba 1% populace

Dalš í vlastnosti GA ●

vyvažování –

odhad fitness není dokonalý

–

má tendenci protežovat jedince s hodně 1

–

proto penalizace za počet ponechaných 1

Měření ●

měření provedena na češ tině a angličtině

●

češ tina –

trénovací množina ●

–

měřící množina ●

●

69 beletrie + 931 novinových článků z PDT 69 beletrie + 6931 novinových článků

angličtina –

trénovací množina ●

–

100 beletrie + 900 právních dokumentů

měřící množina

Výsledky

Výsledky

Výsledky

Výsledky

Výsledky

Závěry ●

Nové slovníky vylepš ují chování HuffSyllable

●

pro LZWL nepřináš í nic moc –

●

●

ale ani nijak výrazně neš kodí

slabikové metody se na menš ích souborech osvědčily

Možná zlepš ení ●

mutace

●

pustit genetický algoritmus i na speciální slabiky

●

proměnlivá selekce –

explorace vs. exploatace

Zkuš enosti a povzdechy ●

MS Visual Studio .Net –

●

wine –

●

kvůli nepřenositelnému kódu možnost spouš tět výpočty vzdáleně

nějaká knihovna GA –

příš tě už bych ji použil

Otázky a odpovědi

...snad budu vědět :-)

Poděkování

Děkuji za pozornost