texto sirve que para introducción huffman entropía datos código compresión compresion codigo canónico biografia algoritmo algorithm data-structures dictionary

algorithm - sirve - Algoritmo de compresión para codificar listas de palabras



introducción a la compresión huffman y entropía (9)

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 ortografía. Los objetivos de este esquema darían como resultado una relación de compresión muy alta de la lista de palabras primas 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 contra 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. No es necesario que el formulario del diccionario codificado se pueda convertir [fácilmente] a la forma original de la lista de palabras: un resultado binario sí / no es todo lo que se necesita 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 lenguaje dado, como formas singulares y plurales, formas posesivas, contracciones, etc. Estoy especialmente interesado en la codificación principalmente de palabras en inglés, pero para ser claro , el esquema debe poder codificar cualquiera y todas las "palabras" de texto ASCII.

La aplicación particular que tengo en mente que puede suponer es para dispositivos integrados en los que el espacio de almacenamiento no volátil es escaso y el diccionario sería un área de memoria de solo lectura accesible al azar.

EDITAR : 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

Creo que su mejor opción es un Árbol de sufijos comprimido / Sufijo comprimido . Puede encontrar una gran cantidad de información en los enlaces de arriba. Esta es un área de investigación en curso, muy interesante.

Knuth menciona una "Patricia trie" en The Art of Computer Programming vol. 3 . Nunca lo he usado para ningún trabajo real, pero tal vez eso sería útil.

editar: ¿cuál es tu restricción de RAM? Si tiene mucha más RAM que ROM disponible, quizás la compresión de datos en la ROM (que requiere la descompresión en la RAM) sea la forma correcta de hacerlo. 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 una memoria caché utilizada menos recientemente para mantener varios de ellos, luego descomprimir dinámicamente el apropiado blob cuando no está en el caché.

No soy un experto en esto, pero ¿no es el árbol de prefijo una solución bastante estándar para esto? Eso almacena prefijos comunes de palabras solo una vez.

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" era la raíz, por lo que se podrían haber agregado pre y post-correcciones:

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

Puede obtener una proporción de compresión de más del 30% almacenando palabras como sufijos sucesivos en formato de 7 bits. No estoy seguro de cómo se llama, 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:

un anuncio como y cualquier andes android

que es 33.

Teniendo en cuenta la relación de compresión del 12.5% ​​para almacenar como contenido de 7 bits, eso es aproximadamente un 31% de compresión total. La relación de compresión depende, por supuesto, del tamaño y 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 plano con un archivo plano.

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

Vea "Desarrollo de una lista de ortografía" de McIlroy en su página de pubs . Documento clásico antiguo sobre la revisión ortográfica en un miniordenador, cuyas restricciones se corresponden sorprendentemente bien con las que ha enumerado. Análisis detallado de affix stripping y dos métodos de compresión diferentes: Bloom filters y un esquema relacionado Huffman -coding un conjunto de bits disperso; Iría con los filtros Bloom, probablemente con preferencia al método que eligió, lo que exprime unos cuantos kB más a un costo significativo en velocidad. ( Programming Pearls tiene un breve capítulo sobre este documento).

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