- 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 explicitamente definidos.
Contenido
Definición
Un transductor es adelantado si la salida esta 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
, con E un conjunto finito, el correspondiente transductor de estados finitos determinista p-subsecuencial adelantado (EDpSST, earliest deterministic finite-state p-subsequential transducer) es T = (Q,Σ,Γ,δ,λ,qI,ψ), donde :- Q es el conjunto
de todos los prefijos de entrada más el estado de absorción - Σ es el alfabeto de entrada
- Γ es el alfabeto de salida
es la función de transición
es la función de salida
λ(x,σ) = [LCP(τ(xx − 1E))] − 1[LCP(τ((xσ)(xσ) − 1E))] para
, e indefinido en otro caso.Si
![\mathrm{LCP}[\tau(E)]\neq\varepsilon](b/58bcf2afb6d92b82436eb9d0f42ddc00.png)
, todas las salidas 
tienen LCP[τ(E)] como prefijo.- qI = {ε} es el estado inicial
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.](8/4e86343ebe66e1374a1222de31b368bc.png)
Esta construcción es básicamente un trie para las cadenas de E dotada de funciones de salida λ y ψ 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
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ógido de la tablaLa 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 ∈ Σ es la cadena de entrada y t ∈ Γ 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
- 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
- Transductor de estados finitos
- Transductor secuencial
- Transductor subsecuencial
- Transductor p-subsecuencial
- Transductor p-subsecuencial adelantado
- Transductor de estados finitos determinista p-subsecuencial
Referencias
- Alicia Garrido-Alenda; Mikel L. Forcada (2002). «Comparing nondeterministic and quasideterministic finite-state transducers built from morphological dictionaries». Procesamiento del Lenguaje Natural. http://www.dlsi.ua.es/~mlf/docum/garrido02j.pdf.
- 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.
Categorías:- Lingüística computacional
- Transductores
- Q es el conjunto
Wikimedia foundation. 2010.
