Q-systémy - Q-systems
![]() | Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace.Květen 2012) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
![]() | tento článek poskytuje nedostatečný kontext osobám, které toto téma neznají.Října 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
Q-systémy jsou metodou řízený graf transformace podle daných gramatika pravidla, vyvinutá na Université de Montréal podle Alain Colmerauer v letech 1967-70 pro použití v zpracování přirozeného jazyka. Université de Montréal's strojový překlad Systém, TAUM-73, použil Q-Systems jako svůj jazykový formalismus.
Datová struktura manipulovaná systémem Q je a Q-graf, což je směrovaný acyklický graf s jedním vstupním uzlem a jedním výstupním uzlem, kde každý oblouk nese a označený objednaný strom. Vstupní věta je obvykle reprezentována lineárním Q-grafem, kde každý oblouk nese slovo (strom redukovaný na jeden uzel označený tímto slovem). Po analýze je Q-graf obvykle svazek cest 1 oblouku, přičemž každý oblouk nese možný strom analýzy. Po generaci je cílem obvykle vyprodukovat tolik cest, kolik požadovaných výstupů, s opět jedním slovem na oblouk.
Q-systém se skládá z posloupnosti Q-ošetření, z nichž každý je soubor Q-pravidla, ve tvaru [ Ošetření Q funguje ve dvou krocích, přidání a čištění. Nejprve aplikuje všechna svá pravidla vyčerpávajícím způsobem instance (jednosměrné sjednocení), čímž se přidají nové cesty k aktuálnímu Q-grafu (přidané oblouky a jejich stromy lze použít k vytvoření nových cest). Pokud a kdy se tento proces přidání zastaví, jsou vymazány všechny oblouky použité v nějaké úspěšné aplikaci pravidel, stejně jako všechny nepoužité oblouky, které již nejsou na žádné cestě ze vstupního uzlu do výstupního uzlu. Výsledkem, pokud existuje (je-li krok přidání ukončen), je tedy opět Q-graf. To umožňuje zřetězit několik Q-systémů, z nichž každý provádí specializovaný úkol a společně tvoří komplexní systém. Například TAUM 73 sestával z patnácti zřetězených Q-systémů. Rozšíření základní myšlenky Q-systémů, konkrétně nahradit instanci pomocí unifikace (jednoduše řečeno, povolit „nové“ proměnné v pravé části pravidla a nahradit parametrizované označené stromy logickými výrazy) vedlo k Prolog, navrhl Alain Colmerauer a Philippe Roussel v roce 1972. Vylepšení v opačném směru (snížení nedeterminismu a zavedení typových štítků) o John Chandioux vedl k GramR, který se používá k programování METEO od roku 1985. V roce 2009 Hong Thai Nguyen ze společnosti GETALP[1], Laboratoire d'Informatique de Grenoble[2] (reimplemented the Q-language in C, using ANTLR to compile the Q-systems and the Q-graphs, and the algorithm scheduled by Christian Boitet (as none were been published and sources of the previous Fortran implementation were been lost). byl opraven, doplněn a rozšířen (na štítky používající znaky Unicode a nejen tisknutelné znaky CDC6600 historické verze) Davidem Cattanéem v letech 2010-11.Viz také
Reference
Další čtení
externí odkazy