Что такое преобразователь конечного состояния?

Ответ 1

Преобразователь конечного состояния (FST) представляет собой автомат с конечным состоянием (FSA, FA), который производит выход, а также считывающий ввод, что означает, что он полезен для синтаксического анализа (в то время как "голый" FSA может использоваться только для распознавания, т.е. сопоставление с образцом).

FST состоит из конечного числа состояний, которые связаны переходами, помеченными парой ввода/вывода. FST запускается в заданном начальном состоянии и переходит в разные состояния в зависимости от входа, при этом выдавая результат в соответствии со своей таблицей перехода.

FST полезны в НЛП и распознавании речи, потому что они обладают хорошими алгебраическими свойствами, особенно в том, что они могут быть свободно объединены (образуют алгебру) по композиции, которая реализует реляционный состав на регулярных отношениях (думайте об этом как недетерминированную функцию состав), оставаясь очень компактным. FST могут обрабатывать регулярные языки в строки в линейном времени.

В качестве примера я однажды применил морфологическое разборку как группу FST. Мой основной FST для глаголов превратил обычный глагол, скажем, "пошел", в "walk + PAST". У меня также был FST для глагола "быть", который превратил бы "есть" в "be + PRESENT + 3rd" (3-й человек) и аналогично для других неправильных глаголов. Все FST были объединены в один, используя компилятор FST, который создал один FST, который был намного меньше суммы его частей и работал очень быстро. FST могут быть созданы различными инструментами, которые принимают расширенный синтаксис регулярных выражений.

Ответ 2

Преобразователь конечного состояния по существу является автоматом конечного состояния, который работает на двух (или более) лентах. Самый распространенный способ думать о преобразователях - это своего рода "переводная машина". Они читают с одной из лент и пишут на другую. Это, например, преобразователь, переводящий a в b s:

a:b по дуге означает, что в этом переходе преобразователь считывает a с первой ленты и записывает b на второй.

Ссылка: Конечные преобразователи состояния

Ответ 3

В максимально простых терминах я понимаю, что FST - это, по сути, "вещь", которая перемещается из одного состояния в другое на основе входной ленты и записывает на другую выходную ленту. Лента - это, по существу, набор входов, таких как символы в строке.

Весь FST представлен множеством состояний и связей между ними. Ссылка активируется, когда ее входное условие правильное, а затем дает затем следующее состояние скорректированной ленты.

Например, скажем, FST начинается с ленты abc в состоянии 1. Ссылка на состояние 2 соответствует a и изменяется на b. Это будет активировано, установите выходную ленту только на b и передайте оставшуюся bc в состояние 2. Как вы можете видеть, каждое состояние активируется только в том случае, если есть ссылка на него, условия ввода которого были правильными, проходит оставшийся вход в следующее состояние и записывается на отдельную выходную ленту. Каждый FST работает по ленте один раз и выводит на другую ленту один раз.

Чтобы получить более четкое представление о них прочитать и взглянуть на диаграммы в этой статье.