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 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.

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:
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:

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.
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.
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.