next up previous
Siguiente: 2. El programa a Subir: Presentación del problema y Anterior: Presentación del problema y

1. Planteamiento del problema.

Un texto T es una secuencia de líneas. Cada línea es una secuencia de tokens terminada por un carácter de salto de línea (código ASCII 0x0A). Un token es un signo de puntuación o una palabra. Una palabra es una secuencia de caracteres contiguos sin signos de puntuación rodeada de espacio en blanco. Un espacio en blanco es una secuencia de espacios, tabuladores u otros caracteres no visualizables, exceptuando el salto de línea. El Vocabulario de T es el conjunto de tokens distintos que se encuentran en T.

En aras a la simplificación, en todos los textos que se van a considerar en este concurso, los signos de puntuación estarán siempre separados por espacio en blanco y todas las palabras estarán en minúsculas.

Dado un texto T, una Bigrama es una terna (y', y, p), donde y', y son 2 tokens consecutivos de T, y p es la probabilidad condicional Pr(y | y'); es decir, la probabilidad de que el token y aparezca a continuación de y'.

En general, en corpus grandes, si N es el número de tokens y M es el tamaño del vocabulario, el número de Bigramas distintas puede crecer cuadraticamente con M, siempre que M sea mucho menor que N.

El concepto de Bigrama es muy versátil para resolver distintos problemas asociados al tratamiento del lenguaje natural. Por ejemplo, las Bigramas se usan como Modelos del Lenguaje en Reconocimiento Automático del Habla para conseguir precisión aceptable en reconocimiento de habla contínua o aplicaciones de dictado. Así mismo, las N-Gramas se usan en aplicaciones de Procesado Predictivo de Texto, como por ejemplo para facilitar la edición de mensajes o textos cortos en teléfonos móviles y/o PDAs, o como asistente de edición en dispositivos de entrada de texto para minusválidos.

Las Bigramas son también útiles para implementar sistemas estadísticos de Traducción Automática, capaces de traducir texto de una Lengua Fuente en una Lengua Destino.

Para ello, se necesita un conjunto de Bigramas, B, de la lengua destino y un Diccionario Estadístico, E. Este diccionario es un conjunto de ternas (x, y, p), donde x e y son tokens de las lengua fuente y destino, respectivamente, y p es la probabilidad condicional Pr(y | x); es decir, la probabilidad de que y sea la traducción del token dado x.

Un Corpus Bilingüe es una secuencia de pares de líneas (f, d) de texto de una lengua fuente y una lengua destino, tales que d es la traducción de f. Tanto B como E pueden obtenerse a partir de un corpus bilingüe mediante métodos estadísticos adecuados. A continuación se muestra un ejemplo de corpus bilingüe C y los correspondientes B como E estimados a partir de C:



Ejemplo de corpus bilingüe

el triunfo de un descreído puede estar cercano 
el triomf d' un descregut pot estar proper

ser un descreído tiene la ventaja de estar muy cercano de la verdad
ser un descregut té l' avantatge d' estar molt proper de la veritat

Ejemplo de parte de un diccionario estadístico (fuente destino probabilidad)

el el 1.0
la la 0.5
la l'  0.5
descreído 1descregut .0
del del 1.0
de d' 0.66
de de 0.33
triunfo triomf  1.0
cercano proper 1.0
...

Ejemplo de parte de un modelo de bigramas (destino-previo destino probabilidad)

<INI> el 0.5
el triomf 1.0
descregut pot 0.5
descregut té d 0.5
estar proper 0.5
estar molt  0.5
l' avantatge  1.0
d' un  0.5
d' estar 0.5
...

Existen en la actualidad métodos sofisticados para obtener traducciones estadísticas de calidad razonable. Aquí nos limitaremos a un método extremadamente simple para obtener traducciones palabra a palabra. Esta limitación puede eliminarse mediante extensiones de dicho método que no se considerarán en este concurso. El método propuesto obtiene una traducción de una línea de texto fuente f en una línea de texto destino d mediante el siguiente algoritmo voraz, A:

Algoritmo voraz para la traducción monótona palabra a palabra
Datos:
Una frase fuente de n palabras f1, f2, ... ,fn.
Un diccionario estadístico: E.
Un modelo de bigramas destino: B.
Resultado:
Una frase destino de n palabras d1, d2, ..., dn

Procedimiento:
Para i=1 hasta n
Escoger di tal que E(di,si)xB(di,di-1)  >   E(d,si)xB(d,di-1) para cualquier otra d
Fin para
Fin algoritmo

Así pues, el problema planteado en este concurso consite en:

Dado un Diccionario Estadístico, E, un conjunto de Bigramas, B, y un texto de la lengua fuente, F, obtener la traducción de F en la lengua destino mediante el algoritmo voraz A indicado anteriormente; es decir, obtener D = A(E, B, F)

Utilizando las estructuras de datos y algoritmos adecuados, el problema propuesto puede resolverse de muy diversas maneras. En general puede ser útil comenzar por representar los tokens mediante números enteros, utilizando una correspondencia basada en un diccionario o tabla hash. Por otra parte, para representar E y/o B tambíen sería posible utilizar hashing, aunque en este caso la representación más adecuada dependerá de cómo se vaya a abordar el subsiguente problema de cómputo.


next up previous
Siguiente: 2. El programa a Subir: Presentación del problema y Anterior: Presentación del problema y
oraculo@dsic.upv.es