Filtrovaná praskající rekurzivní přechodová síť - Filtered-popping recursive transition network - Wikipedia

A filtrovaná praskající rekurzivní přechodová síť (FPRTN),^[1] nebo jednoduše filtrovaná síť (FPN), je rekurzivní přechodová síť (RTN )^[2] rozšířen o mapu států ke klíčům, kde se vrací z a podprogram skok vyžaduje, aby byly akceptor a návratové stavy mapovány na stejný klíč. RTN jsou stroje konečného stavu které lze vidět jako konečné automaty prodloužena o a zásobník návratových států; stejně jako náročné přechody a ${ displaystyle varepsilon}$- přechody, RTN může definovat přechody hovorů. Tyto přechody provádějí a podprogram skok zatlačením cílového stavu přechodu na zásobník a přivedením stroje do volaného stavu. Pokaždé, když je dosažen stav akceptoru, je vrácen stav návratu v horní části zásobníku, za předpokladu, že zásobník není prázdný, a stroj je uveden do tohoto stavu.

V celém tomto článku označujeme rekurzivní přechodové sítě s filtrovaným vyskakováním jako FPN, i když tato zkratka je nejednoznačná (např .: fuzzy Petriho sítě ). Filtrované sítě a FPRTN jsou jednoznačné alternativy.

Formální definice

FPN je struktura ${ displaystyle (Q, K, Sigma, delta, kappa, Q_ {I}, F)}$ kde

• ${ displaystyle Q}$ je konečná množina států,
• ${ displaystyle K}$ je konečná sada klíčů,
• ${ displaystyle Sigma}$ je abeceda konečných vstupů,
• ${ displaystyle delta: Q krát ( Sigma pohár { varepsilon } pohár Q) do Q}$ je funkce částečného přechodu, ${ displaystyle varepsilon}$ jako prázdný symbol,
• ${ displaystyle kappa: Q až K}$ je mapa států ke klíčům,
• ${ displaystyle Q_ {I} subseteq Q}$ je množina počátečních stavů a
• ${ displaystyle F subseteq Q}$ je sada stavů přijetí.

Přechody

Přechody představují možnost přenést FPN ze zdrojového stavu ${ displaystyle q_ {s}}$ do cílového stavu ${ displaystyle q_ {t}}$ případně provedením další akce. V závislosti na této akci rozlišujeme následující typy výslovně-definované přechody:

• ${ displaystyle varepsilon}$- přechody jsou přechody formuláře ${ displaystyle delta (q_ {s}, varepsilon) až q_ {t}}$ a neprovádět žádnou další akci,
• náročné přechody jsou přechody formuláře ${ displaystyle delta (q_ {s}, sigma) až q_ {t}}$ a spotřebují vstupní symbol ${ displaystyle sigma}$, a
• přechody hovorů jsou přechody formuláře ${ displaystyle delta (q_ {s}, q_ {c}) až q_ {t}}$ a proveďte a podprogram skočit do volaného stavu ${ displaystyle q_ {c}}$ před dosažením ${ displaystyle q_ {t}}$.

Chování přechodů hovorů se řídí dvěma druhy implicitně-definované přechody:

• pro každý přechod hovoru ${ displaystyle delta (q_ {s}, q_ {c}) až q_ {t}}$ FPN implicitně definuje a push přechod , ze kterého stroj pochází ${ displaystyle q_ {s}}$ na ${ displaystyle q_ {c}}$ tlačením ${ displaystyle q_ {t}}$ na zásobník, a
• pro každou dvojici států ${ displaystyle (q_ {f}, q_ {r}) v F krát Q}$ FPN implicitně definuje a pop přechod , který přináší stroj z ${ displaystyle q_ {f}}$ na ${ displaystyle q_ {r}}$ praskáním ${ displaystyle q_ {r}}$ ze zásobníku iff ${ displaystyle q_ {r}}$ je stav v horní části zásobníku a ${ displaystyle kappa (q_ {f}) = kappa (q_ {r})}$.

Inicializace přechodů push podprogram skoky a popové přechody jsou ekvivalentní návratové příkazy.

Účel

A (přirozený jazyk ) text lze obohatit o metainformace aplikací a RTN s výstupem; například vložení RTN XML značky lze použít pro transformaci a prostý text do strukturovaného dokumentu XML. RTN s výstupem představujícím a přirozený jazyk gramatika by vymezil a přidal syntaktickou strukturu každé věty textu (viz analýza ). Ostatní RTN s výstupem mohou jednoduše označit textové segmenty obsahující relevantní informace (viz extrakce informací ). Aplikace RTN s výstupem představujícím nejednoznačná gramatika vede k souboru možných překladů nebo interpretací vstupu. Výpočet této sady má exponenciál náklady v nejhorším případě, dokonce i pro Earley parser pro RTN s výstupem,^[3] kvůli případům, kdy počet překladů exponenciálně roste w.r.t. vstupní délka; například počet interpretací a přirozený jazyk věta se exponenciálně zvyšuje w.r.t. počet nevyřešených předložková fráze přílohy:^[4][5]

• ve větě dívka uviděla opici dalekohledem, není známo, zda dívka použila dalekohled nebo ji opice držela (2¹ interpretace),
• ve větě dívka zahlédla opici s dalekohledem v zahradě, není také známo, zda byla opice na zahradě nebo se akce odehrála na zahradě (2² interpretace),
• ve větě dívka zahlédla opici s dalekohledem v zahradě pod stromem, není také známo, zda byla opice pod stromem nebo se akce odehrála pod stromem (2³ interpretace),
• atd.

FPN slouží jako kompaktní reprezentace této sady překladů a umožňují ji vypočítat v kubickém čase pomocí analyzátoru podobného Earleymu.^[1] Stavy FPN odpovídají stavům provádění (viz instrukční kroky ) analyzátoru Earley pro RTN bez výstup a přechody FPN odpovídají možným překladům vstupních symbolů. The ${ displaystyle kappa}$ mapa výsledného FPN dává korespondenci mezi reprezentovanými výstupními segmenty a rozpoznanými vstupními segmenty: vzhledem k rozpoznané vstupní posloupnosti ${ displaystyle sigma _ {1} ldots sigma _ {l}}$ a cestu FPN ${ displaystyle p}$ počínaje stavem ${ displaystyle q}$ a končí ve stavu ${ displaystyle q ^ { prime}}$, ${ displaystyle p}$ představuje možný překlad vstupního segmentu ${ displaystyle sigma _ { kappa (q) +1} ldots sigma _ { kappa (q ^ { prime})}}$. Funkce filtrovaného vyskakování je nutná, aby se zabránilo cestám FPN, které představují překlady odpojen nebo překrývající se vstupní segmenty: volání FPN může obsahovat několik překladových cest ze stavu volání do stavu akceptoru, kde vstupní segmenty, které odpovídají, sdílejí stejný počáteční bod, ale nemusí mít nutně stejnou délku. Pouze návratové stavy odpovídající stejnému vstupnímu bodu, než je stav přijímajícího, který ukončí hovor platný návratové státy.

Reference