COMPRESIÓN DE MODELOS DE LENGUAJE CON CODIFICACIÓN GOLOMB.

Compresión de modelos de lenguaje con codificación Golomb La explicación dada a continuación se proporciona meramente como información de antecedentes general y no se pretende que se use como una ayuda al determinar el alcance de la materia objeto que se reivindica. Los modelos de lenguaje se usan en una variedad de aplicaciones incluyendo aplicaciones de canal con ruido tales como procesamiento de lenguaje natural, revisión ortográfica y similares. En las aplicaciones de lenguaje natural, normalmente actúa un reconocedor de voz que combina evidencia acústica (modelo de canal) con unas expectativas acerca de lo que es probable que diga el usuario (modelo de lenguaje). Se hace referencia a una forma común de modelos de lenguaje como un trigrama. En general, un ngrama es una secuencia secundaria de n testigos (palabras). Un trigrama es una secuencia secundaria de 3 testigos. Por ejemplo, a partir de la expresión to be or not to be, pueden generarse 8 trigramas: $ $ to, $ to be, to be or be or not, or not to, not to be, to be $ y be $ $, en los que la cadena de entrada se rellena con dos testigos especiales que se indican en: $. La estadística puede aplicarse a tales ngramas para estimar una probabilidad de que un usuario pretendiera una entrada particular. A pesar de que mil millones de palabras de texto solía considerarse una cantidad grande, los conjuntos de entrenamiento para reconocimiento de voz se entrenan de forma rutinaria con diez mil millones de palabras de texto. En general, los modelos de lenguaje grandes funcionan bien (lo que quiere decir que tienen una baja entropía); no obstante, la capacidad de memoria es a menudo limitada, especialmente en dispositivos móviles tales como teléfonos móviles, asistentes digitales personales (PDA), agendas electrónicas y similares. Una técnica para ocuparse de la situación de la memoria implica el recorte del modelo de lenguaje, eliminando palabras que se usan con poca frecuencia y variantes poco comunes. No obstante, la eliminación de tales términos reduce la efectividad global del modelo de lenguaje, lo que conduce a más errores de semántica debido a la incapacidad de hacer que se corresponda la entrada con las palabras en el modelo recortado. La patente US 6.092.038 A se refiere a técnicas para proporcionar una compresión sin pérdida de modelos de lenguaje ngramas en un decodificador en tiempo real. En un ejemplo, una serie de palabras de registros de n grama se asigna a números de palabra. Una diferencia entre números de palabra posteriores de los registros de n grama se calcula a continuación y estas diferencias se almacenan de tal modo que las diferencias ocupan unos bloques más pequeños de memoria que los números de palabra. El documento WO 01/10036 A1 se refiere a un sistema de codificación/ decodificación de longitud variable eficiente en cuanto a la memoria. Para evitar el almacenamiento de grandes tablas de consulta, se han desarrollado las técnicas de codificación Golomb. Se puede pensar en los códigos Golomb como en un conjunto especial de palabras de código libres de prefijo de longitud variable que se optimiza para unos números no negativos que tienen una distribución de probabilidad geométrica que disminuye de forma exponencial. Las palabras de código se construyen de tal modo que pueden decodificarse directamente sin la necesidad de una tabla de consulta. El documento US 2004/138884 se refiere a modelos de compresión de lenguaje y a identificadores de palabras que se usan por tales sistemas. El documento US 6.169.969 B1 se refiere al campo del establecimiento de correspondencia de cadena rápido y masivo. Sumario El objeto de la presente invención es la mejora de los sistemas de la técnica anterior. Este objeto se soluciona mediante la materia objeto de las reivindicaciones independientes. Las realizaciones preferidas se definen mediante las reivindicaciones dependientes. Este sumario se proporciona para introducir de una forma simplificada algunos conceptos, que se describen a continuación en la Descripción detallada. No se pretende que este Sumario identifique los rasgos clave o las características esenciales de la materia objeto que se reivindica, ni se pretende que se use como una ayuda al determinar el alcance de la materia objeto que se reivindica. En una realización, un modelo de lenguaje se comprime usando técnicas de codificación Golomb. Una lista de valores se genera a partir de elementos del modelo de lenguaje. La lista de valores enteros se ordena, y para cada elemento, se calcula una diferencia entre valores enteros adyacentes en la lista. Cada diferencia calculada se codifica usando un código Golomb. En otra realización, un sistema para procesar entradas de usuario tiene una interfaz de usuario, una memoria, un codificador/ decodificador Golomb, y un procesador. La interfaz de usuario está adaptada para recibir entradas de usuario. La memoria está adaptada para almacenar información y para almacenar un modelo de lenguaje comprimido por codificación Golomb. El codificador/ decodificador Golomb está adaptado para codificar una entrada 2 E06772381 29-11-2011   de usuario y para decodificar elementos del modelo de lenguaje comprimido por codificación Golomb. El procesador está adaptado para comparar una entrada de usuario codificada frente a elementos del modelo de lenguaje comprimido por codificación Golomb para identificar las correspondencias probables. En otra realización, se proporciona un procedimiento de decodificación de entradas de usuario usando un modelo de lenguaje codificado por codificación Golomb. Una entrada de usuario se divide en una pluralidad de elementos, cada uno de los cuales se codifica usando una técnica de función hash. Cada elemento codificado se compara con unos elementos de un modelo de lenguaje codificado por codificación Golomb para identificar las correspondencias posibles. Las correspondencias posibles se analizan estadísticamente para estimar una probabilidad de que una correspondencia posible sea una asignación correcta de la entrada de usuario para el modelo de lenguaje codificado por codificación Golomb. Breve descripción de los dibujos La figura 1 es un diagrama de bloques de un entorno de cálculo en el que pueden ponerse en práctica las realizaciones. La figura 2 es un diagrama de bloques de un entorno de cálculo alternativo en el que pueden ponerse en práctica las realizaciones. La figura 3 es un diagrama de flujo simplificado de una realización de un proceso para la compresión de un modelo de lenguaje para su uso en dispositivos de cálculo. La figura 4 es un diagrama de flujo simplificado de un proceso para la codificación Golomb de diferencias entre unos valores de función hash que se calculan de acuerdo con el proceso de la figura 3. La figura 5 es un diagrama de bloques simplificado de un árbol de Huffman que ilustra un código unario. La figura 6 es un diagrama de flujo simplificado de una realización de un proceso para la decodificación de una primera diferencia codificada por codificación Golomb. La figura 7 es un diagrama de bloques simplificado de una realización de un sistema adaptado para usar un modelo de lenguaje comprimido con técnicas de codificación Golomb. La figura 8 es un diagrama de flujo simplificado de una realización de un proceso para la decodificación de entrada de usuario frente a un modelo de lenguaje codificado por codificación Golomb. Descripción detallada Los modelos de lenguaje se utilizan en sistemas de reconocimiento de voz, en sistemas de corrección ortográfica sensibles al contexto, en interfaces que se usan para introducir caracteres asiáticos en los ordenadores y similares. Las técnicas de compresión Golomb pueden aplicarse a entradas de usuario, tales como los datos de localizador de recursos uniforme (URL) para la navegación en redes informáticas globales, tal como Internet. Debido a que la memoria está a menudo limitada en la práctica, especialmente en plataformas móviles tales como teléfonos móviles, asistentes digitales personales (PDA) y similares, la compresión del modelo de lenguaje puede ser bastante útil, y las técnicas de codificación Golomb pueden usarse tanto para comprimir un modelo de lenguaje como para decodificar los resultados. La figura 1 ilustra un ejemplo de un entorno 100 de sistema de cálculo adecuado sobre el que pueden llevarse a cabo las técnicas de compresión de modelo de lenguaje de las realizaciones. El entorno 100 de sistema de cálculo es sólo un ejemplo de un entorno de cálculo adecuado y no se pretende sugerir ninguna limitación en lo que concierne al alcance del uso o la funcionalidad de la invención. Tampoco ha de interpretarse el entorno 100 de cálculo tal como si tuviera ninguna dependencia o requisito en relación con ninguno de los componentes o ninguna combinación de los mismos que se ilustra en el entorno 100 operativo a... [Seguir leyendo]

1. Un procedimiento de compresión de un modelo de lenguaje que comprende: obtener (300) valores numéricos mediante la aplicación de una función hash a ngramas de una entrada de usuario y generar una lista de los valores numéricos; ordenar (302) la lista de valores; calcular (304) las diferencias entre los valores adyacentes en la lista; y codificar cada diferencia calculada usando un código Golomb: elegir un valor M que es aproximadamente igual a la mitad de un valor esperado de las diferencias calculadas entre los valores adyacentes en la lista; calcular (404, 406) un valor de cociente y un valor de resto a partir de la proporción de la diferencia calculada y el valor M para cada diferencia calculada; y almacenar el valor de cociente y el valor de resto en una memoria. 2. El procedimiento de la reivindicación 1, en el que la etapa de almacenar comprende: almacenar el valor de cociente en un formato unario; y almacenar el valor de resto en un formato binario. 3. El procedimiento de la reivindicación 1, en el que el valor de cociente comprende una proporción de una primera diferencia con respecto al valor M redondeado a la baja hasta el valor entero más cercano. 4. El procedimiento de la reivindicación 1, en el que el valor de resto comprende un resto de una proporción de una primera diferencia con respecto al valor M redondeado a la baja hasta el valor entero más cercano. 5. El procedimiento de la reivindicación 1, que además comprende: almacenar las diferencias codificadas en una memoria. 6. El procedimiento de la reivindicación 5 en el que las diferencias codificadas ocupan un número de bits (H) en la memoria de acuerdo con una ecuación 7. El procedimiento de la reivindicación 1, que además comprende: almacenar instrucciones legibles por ordenador en un medio de almacenamiento, definiendo las instrucciones legibles por ordenador las etapas de generar, ordenar, calcular y codificar. 8. Un sistema para procesar entradas de usuario que comprende: una interfaz (704) de usuario adaptada para recibir entradas de usuario; una memoria (706) adaptada para almacenar información y para almacenar un modelo de lenguaje comprimido por codificación Golomb; un codificador/ decodificador (702) Golomb adaptado para codificar una entrada de usuario y para decodificar elementos del modelo de lenguaje comprimido por codificación Golomb, en el que el codificador/ decodificador Golomb está adaptado para calcular un valor M en base a un valor esperado de las diferencias entre unos valores de función hash adyacentes en una lista ordenada de valores de función hash, estando el codificador/ decodificador Golomb adaptado para calcular un cociente y un resto en base a una proporción de las diferencias con respecto al valor esperado; y un procesador (710) adaptado para comparar una entrada de usuario frente a elementos del modelo de lenguaje comprimido por codificación Golomb para identificar las correspondencias probables. 9. El sistema de la reivindicación 8, que además comprende: un conjunto de algoritmos estadísticos adaptados para su uso por el procesador para identificar las correspondencias probables. 10. El sistema de la reivindicación 8, en el que el procesador está adaptado para proporcionar las correspondencias probables identificadas a la interfaz de usuario como salidas para su visualización a un usuario. 11. El sistema de la reivindicación 8, en el que el procesador está adaptado para calcular valores numéricos que se refieren a una entrada de usuario y en el que el codificador/ decodificador Golomb está adaptado para codificar los valores numéricos calculados. 12. Un procedimiento de decodificación de una entrada de usuario con un modelo de lenguaje codificado por codificación Golomb que comprende: 9 E06772381 29-11-2011   dividir (802) una entrada de usuario recibida en una pluralidad de ngramas; codificar (804) cada ngrama usando una técnica de función hash; comparar (806) cada ngrama codificado con un modelo de lenguaje codificado por codificación Golomb para identificar las correspondencias posibles; y estimar (808) estadísticamente una probabilidad de que cada correspondencia posible sea una asignación correcta de la entrada de usuario recibida a un elemento dentro del modelo de lenguaje codificado por codificación Golomb; en el que la etapa de codificar comprende: obtener valores numéricos mediante la aplicación de una función hash a la pluralidad de n gramas; generar una lista ordenada de los valores numéricos; calcular una diferencia entre los valores adyacentes en la lista; elegir un valor M para cada diferencia calculada que es aproximadamente igual a la mitad de un valor esperado de la diferencia calculada entre los valores adyacentes en la lista; calcular un valor de cociente y un valor de resto a partir de la proporción de la diferencia y el valor M para cada diferencia calculada. 13. El procedimiento de la reivindicación 12, en el que la etapa de comparar comprende: sumar las diferencias entre ngramas codificados en el modelo de lenguaje hasta que una suma acumulativa es igual a o mayor que un valor del ngrama codificado; y asociar la entrada de usuario recibida con un valor en el modelo de lenguaje para el ngrama adecuado. 14. El procedimiento de la reivindicación 13, en el que la entrada de usuario recibida asociada comprende la correspondencia posible. 15. El procedimiento de la reivindicación 13, en el que la etapa de codificar comprende además: combinar el valor de cociente en formato unario y el valor de resto en formato binario para formar el n grama codificado para cada ngrama. 16. El procedimiento de la reivindicación 12, que además comprende: almacenar instrucciones legibles por ordenador en un medio de almacenamiento, definiendo las instrucciones legibles por ordenador las etapas de dividir, codificar, comparar, y estimar. 17. Un dispositivo de cálculo portátil adaptado para decodificar una entrada de usuario comparando la entrada de usuario frente a un modelo de lenguaje comprimido por codificación Golomb de acuerdo con el procedimiento de la reivindicación 12. E06772381 29-11-2011   11 E06772381 29-11-2011   12 E06772381 29-11-2011   13 E06772381 29-11-2011   14 E06772381 29-11-2011   E06772381 29-11-2011   16 E06772381 29-11-2011