Konečný převodník

Konečný převodník je konečný automat se dvěma paměťovými páskami podle terminologie používané pro Turingovy stroje: vstupní páskou a výstupní páskou. Tím se odlišuje od obyčejného konečného automatu, který má jen jednu pásku. Konečný převodník je typem konečného automatu, který provádí převod mezi dvěma množinami symbolů. Konečné převodníky lze považovat za zobecnění konečných automatů; zatímco konečný automat definuje formální jazyk určením množiny přijímaných řetězců, konečný převodník definuje relaci mezi množinami řetězců.

Konečný převodník čte řetězce ze vstupní pásky a generuje množinu relací na výstupní pásce. Na konečný převodník lze pohlížet jako na překladač nebo zařízení pro určení vztahů mezi množinami řetězců.

Při morfologické analýze může být vstupem konečného převodníku řetězec symbolů, a konečný převodník produkuje řetězec morfémů.

Úvod

Pokud chápeme obsah vstupní pásky jako vstup automatu, pak říkáme, že automat přijímá řetězec. Jinými slovy, automat počítá funkci, která přiřazuje řetězcům hodnoty {0,1}. +more Alternativně můžeme říct, že automat generuje řetězec, pokud pohlížíme na jeho pásku jako na výstup. Při tomto přístupu automat generuje formální jazyk, který je sadou řetězců. Oba pohledy na automat jsou ekvivalentní: funkce, kterou automat počítá, je právě charakteristická funkce množiny řetězců, které generuje. Třída jazyků generovaných konečnými automaty se nazývá regulární jazyky.

Na dvě pásky převodníku obvykle pohlížíme jako na vstupní pásku a výstupní pásku. Při tomto přístupu převodník převádí (překládá) obsah své vstupní pásky na výstupní pásku, načtením řetězce ze vstupní pásky a vygenerováním jiného řetězce na výstupní pásku. +more Převodník může pracovat nedeterministicky, a může produkovat více než jeden výstup pro každý vstupní řetězec. Převodník může také neprodukovat žádný výstup pro daný vstupní řetězec, čemuž říkáme, že daný vstup odmítá. Obecně převodník počítá relaci mezi dvěma formálními jazyky.

Každý konečný převodník, který převádí jeden řetězec na druhý, ukazuje souvislost vstupní abecedy Σ s výstupní abecedou Γ. Relace R na Σ*×Γ*, které lze implementovat jako konečné převodníky se nazývají racionální relace. +more Racionální relace, které jsou zobrazeními (tj. přiřazují každému vstupnímu řetězci z Σ* nejvýše jeden řetězec z Γ*, se nazývají racionální funkce.

Konečné převodníky se často používají pro fonologickou a morfologickou analýzu při výzkumu i v aplikacích v oblasti zpracování přirozeného jazyka. K průkopníkům v této oblasti patří Ronald Kaplan, Lauri Karttunen, Martin Kay a Kimmo Koskenniemi. +more Obvyklým způsobem použití převodníků je tak zvaná „kaskáda“, kdy se převodníky pro různé operace kombinují do jediného převodníku opakovanou aplikací operátoru skládání relací (definovaného níže).

Formalní konstrukce

Formálně je konečný převodník T šestice taková, že:

* je konečná množina stavů; * je konečná množina nazývaná vstupní abeceda; * je konečná množina nazývaná výstupní abeceda; * je podmnožina množiny , množina počátečních stavů; * je podmnožina , množina koncových stavů; a * \delta \subseteq Q \times (\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\}) \times Q je přechodová relace (ε je prázdný řetězec).

Na (Q, δ) můžeme nahlížet jako na orientovaný graf, nazývaný přechodový graf T: množina vrcholů je Q a (q,a,b,r)\in\delta znamená, že existuje označená hrana jdoucí z vrcholu q do vrcholu r. Přitom a je vstupní návěstí a b výstupní návěstí této hrany.

Poznámka: Tato definice konečného převodníku se také nazývá písmenový převodník (Roche a Schabes 1997); existují alternativní definice, ale všechny mohou být převedeny na převodníky, jako je tento.

Definujeme rozšířenou přechodovou relaci \delta^* jako nejmenší množinu takovou, že:

* \delta\subseteq\delta^*; * (q,\epsilon,\epsilon,q)\in\delta^* pro všechny q\in Q; a * když (q,x,y,r) \in \delta^* a (r,a,b,s) \in \delta pak (q,xa,yb,s) \in \delta^*.

Rozšířená přechodová relace je v zásadě reflexivní a tranzitivní uzávěr přechodového grafu, který byl rozšířen o návěstí hran. Prvky \delta^* se nazývají cesty. +more Návěstí cesty se získá zřetězením návěstí jednotlivých hran v tom pořadí, v jaké se procházely.

Chování převodníku T je racionální relace [T] definovaná takto: x[T]y právě tehdy, když existuje i \in I a f \in F tak, že (i,x,y,f) \in \delta^*. To znamená, že T převádí řetězec x\in\Sigma^* na řetězec y\in\Gamma^*, pokud existuje cesta z počátečního stavu do koncového stavu, jejíž vstupní návěstí je x, a výstupní návěstí y.

Vážený konečný převodník

Konečné převodníky lze rozšířit o váhy tak, že každému přechodu je přiřazeno nejen vstupní a výstupní návěstí, ale také váha. Vážený konečný převodník ({{Vjazyce2|en|Weighted Finite State Transducer, WFST) s množinou vah K lze definovat obdobně jako převodník bez vah - jako osmici , kde: * jsou definovány jako výše; * E \subseteq Q \times (\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\}) \times Q \times K (kde ε je prázdný řetězec) je konečná množina přechodů; * \lambda: I \rightarrow K přiřazuje váhy počátečním stavům; * \rho: F \rightarrow K přiřazuje váhy koncovým stavům. +more Aby byly určité operace na vážených konečných převodnících dobře definované, je vhodné vyžadovat, aby množina vah tvořila polookruh. Dva typické polookruhy používané v praxi jsou logaritmický polookruh a tropický polookruh: automaty bez vah mohou být považovány za automaty, jejichž váhy jsou v Booleovském polookruhu.

Stochastické konečné převodníky

Stochastické konečné převodníky (nazývané také pravděpodobnostní konečné převodníky nebo statistické konečné převodníky) jsou podle všeho tvarem vážených konečných převodníků.

Operace na konečných převodnících

Následující operace definované na konečných automatech lze také aplikovat na konečné převodníky:

* Sjednocení. Jsou-li dány převodníky a , existuje převodník T\cup S tak, že x[T\cup S]y právě tehdy, když x[T]y nebo x[S]y. +more * Zřetězení. Jsou-li dány převodníky a , existuje převodník T\cdot S tak, že x[T\cdot S]y právě tehdy, když existuje x_1, x_2, y_1, y_2 s x=x_1x_2, y =y_1y_2, x_1[T]y_1 a x_2[S]y_2. * Kleeneho uzávěr. Je-li dán převodník , existuje převodník T^* s následujícími vlastnostmi: }}.

:: přičemž x[T^*]y neplatí, pokud není zaručeno nebo . * Skládání relací. +more Je-li dán převodník na abecedách Σ a Γ a převodník na abecedách Γ a Δ, existuje převodník T \circ S na Σ a Δ takový, že x[T \circ S]z právě tehdy, když existuje řetězec y\in\Gamma^* tak, že x[T]y a y[S]z. Tuto operaci lze rozšířit na vážené konečné převodníky.

:Tato definice používá notaci používanou v matematice pro skládání relací. Nicméně obvyklé chápání skládání relací je jiné: jsou-li dány dvě relace a , (x,z)\in T\circ S, když existuje nějaké tak, že (x,y)\in S a (y,z)\in T.

* Projekce automatu. Existují dvě projekční funkce: \pi_1 zachovává vstupní pásku a \pi_2 zachovává výstupní pásku. +more První projekce \pi_1 je definována takto:.

: Je-li dán převodník , existuje konečný automat \pi_1 T tak, že \pi_1 T přijme x právě tehdy, když existuje řetězec y pro který x[T]y.

:Druhá projekce \pi_2 je definovaná obdobně.

* Determinizace. Je-li dán převodník , chceme vytvořit ekvivalentní převodník, které má jedinečná/jednoznačná počáteční stav a tak, že žádné dva přechody ponechává jakýkoli stav sdílí stejný vstupní návěstí. +more Pomocí podmnožinové konstrukce lze tuto vlastnost rozšířit na konečné převodníky i na vážené konečné převodníky, které se ale někdy nemusí zastavit; skutečně, některé nedeterministické převodníky nepřipouštějí ekvivalentní deterministické převodníky. Byly navrženy různé charakterizace determinizovatelných převodníků spolu s efektivními algoritmy, jak je testovat: spoléhají na vlastnosti polookruhu používaného ve váženém případě, i na obecné vlastnosti struktury převodníku (tzv. ). * Ukládání vah pro vážené konečné převodníky. * Minimalizace vážených konečných převodníků. * Odstranění epsilon přechodů.

Další vlastnosti konečných převodníků

Je rozhodnutelné, zda relace [T] převodníku T je prázdná. * Je rozhodnutelné, zda existuje řetězec y tak, že x[T]y pro daný řetězec x. +more * Je nerozhodnutelné, zda dva převodníky jsou ekvivalentní. Ekvivalence je ale rozhodnutelná ve speciálním případě, když relace [T] převodníku T je zobrazení. * Pokud definujeme abecedu návěstí L=(\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\}), konečné převodníky jsou izomorfní s nedeterministickými konečnými automaty s abecedou L, takže mohou být determinizovány (převedeny na deterministický konečný automat nad abecedou L=[(\Sigma\cup\{\epsilon\}) \times \Gamma] \cup [\Sigma \times (\Gamma\cup\{\epsilon\})]) a následně minimalizovány, čímž se minimalizuje počet stavů.

Aplikace

Kontextová přepisovací pravidla tvaru a → b / c _ d, používaná v lingvistice pro modelování fonologických pravidel a posouvání hlásek jsou výpočetně ekvivalentní s konečnými převodníky za předpokladu, že jejich aplikace není rekurzivní, tj. není povoleno, aby pravidla přepisovala stejný podřetězec opakovaně.

Vážené konečné převodníky se používají pro zpracování přirozeného jazyka, včetně strojového překladu a pro strojové učení. Jednou z komponent knihovny OpenGrm je implementace morfologického značkování.

Odkazy

Reference

Literatura

Související články

Mealyho automat * Mooreův stroj * Morfologický slovník * Foma (software) * Stromový převodník * Dvouúrovňová morfologie

Externí odkazy

[url=http://openfst. org/]OpenFst[/url], knihovna s otevřeným zdrojovým textem pro práci s konečnými převodníky. +more * [url=http://www. cis. uni-muenchen. de/~schmid/tools/SFST/]Stuttgart Finite State Transducer Tools[/url], sada nástrojů s otevřeným zdrojovým textem pro konečné převodníky * [url=http://jsalatas. ictpro. gr/java-fst-framework-api-review/]java FST Framework[/url], Java FST Framework s otevřeným zdrojovým textem schopný zpracovávat textový formát OpenFst. * [url=http://vcsn. lrde. epita. fr/]Vcsn[/url] , platforma s otevřeným zdrojovým textem pro C++ & IPython pro vážené automaty a racionální výrazy. * [url=http://web. stanford. edu/~laurik/fsmbook/home. html]Finite State Morphology--The Book[/url] XFST/ LEXC, popis implementace konečných převodníků firmy Xerox určených pro lingvistické aplikace. * [url=https://code. google. com/archive/p/foma/]FOMA[/url], implementace s otevřeným zdrojovým textem většiny funkcionalit implementace XFST/LEXC firmy Xerox.

Kategorie:Konečné automaty