Конечный преобразователь

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (August 2014) (Learn how and when to remove this message) This article has an unclear citation style. The references used may be made clearer with a different or consistent style of citation and footnoting. (August 2014) (Learn how and when to remove this message) (Learn how and when to remove this message)

Конечный автомат ( FST ) — это конечный автомат с двумя лентами памяти , следуя терминологии машин Тьюринга : входная лента и выходная лента. Это контрастирует с обычным конечным автоматом , который имеет одну ленту. FST — это тип конечного автомата (FSA), который отображает два набора символов. ^[1] FST более общий, чем FSA. FSA определяет формальный язык , определяя набор принятых строк, в то время как FST определяет отношение между наборами строк.

FST будет считывать набор строк на входной ленте и генерировать набор отношений на выходной ленте. FST можно рассматривать как транслятор или релятор между строками в наборе.

В морфологическом анализе примером может служить ввод строки букв в FST, после чего FST выводит строку морфем .

Внешние видео
Конечные преобразователи // Технологический институт Карлсруэ , видео на YouTube

Можно сказать, что автомат распознает строку , если рассматривать содержимое его ленты как входные данные. Другими словами, автомат вычисляет функцию, которая отображает строки в множество {0,1}. В качестве альтернативы можно сказать, что автомат генерирует строки, что означает рассмотрение его ленты как выходной ленты. С этой точки зрения автомат генерирует формальный язык , который является набором строк. Два представления автоматов эквивалентны: функция, которую вычисляет автомат, является в точности индикаторной функцией набора строк, которые он генерирует. Класс языков, генерируемых конечными автоматами, известен как класс регулярных языков .

Две ленты преобразователя обычно рассматриваются как входная лента и выходная лента. С этой точки зрения преобразователь, как говорят, преобразует (т. е. переводит) содержимое своей входной ленты на свою выходную ленту, принимая строку на своей входной ленте и генерируя другую строку на своей выходной ленте. Он может делать это недетерминированно и может производить более одного вывода для каждой входной строки. Преобразователь также может не производить вывода для заданной входной строки, в этом случае говорят, что он отклоняет ввод. В общем случае преобразователь вычисляет отношение между двумя формальными языками.

Каждый конечный преобразователь строка-строка связывает входной алфавит Σ с выходным алфавитом Γ. Отношения R на Σ*×Γ*, которые могут быть реализованы как конечные преобразователи, называются рациональными отношениями . Рациональные отношения, которые являются частичными функциями , т. е. связывают каждую входную строку из Σ* с максимум одним Γ*, называются рациональными функциями .

Конечные преобразователи часто используются для фонологического и морфологического анализа в исследованиях и приложениях обработки естественного языка . Пионеры в этой области включают Рональда Каплана , Лаури Карттунена , Мартина Кей и Киммо Коскенниеми . ^{[2] [ необходим неосновной источник ]} Распространенный способ использования преобразователей — это так называемый «каскад», где преобразователи для различных операций объединяются в один преобразователь путем повторного применения оператора композиции (определенного ниже).

Формально конечный преобразователь T представляет собой 6-кортеж ( Q , Σ, Γ, I , F , δ ), такой что:

• Q — конечное множество , множество состояний ;
• Σ — конечный набор, называемый входным алфавитом ;
• Γ — конечное множество, называемое выходным алфавитом ;
• I — подмножество Q , множества начальных состояний ;
• F — это подмножество Q , множества конечных состояний ; и
• ${\displaystyle \delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q}$(где ε — пустая строка ) — отношение перехода .

Мы можем рассматривать ( Q , δ ) как помеченный ориентированный граф , известный как граф переходов T : множество вершин равно Q , и это означает, что существует помеченное ребро, идущее от вершины q к вершине r . Мы также говорим, что a — это входная метка , а b — выходная метка этого ребра.${\displaystyle (q,a,b,r)\in \delta }$

ПРИМЕЧАНИЕ: Это определение конечного преобразователя также называется буквенным преобразователем (Roche и Schabes, 1997); возможны альтернативные определения, но все они могут быть преобразованы в преобразователи, следующие этому.

Определим расширенное отношение перехода как наименьшее множество, такое что:${\displaystyle \delta ^{*}}$

• ${\displaystyle \delta \subseteq \delta ^{*}}$;
• ${\displaystyle (q,\epsilon ,\epsilon ,q)\in \delta ^{*}}$для всех ; и${\displaystyle q\in Q}$
• когда бы то ни было и тогда .${\displaystyle (q,x,y,r)\in \delta ^{*}}$${\displaystyle (r,a,b,s)\in \delta }$${\displaystyle (q,xa,yb,s)\in \delta ^{*}}$

Расширенное отношение перехода по сути является рефлексивным транзитивным замыканием графа перехода, которое было дополнено для учета меток ребер. Элементы известны как пути . Метки ребер пути получаются путем конкатенации меток ребер его составляющих переходов по порядку.${\displaystyle \delta ^{*}}$

Поведение преобразователя T — это рациональное отношение [ T ], определяемое следующим образом: тогда и только тогда, когда существует и такое, что . Это означает, что T преобразует строку в строку , если существует путь из начального состояния в конечное состояние, входная метка которого — x , а выходная метка — y .${\displaystyle x[T]y}$ ${\displaystyle i\in I}$${\displaystyle f\in F}$${\displaystyle (i,x,y,f)\in \delta ^{*}}$${\displaystyle x\in \Sigma ^{*}}$${\displaystyle y\in \Gamma ^{*}}$

Конечные преобразователи состояний могут быть взвешенными, где каждый переход помечен весом в дополнение к входным и выходным меткам. Взвешенный конечный преобразователь состояний (WFST) над набором K весов может быть определен аналогично невзвешенному как 8-кортеж T =( Q , Σ, Γ, I , F , E , λ , ρ ) , где:

• Q , Σ, Γ, I , F определены, как указано выше;
• ${\displaystyle E\subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q\times K}$(где ε — пустая строка ) — конечный набор переходов;
• ${\displaystyle \lambda :I\rightarrow K}$отображает начальные состояния в веса;
• ${\displaystyle \rho :F\rightarrow K}$отображает конечные состояния в веса.

Для того чтобы сделать некоторые операции над WFST хорошо определенными, удобно потребовать, чтобы набор весов образовывал полукольцо . ^[3] Два типичных полукольца, используемых на практике, — это логарифмическое полукольцо и тропическое полукольцо : недетерминированные автоматы можно рассматривать как имеющие веса в булевом полукольце . ^[4]

Стохастические FST (также известные как вероятностные FST или статистические FST) предположительно являются формой взвешенных FST. ^{[ необходима ссылка ]}

Следующие операции, определенные на конечных автоматах, также применимы к конечным преобразователям:

• Объединение . Для данных преобразователей T и S существует преобразователь такой, что тогда и только тогда, когда или .${\displaystyle T\cup S}$${\displaystyle x[T\cup S]y}$${\displaystyle x[T]y}$${\displaystyle x[S]y}$
• Конкатенация . При наличии преобразователей T и S существует преобразователь такой, что тогда и только тогда, когда существуют с и${\displaystyle T\cdot S}$${\displaystyle x[T\cdot S]y}$${\displaystyle x_{1},x_{2},y_{1},y_{2}}$${\displaystyle x=x_{1}x_{2},y=y_{1}y_{2},x_{1}[T]y_{1}}$${\displaystyle x_{2}[S]y_{2}.}$
• Замыкание Клини . При наличии преобразователя T может существовать преобразователь со следующими свойствами: ^[5]${\displaystyle T^{*}}$

${\displaystyle \epsilon [T^{*}]\epsilon }$;

( к1 )

если и , то ;${\displaystyle w[T^{*}]y}$${\displaystyle x[T]z}$${\displaystyle wx[T^{*}]yz}$

( к2 )

и не выполняется, если это не предписано ( k1 ) или ( k2 ).${\displaystyle x[T^{*}]y}$

• Композиция . Если задан преобразователь T на алфавитах Σ и Γ и преобразователь S на алфавитах Γ и Δ, то существует преобразователь на Σ и Δ такой, что тогда и только тогда, когда существует строка такая, что и . Эта операция распространяется на взвешенный случай. ^[6]${\displaystyle T\circ S}$${\displaystyle x[T\circ S]z}$${\displaystyle y\in \Gamma ^{*}}$${\displaystyle x[T]y}$${\displaystyle y[S]z}$

Это определение использует ту же нотацию, которая используется в математике для композиции отношений . Однако общепринятое прочтение композиции отношений — наоборот: даны два отношения T и S , когда существуют некоторые y, такие что и${\displaystyle (x,z)\in T\circ S}$${\displaystyle (x,y)\in S}$${\displaystyle (y,z)\in T.}$

• Проекция на автомат. Есть две функции проекции: сохраняет входную ленту и сохраняет выходную ленту. Первая проекция определяется следующим образом:${\displaystyle \pi _{1}}$${\displaystyle \pi _{2}}$${\displaystyle \pi _{1}}$

Для данного преобразователя T существует конечный автомат , который принимает x тогда и только тогда, когда существует строка y, для которой${\displaystyle \pi _{1}T}$${\displaystyle \pi _{1}T}$${\displaystyle x[T]y.}$

Вторая проекция определяется аналогично.${\displaystyle \pi _{2}}$

• Детерминизация . При наличии преобразователя T мы хотим построить эквивалентный преобразователь, который имеет уникальное начальное состояние и такой, что никакие два перехода, покидающие любое состояние, не имеют одну и ту же входную метку. Конструкция powerset может быть расширена до преобразователей или даже весовых преобразователей, но иногда не останавливается; действительно, некоторые недетерминированные преобразователи не допускают эквивалентных детерминированных преобразователей. ^[7] Были предложены характеристики детерминируемых преобразователей ^[8] вместе с эффективными алгоритмами для их проверки: ^[9] они полагаются на полукольцо, используемое в весовом случае, а также на общее свойство структуры преобразователя (свойство близнецов).
• Толкание веса для утяжеленного случая. ^[10]
• Минимизация для взвешенного случая. ^[11]
• Удаление эпсилон-переходов .

• Можно решить , является ли отношение [ T ] преобразователя T пустым.
• Можно решить, существует ли строка y такая, что x [ T ] y для данной строки x .
• Невозможно решить , эквивалентны ли два преобразователя. ^[12] Однако эквивалентность разрешима в частном случае, когда отношение [ T ] преобразователя T является (частичной) функцией.
• Если определить алфавит меток , то конечные преобразователи изоморфны NDFA над алфавитом и, следовательно, могут быть детерминированы (превращены в детерминированные конечные автоматы над алфавитом ) и впоследствии минимизированы так, чтобы они имели минимальное количество состояний. ^{[ требуется ссылка ]}${\displaystyle L=(\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})}$${\displaystyle L}$${\displaystyle L=[(\Sigma \cup \{\epsilon \})\times \Gamma ]\cup [\Sigma \times (\Gamma \cup \{\epsilon \})]}$

FST используются на этапе лексического анализа компиляторов для связывания семантического значения с обнаруженными токенами. ^[13]

Контекстно-зависимые правила перезаписи вида a → b / c _ d , используемые в лингвистике для моделирования фонологических правил и изменения звука , вычислительно эквивалентны конечным преобразователям, при условии, что применение нерекурсивно, т. е. правилу не разрешено переписывать одну и ту же подстроку дважды. ^[14]

Взвешенные FST нашли применение в обработке естественного языка , включая машинный перевод , и в машинном обучении . ^{[15] [16]} Реализацию для разметки частей речи можно найти в качестве одного из компонентов библиотеки OpenGrm ^[17] .

• Машина для помола муки
• машина Мура
• Морфологический словарь
• фома (программное обеспечение)
• Древесный преобразователь
• Реляционный преобразователь

• OpenFst — библиотека с открытым исходным кодом для операций FST.
• Конечно-ступенчатая морфология — книга, заархивированная 25 марта 2022 г. на Wayback Machine XFST/LEXC, описание реализации компанией Xerox конечных преобразователей, предназначенных для лингвистических приложений.
• Реализация и расширение Xerox fst с открытым исходным кодом в Хельсинки
• FOMA — реализация с открытым исходным кодом большинства возможностей реализации Xerox XFST/LEXC.
• Stuttgart Finite State Transducer Tools — еще один набор инструментов FST с открытым исходным кодом
• java FST Framework — java FST Framework с открытым исходным кодом, способный обрабатывать текстовый формат OpenFst.
• Vcsn Архивировано 23 июня 2020 г. на Wayback Machine , платформе с открытым исходным кодом (C++ и IPython) для взвешенных автоматов и рациональных выражений.

• Джурафски, Дэниел ; Джеймс Х. Мартин (2000). Обработка речи и языка . Prentice Hall. стр. 71–83. ISBN 0-13-095069-6.
• Корнаи, Андраш (1999). Расширенные модели языка с конечным состоянием . Издательство Кембриджского университета. ISBN 0-521-63198-X.
• Рош, Эммануэль; Ив Шабес (1997). Обработка конечного языка . МТИ Пресс. стр. 1–65. ISBN 0-262-18182-7.
• Бисли, Кеннет Р.; Лаури Карттунен (2003). Морфология конечных состояний . Центр изучения языка и информации. ISBN 1-57586-434-7.
• Роарк, Брайан; Ричард Спроут (2007). Вычислительные подходы к морфологии и синтаксису . Oxford University Press. ISBN 978-0-19-927478-9.
• Берстель, Жан (1979). Трансдукции и контекстно-свободные языки . Тойбнер Верлаг.. Бесплатная версия PDF