Algoritmo de compresión para codificar listas de palabras

Question

Estoy buscando sugerencias específicas o referencias a un algoritmo y / o estructuras de datos para codificar una lista de palabras en lo que efectivamente resultaría ser un diccionario de corrección ortográfica. Los objetivos de este esquema darían como resultado una relación de compresión muy alta de la lista de palabras sin formato en la forma codificada. El único requisito de salida que tengo en el diccionario codificado es que cualquier palabra objetivo propuesta puede probarse para su existencia en la lista de palabras original de una manera relativamente eficiente. Por ejemplo, la aplicación podría querer verificar 10,000 palabras contra un diccionario de 100,000 palabras. Es not un requisito para que el formulario de diccionario codificado pueda convertirse [fácilmente] de nuevo en el formulario de lista de palabras original; un resultado binario sí / no es todo lo que es necesario para cada palabra probada contra el diccionario resultante.

Supongo que el esquema de codificación, para mejorar la relación de compresión, aprovecharía las estructuras conocidas en un idioma dado, como formas singulares y plurales, formas posesivas, contracciones, etc. Estoy específicamente interesado en codificar principalmente palabras en inglés, pero Para que quede claro, el esquema debe ser capaz de codificar todas y cada una de las palabras de texto ASCII.

La aplicación particular que tengo en mente que puede asumir es para dispositivos embebidos donde el espacio de almacenamiento no volátil es muy importante y el diccionario sería un área de memoria de solo lectura accesible al azar.

EDIT : para resumir los requisitos del diccionario:

• cero falsos positivos
• cero falsos negativos
• relación de compresión muy alta
• no hay necesidad de descompresión

Answer 1

Vea " Desarrollo de una lista de ortografía " de McIlroy en su página de pubs . Documento antiguo clásico sobre el corrector ortográfico en una minicomputadora, cuyas restricciones se asignan sorprendentemente bien a las que enumeró. Análisis detallado de la eliminación de afijos y dos métodos de compresión diferentes: filtros Bloom y un esquema relacionado que codifica Huffman en un conjunto de bits disperso; Yo preferiría los filtros Bloom con preferencia al método que eligió, que exprime unos cuantos kB más a un costo significativo en velocidad. ( Programming Pearls tiene un capítulo corto sobre este documento).

Consulte también los métodos utilizados para almacenar el léxico en sistemas de búsqueda de texto completo, p. Introducción a la recuperación de información . A diferencia de los métodos anteriores, esto no tiene falsos positivos.

Answer 2

Un filtro de Bloom ( http://en.wikipedia.org/wiki/Bloom_filter y http://www.coolsnap.net/kevin/?p=13 ) es Una estructura de datos utilizada para almacenar las palabras del diccionario de forma muy compacta en algunos correctores ortográficos. Sin embargo, existe el riesgo de falsos positivos.

Answer 3

Sugeriría un árbol de sufijo acolchado. Buena compresión en las listas de palabras y excelentes tiempos de búsqueda.

http://en.wikipedia.org/wiki/Suffix_tree

Answer 4

Para resumir:

• cero falsos positivos
• cero falsos negativos
• alta relación de compresión
• no es necesario invertir (es decir, no es necesario descomprimir)

Iba a sugerir filtros Bloom, pero estos tienen falsos positivos distintos de cero.

En cambio, Programming Pearls habla de un conjunto similar de requisitos ( / usr / share / dict / words en 41K).

Esto tomó el enfoque de la contracción de los tallos: Por ejemplo: enviado fue la raíz, por lo que podría haber agregado correcciones previas y posteriores:

• presente
• representar
• representación
• tergiversación

Answer 5

Puede obtener una relación de compresión de más del 30% al almacenar palabras como sufijos sucesivos en formato de 7 bits. No estoy seguro de cómo se llama esto, pero se traduce con bastante eficacia en una estructura de árbol.

ej .: a + n + d + s | an + d + y | y + es + roid

tiene 26 caracteres, en comparación con:

a un anuncio como y alguna Andes android

que es 33.

Factorizando en una relación de compresión de 12.5% ??para almacenar como contenido de 7 bits, eso es aproximadamente 31% de compresión total. La relación de compresión depende, por supuesto, del tamaño y el contenido de su lista de palabras.

Convertir esto en una estructura de árbol de 26 raíces probablemente resultaría en búsquedas que son más rápidas que una comparación de subcadenas de texto sin formato con un archivo plano.

Ahora que lo pienso, si solo está usando 26 caracteres más dos para delimitadores, puede hacer todo en 5 bits, que es una compresión del 37.5% en sí mismo, llevando el ejemplo anterior a una compresión superior al 50% tasa.

Answer 6

Creo que su mejor apuesta es un Árbol de sufijo comprimido / Matriz de sufijo comprimido . Puede encontrar una gran cantidad de información en los enlaces anteriores. Esta es un área de investigación en curso, muy interesante de hecho.

Answer 7

No soy un experto en esto, pero no es árbol de prefijos más o menos solución estándar a esto? Eso almacena prefijos comunes de palabras solo una vez.

Answer 8

Para una compresión pura, el sitio Máxima compresión ofrece algunos resultados para 4 MB lista de palabras en inglés, el mejor programa comprime esto a alrededor de 400 KB. Algunos otros recursos de compresión para la compresión de texto / palabra son la página del Premio Hutter y la Punto de referencia de compresión de texto grande .

Answer 9

Knuth menciona un " Patricia trie " en El arte de la programación informática vol. 3 . Nunca lo he usado para ningún trabajo real, pero tal vez eso sería útil.

editar: ¿cuál es su restricción de RAM? Si tiene mucha más RAM que ROM disponible, tal vez la compresión de datos en ROM (que requiere descompresión en RAM) es el camino correcto. Supongo que si tiene una cantidad de RAM media pero no grande, técnicamente también podría almacenar partes de la estructura de datos como blobs comprimidos en la memoria, y un caché menos utilizado recientemente para mantener varios de ellos, luego descomprimir dinámicamente el apropiado blob cuando no está en el caché.