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:25] – [Decoding LZW] 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 90: Line 91:
 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"`+  * **Decoded string so far**: `"A"`
  
-2. **66**: Look up in the dictionary. It maps to `"B"`.+2.) **66**: Look up in the dictionary. It maps to `"B"`.
  
-**Decoded string so far**: `"AB"`+  * **Decoded string so far**: `"AB"`
  
-3. **256**: Look up in the dictionary. It maps to `"AB"`.+3.) **256**: Look up in the dictionary. It maps to `"AB"`.
  
-**Decoded string so far**: `"ABAB"`+  * **Decoded string so far**: `"ABAB"`
  
-4. **258**: Look up in the dictionary. It maps to `"ABA"`.+4.) **258**: Look up in the dictionary. It maps to `"ABA"`.
  
-**Decoded string so far**: `"ABABABA"`+  * **Decoded string so far**: `"ABABABA"`
  
 The original string ''ABABABA'' is reconstructed from the compressed codes. The original string ''ABABABA'' is reconstructed from the compressed codes.
Line 123: 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.1728289522.txt.gz · Last modified: 2024/10/07 08:25 by knehez