LZW Coding Back

LZW Coding

• LZW編碼: 是一種基於字典的編碼技術
• 開始編碼時, 字典必須含有出現的所有單個字符
• 每次加進一個前綴和一個字符

數據結構

class dictionary
{
private:
    int index;
    char value[MAXSIZE];
    int code;
public:
    dictionary(int index, char value[]) :index(index){ strcpy((*this).value, value); };
    char* get_value(){ return value; }
    int get_index(){ return index; }
    void set_code(int set){ code = set; }
    int get_code(){ return code; }
};

算法實現

/* Coding */
void LZW_CODING(const char* input)
{
    const char* ch = input;
    int count = 1;                    //用于char指针跳转
    while (*(ch + 1) != '\0')
    {
        char a[MAXSIZE];
        bool isexisted = false;
        for (int i = 0; i < num; i++)
        {
            strncpy(a, ch, count + 1);
            a[count + 1] = '\0';

            if (!strcmp((*d[i]).get_value(),a))
            {
                isexisted = true;
                break;
            }
        }
        if (isexisted == false)
        {
            char b[MAXSIZE];
            strncpy(b, ch, count);
            b[count] = '\0';
            for (int i = 0; i < num; i++)
            {
                if (!strcmp((*d[i]).get_value(), b))
                {
                    d[num++] = new dictionary(num + 1, a);
                    (*d[num - 1]).set_code((*d[i]).get_index());
                    break;
                }
            }
            ch += count;
            count = 1;
        }
        else
        {
            count++;
        }
    }

    for (int i = 0; i < num; i++)
    {
        if ((*((*d[i]).get_value()) == extract_last((*d[num - 1]).get_value())))
        {
            d[num++] = new dictionary(num + 1, "");
            (*d[num - 1]).set_code((*d[i]).get_index());
            break;
        }
    }

    cout << "EnCode: ";
    for (int i = _count; i < num; i++)
        cout << (*d[i]).get_code();
    cout << endl;
}

/* Initialize */
void INITIALIZE_DICTIONARY(const char* input)
{
    const char* ch = input;

    while (*ch != '\0')
    {
        bool isexisted = false;
        for (int i = 0; i < num; i++)
        {
            if (*(*d[i]).get_value() == *ch)
                isexisted = true;
        }
        if (isexisted == false)
        {
            char a[MAXSIZE];
            strncpy(a, ch, 1);
            a[1] = '\0';
            d[num++] = new dictionary(num + 1, a);
        }
        ch++;
    }
}