Jump to content

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 годах.

См. также

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

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

[ редактировать ]
  • Колмерауэр, А: Q-системы или формализм для анализа и синтеза предложений на компьютере. Мимео, Монреаль, 1969 год.
  • Нгуен, Х.Т.: От гомогенных к гетерогенным CAT-системам. Диссертация UJF, Гренобль, 2009 г.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 40492abe2a212ddd75fb18bec1532e83__1715894340
URL1:https://arc.ask3.ru/arc/aa/40/83/40492abe2a212ddd75fb18bec1532e83.html
Заголовок, (Title) документа по адресу, URL1:
Q-systems - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)