algorithm - Compresión sin pérdidas en bloques pequeños con diccionario precalculado.

compression

Question

Tengo una aplicación donde estoy leyendo y escribiendo pequeños bloques de datos (unos pocos cientos de bytes) cientos de millones de veces. Me gustaría generar un diccionario de compresión basado en un archivo de datos de ejemplo y usar ese diccionario para siempre mientras leo y escribo los bloques pequeños. Me estoy inclinando hacia el algoritmo de compresión LZW. La página de Wikipedia ( http://en.wikipedia.org/wiki/Lempel-Ziv-Welch ) enumera el pseudocódigo para compresión y descompresión. Parece bastante sencillo modificarlo de tal manera que la creación del diccionario sea un bloque de código separado. Así que tengo dos preguntas:

1. ¿Estoy en el camino correcto o hay una mejor manera?
2. ¿Por qué el algoritmo LZW se agrega al diccionario durante el paso de descompresión? ¿Puedo omitir eso, o perdería eficiencia en mi diccionario?

Gracias.

Actualización: Ahora estoy pensando que el caso ideal sería encontrar una biblioteca que me permita almacenar el diccionario por separado de los datos comprimidos. ¿Existe algo así?

Actualización: terminé tomando el código en http://www.enusbaum.com/blog/2009/05/22/example-huffman-compression-routine-in-c y adaptándolo. Soy Chris en los comentarios de esa página. Le envié por correo electrónico mis modificaciones al autor del blog, pero aún no he recibido respuesta. Las tasas de compresión que estoy viendo con ese código no son para nada impresionantes. Tal vez eso se deba al tamaño del árbol de 8 bits.

Actualización: Lo convertí a 16 bits y la compresión es mejor. También es mucho más rápido que el código original.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace Book.Core
{
  public class Huffman16
  {
    private readonly double log2 = Math.Log(2);

    private List<Node> HuffmanTree = new List<Node>();

    internal class Node
    {
      public long Frequency { get; set; }
      public byte Uncoded0 { get; set; }
      public byte Uncoded1 { get; set; }
      public uint Coded { get; set; }
      public int CodeLength { get; set; }
      public Node Left { get; set; }
      public Node Right { get; set; }

      public bool IsLeaf
      {
        get { return Left == null; }
      }

      public override string ToString()
      {
        var coded = "00000000" + Convert.ToString(Coded, 2);
        return string.Format("Uncoded={0}, Coded={1}, Frequency={2}", (Uncoded1 << 8) | Uncoded0, coded.Substring(coded.Length - CodeLength), Frequency);
      }
    }

    public Huffman16(long[] frequencies)
    {
      if (frequencies.Length != ushort.MaxValue + 1)
      {
        throw new ArgumentException("frequencies.Length must equal " + ushort.MaxValue + 1);
      }
      BuildTree(frequencies);
      EncodeTree(HuffmanTree[HuffmanTree.Count - 1], 0, 0);
    }

    public static long[] GetFrequencies(byte[] sampleData, bool safe)
    {
      if (sampleData.Length % 2 != 0)
      {
        throw new ArgumentException("sampleData.Length must be a multiple of 2.");
      }
      var histogram = new long[ushort.MaxValue + 1];
      if (safe)
      {
        for (int i = 0; i <= ushort.MaxValue; i++)
        {
          histogram[i] = 1;
        }
      }
      for (int i = 0; i < sampleData.Length; i += 2)
      {
        histogram[(sampleData[i] << 8) | sampleData[i + 1]] += 1000;
      }
      return histogram;
    }

    public byte[] Encode(byte[] plainData)
    {
      if (plainData.Length % 2 != 0)
      {
        throw new ArgumentException("plainData.Length must be a multiple of 2.");
      }

      Int64 iBuffer = 0;
      int iBufferCount = 0;

      using (MemoryStream msEncodedOutput = new MemoryStream())
      {
        //Write Final Output Size 1st
        msEncodedOutput.Write(BitConverter.GetBytes(plainData.Length), 0, 4);

        //Begin Writing Encoded Data Stream
        iBuffer = 0;
        iBufferCount = 0;
        for (int i = 0; i < plainData.Length; i += 2)
        {
          Node FoundLeaf = HuffmanTree[(plainData[i] << 8) | plainData[i + 1]];

          //How many bits are we adding?
          iBufferCount += FoundLeaf.CodeLength;

          //Shift the buffer
          iBuffer = (iBuffer << FoundLeaf.CodeLength) | FoundLeaf.Coded;

          //Are there at least 8 bits in the buffer?
          while (iBufferCount > 7)
          {
            //Write to output
            int iBufferOutput = (int)(iBuffer >> (iBufferCount - 8));
            msEncodedOutput.WriteByte((byte)iBufferOutput);
            iBufferCount = iBufferCount - 8;
            iBufferOutput <<= iBufferCount;
            iBuffer ^= iBufferOutput;
          }
        }

        //Write remaining bits in buffer
        if (iBufferCount > 0)
        {
          iBuffer = iBuffer << (8 - iBufferCount);
          msEncodedOutput.WriteByte((byte)iBuffer);
        }
        return msEncodedOutput.ToArray();
      }
    }

    public byte[] Decode(byte[] bInput)
    {
      long iInputBuffer = 0;
      int iBytesWritten = 0;

      //Establish Output Buffer to write unencoded data to
      byte[] bDecodedOutput = new byte[BitConverter.ToInt32(bInput, 0)];

      var current = HuffmanTree[HuffmanTree.Count - 1];

      //Begin Looping through Input and Decoding
      iInputBuffer = 0;
      for (int i = 4; i < bInput.Length; i++)
      {
        iInputBuffer = bInput[i];

        for (int bit = 0; bit < 8; bit++)
        {
          if ((iInputBuffer & 128) == 0)
          {
            current = current.Left;
          }
          else
          {
            current = current.Right;
          }
          if (current.IsLeaf)
          {
            bDecodedOutput[iBytesWritten++] = current.Uncoded1;
            bDecodedOutput[iBytesWritten++] = current.Uncoded0;
            if (iBytesWritten == bDecodedOutput.Length)
            {
              return bDecodedOutput;
            }
            current = HuffmanTree[HuffmanTree.Count - 1];
          }
          iInputBuffer <<= 1;
        }
      }
      throw new Exception();
    }

    private static void EncodeTree(Node node, int depth, uint value)
    {
      if (node != null)
      {
        if (node.IsLeaf)
        {
          node.CodeLength = depth;
          node.Coded = value;
        }
        else
        {
          depth++;
          value <<= 1;
          EncodeTree(node.Left, depth, value);
          EncodeTree(node.Right, depth, value | 1);
        }
      }
    }

    private void BuildTree(long[] frequencies)
    {
      var tiny = 0.1 / ushort.MaxValue;
      var fraction = 0.0;

      SortedDictionary<double, Node> trees = new SortedDictionary<double, Node>();
      for (int i = 0; i <= ushort.MaxValue; i++)
      {
        var leaf = new Node()
        {
          Uncoded1 = (byte)(i >> 8),
          Uncoded0 = (byte)(i & 255),
          Frequency = frequencies[i]
        };
        HuffmanTree.Add(leaf);
        if (leaf.Frequency > 0)
        {
          trees.Add(leaf.Frequency + (fraction += tiny), leaf);
        }
      }

      while (trees.Count > 1)
      {
        var e = trees.GetEnumerator();
        e.MoveNext();
        var first = e.Current;
        e.MoveNext();
        var second = e.Current;

        //Join smallest two nodes
        var NewParent = new Node();
        NewParent.Frequency = first.Value.Frequency + second.Value.Frequency;
        NewParent.Left = first.Value;
        NewParent.Right = second.Value;

        HuffmanTree.Add(NewParent);

        //Remove the two that just got joined into one
        trees.Remove(first.Key);
        trees.Remove(second.Key);

        trees.Add(NewParent.Frequency + (fraction += tiny), NewParent);
      }
    }

  }

}

Ejemplos de uso:

Para crear el diccionario a partir de datos de muestra:

var freqs = Huffman16.GetFrequencies(File.ReadAllBytes(@"D:/nodes"), true);

Para inicializar un codificador con un diccionario dado:

var huff = new Huffman16(freqs);

Y para hacer algo de compresión:

var encoded = huff.Encode(raw);

Y la descompresión.

var raw = huff.Decode(encoded);

Answer 1

1. El camino correcto es utilizar una biblioteca: casi todos los lenguajes modernos tienen una biblioteca de compresión. C #, Python, Perl, Java, VB.net, cualquier cosa que uses.

2. LZW ahorra espacio dependiendo del diccionario en las entradas anteriores. Tiene un diccionario inicial, y cuando descomprimes algo, los añades al diccionario, por lo que el diccionario está creciendo. (Omito algunos detalles aquí, pero esta es la idea general)

Puede omitir este paso proporcionando el diccionario completo (completo) como el inicial. Pero esto costaría algo de espacio.

Answer 2

Encuentro este enfoque bastante interesante para las entradas de registro repetidas y algo que me gustaría explorar usando.

¿Puede compartir las estadísticas de compresión para utilizar este enfoque en su caso de uso, de modo que pueda compararlo con otras alternativas?

¿Ha considerado que el diccionario común crezca con el tiempo o no es una opción válida?

Answer 3

LZW se agrega al diccionario durante la descompresión para garantizar que tenga el mismo estado de diccionario que el compresor. De lo contrario, la decodificación no funcionaría correctamente.

Sin embargo, si estuviera en un estado en el que se arregló el diccionario, entonces, sí, no tendría que agregar nuevos códigos.

Su enfoque funcionará razonablemente bien y es fácil utilizar las herramientas existentes para crear prototipos y medir los resultados. Es decir, comprima el archivo de ejemplo y luego el ejemplo y los datos de prueba juntos. El tamaño de este último menos el primero será el tamaño comprimido esperado de un bloque.

LZW es una forma inteligente de crear un diccionario sobre la marcha y da resultados decentes. Pero es probable que un análisis más completo de sus bloques de datos típicos genere un diccionario más eficiente.

También hay espacio para mejorar la forma en que LZW representa datos comprimidos. Por ejemplo, cada referencia del diccionario podría estar codificada por Huffman a una longitud más cercana a la óptima en función de la frecuencia esperada de su uso. Para ser verdaderamente óptimos, los códigos deben ser aritméticos codificados.

Answer 4

La parte difícil en mi mente es cómo construyes tu diccionario estático. No desea utilizar el diccionario LZW creado a partir de sus datos de muestra. LZW pierde un montón de tiempo de aprendizaje ya que no puede construir el diccionario más rápido que el descompresor (un token solo se usará la segunda vez que lo vea el compresor, de modo que el descompresor pueda agregarlo a su diccionario la primera vez que lo vea) . La otra cara de esto es que está agregando cosas al diccionario que puede que nunca se usen, en caso de que la cadena aparezca de nuevo. (Por ejemplo, para tener un token para '''' también tendrá entradas para ''ac'', ''ko'', ''ve'', ''rf'' etc ...)

Sin embargo, mirar el flujo de token sin procesar desde un algoritmo LZ77 podría funcionar bien. Solo verás tokens para las cuerdas vistas al menos dos veces. Luego puede crear una lista de los tokens / cadenas más comunes para incluir en su diccionario.

Una vez que tenga un diccionario estático, usar LZW sin la actualización del diccionario parece una implementación fácil, pero para obtener la mejor compresión consideraría una tabla de Huffman estática en lugar del token de tamaño fijo de 12 bits tradicional (como sugirió George Phillips). Un diccionario LZW quemará tokens para todas las sub-cadenas que realmente nunca codificarás (por ejemplo, si puedes codificar '''', habrá tokens para ''st'', ''sta'', ''stac'', ''stack'', '' stacko ''etc.).

En este punto, realmente no es LZW; lo que hace a LZW inteligente es cómo el descompresor puede construir el mismo diccionario que usó el compresor solo para ver el flujo de datos comprimidos. Algo que no vas a utilizar. Pero todas las implementaciones de LZW tienen un estado donde el diccionario está lleno y ya no se actualiza, así es como lo usarías con tu diccionario estático.

Answer 5

Me gustaría ver sus datos para ver si hay una razón obvia por la cual es tan fácil de comprimir. Es posible que puedas hacer algo mucho más simple que LZ78. He hecho tanto LZ77 (lookback) como LZ78 (diccionario).

Intente ejecutar un LZ77 en sus datos. No hay diccionario con LZ77, por lo que puede usar una biblioteca sin modificaciones. Deflate es una implementación de LZ77.

Su idea de usar un diccionario común es buena, pero es difícil saber si los archivos son similares entre sí o solo se parecen a sí mismos sin hacer algunas pruebas.