Q-системы представляют собой метод ориентированного графа преобразований в соответствии с заданными грамматическими правилами, разработанный в Университете Монреале по Ален Колмерауэр в 1967-70 для использования в обработке естественного языка . Система машинного перевода Университета Монреаля , TAUM-73 , использовала Q-Systems в качестве языкового формализма.
Структура данных, управляемая Q-системой, представляет собой Q-граф , который представляет собой ориентированный ациклический граф с одним входным узлом и одним выходным узлом, где каждая дуга несет помеченное упорядоченное дерево . Входное предложение обычно представлено линейным Q-графом, в котором каждая дуга содержит слово (дерево, сведенное к одному узлу, помеченному этим словом). После анализа Q-граф обычно представляет собой связку путей с одной дугой, каждая дуга имеет возможное дерево анализа. После генерации цель обычно состоит в том, чтобы создать столько путей, сколько требуется на выходе, снова с одним словом на дугу.
Q-система состоит из последовательности Q-обработок , каждая из которых является набором Q-правил , в форме
Q-обработка состоит из двух этапов: добавления и очистки. Сначала он исчерпывающе применяет все свои правила, используя создание экземпляров (одностороннее объединение), тем самым добавляя новые пути к текущему Q-графу (добавленные дуги и их деревья могут использоваться для создания новых путей). Если и когда этот процесс добавления останавливается, все дуги, использованные в каком-либо успешном применении правила, стираются, а также все неиспользуемые дуги, которых больше нет на любом пути от входного узла к выходному узлу. Следовательно, результат, если он есть (если этап сложения завершается), снова является Q-графом. Это позволяет объединить в цепочку несколько Q-систем, каждая из которых выполняет специализированную задачу, вместе формируя сложную систему. Например, TAUM 73 состоял из пятнадцати связанных Q-систем.
Расширение основной идеи Q-систем, а именно замена создания экземпляров унификацией (проще говоря, разрешить «новые» переменные в правой части правила и заменить параметризованные помеченные деревья логическими терминами) привело к Prolog , разработанный Аленом Колмерауэром и Филиппом Русселем в 1972 году. Уточнения в другом направлении (уменьшение недетерминизма и введение типизированных меток) Джона Чандиу привели к GramR , который используется для программирования METEO с 1985 года.
В 2009 году Хонг Тай Нгуен из GETALP, [1] Laboratoire d'Informatique de Grenoble [2] (повторно реализовал Q-язык на C, используя ANTLR для компиляции Q-систем и Q-графов, а также алгоритм, предложенный Кристианом). Boitet (поскольку ни один не был опубликован, а исходные коды предыдущей реализации Fortran были утеряны). Эта реализация была исправлена, дополнена и расширена (для меток, использующих символы Unicode, а не только печатные символы CDC6600 исторической версии) Дэвидом Каттанео. в 2010-11 гг.
Смотрите также
Рекомендации
- ^ "Groupe d'Etude en Traduction Automatique / Traitement Automatisé des Langues et de la Parol" (на французском языке).
- ^ «ЛИГ» (на французском).
дальнейшее чтение
- Colmerauer, A: Les systèmes Q или формализм для анализатора и синтезатора фраз на основе обычных данных. Мимео, Монреаль, 1969.
- Нгуен, HT: Des systèmes de TA homogènes aux systèmes de TAO hétérogènes. этот UJF, Гренобль, 2009.
Внешние ссылки
- http://unldeco.imag.fr/unldeco/SystemsQ.po?localhost=/home/nguyenht/SYS-Q/MONITEUR/ ] демонстрация новых Q-систем