Transductor de estados finitos determinista p-subsecuencial adelantado

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 \tau:E\to 2^{\Gamma^*}, 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 Pr(E)\cup\{\perp\} de todos los prefijos de entrada más el estado de absorción
  • Σ es el alfabeto de entrada
  • Γ 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

λ(x,σ) = [LCP(τ(xx − 1E))] − 1[LCP(τ((xσ)(xσ) − 1E))] 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 LCP[τ(E)] como prefijo.

  • qI = {ε} 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 λ 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 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 ∈ Σ 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

Referencias

  • 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. 

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Transductor de estados finitos determinista p-subsecuencial — Un transductor de estados finitos determinista p subsecuencial es un Autómata de estados finitos deterministas con transiciones sobre parejas de símbolos. Éstos transductores no tienen estados de aceptación explicitamente definidos. Cada uno de… …   Wikipedia Español

  • Transductor de estados finitos — Un transductor de estados finitos, o transductor finito, es un autómata finito (o máquina de estados finitos) con dos cintas, una de entrada y otra de salida. Esto contrasta con un autómata finito habitual, que tienes solamente una cinta. Podemos …   Wikipedia Español

  • Transductor p-subsecuencial adelantado — Un Transductor p subsecuencial adelatado es un transductor p subsecuencial con la salida asignada a los arcos de forma que se produzca tan pronto como sea posible. Una transducción que asigna a cada cadena de caracteres en un conjunto de cadenas… …   Wikipedia Español

  • Transductor subsecuencial — Un transductor subsecuencial o transductor 1 subsecuencial es aquel donde los símbolos de salida se generan sólo cuando se han visto suficientes símbolos en la entrada para garantizar una salida correcta. Se puede decir que es un transductor… …   Wikipedia Español

  • Transductor p-subsecuencial — Un transductor p subsecuencial es un transductor subsecuencial que produce un número p de cadenas de salida adicional.[1] Se puede decir que es un transductor secuencial ampliado para permitir un número finito p de cadenas de salida en los… …   Wikipedia Español

  • Transducción secuencial — Este artículo o sección tiene un estilo difícil de entender para los lectores interesados en el tema. Si puedes, por favor edítalo y contribuye a hacerlo más accesible para el público general, sin eliminar los detalles técnicos que interesan a… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”