Q-системы
![]() | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( Май 2012 г. ) |
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-систем