Q-системы

Q-системы — это метод направленных преобразований графов в соответствии с заданными грамматическими правилами, разработанный в Университете Монреаля Аленом Кольмерауэром в 1967–70 годах для использования в обработке естественного языка . Университета Монреаля машинного перевода Система , TAUM-73 , использовала Q-Systems в качестве языкового формализма.

Структура данных, которой управляет Q-система, представляет собой Q-граф , который представляет собой ориентированный ациклический граф с одним входным узлом и одним выходным узлом, где каждая дуга несет помеченное упорядоченное дерево . Входное предложение обычно представляет собой линейный Q-граф, где каждая дуга содержит слово (дерево, сведенное к одному узлу, помеченному этим словом). После анализа Q-граф обычно представляет собой пучок путей из 1 дуги, каждая дуга несет в себе возможное дерево анализа. После генерации цель обычно состоит в том, чтобы создать столько путей, сколько желаемых выходных данных, снова с одним словом на дугу.

Q-система состоит из последовательности Q-обработок , каждая из которых представляет собой набор Q-правил вида <совпадающий_путь> == <добавленный_путь> [<условие>]. Q-обработки применяются последовательно, если только один из них не создает пустой Q-граф, и в этом случае результатом является последний полученный Q-граф. Три части правила могут содержать переменные для меток, деревьев и лесов. Все переменные после "==" должны присутствовать в части <matched_path>. Переменные являются локальными для правил.

Q-обработка работает в два этапа: добавление и очистка. Сначала он исчерпывающе применяет все свои правила, используя создание экземпляров (одностороннее объединение), тем самым добавляя новые пути к текущему Q-графу (добавленные дуги и их деревья могут использоваться для создания новых путей). Если и когда этот процесс добавления останавливается, все дуги, используемые в каком-либо успешном применении правила, удаляются, а также все неиспользуемые дуги, которых больше нет на пути от входного узла к выходному узлу. Следовательно, результат, если таковой имеется (если этап сложения завершается), снова является Q-графом. Это позволяет объединить несколько Q-систем, каждая из которых выполняет специализированную задачу, образуя вместе сложную систему. Например, ТАУМ 73 состоял из пятнадцати связанных Q-систем.

Расширение основной идеи Q-систем, а именно замена создания экземпляров унификацией (проще говоря, разрешение «новых» переменных в правой части правила и замена параметризованных помеченных деревьев логическими терминами) привело к Пролог , разработанный Аленом Кольмерауэром и Филиппом Русселем в 1972 году. Уточнения в другом направлении (уменьшение недетерминированности и введение типизированных меток) Джона Чандиу привели к созданию GramR , используемого для программирования METEO с 1985 года.

В 2009 году Хонг Тхай Нгуен или GETALP, ^[1] Гренобльская лаборатория компьютерных наук ^[2] переопределил Q-язык на C, используя ANTLR для компиляции Q-систем и Q-графов, а также алгоритм, предложенный Кристианом Бойте (поскольку ни один из них не был опубликован, а источники предыдущей реализации Fortran были утеряны). Эта реализация была исправлена, дополнена и расширена (для этикеток, использующих символы Юникода, а не только печатные символы CDC6600 исторической версии) Дэвидом Каттанео в 2010–2011 годах.

См. также

Погодная система

Ссылки

^ «Исследовательская группа по автоматическому переводу/автоматизированной языковой и речевой обработке» (на французском языке).
^ «ЛИГ» (на французском языке).

Дальнейшее чтение

Колмерауэр, А: Q-системы или формализм для анализа и синтеза предложений на компьютере. Мимео, Монреаль, 1969 год.
Нгуен, Х.Т.: От гомогенных к гетерогенным CAT-системам. Диссертация UJF, Гренобль, 2009 г.

Внешние ссылки

http://unldeco.imag.fr/unldeco/SystemsQ.po?localhost=/home/nguyenht/SYS-Q/MONITEUR/ ] новая демонстрация Q-систем

[1] «Исследовательская группа по автоматическому переводу/автоматизированной языковой и речевой обработке» (на французском языке).

[2] «ЛИГ» (на французском языке).

[1]

[2]