Transductor de estados finitos determinista p-subsecuencial adelantado

Los transductores de estados finitos son Autómatas de estados finitos deterministas con transiciones sobre parejas de símbolos.

Un transductor de estados finitos determinista p-subsecuencial adelantado (TpSSDA o EDpSST de sus siglas en inglés Earliest Deterministic Finite-State p-Subsequential Transducers) es la implementación habitual de las transducciones p-subsecuenciales adelantadas para un diccionario morfológico no alineado. Éstos transductores no tienen estados de aceptación explícitamente definidos.

Definición editar

Un transductor es adelantado si la salida está asignada a los arcos de forma que se produzca tan pronto como sea posible.

Un transductor de estados finitos determinista p-subsecuencial adelantado es la implementación habitual de las transducciones p-subsecuenciales adelantadas para un diccionario morfológico no alineado.

Cada uno de sus estados representa el conjunto de prefijos que comparten un prefijo (el más largo posible) de salida común.

Se llega a un único estado para cada símbolo de entrada y estado, lo que hace que el autómata sea determinista.

La salida está asociada a las transiciones estado-a-estado: se va construyendo incrementalmente el prefijo común más largo.

Formalmente se define como:

Dada una transducción $\tau :E\to 2^{\Gamma ^{*}}$ , con $E$ un conjunto finito, el correspondiente transductor de estados finitos determinista $p$ -subsecuencial adelantado (ED $p$ SST, earliest deterministic finite-state $p$ -subsequential transducer) es $T=(Q,\Sigma ,\Gamma ,\delta ,\lambda ,q_{I},\psi )$ , donde :

$Q$ es el conjunto $Pr(E)\cup \{\perp \}$ de todos los prefijos de entrada más el estado de absorción
$\Sigma$ es el alfabeto de entrada
$\Gamma$ es el alfabeto de salida
$\delta :Q\times \Sigma \rightarrow Q$ es la función de transición

$\delta (x,\sigma )=\left\{{\begin{array}{cl}x\sigma &{\mbox{ Si }}x,x\sigma \in \mathrm {Pr} (E)\\\perp &{\mbox{otro caso }}\end{array}}\right.$

$\lambda :Q\times \Sigma \rightarrow \Gamma ^{*}$ es la función de salida

$\lambda (x,\sigma )=[\mathrm {LCP} (\tau (xx^{-1}E))]^{-1}[\mathrm {LCP} (\tau ((x\sigma )(x\sigma )^{-1}E))]$ para $x,x\sigma \in \mathrm {Pr} (E)$ , e indefinido en otro caso.

Si $\mathrm {LCP} [\tau (E)]\neq \varepsilon$ , todas las salidas $\lambda (\epsilon ,\sigma )$ tienen $\mathrm {LCP} [\tau (E)]$ como prefijo.

$q_{I}=\{\varepsilon \}$ es el estado inicial
$\psi :Q\rightarrow 2^{\Gamma ^{*}}$ es una función que asigna a cada estado un conjunto de colas a agregar a la salida al final de la entrada

$\psi (w)=\left\{{\begin{array}{cl}[\mathrm {LCP} (\tau (xx^{-1}E))]^{-1}\tau (w)&{\mbox{ si }}w\in E\\\emptyset &{\mbox{ otro caso }}\end{array}}\right.$

Esta construcción es básicamente un trie para las cadenas de $E$ dotada de funciones de salida $\lambda$ y $\psi$ que producen la cadena de salida tan pronto como es posible (la información de salida puede ser añadida fácilmente a lo largo del recorrido en post-orden del trie). El transductor resultante (acíclico) se puede minimizar fácilmente en un transductor equivalente que produce la misma salida para todos los prefijos en $Pr(E)$ y añadiendo las mismas colas a todas las cadenas de caracteres en E mientras utiliza el número mínimo de estados.

Ejemplo editar

Tabla del diccionario morfológico utilizado para construir el Transductor de estados finitos determinista p-subsecuencial adelantado

Transductor de estados finitos determinista p-subsecuencial adelantado correspondiente al diccionario morfológico de la tabla

La imagen de la tabla representa el diccionario morfológico alineado utilizado para representar el transductor de estados finitos determinista p-subsecuencial adelantado que se representa en la segunda imagen.

En la representación del transductor, las arístas tienen representadas los pares de entrada y salida separados por el signo ':', es decir, el par s : t, donde s ∈ $\Sigma$ es la cadena de entrada y t ∈ $\Gamma$ es la cadena de salida.

Podemos observar que es adelantado, puesto que una vez que se ha visto la cadena "reco" el transductor asigna a la salida la cadena "recordar".

Inconvenientes del uso de TpSSDA como analizador morfológico editar

Si una transducción se valida solamente al final de la entrada, se tiene que retrasar salida.
Si se añade una nueva entrada en el diccionario morfológico, el transductor tiene que reconstruirse de nuevo, los cálculos del prefijo común más largo y los estados equivalentes pueden no ser correctos para muchos estados.

Estos inconvenientes pueden evitarse permitiendo al transductor mantener varias hipótesis de transducción vivas durante el proceso, algunas de los cuales se podrán descartar después de leer más entrada (es decir, un transductor no determinista). Este tipo de la transformación no requiere un realineamiento de las entradas y salidas, pero puede conservar las alineaciones en un diccionario morfológico alineado.

Véase también editar

Referencias editar

Alicia Garrido-Alenda; Mikel L. Forcada (2002). «Comparing nondeterministic and quasideterministic finite-state transducers built from morphological dictionaries». Procesamiento del Lenguaje Natural.

Mehryar Mohri (1997,). «Finite-state transducers in language and speech processing,». Computational Linguistics,. 23, (2,). 269--311.

J. Oncina and P. García and E. Vidal, (1993,). «Learning subsequential transducers for pattern recognition interpretation tasks,». IEEE Transactions on Pattern Analysis and Machine Intelligence,. 15,. 448--458.

Datos: Q6151640