Institute of Information Science - University of Miskolc

User Tools

Site Tools

Trace:
tanszek:oktatas:techcomm:lzw_coding

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
tanszek:oktatas:techcomm:lzw_coding [2024/10/07 08:23] – [Key Steps in LZW Compression] kneheztanszek:oktatas:techcomm:lzw_coding [2024/11/19 07:54] (current) – knehez
Line 10: Line 10:
  
 3. **Add new substrings** to the dictionary and output the dictionary index for the current substring when it can no longer be extended by the next character in the input. 3. **Add new substrings** to the dictionary and output the dictionary index for the current substring when it can no longer be extended by the next character in the input.
 +----
  
 === Example of LZW Compression === === Example of LZW Compression ===
Line 88: Line 89:
 To decode an LZW-compressed string, you use the same dictionary-based approach but in reverse. The decoder reconstructs the dictionary entries as it processes the encoded output, using the indices to retrieve the corresponding substrings. To decode an LZW-compressed string, you use the same dictionary-based approach but in reverse. The decoder reconstructs the dictionary entries as it processes the encoded output, using the indices to retrieve the corresponding substrings.
  
-Let’s go through the decoding process of the encoded sequence `65 66 256 65`:+Let’s go through the decoding process of the encoded sequence ''65 66 256 65'':
  
-1. **65**: Look up in the dictionary. It maps to `"A"`. +1.) **65**: Look up in the dictionary. It maps to `"A"`.
-   - **Decoded string so far**: `"A"`+
  
-2. **66**: Look up in the dictionary. It maps to `"B"`. +  * **Decoded string so far**: `"A"`
-   - **Decoded string so far**: `"AB"`+
  
-3. **256**: Look up in the dictionary. It maps to `"AB"`. +2.) **66**: Look up in the dictionary. It maps to `"B"`.
-   - **Decoded string so far**: `"ABAB"`+
  
-4. **258**: Look up in the dictionary. It maps to `"ABA"`. +  * **Decoded string so far**: `"AB"`
-   - **Decoded string so far**: `"ABABABA"`+
  
-The original string `"ABABABA"` is reconstructed from the compressed codes.+3.) **256**: Look up in the dictionary. It maps to `"AB"`. 
 + 
 +  * **Decoded string so far**: `"ABAB"` 
 + 
 +4.) **258**: Look up in the dictionary. It maps to `"ABA"`. 
 + 
 +  * **Decoded string so far**: `"ABABABA"` 
 + 
 +The original string ''ABABABA'' is reconstructed from the compressed codes.
  
 --- ---
Line 119: Line 124:
  
  
 +C implementation of LZW encoding:
 +
 +<sxh c>
 +#include <stdio.h>
 +#include <string.h>
 +
 +#define MAX_sxhS 100
 +
 +char sxhTable[MAX_sxhS][10] = {"a","b","c","d","e"};
 +
 +int tableElements = 5;
 +
 +int isInsxhTable(char *s)
 +{
 +    for(int i = 0; i < tableElements; i++)
 +    {
 +        if(strcmp(sxhTable[i], s) == 0)
 +        {
 +            return i;
 +        }
 +    }
 +    return -1;
 +}
 +
 +int main()
 +{
 +    char text[] = "dabbacdabbacdabbacdabbacdee";
 +    char *p = text;
 +    int bufferEnd = 1;
 +
 +    int lastFoundIndex = -1;
 +    while(*p != '\0')
 +    {
 +        char subStr[10];
 +        strncpy(subStr, p, bufferEnd);
 +        subStr[bufferEnd] = '\0';
 +        int foundIndex = isInsxhTable(subStr);
 +        if(foundIndex != -1)
 +        {
 +           bufferEnd++;
 +           lastFoundIndex = foundIndex;
 +           continue;
 +        }
 +        p += strlen(subStr) - 1;
 +        bufferEnd = 1;
 +        strcpy(sxhTable[tableElements++], subStr);
 +        printf("%d,", lastFoundIndex + 1);
 +    }
 +}
  
 +</sxh>
tanszek/oktatas/techcomm/lzw_coding.1728289389.txt.gz · Last modified: 2024/10/07 08:23 by knehez