La codificación incremental , también conocida como compresión frontal , compresión posterior o codificación frontal , es un tipo de algoritmo de compresión de codificación delta mediante el cual los prefijos o sufijos comunes y sus longitudes se registran para que no sea necesario duplicarlos. Este algoritmo es particularmente adecuado para comprimir datos clasificados , por ejemplo, una lista de palabras de un diccionario .
Por ejemplo:
Aporte | Prefijo común | Salida comprimida |
---|---|---|
myxamixofitamixópodocogeratrapadoatraparnabitnabknababnacaratgóndola | sin palabra precedente'myx''myxop'sin prefijo común'coger''nabb''coger''coger''coger''n / A''nac' | 0 myxa3 ophyta5 od0 nab3 hab4 ing3 es3 k3 ob2 quilates3 elle |
64 bytes | 46 bytes |
La codificación utilizada para almacenar la longitud del prefijo común varía de una aplicación a otra. Las técnicas típicas almacenan el valor como un solo byte; codificación delta , que almacena solo el cambio en la longitud del prefijo común; y varios códigos universales . Puede combinarse con otras técnicas generales de compresión de datos sin pérdida , como la codificación de entropía y los codificadores de diccionario para comprimir los sufijos restantes.
Aplicaciones
La codificación incremental se usa ampliamente en la recuperación de información para comprimir los léxicos usados en los índices de búsqueda ; estos enumeran todas las palabras que se encuentran en todos los documentos y un puntero para cada uno a una lista de ubicaciones. Por lo general, comprime estos índices en aproximadamente un 40%. [1]
Por ejemplo, la utilidad de localización de GNU utiliza la codificación incremental como punto de partida , en un índice de nombres de archivos y directorios. La utilidad de localización de GNU utiliza además la codificación bigram para acortar aún más los prefijos de rutas de archivo populares.