Estoy escribiendo un programa para una tarea que tiene que aplicar compresión LZW/descompresión.
Estoy usando los siguientes algoritmos para esto:

de compresión de

w = NIL;
   while ( read a character k )
       {
         if wk exists in the dictionary
         w = wk;
         else
         add wk to the dictionary;
         output the code for w;
         w = k;
       }

-descompresión

read a character k;
   output k;
   w = k;
   while ( read a character k )    
  /* k could be a character or a code. */
        {
         entry = dictionary entry for k;
         output entry;
         add w + entry[0] to dictionary;
         w = entry;
        }

Para la etapa de compresión sólo estoy de imprimir enteros que representa el índice de la
entrada de diccionario, también el inicio de diccionario se compone de caracteres ascii (0 – 255).
Pero cuando llego a la etapa de descompresión me sale este error
por ejemplo si quiero comprimir un archivo de texto que consta de sólo «booop»
va a ir a través de estos pasos para generar un archivo de salida:

w       k       Dictionary          Output

-       b       -                   -
b       o       bo (256)            98 (b)
o       o       oo (257)            111 (o)
o       o       -                   -
oo      p       oop (258)           257 (oo)
p       -       -                   112 (p)

output.txt:
98
111
257
112

Luego cuando voy a descomprimir el archivo

w       k          entry        output       Dictionary
        98 (b)                  b   
b       111 (o)    o            o             bo (256)
o       257 (error)

257 (oo) no se ha agregado aún. ¿Puede alguien ver a donde voy mal aquí, porque estoy
perplejos. Es el algoritmo de malo?

  • Puede que nos muestran el código real porque pseudocódigo es siempre ambigua.
  • Se ha resuelto el problema?
  • Sí he implementado los cambios realizados en el algoritmo y funciona.

2 Comentarios

  1. 7

    Su compresión parte es correcta y completa, pero la descompresión parte no es completa. Sólo incluye el caso cuando el código está en el diccionario. Desde el proceso de descompresión siempre está un paso por detrás de el proceso de compresión, existe la posibilidad de que cuando el decodificador de encontrar un código que no está en el diccionario. Pero ya que es tan sólo un paso por detrás, se puede averiguar lo que el proceso de codificación se agregará siguiente y correctamente la salida de la cadena decodificada, a continuación, agregar al diccionario. Para continuar con su proceso de descompresión como este:

    -descompresión

    read a character k;
       output k;
       w = k;
       while ( read a character k )    
      /* k could be a character or a code. */
            {
             if k exists in the dictionary
             entry = dictionary entry for k;
             output entry;
             add w + entry[0] to dictionary;
             w = entry;
             else
             output entry = w + firstCharacterOf(w);
             add entry to dictionary;
             w = entry;
            }
    

    Luego, cuando se llega a descomprimir el archivo y ver 257, se encuentra que no existe en el diccionario. Pero usted sabe que la entrada anterior es ‘o’ y es el primer personaje es ‘o’ demasiado, ponerlos juntos, le «oo». Ahora la salida oo y añadirla al diccionario. Siguiente código 112 y asegúrese de que usted sabe que es p. HECHO!

    w       k          entry        output       Dictionary
            98 (b)                  b   
    b       111 (o)    o            o             bo (256)
    o       257 (oo)                oo            oo(257)
    oo      112(p)                  p
    

    Ver: este explicación por Steve Blackstock para obtener más información. Un mejor página con diagrama de flujo para el decodificador y codificador de la aplicación en la que el «icafe» Java biblioteca de imágenes GIF codificador y el decodificador se basan.

    • Funciona como un encanto, gracias.
  2. 1

    De http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch están cayendo en este caso?

    ¿Qué sucede si el decodificador recibe un código Z que todavía no está en su diccionario? Desde el decodificador es siempre sólo un código detrás del codificador, Z puede ser en el codificador del diccionario sólo si el codificador genera, al emitir el código anterior X para χ. Por lo tanto Z códigos de algunos ω que es χ + ?, y el decodificador puede determinar el carácter desconocido de la siguiente manera:

    1) The decoder sees X and then Z.
    2) It knows X codes the sequence χ and Z codes some unknown sequence ω.
    3) It knows the encoder just added Z to code χ + some unknown character,
    4) and it knows that the unknown character is the first letter z of ω.
    5) But the first letter of ω (= χ + ?) must then also be the first letter of χ.
    6) So ω must be χ + x, where x is the first letter of χ.
    7) So the decoder figures out what Z codes even though it's not in the table,
    8) and upon receiving Z, the decoder decodes it as χ + x, and adds χ + x to the table as the value of Z.
    

    Esta situación se produce cuando el codificador de encuentros de entrada de la forma cScSc, donde c es un carácter único, S es una cadena y el cS ya está en el diccionario, pero el cSc no lo es. El codificador emite el código de cS, poniendo un nuevo código para cSc en el diccionario. A continuación se ve la cSc en la entrada (a partir de la segunda c de cScSc) y emite el nuevo código que acabamos de insertar. El argumento anterior muestra que cuando el decodificador recibe un código que no está en su diccionario, la situación debe de tener este aspecto.

    Aunque de entrada de forma cScSc puede parecer raro, este patrón es bastante común cuando el flujo de entrada se caracteriza por una significativa la repetición. En particular, las cadenas largas de un solo carácter (que son comunes en el tipo de imágenes que LZW es a menudo utilizado para codificar) repetidamente generar patrones de este tipo.


    Para este caso específico, la wikipedia, cosa que se ajusta, se tiene X+? donde X es (o), Z es desconocido hasta el momento por lo que la primera letra es X dar (oo) agregar (oo) a la tabla como 257. Yo sólo voy a lo que he leído en la wikipedia, que nos permita saber cómo esto resulta que si que no es la solución.

    • Gracias tengo una mejor comprensión de cómo funciona realmente ahora.

Dejar respuesta

Please enter your comment!
Please enter your name here