N-gram

N-gram je definovaný ako sled n po sebe idúcich položiek z danej sekvencie. Zo sémantického pohľadu môže byť táto postupnosť buď postupnosťou hlások, slabík, písmen alebo slov. V praxi sa častejšie vyskytujú n-gramy ako sled slov. Sled dvoch po sebe nasledujúcich položiek býva často označovaný ako bigram, pre sled troch položiek je zaužívaný pojem trigram. Od štyroch a vyššie sa používa označenie N-gram, kde N je nahradené počtom za sebou nasledujúcich elementov.

Využitie n-gramov

Všeobecné využitie n-gramov

N-gramy vo všeobecnosti nachádzajú svoje uplatnenie v širokej sfére zameraní. Uplatniť sa dokážu napríklad v oblasti teoretickej matematiky, biológie, kartografie ale aj v oblasti hudby. Medzi najzaujímavejšie využitia n-gramov patrí:

• extrahovanie čŕt pre zhlukovanie sérií satelitných snímok Zeme, a následné rozhodovanie, ktorú konkrétnu časť Zeme daná snímka zobrazuje,
• vyhľadávanie genetických sekvencií,
• na poli genetiky sú využívané pre určenie, ktorému konkrétneho živočíšnemu druhu odobraná vzorka DNA patrí,
• z počítačovej vedy sú uplatňované pri kompresii,
• pomocou n-gramov bývajú indexované dáta, súvisiace so zvukom.

Využitie n-gramov pre potreby spracovania prirodzeného jazyka

Širokú aplikáciu majú n-gramy v oblasti spracovania prirodzeného jazyka. Slúžia ako vstupný element pre riešenie obšírneho celku problémov.

Vo sfére spracovania prirodzeného jazyka sa n-gramy využívajú hlavne na predikciu slov, kde sa využívajú pravdepodobnostné modely zvané N-gram modely. N-gram model počíta pravdepodobnosť výskytu posledného slova n-gramu z predchádzajúcich n-gramov. Pokiaľ je tento prístup použitý pre modelovanie jazyka, tak výskyt každého slova závisí len na predchádzajúcich n slovách. N-gram model je tým pádom Markovský model, čo značne uľahčuje strojové získanie znalostí o modele jazyka z textu.

Ďalším využitím n-gramov je odhaľovanie plagiátov, a to rozdelením textu na viacero malých fragmentov, reprezentovaných n-gramami. Tie sa dajú ľahko medzi sebou porovnať, a tým odvodiť mieru podobnosti kontrolovaných dokumentov. N-gramy sú často úspešne využívané pre kategorizáciu textu alebo jazyka. Ďalej bývajú využívané pre vytváranie funkcií, ktoré umožňujú algoritmom strojového učenia získavať znalosti z textových dát. Pomocou n-gramov je takisto možné efektívne vyhľadanie kandidátov pre náhradu za pravopisne chybne napísané slovo.

Výskumné projekty Google

Vo výskumných centrách Google boli využívané n-gram modely pre širokú paletu výskumných a vývojárskych projektov. Medzi tieto projekty patrí napríklad štatistický preklad z jedného jazyka do druhého, rozpoznávanie reči, oprava pravopisných chýb, extrakcia informácií, detekcia entít a mnoho ďalších. Pre účely týchto projektov boli použité textové korpusy s obsahom niekoľko biliónov slov.
Spoločnosť Google sa rozhodla svoje tréningové korpusy nahromadiť a spojiť. Z toho vznikol tzv. Google teracorpus, ktorý obsahuje 1 024 908 267 229 slov zozbieraných z verejných webových stránok. Pre tento teracorpus bola takisto zverejnená početnosť všetkých piatich po sebe nasledujúcich slov v texte, 5-gramov. Google distribuuje teracorpus prostredníctvom Linguistic Data Consortium za istý poplatok. Tým pádom nie je teracorpus dostupný úplne každému.

Metódy na extrakciu n-gramov

Kvôli častému využívaniu n-gramov pre riešenie rôznych úloh je potrebný spoľahlivý a rýchly algoritmus pre ich extrakciu z textu. Vhodný nástroj slúžiaci na extrakciu n-gramov z textu by mal dokázať pracovať s textom neobmedzenej veľkosti, pracovať rýchlo a efektívne využívať dostupnú operačnú pamäť. Existuje viacero metód extrahujúcich n-gramy z textu. Tieto metódy sú založené na rôznych princípoch:

• algoritmus Nagao '94
• algoritmus Lempel-Ziv-Welch pre kompresiu
• sufixové pole
• sufixový strom
• invertovaný index

Nagao '94 algoritmus

Metóda sa používa na extrakciu n-gramov z japonského textu, kde je každé slovo reprezentované jedným znakom. Určuje frekvenciu výskytu postupnosti znakov. Tento postup pozostáva z dvoch etáp. V prvej etape je vstupný text reprezentovaný ako dlhý reťazec pozostávajúci zo slov, bielych znakov atď. Tento text je uložený v jednom poli. Druhé pole, rovnakej veľkosti ako prvé pole, obsahuje ukazovatele na podreťazce v prvom poli, tak ako je znázornené na nasledujucom obrázku:

Prvá etapa algoritmu Nagao '94

Podreťazec, na ktorý ukazuje i-1 ukazovateľ je definovaný ako kompozícia znakov od i-tej pozície po koniec textového reťazca. Pole ukazovateľov je následne abecedne zoradené, výsledkom čoho sú zhodné podreťazce pri sebe. Radením poľa ukazovateľov sa nezmení obsah textového poľa.

Po zoradení poľa sú porovnávané každé dva susedné podreťazce a vypočíta sa dĺžka prefixu, ktorý je zhodný pre oba podreťazce. Napríklad ak sú dva susedné podreťazce „na žltej zahneme vpravo“ a „na žltej zahneme vľavo“, tak je dĺžka zhodného prefixu rovná sedemnásť. Toto číslo je potom uložené do tabuľky súčasných výskytov prefixov podreťazcov.

Druhá etapa je výpočet frekvencie n-gramov. Používa sa pole ukazovateľov a tabuľka súčasných výskytov prefixov znakov, vytvorené v predchádzajúcej etape. Pre zvolené n sa prechádza pole ukazovateľov, načíta sa prvých n znakov prvého slova a kontroluje sa číslo v tabuľke. Ak je toto číslo väčšie alebo rovné ako n, tak to znamená, že druhé slovo má najmenej n spoločných prefixových znakov s prvým slovom. Následne sa kontroluje ďalší záznam v tabuľke a porovnáva sa s n. Tento postup sa opakuje až kým číslo z tabuľky nie je menšie ako n. Počet takto prejdených slov od prvého slova je frekvencia výskytu n znakov z prvého slova. Tento istý postup sa opakuje pre všetky slová.

Metóda využívajúca LZW algoritmus

Táto metóda je inšpirovaná Lempel-Ziv-Welch (LZW) algoritmom bezstratovej dátovej kompresie. Princíp LZW algoritmu spočíva v postupnom vytváraní kódovacej tabuľky zo slov použitých v už zakódovanom texte. V tejto tabuľke je každý vstup mapovaný na slová s pevne stanovenou dĺžkou. Pri začiatku kódovania je tabuľka zvyčajne inicializovaná pomocou všetkých znakov z ASCII tabuľky. Algoritmus potom sekvenčne prehľadáva text a ukladá si do tabuľky každé unikátne dvojznakové slovo ako spojenie kódu a vzoru. Po uložení všetkých dvojznakových slov je na výstup poslaný kód prvého znaku na vstupu. Algoritmus pokračuje v kódovaní, keď narazí na už zakódované slovo tak na výstup odošle zodpovedajúci kódový znak s prvým znakom slova.

Príklad algoritmu na extrakciu n-gramov z textu, ktorý je založený na vyššie popísanom princípe LZW. Tento algoritmus používa binárny strom na uloženie už extrahovaných vzoriek. Jednotlivé vzorky sú v tomto prípade chápané ako slová.Princíp algoritmu je znázornený vývojovým diagramom na nasledujúcom obrázku:

Vývojový diagram algoritmu extrahujúceho n-gramy z textu na základe LZW algoritmu

Sufixové pole a sufixový strom

Sufixové pole

Ďalším, veľmi často používaný prístup pre získanie n-gramov a ich početností z textu je metóda založená na práci so sufixovým poľom.

Sufixové pole je dátová štruktúra obsahujúca N sufixov, abecedne zoradených. Sufix, s[i], je reťazec, ktorý začína na i-tej pozícii v korpuse a pokračuje až do konca korpusu. Nasledujúci znázorňuje rozdelenie vstupného reťazca „to be or not to be“ do poľa znakov a jeho indexáciu v sufixovom poli.

Obsah sufixového poľa pre vstupný reťazec "to be or not to be"

Predchádzajúci obrázok ilustruje obsah sufixového poľa pre reťazec “to be or not to be“. Po načítaní reťazca a vytvorení sufixového poľa nasleduje zoradenie sufixov podľa abecedy. Stav sufixového poľa po zoradení demonštruje nasledujúci obrázok.

Sufixové pole pred a po zoradení, príklad výpočtu frekvencie termu

Frekvencia jednotlivých termov sa vypočíta ako rozdiel indexu prvého výskytu a indexu posledného výskytu daného termu. K tomuto rozdielu sa pripočíta jednotka. Frekvencia výskytov jednotlivých termov sa uloží do tzv. LCP (longest common prefix) poľa.
Po naplnení LCP poľa je vhodné vytvoriť štruktúru tzv. n-gram deskriptorov, ktorá obsahuje dvojicu (koncová pozícia, frekvencia). Vďaka uloženiu do štruktúr deskriptorov je možné prevádzať nad n-gramami niekoľko vhodných operácií pre konečný výstup. Prvou je vytriedenie menej frekventovaných deskriptorov, čo je užitočné pokiaľ nie je požiadavka aby výstup zahrňoval n-gramy s nízkou frekvenciou výskytu. Druhou, nemenej podstatnou operáciou je zoradenie deskriptorov podľa koncovej pozície,výsledkom čoho je abecedné zoradenie deskriptorov. Posledným krokom je extrakcia n-gramov z deskriptorov, čo je pomocou koncovej pozície, frekvencie a požadovanej dĺžky n-gramov triviálna úloha.

Sufixový strom

Sufixový strom je taká dátová štruktúra, v ktorej každý vrchol v reprezentuje časť podreťazca (príp. slova), ktorý dostaneme ako zreťazenie hrán na ceste z koreňa do listu. Metóda na extrakciu n-gramov pomocou sufixových stromov je veľmi podobná prístupu so sufixovým poľom. Rozdiel je práve v dátovej štruktúre, do ktorej sú ukladané ukazovatele na jednotlivé slová vstupného reťazca. Uloženie vstupného reťazca „to be or not to be“ do sufixového stromu znázorňuje nasledujúci obrázok.

Uloženie vstupného reťazca "to be or not to be" do sufixového stromu.

Na predchádzajúcom obrázku je zobrazený obsah sufixového stromu po načítaní vstupného reťazca. V uzloch nie sú uložené kompletné slová, ale každý synovský uzol koreňového uzla ukazuje na podreťazec slov v poli obsahujúcom vstupný textový reťazec. Ďalší postup pre extrakciu slovných n-gramov je zhodný s postupom kde sa využíva sufixové pole. Postupy pre extrakciu slovných n-gramov z textu bývajú často založené práve buď na práci so sufixovým poľom, alebo práci so sufixovým stromom. Okrem extrakcie slovných n-gramov majú sufixové stromy využitie v mnoho iných oblastiach práce s textom, medzi ne patrí:

• určenie, či je dané slovo y podreťazcom (príp. podslovom) iného reťazca x (príp. slova)
• nájdenie všetkých výskytov slova y v reťazci x,
• vyhľadávanie dvojíc opakovaných výskytov,
• vyhľadávanie maximálnych opakovaní,
• vyhľadávanie najdlhšieho palindromu v texte,
• kompresia dát,
• identifikácia osôb pomocou DNA.

Hlavnou nevýhodou použitia sufixových stromov je ich priestorová náročnosť.

Porovnanie metód založených na sufixovom poli a sufixovom strome

Hlavným cieľom Kozlowského a kol. bolo zistenie možnosti zefektívnenia extrakcie n-gramov pomocou sufixového poľa ako aj vzájomné porovnanie s implementáciou metódy využívajúcej sufixový strom. Výpočtová zložitosť pre sufixové pole je Θ(N • log(N)), a pre sufixový strom je zložitosť logaritmická, Θ(log(N)), kde N je veľkosť vstupného textového korpusu v počte slov. Preto autori porovnávali práve tieto dve metódy.

Sufixové pole bolo zoraďované pomocou algoritmu quick sort. Časová zložitosť bola v tomto prípade Θ(N • log(N)). Pre sufixový strom autori použili dve implementácie:

1. implementácia sufixového stromu založená na zreťazenom zozname,
2. implementácia sufixového stromu založená na hashovacej tabuľke.

V prvom prípade bola časová zložitosť pre vytvorenie sufixového stromu Θ(N • K), kde K vyjadruje veľkosť abecedy. Druhý algoritmus umožňuje veľmi rýchle vytvorenie sufixového stromu s časovou zložitosťou Θ(N), avšak tento postup nie je vhodný pre extrakciu n-gramov. Pre extrakciu n-gramov je potrebný čas rovný Θ(N•K).

Každý algoritmus sa skladá z dvoch fáz, prvá fáza je načítanie vstupného korpusu a vytvorenie dátovej štruktúry s jej následným naplnením. Druhá fáza je vlastná extrakcia n-gramov pomocou naplnených dátových štruktúr. Vzhľadom na vytvorenie dátovej štruktúry je najrýchlejšou metódou sufixové pole. Pre nízky počet slov, je rýchlejšia metóda využívajúca sufixový strom, avšak s narastajúcou komplexnosťou výpočtu a zložitosťou algoritmu efektivita tejto metódy klesá.

V druhej fáze je najrýchlejšia metóda opäť tá, ktorá využíva sufixové pole, najpomalšou je implementácia sufixového stromu pomocou hashovacej tabuľky, práve kvôli jej zložitosti Θ(N • K).

Invertovaný index

Veľmi často využívanou dátovou štruktúrou pre potreby spracovania prirodzeného jazyka je invertovaný index. Táto štruktúra je významná nie tak pre extrakciu n-gramov z textu, ale hlavne pre jej efektivitu pri vyhľadávaní podreťazcov v texte. Pre vyhľadávanie podreťazcov sa využívajú práve n-gramy. Dátová štruktúra invertovaného indexu spravidla obsahuje dvojicu:

• zoznam dokumentov, ktoré obsahujú konkrétny term,
• pre každý výskyt termu v dokumente obsahuje frekvenciu výskytu v danom dokumente a pozície, na ktorých sa term v dokumente vyskytuje.

Na extrakciu n-gramov z textu nie je invertovaný index vhodným prístupom, hlavne kvôli jeho priestorovým nárokom ako aj neefektívnosti v prípade vyššej dĺžky n-gramov. Svoje uplatnenie však okrem spomenutého vyhľadávania nachádza v oblasti získavania informácií z textu, bioinformatike. Vďaka jeho nezávislosti na jazyku je často využívaný pre prácu s japonským, kórejským a čínskym textom.