Codificación incremental

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 que registra los prefijos o sufijos comunes y sus longitudes para evitar su duplicación. Este algoritmo es especialmente adecuado para comprimir datos ordenados , por ejemplo, una lista de palabras de un diccionario .

Por ejemplo:

La codificación utilizada para almacenar la longitud del prefijo común varía según la aplicación. Las técnicas típicas incluyen almacenar el valor como un solo byte; la codificación delta , que almacena únicamente el cambio en la longitud del prefijo común; y diversos códigos universales . Puede combinarse con otras técnicas generales de compresión de datos sin pérdida, como la codificación entrópica y los codificadores de diccionario, para comprimir los sufijos restantes.

La codificación incremental se utiliza ampliamente en la recuperación de información para comprimir los léxicos empleados en los índices de búsqueda ; estos listan todas las palabras encontradas en todos los documentos y un puntero para cada una a una lista de ubicaciones. Normalmente, comprime estos índices en aproximadamente un 40 %. ^{[ 1 ]}

Por ejemplo, la utilidad GNU locate utiliza la codificación incremental como punto de partida en un índice de nombres de archivo y directorios. Además, la utilidad GNU locate utiliza la codificación bigrama para acortar aún más los prefijos de ruta de archivo más comunes.