Click here to Skip to main content
14,028,229 members
Click here to Skip to main content
Add your own
alternative version

Stats

173.2K views
3.1K downloads
130 bookmarked
Posted 17 Dec 2012
Licenced CPOL

Fast LZW Compression Using Binary Tree

, 17 Dec 2012
Rate this:
Please Sign up or sign in to vote.
Fast LZW implementation using Binary Tree as a dictionary
Sample Image - LZW.gif

Introduction

One day, I was talking with one of my colleagues about compression, and I was surprised when he told me that there is an algorithm that uses a dictionary during compression then leaves it aside and saves the compressed data without the dictionary. I asked him, "How can it construct the original data again?", he replied: "Simply by constructing the dictionary again during the decompression process"!!!

It is the LZW compression. I decided that day to read about it and try to implement this so nice idea algorithm, and I spent a long time to make it as fast as I can, but I think I failed as it compresses 1 MB/sec in normal cases. The code seems hard to be understood, but it will be easy if you take a look at the algorithm through the Background section or through any of the References down the page.

Background

In 1984, Terry Welch was working on a compression algorithm for high-performance disk controllers. He developed a rather simple algorithm that was based on the LZ78 algorithm and that is now called LZW. LZW is a lossless 'dictionary based' compression algorithm. Dictionary based algorithms scan a file for sequences of data that occur more than once. These sequences are then stored in a dictionary, and within the compressed file, references are put where-ever repetitive data occurred.

LZW Idea

LZW compression replaces strings of characters with single codes. It does not do any analysis of the incoming text. Instead, it just adds every new string of characters it sees to a table of strings. Compression occurs when a single code is output instead of a string of characters. So, any code in the dictionary must have a string in the compressed buffer for the first time only, that means the dictionary just keeps a reference to uncompressed strings in the compressed buffer, no need to let the dictionary take a copy of these strings. So, it is not necessary to preserve the dictionary to decode the LZW data stream. This can save quite a bit of space when storing the LZW-encoded data.

The code that the LZW algorithm outputs can be of any arbitrary length, but it must have more bits in it than a single character. The first 256 codes (when using eight bit characters) are, by default, assigned to the standard character set. The remaining codes are assigned to strings as the algorithm proceeds. The sample program runs as shown with 12 bit to 31 bit codes. This means, codes 0-255 refer to individual bytes, while codes 256-2^n refer to substrings, where n equal to number of bits per code, as in the following figure.

LZW dictionary

LZW Algorithm

Compression

The LZW Compression Algorithm can be summarized as follows:

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;
    }
}

Original algorithm used a dictionary of 4094 entries; first 256 for ASCII codes, and the rest for substrings. As you see, the algorithm scans one character at a time. If the string is in the dictionary, then it adds the character to the current string and goes for the next character. If the work string is not in the dictionary, it adds the work string to the dictionary and sends the work string without the new character. It then sets the work string to the new character.

Compression Example
Input string is "^WED^WE^WEE^WEB^WET". 

             w    k    output    index    symbol
          -----------------------------------------
            NIL   ^               
             ^    W      ^        256       ^W
             W    E      W        257       WE
             E    D      E        258       ED
             D    ^      D        259       D^
             ^    W       
            ^W    E     256       260      ^WE
             E    ^      E        261       E^
             ^    W
            ^W    E
           ^WE    E     260       262     ^WEE
             E    ^
            E^    W     261       263      E^W
             W    E
            WE    B     257       264      WEB
             B    ^      B        265       B^
             ^    W
            ^W    E
           ^WE    T     260       266     ^WET
             T   EOF     T

[1] Stepping through the start of the algorithm for this string, you can see that in the first pass through the loop, a check is performed to see if the string "^W" is in the table. Since it isn't, the code for '^' is output, and the string "^W" is added to the table. Since we have 256 characters already defined for codes 0-255, the first string definition can be assigned to code 256. After the third letter, 'E', has been read in, the second string code "WE" is added to the table and the code for letter 'W' is output. This continues until in the second word, the characters '^' and 'W' are read in, matching string number 256. In this case, the code 256 is output, and a three character string is added to the string table. The process continues until the string is exhausted and all of the codes have been output.

Decompression

The LZW Decompression Algorithm is as follows:

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;
}

As we said before, the decompression builds its own dictionary that matches exactly the compressor's, so that only the codes need to be saved in the compression.

Decompression Example
Input string is "^WED<256>E<260><261><257>B<260>T". 

             w      k    output    index    symbol
          -------------------------------------------
                    ^       ^
             ^      W       W       256       ^W
             W      E       E       257       WE
             E      D       D       258       ED
             D    <256>    ^W       259       D^
           <256>    E       E       260      ^WE
             E    <260>   ^WE       261       E^
           <260>  <261>    E^       262     ^WEE
           <261>  <257>    WE       263      E^W
           <257>    B       B       264      WEB
             B    <260>   ^WE       265       B^
           <260>    T       T       266     ^WET

[1] Just like the compression algorithm, it adds a new string to the string table each time it reads in a new code. All it needs to do in addition to that is translate each incoming code into a string and send it to the output. The important thing to note is that the string table ends up looking exactly like the table built up during compression. The output string is identical to the input string from the compression algorithm. Note that the first 256 codes are already defined to translate to single character strings, just like in the compression code.

Code Usage

Code usage is so simple, just the input buffer and its length, and the output buffer and its length. The compress function includes an additional parameter nBitsPerSample to determine the number of bits to save dictionary code, so dictionary entries will be up to 2^nBitsPerSample.

bool CompressLZW(BYTE* pSrc, int nSrcLen, BYTE* &pDes,
                 int &nDesLen, int nBitsPerSample = 12);
bool DecompressLZW(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);

Code Description

I have only two functions CompressLZW and DecompressLZW, I will start with the first.

CompressLZW Function

  • In this function, I am scanning the input buffer pSrc and adding new entries to the dictionary component CBinaryTreeNode. CBinaryTreeNode is a Binary Tree class that keeps a unique instance of all input keys, and it does that in a very fast way, using binary search. To have more information about it, you can check my article about it in my Articles page.
  • In the out buffer, I precede it with a header of 5 bytes: 4 bytes for the original length, 1 byte for bits per sample.
1:bool CompressLZW(BYTE *pSrc, int nSrcLen, BYTE *&pDes, 
                  int &nDesLen, int nBitsPerSample = 12)
2:{
3:     ...
4:     CBinaryTree<CBuffer, CBuffer*, int, int> dictionary;
5:     // keep first 256 IDs for ascii Samples
6:     dictionary.Serial = 256;
7:     // scan the input buffer
8:    while(nSrcLen-- > 0)
9:    {
10:         ...
11:         pNode = dictionary.Insert(&node, -1, pNode);
12:         if(pNode->Count > 1 && nSrcLen)
13:             // (repeated Sample)
14:             nSample = pNode->ID, node.m_nLength++;
15:         else
16:         {    // write last success Sample
17:             *(DWORD*)(pDes+sizeof(DWORD)+1+
                         (nDesLen>>3)) |= nSample << (nDesLen&7);
18:             nDesLen += nBitsPerSample;
19:             // initialize node to next Sample
20:             node.m_pBuffer += node.m_nLength-1;
21:             node.m_nLength = 2;
22:             // copy first byte of the node as a new Sample
23:             nSample = *node.m_pBuffer;
24:             ...
25:         }
26:     }
27:    ...
28:}

I included only the main points of the algorithm. I find line 17 is the only line that needs a description:

17: *(DWORD*)(pDes+sizeof(DWORD)+1+(nDesLen>>3)) |= nSample << (nDesLen&7);

It copies the sample code to the compressed buffer, but it needs to start copying at the right bit. I know some people always invert the function of the shift operators in their minds, so I will dig a little bit on this line:

  • sizeof(DWORD)+1: to exclude the buffer header.
  • (nDesLen>>3): >>3 to divide by 8 to reach the right byte to start with.
  • |=: to avoid writing over the previous code.
  • (nDesLen&7): &7 to get the remainder of dividing by 8, to get the start bit.
  • nSample << (nDesLen&7): to shift the code to left to match the starting bit at the destination buffer.

DecompressLZW Function

  • This function is faster that the compression as it doesn't need any comparisons, as in the insertion in the CBinaryTree in the compression process.
  • In this function, I am scanning the input buffer pSrc and getting code from it, then getting node string pointer from the dictionary.
  • I am using the simple vector STL template to keep the dictionary.
  • In the out buffer, I precede it with a header of 5 bytes: 4 bytes for the original length, 1 byte for bits per sample.
1:bool DecompressLZW(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen)
2:{
3:    // copy bits pre Sample
4:    int nBitsPerSample = *(pSrc+sizeof(DWORD)); 
5:    ...
6:    //    dictionary array 
7:    vector<CBUFFER *> dictionary;
8:    // scan input buffer
9:    while(nDesIndex < nDesLen)
10:    {
11:        // read sample code
12:        nSample = (*(DWORD*)(pSrc+sizeof(DWORD)+1+
                     (nSrcIndex>>3)))>>(nSrcIndex&7) & (nMaxSamples-1);
13:        nSrcIndex += nBitsPerSample;
14:        // get code string node from the dictionary
15:        if(nSample >= 256)
16:            if(nSample-256 < (int)dictionary.size()) 
17:            {    // normal case, valid dictionary Sample 
18:                pNodeSample = dictionary.at(nSample-256); 
19:                nSampleLen = pNodeSample->m_nLength+1; 
20:                // copy dictionary node    buffer to decompressed buffer 
21:                memcpy(pDes+nDesIndex, pNodeSample->m_pBuffer, 
                          pNodeSample->m_nLength); 
22:                nDesIndex += pNodeSample->m_nLength;
23:            } 
24:            else // out of range Sample 
25:                ...
26:        else 
27:            nDesIndexSave =    nDesIndex, *(pDes+nDesIndex++) 
                                  = (BYTE)nSample, nSampleLen = 2;
28:        ... 
29:        // add current segment to the dictionary
30:        dictionary.push_back(new CBuffer(node)); 
31:        // increment next node pointer to the last char of the added Sample 
32:        node.m_pBuffer += node.m_nLength-1; 
33:        node.m_nLength = nSampleLen;
34:    } 
35:    ...
36:}

As in the compression, I included only the main points of the algorithm. I find line 12 is the only line that needs a description at this point:

12: nSample = (*(DWORD*)(pSrc+sizeof(DWORD)+1+
       (nSrcIndex>>3)))>>(nSrcIndex&7) & (nMaxSamples-1);

It copies the sample code from the compressed buffer, but it needs to start copying at the right bit:

  • sizeof(DWORD)+1: to exclude the buffer header.
  • (nSrcIndex>>3): >>3 to divide by 8 to reach the right byte to start with.
  • (nSrcIndex&7): &7 to get the remainder of dividing by 8, to get the start bit.
  • >>(nSrcIndex&7): shift right to the start bit to take the code at bit 0 (closer the wall).
  • (nMaxSamples-1): nMaxSamples must be power of 2 as it is calculated by 2^nBitsPerSample or 1<<nPitsPerSample; so to use nMaxSamples as a mask, we subtract 1.
  • & (nMaxSamples-1): to use it as a mask to remove extra bits that exceed code limits (Bits Per Sample).

Points of Interest

  1. At the compression function, I am using a binary tree to hold the dictionary. I was thinking of using hash table, may be it can increase insertion speed. Any way, it takes less than 1 sec to compress 1 MB, and decompresses it in less than 200 ms.
  2. This code's advantage is the variable number of bits for dictionary index, the compression function includes a parameter nBitsPerSample.

    That means, if the number of entries in the dictionary reaches limits of max index value, we need to free the dictionary and start a new empty dictionary. This can be seen in the following section at the CompressLZW function:

    int nMaxSamples = 1 << nBitsPerSample;
    ...
    while(nSrcLen-- > 0)
    {
        if(dictionary.Serial == nMaxSamples)
        {
            dictionary.RemoveAll();
            dictionary.Serial = 256;
        }
        ...
    }
    
  3. As in the previous point, at the decompression function, get nBitsPerSample from the compressed buffer (fifth byte). And in the same way, if number of entries in the dictionary reaches limits of max index value, we need to free the dictionary and start a new empty dictionary. This can be seen in the following section at the DecompressLZW function:
    int nBitsPerSample = *(pSrc+sizeof(DWORD));
    ...
    while(nDesIndex > nDesLen)
    {
        ...
        if(dictionary.size() == nMaxSamples-256)
            ClearDictionary(dictionary);
        ...
    }
    
  4. As mentioned in the first reference [1], there is a single exception case in the LZW compression algorithm that causes some trouble to the decompression function. Suppose there is a string consisting of a (string, char) pair already defined in the table, and the input stream then sees a sequence of (string, char, string, char, string), or we can say, if the encoding algorithm reads the string that it has just added to the dictionary in the previous step. During the decoding, this string is not yet present in the dictionary. A string can occur twice in a row in the char stream only if its first and last characters are equal, because the next string always starts with the last character of the previous one. As in the following example in the compression process:
    Input string is "...JOEYNA...JOEYNJOEYNJOEY...".
    
                w        k    output    index   dictionary    
               --------------------------------------------
              JOEY       N   288(JOEY)    300    JOEYN
                N        A      N         301    NA
                ...
               JOEYN     J   300(JOEYN)   400    JOEYNJ
               JOEYNJ    O   400(JOEYNJ)  401    JOEYNJO
                O        E   O            402    OE
                ...

    In the decompression algorithm, it is like that:

    1:Input string is "...<288>NA...<300><400>O..."
    2:          w     k    output    index    dictionary
    3:          --------------------------------------------
    4:          ...  <288>   JOEY    299     ...J
    5:          JOEY   J       J     300     JOEYJ     
    6:          ...
    7:          ...  <300>   JOEYN   399     ...J
    8:          <400>  O     JOEYNJ  400     JOEYNJ
    9:          ...

    The problem is at line 8, as the new symbol to be added to the dictionary is JOEYN plus the incoming character which is the code 400, which is not coming yet to the dictionary. So we need a special case of repeating the first character of the previous symbol at the end of the dictionary entry, so (JOEYN?) becomes (JOEYNJ). To handle that, we take the previous symbol JOEN and end it with its first character. The following code handles this case:

    bool DecompressLZW(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen)
    {
        ...
        while(nDesIndex < nDesLen)
        {
            nSample = (*(DWORD*)(pSrc+sizeof(DWORD)+1+
                      (nSrcIndex>>3)))>>(nSrcIndex&7) & (nMaxSamples-1);
            nSrcIndex += nBitsPerSample;
    
            if(nSample >= 256)
                if(nSample-256 < (int)dictionary.size())
                {
                    // normal case, valid dictionary Sample
                    nDesIndexSave = nDesIndex;
                    ...
                }
                else
                {
                    // out of range Sample
                    nSampleLen = nDesIndex-nDesIndexSave+2;
                    // copy previous decompressed Sample as a new one + ...
                    memcpy(pDes+nDesIndex, pDes+nDesIndexSave, 
                           nDesIndex-nDesIndexSave);
                    nDesIndex += nDesIndex-nDesIndexSave;
                    // add first char of the previous decompressed Sample
                    *(pDes+nDesIndex++) = *(pDes+nDesIndexSave);
                    nDesIndexSave += nSampleLen-2;
                }
            else
                ...
            ...
        }
        ...
    }

    At this code, I just save the old symbol entry by the variable nDesIndexSave to be used in case of out of range symbol.

Source Code Files

LZW.cpp, LZW.h and BinaryTree.h.

Updates

  • 20-1-2005: I have solved a very special bug in the decompression, if any one took the code before this date, please update it.
  • 1-1-2008: solved the bug of end file mismatch for big files' compression. Thanks go to "Wael AlGhool."
  • 15-01-2008: update the pseudo code of the compression.

References

  1. Mark Nelson's "LZW Data Compression" from the October, 1989 issue of Dr. Dobb's Journal.

Thanks to...

I owe a lot to my colleagues for helping me in implementing and testing this code. (JAK)

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author


You may also be interested in...

Pro

Comments and Discussions

 
QuestionCode don't work on 8 bits Pin
bioparts11-Dec-13 11:17
memberbioparts11-Dec-13 11:17 
GeneralMy vote of 5 Pin
Mihai MOGA15-Jan-13 6:51
professionalMihai MOGA15-Jan-13 6:51 
QuestionVariante para comprimir archivos binarios Pin
Manuel Vargas Herrera25-Dec-12 12:31
memberManuel Vargas Herrera25-Dec-12 12:31 
Se me ocurre una variante de este método para archivos binarios:

Esta consiste en que se tomen grupos de N bits y se vayan insertando en un diccionario. El diccionario también guardaría el número de veces que ha aparecido cada grupo. Luego se tomarían los primeros M grupos de N bits (que se repitan más veces) y se haría la compresión con base en ellos. Se podría utilizar un bit indicador de grupo comprimido o no comprimido, dentro del archivo comprimido. Si está comprimido, se insertaría (o leería) el siguiente código de grupo y si no está comprimido, se insertaría (o leería) el siguiente grupo de N bits no comprimidos. En la cabecera del archivo comprimido, se insertarían los grupos de N bits comprimidos y el código correspondiente, sería el orden en que se encuentra el grupo dentro de la cabecera.

M podría ser igual, a lo sumo, a N - 2, pues no tiene sentido que sea igual a N, pues abarcaría todos los grupos y tampoco tendría sentido que sea igual a N - 1, pues el bit que se ganaría, se perdería con el bit indicador de grupo comprimido o no comprimido. (Aunque también habría que considerar el tamaño de la cabecera y el número de bits colocados adicionalmente, con los indicadores de grupo comprimido o no comprimido).

Usted podría calcular el valor de N dinámicamente, verificando con cual valor se obtiene un número promedio de grupos de N bits, mayor o igual que 3 (por decir un número razonable). Por ejemplo, si un archivo tiene mil bits, entonces:

x = número de grupos de N bits
1000/x >= 3
-> 1000/3 >= x
-> x = 333.33

Si se divide 1000/333, se obtiene 3.003 y si se divide 100/334, se obtiene 2.994. Por lo tanto, se redondea x a 333, pues 1000/333 >= 3 y no así 1000/334.

Para calcular el número de bits que requiere 333, se calcula el logaritmo en base 2 de 333:

log2(333) = 8.38

2^8 = 256 y 2^9 = 512. Por lo tanto, el número 333 cabe en 9 bits.

Ahora bien, 1000/512 = 1.95, mientras que 1000/256 = 3.9. Por lo tanto, N debe ser igual a 8 bits y no a 9 bits.

M podría ser igual a N - 3. Por lo tanto, en este caso, M = 5 bits.

Ahora bien, este cálculo de M tiene el problema de que conforme N crezca, el valor porcentual de M se va acercando al 100% de N. Por ejemplo, si N = 100, M = N - 3 = 97 (el 97% de N). Así que otra forma de calcular el valor de M, es asignarle un valor porcentual de N. Así si N = 100 y M = 50% de N, entonces M = 50.

Por otra parte, conforme el archivo por comprimir crezca, el valor porcentual de los bits indicadores de bloque comprimido y bloque no comprimido, con respecto al tamaño total del archivo, tiende hacia 0. Por ejemplo, con grupos de 10 bits, con el bit indicador pasan a ser de 11 bits (un 10% adicional), mientras que con grupos de 50 bits, con el bit indicador pasan a ser de 51 bits (un 2% adicional).

Además, conforme el tamaño del archivo comprimido sea más grande, el tamaño del encabezado es, proporcionalmente, cada vez más pequeño. Por ejemplo, en este caso, el tamaño del archivo comprimido es aproximadamente (2^N)*3, mientras que el tamaño del encabezado es (2^M)*N. Para N = 8 y M = 4, esto equivale a (2^8)*3 y (2^4)*8. Si se divide (2^4)*8 entre (2^8)*3, se obtiene 128/768 que es igual a 0.1667 (el 16.67%). Para N = 20 y M = 10, esto equivale a (2^20)*3 y (2^10)*20. Si se divide (2^10)*20 entre (2^20)*3, se obtiene 20480/3145728 que es igual a = 0.0065 (el 0.65%). Para N = 29 y M = 14, esto equivale a (2^29)*3 y (2^14)*29. Si se divide (2^14)*29 entre (2^29)*3, se obtiene 475136/1610612736 que es igual a = 0.000295 (el 0.0295%).

En realidad aquí me equivoqué con el cálculo del número de veces en que se repite N en el archivo. Para que se repita 3 veces, se debe realizar la siguiente operación: (2^N)*N*3. Si N = 8, esto equivale a (2^8)*8*3 = 6144. Para que se repita una vez, se debe realizar la operación: (2^N)*N, que con N = 8 equivale a (2^8)*8 = 2048. Si se divide (2^N)*3 entre (2^N)*N, con N = 8, esto equivale a ((2^8)*3)/((2^8)*8) = 768/2048 = 0.375 (el 37.5%). Esto significa que en un archivo de 768 bits, se usa el 37.5% de todas las combinaciones posibles de números de 8 bits. El cálculo también se puede hacer dividiendo ((2^N)*3)/N que con N = 8 es igual a ((2^8)*3)/8 = 96 y luego dividiendo 96/(2^N) que con N = 8 es igual a 96/(2^8) = 0.375.

El número de bits indicadores de bloque comprimido o no comprimido, con tres repeticiones, es igual a (2^N)*1*3 y con una repetición es igual a (2^N)*1*1. Si se divide (2^N)*1*3 entre (2^N)*N*3, se obtiene 1/N, que con N = 10 bits, equivale a 1/10 = 0.1 (el 10%), mientras que con N = 20 bits, equivale a 1/20 = 0.05 (el 5%). Lo mismo ocurre con (2^N)*1*1 entre (2^N)*N*1.

El tamaño proporcional del encabezado, también disminuye mucho, pues con una repetición es igual a ((2^M)*N)/((2^N)*N), que con N = 8 y M = 4, es igual a ((2^4)*8)/((2^8)*8) = 0.0625 (el 6.25%). Con 3 repeticiones es igual a ((2^M)*N)/((2^N)*N*3), que, con estos mismos valores de N y de M, es igual a ((2^4)*8)/((2^8)*8*3) = 0.0208 (el 2.08%).

Para calcular el valor de N, se puede comenzar calculando el logaritmo en base 2 del tamaño total del archivo por comprimir. Así por ejemplo si el archivo mide mil bits, entonces log2(1000) = 9.97. Si se comienza con N = 10 y se usa un tamaño promedio de 3 veces, entonces:

(2^10)*10*3 = 30720 (muy grande).
(2^9)*9*3 = 13824 (todavía muy grande).
(2^8)*8*3 = 6144 (todavía muy grande).
(2^7)*7*3 = 2688 (todavía mayor que 1000).
(2^6)*6*3 = 1152 (todavía mayor que 1000).
(2^5)*5*3 = 480 (480 es menor o igual que 1000). Por lo tanto, N debe ser igual a 5 bits.

Con un número promedio de repeticiones de 3 veces, se podría escoger el valor de M hasta que se cumpla la condición de que se hayan tomado todos los grupos que se repiten al menos 4 veces. (4 = 3+1 repeticiones de grupos de N bits). De esta forma, M nunca superaría el 50% del valor de N).

Otra forma de calcular el valor de M, consiste en que cada vez en que el número de decimales de log2(X) sea igual a 0, se efectúe la operación ((2^M)*X + R)/((2^N)*N*3). X es igual al número acumulado de veces que se repiten los códigos de M bits, empezando desde los grupos de N bits que se repiten más veces, hasta los que se repiten menos veces. M sería igual a log2(X). R es igual al tamaño restante del archivo, que se calcularía como: ((2^N)*N*3 - N*X). Se tomaría el valor de M que minimice la relación. Para no tener que hacer el cálculo de M, cada vez que se incremente el valor de X en 1, se podría hacer cada vez que se duplique el valor de X. En este caso, M siempre se incrementaría en 1.

El algoritmo podría ser algo similar al siguiente:

M = -1
X = 0
m_iMejorValorM = M
m_iMejorValorX = X
m_dMejorRelacion = 1
m_iNumGruposNBits = 0
m_bQuedanGruposNBits = DemeSiguienteGrupoNBits(m_iNumVecesRepite)

while m_bQuedanGruposNBits
    m_iNumGruposNBits += 1
    X += m_iNumVecesRepite
    M = ceiling(log2(m_iNumGruposNBits))

    m_dNuevaRelacion = CalcularRelacion(N, M, X)

    if m_dNuevaRelacion < m_dMejorRelacion then
        m_dMejorRelacion = m_dNuevaRelacion
        m_iMejorValorM = M
        m_iMejorValorX = X
    end if

    m_bQuedanGruposNBits = DemeSiguienteGrupoNBits(m_iNumVecesRepite)
end while


En realidad, M es un valor que puede encontrarse entre 0 y ceiling(log2(X)). La explicación es que si la primera palabra se repite 15 veces, X = 15, mientras que M es igual a 0 (no a ceiling(log2(X)) = 4).

La fórmula original es: ((2^M)*X + R)/((2^N)*N*3), que es igual a: ((2^M)*X + (2^N)*N*3 - N*X)/((2^N)*N*3), que es igual a: ((2^M)*X - N*X + (2^N)*N*3)/((2^N)*N*3), que es igual a: ((2^M)*X - N*X)/((2^N)*N*3) + ((2^N)*N*3)/((2^N)*N*3), que es igual a: ((2^M)*X - N*X)/((2^N)*N*3) + 1, que es igual a: ((2^M - N)*X)/((2^N)*N*3) + 1. Independientemente del valor que tome X, el resultado de la función es menor que 1, mientras 2^M - N < 0. (N es una constante que se calcula antes de iniciar el algoritmo y M es una variable que se va incrementando durante el transcurso del algoritmo). Por lo tanto, en el momento en que 2^M - N >= 0, se puede concluir la ejecución del algoritmo.

De esta forma, el algoritmo se podría reescribir como:

M = -1
X = 0
m_iMejorValorM = M
m_iMejorValorX = X
m_dMejorRelacion = 1
m_iNumGruposNBits = 0
m_iNumVecesRepite = 0
m_bQuedanGruposNBits = DemeSiguienteGrupoNBits(m_iNumVecesRepite)
m_bSePuedeTerminar = false

while m_bQuedanGruposNBits andalso not m_bSePuedeTerminar
    m_iNumGruposNBits += 1
    X += m_iNumVecesRepite
    M = ceiling(log2(m_iNumGruposNBits))

    m_dNuevaRelacion = CalcularRelacion(N, M, X, m_bSePuedeTerminar)

    if m_dNuevaRelacion < m_dMejorRelacion then
        m_dMejorRelacion = m_dNuevaRelacion
        m_iMejorValorM = M
        m_iMejorValorX = X
    end if

    m_bQuedanGruposNBits = DemeSiguienteGrupoNBits(m_iNumVecesRepite)
end while


Ahora bien, supongamos que N = 25, que M = 5 y que X es igual a 100. N*X = 25*100 = 2500. Por su parte, (2^M)*X = (2^5)*100 = 32*100 = 3200. Como se puede observar, en este caso (2^M)*X > N*X, lo cual equivale a decir que (2^M) > N y que (2^M) - N > 0. Esto no sucede si M = 4, pues en este caso (2^M)*X = (2^4)*100 = 16*100 = 1600. En este caso si se cumple que (2^M)*X < N*X -> (2^M) < N -> (2^M) - N < 0. Esto se da porque con N = 25, se ocupan 5 bits, sin embargo 25 < 2^5 -> 25 < 32. Esto no ocurre con 2^4, pues 25 > 2^4 -> 25 > 16. De allí que se utilice:

M = ceiling(log2(m_iNumGruposNBits))
en vez de...
M = floor(log2(m_iNumGruposNBits))

Esto por cuanto si N = 25 y m_iNumGruposNBits = 16, entonces M = ceiling(log2(m_iNumGruposNBits)) -> M = 4 y 2^M = 2^4 -> 2^M = 16 -> 2^M < N -> 2^M - N < 0. En cambio si N = 25 y m_iNumGruposNBits = 17, entonces M = ceiling(log2(m_iNumGruposNBits)) -> M = 5 y 2^M = 2^5 -> 2^M = 32 -> 2^M > N -> 2^M - N > 0.

Por otra parte, hay que probar mientras 2^M - N < 0, independientemente del valor de X. Esto por cuanto si:

a) M = 3, N = 25 y X = 104, entonces (2^M - N)*X = (2^3 - 25)*104 = (8 - 25)*104 = -17*104 = -1768.
b) M = 4, N = 25 y X = 117, entonces (2^M - N)*X = (2^4 - 25)*117 = (16 - 25)*117 = -9*117 = -1053. -1768 < -1053. Por lo tanto, el caso "a" es mejor que el caso "b".
c) M = 4, N = 25 y X = 208, entonces (2^M - N)*X = (2^4 - 25)*208 = (16 - 25)*208 = -9*208 = -1872. -1872 < -1768. Por lo tanto, el caso "c" es mejor que el caso "a".

Ahora bien, tenemos que la fórmula es: ((2^M - N)*X)/((2^N)*N*3) + 1. Si a esto se le suma el espacio que ocupan los bits indicadores de bloque comprimido o no comprimido (que es igual a 1/N), la fórmula pasa a ser: ((2^M - N)*X)/((2^N)*N*3) + 1 + 1/N. Si el valor resultante, al evaluar esta fórmula, es menor que 1, entonces se comprime el archivo. En caso contrario, no se comprime.

Ahora bien, la fórmula: ((2^M - N)*X)/((2^N)*N*3) + 1 + 1/N, se puede evaluar dentro de la función: "CalcularRelacion" que se encuentra en el algoritmo aquí descrito. Sin embargo, a la variable "m_bSePuedeTerminar" se le puede asignar el valor "true", solo cuando 2^M - N < 0. Esto por cuanto "1/N" es una constante y "((2^M - N)*X)/((2^N)*N*3)" es una variable cuyo valor se puede ir decrementando durante el ciclo del algoritmo. Así se puede dar el caso en que la función retorne un valor mayor o igual que 1, pero este caso nunca ingresará al bloque de código que se encuentra dentro de la condición "if m_dNuevaRelacion < m_dMejorRelacion then", pues "m_dMejorRelacion" se inicia en 1, antes de iniciar el ciclo del algoritmo.

Considerando el tamaño proporcional de encabezado, la fórmula podría convertirse en: ((2^M - N)*X)/((2^N)*N*3) + 1 + 1/N + ((2^M)*N)/((2^N)*N*3).

En realidad me equivoqué con la fórmula: M es el número de bits que ocupan los códigos comprimidos. Por otra parte, se puede usar una variable "G" que indique el número de grupos de N bits que hay en el encabezado. Así la fórmula pasaría a ser:

((M - N)*X)/((2^N)*N*3) + 1 + 1/N + (G*N)/((2^N)*N*3).

que sería igual a:

((M - N)*X + G*N)/((2^N)*N*3) + 1 + 1/N

y el algoritmo sería el siguiente:

M = 0
X = 0
G = 0
m_iMejorValorM = M
m_iMejorValorG = G
m_dMejorRelacion = 1
m_iNumVecesRepite = 0
m_bQuedanGruposNBits = DemeSiguienteGrupoNBits(m_iNumVecesRepite)
m_bSePuedeTerminar = false

while m_bQuedanGruposNBits andalso not m_bSePuedeTerminar
    G += 1
    X += m_iNumVecesRepite

    if G = 1 then
        M = 1
    else
        M = ceiling(log2(G))
    end if

    m_dNuevaRelacion = CalcularRelacion(N, M, X, G, m_bSePuedeTerminar)

    if m_dNuevaRelacion < m_dMejorRelacion then
        m_dMejorRelacion = m_dNuevaRelacion
        m_iMejorValorM = M
        m_iMejorValorG = G
    end if

    m_bQuedanGruposNBits = DemeSiguienteGrupoNBits(m_iNumVecesRepite)
end while


M = ceiling(log2(G)), pues ese es el espacio, en bits, que ocupan los "G" grupos de "N" bits que se van a comprimir. log2(1) es igual a 0, sin embargo, si hay un grupo, se ocupa un bit y M debe ser igual, en este caso, a 1.

El ciclo se repetiría mientras ((M - N)*X + G*N)/((2^N)*N*3) sea menor que 0, pues M, X y G comienzan en un valor mayor o igual que 1, la primera vez que se calcula la relación y se van incrementando durante el transcurso del algoritmo.

Se ocupa la variable "m_iMejorValorG", pues indica cuántos grupos de "N" bits hay en el encabezado. También se ocupa la variable "m_iMejorValorM", pues indica el tamaño, en bits, que ocupa cada grupo comprimido.

En la relación también se podrían sumar los bits que ocupan los campos del encabezado, que podrían ser, el número de versión, el valor de G, el valor de N y el tamaño del archivo. Si el tamaño del campo de número de versión es de 8 bits, el tamaño del campo del valor de G es de 32 bits, el tamaño del campo del valor de N es de 8 bits y el tamaño del campo del tamaño del archivo es de 32 bits, estos datos suman 80 bits. Estos bits no se sumarían en la ecuación ((M - N)*X + G*N)/((2^N)*N*3), pues si M = 1, N = 10, X = 7 y G = 1, entonces (M - N)*X + G*N + 80) = (1 - 10)*7 + 1*10 + 80 = -9*7 + 90 = -63 + 90 = 27 y 27 es mayor que 0. En cambio si M = 1, N = 10, X = 14 y G = 2, entonces (M - N)*X + G*N + 80) = (1- 10)*14 + 2*10 + 80 = -9*14 + 20 + 80 = -126 + 100 = -26 y -26 si es menor que 0.

También el ciclo se podría repetir mientras la ecuación ((M - N)*X + G*N) sea menor que 0, pues, independientemente del valor que tome ((2^N)*N*3), que siempre es mayor que 0, el signo de la ecuación ((M - N)*X + G*N)/((2^N)*N*3) es igual al signo de la ecuación ((M - N)*X + G*N).

Así, la relación pasaría a ser, en este caso, igual a:

((M - N)*X + G*N + 80)/((2^N)*N*3) + 1 + 1/N.

y el ciclo se repetiría mientras:

((M - N)*X + G*N) < 0.

No hace falta incorporar el campo del valor de M en el encabezado, pues es igual a ceiling(log2(G)), o bien, es igual a 1, cuando ceiling(log2(G)) = 0.

El peor caso, es que X sea igual a 3 (pues el número promedio de repeticiones, según este algoritmo, es de 3), en cuyo caso, si M = 1 y G = 1, entonces:

((M - N)*X + G*N) = ((1 - N)*3 + 1*N) = 3 - 3*N + 1*N = 3 - 2*N. Esto es menor que 0, si N es mayor o igual que 2.

modified 30-Dec-12 13:10pm.

SuggestionRe: Variante para comprimir archivos binarios Pin
DaveAuld30-Dec-12 5:15
protectorDaveAuld30-Dec-12 5:15 
GeneralRe: Variante para comprimir archivos binarios Pin
Manuel Vargas Herrera30-Dec-12 9:16
memberManuel Vargas Herrera30-Dec-12 9:16 
GeneralRe: Variante para comprimir archivos binarios Pin
DaveAuld30-Dec-12 19:19
protectorDaveAuld30-Dec-12 19:19 
GeneralRe: Variante para comprimir archivos binarios Pin
Manuel Vargas Herrera30-Dec-12 9:32
memberManuel Vargas Herrera30-Dec-12 9:32 
GeneralRe: Variante para comprimir archivos binarios Pin
Manuel Vargas Herrera30-Dec-12 9:37
memberManuel Vargas Herrera30-Dec-12 9:37 
QuestionCompresión asignándole un número a cada palabra Pin
Manuel Vargas Herrera20-Dec-12 7:41
memberManuel Vargas Herrera20-Dec-12 7:41 
AnswerRe: Compresión asignándole un número a cada palabra Pin
Hatem Mostafa21-Dec-12 1:38
memberHatem Mostafa21-Dec-12 1:38 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Manuel Vargas Herrera21-Dec-12 2:37
memberManuel Vargas Herrera21-Dec-12 2:37 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Manuel Vargas Herrera21-Dec-12 3:16
memberManuel Vargas Herrera21-Dec-12 3:16 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Hatem Mostafa24-Dec-12 0:35
memberHatem Mostafa24-Dec-12 0:35 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Manuel Vargas Herrera24-Dec-12 2:46
memberManuel Vargas Herrera24-Dec-12 2:46 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Manuel Vargas Herrera24-Dec-12 7:27
memberManuel Vargas Herrera24-Dec-12 7:27 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Manuel Vargas Herrera24-Dec-12 8:31
memberManuel Vargas Herrera24-Dec-12 8:31 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Manuel Vargas Herrera21-Dec-12 4:21
memberManuel Vargas Herrera21-Dec-12 4:21 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Manuel Vargas Herrera21-Dec-12 5:42
memberManuel Vargas Herrera21-Dec-12 5:42 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Hatem Mostafa24-Dec-12 0:38
memberHatem Mostafa24-Dec-12 0:38 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Manuel Vargas Herrera24-Dec-12 2:41
memberManuel Vargas Herrera24-Dec-12 2:41 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Manuel Vargas Herrera21-Dec-12 6:11
memberManuel Vargas Herrera21-Dec-12 6:11 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Hatem Mostafa24-Dec-12 0:39
memberHatem Mostafa24-Dec-12 0:39 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Manuel Vargas Herrera21-Dec-12 6:53
memberManuel Vargas Herrera21-Dec-12 6:53 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Manuel Vargas Herrera21-Dec-12 7:53
memberManuel Vargas Herrera21-Dec-12 7:53 
GeneralRe: Compresión asignándole un número a cada palabra Pin
Manuel Vargas Herrera21-Dec-12 8:23
memberManuel Vargas Herrera21-Dec-12 8:23 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web01 | 2.8.190419.4 | Last Updated 18 Dec 2012
Article Copyright 2012 by Hatem Mostafa
Everything else Copyright © CodeProject, 1999-2019
Layout: fixed | fluid