enLZW  LZW 부호
deLZW  LZW 부호로부터의 복호

LZW 부호
    long enLZW(unsigned char *code, long clen,
               unsigned char *text, long tlen);

LZW 부호로부터의 복호
    long deLZW(unsigned char *text, long tlen,
               unsigned char *code, long clen);

LZW 부호 함수에 대해
    code  (입출력) LZW 부호를 격납하는 배열
    clen  (입력) 배열 code의 길이
    text  (입력) 텍스트를 격납하는 배열
    tlen  (입력) 배열 text의 길이

LZW 부호로부터의 복호 함수에 대해
    text  (입출력) 텍스트를 격납하는 배열
    tlen  (입력) 배열 text의 길이
    code  (입력)  LZW 부호를 격납하는 배열
    clen  (입력) 배열 code의 길이

LZW 부호 함수에 대해
    LZW 부호의 길이. encode에 실패했을 때는 -1L.

LZW 부호로부터의 복호 함수에 대해
    텍스트의 길이. 복호에 실패했을 때는 -1L.

#define CHAR_SIZE 256
#define NODE_SIZE 4096
#define BITS_LEN  12           /* 2^^12 = 4096 */

typedef struct {
    unsigned char chr;         /* 문자 */
    int      parent;           /* 친노드에 */
    int      brother;          /* 형제 노드에 */
    int      child;            /* 자 노드에 */
} NODE;

long enLZW(unsigned char *code, long clen,
           unsigned char *text, long tlen)
{
    int  i, j;
    int  w, k, rv;
    long c, len;
    int  freeNode;
    NODE node[NODE_SIZE];
    static int wMask[BITS_LEN] =
        { 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1};
    static unsigned char bit0[8] = {~128,~64,~32,~16,~8,~4,~2,~1};
    static unsigned char bit1[8] = { 128, 64, 32, 16, 8, 4, 2, 1};

    
    if (tlen <= 0) return -1;

    for (i = 0; i <= CHAR_SIZE; i++) {
        node[i]. chr     = (unsigned char) i;
        node[i]. brother = i+1;
        node[i]. parent  = node[i]. child = 0;
    }
    node[CHAR_SIZE]. brother = 0;
    freeNode = CHAR_SIZE + 1;
    
    /* encode와 나무의 갱신 */
    w = text[0];
    for (c = 1, i = 0, len = 0; ; c++) {
        k = (c >= tlen) ?  CHAR_SIZE : text[c];

        /* wk 가 등록제 ?  */
        for (rv = node[w]. child; rv > 0; rv = node[rv]. brother)
            if (node[rv]. chr == k) break;
        if (rv > 0) w = rv;
        else {
            /* 참조 번호를 출력 */
            for (j = 0; j < BITS_LEN; j++) {
                if (w & wMask[j]) *code |= bit1[i];
                else              *code &= bit0[i];
                if (++i == 8) {
                    code++;
                    if (++len > clen) return -1L;
                    i = 0;
                }
            }
            /* wk 를 등록 */
            if (freeNode < NODE_SIZE) {
                node[freeNode]. parent  = w;
                node[freeNode]. chr     = k;
                node[freeNode]. brother = node[w]. child;
                node[freeNode]. child   = 0;
                node[w]. child = freeNode++;
            }
            w = k;
        }
        if (c == tlen+1) break;              /* EOF */
    }
    if (i > 0) len++;
    return (len > clen) ?  -1L : len;
}

long deLZW(unsigned char *text, long tlen,
           unsigned char *code, long clen)
{
    int  i, j;
    int  w, k, rv;
    long c, len;
    int  freeNode;
    NODE node[NODE_SIZE];
    int  stack[NODE_SIZE]; int sp;
    static int wMask[BITS_LEN] =
        { 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1};
    static unsigned char bit1[8] = { 128, 64, 32, 16, 8, 4, 2, 1};

    
    if (clen <= 0) return -1;

    for (i = 0; i <= CHAR_SIZE; i++) {
        node[i]. chr     = (unsigned char) i;
        node[i]. brother = i+1;
        node[i]. parent  = node[i]. child = 0;
    }
    node[CHAR_SIZE]. brother = 0;
    freeNode = CHAR_SIZE + 1;
    
    /* 복호화와 나무의 갱신 */
    for (i = 0, len = 0, c = 0, sp = 0; ; ) {
        for (j = 0, rv = 0; j < BITS_LEN; j++) {
            if (*code & bit1[i]) rv |= wMask[j];
            if (++i == 8) {
                code++;
                if (++c > clen) return -1L;
                i = 0;
            }
        }
        if (rv == CHAR_SIZE) break;              /* EOF */

        /* 참조 번호에 대응하는 노드로부터 루트까지 오르면서 문자를 출력 */
        if (rv >= freeNode) {
            stack[sp++] = k;                     /* 예외 처리 */
            k = w;
        } else k = rv;

        while (k > CHAR_SIZE) {
            stack[sp++] = node[k]. chr;
            k = node[k]. parent;
        }
        stack[sp++] = k;

        while (sp) {
            if (++len > tlen) return -1L;
            *text++ = stack[--sp];
        }

        /* wk 를 등록 */
        if (len > 1 && freeNode < NODE_SIZE) {
            node[freeNode]. parent  = w;
            node[freeNode]. chr     = k;
            node[freeNode]. brother = node[w]. child;
            node[freeNode]. child   = 0;
            node[w]. child = freeNode++;
        }
        w = rv;
    }
    return len;
}

LZ78 부호는, 사전으로서 지금까지 발견한 부분 캐릭터 라인의 일람표를 사용하는 와 (으)로, 포괄적인 사전의 작성이 가능해진다. 실제로는, 입력된 캐릭터 라인을 증 분 분해로 불리는 방법으로 부분 캐릭터 라인 으로 분해해, 얻을 수 있던 부분 캐릭터 라인을 사전에 등록해, 이 사전을 이용해 encode를 실시하고 있다.

LZ78 부호에서는, 부호어중에 반드시 입력 캐릭터 라인중의 문자 그 자체가 포함되어 있다 하지만, LZW 부호에는, 1 문자로부터 되는 부분 캐릭터 라인을 모두 사전에 미리 등록해 (이)라고 두는 것으로, 부호어중에 포함되는 문자를 없애, 항상 사전의 참조 번호 만으로 끝마친다.

구체적으로는, LZW 부호는 입력 텍스트에 있는 부분 캐릭터 라인에 참조 번호를 나누어 진 사전을 만들어, 다시 그 부분 캐릭터 라인이 나타나면(자) 그 참조 번호를 부호어로 해 (이)라고 출력한다. 부분 캐릭터 라인의 조합은 최장 일치법으로 실시해, 새롭게 등록하는 부분문 자렬은 이전에 등록한 것을 1 문자 연장한 것이다. 초기 사전은 입력에 있는 모든 문자에 참조 번호를 할당한 것으로 한다.

LZW 부호에서는, 부호어를 이하와 같이 해 구성한다.

1. 최초의 입력 문자를 w 로 한다.
2. 입력 텍스트로부터 다음의 문자 K 를 읽어들여,
   wK 가 사전에 등록제이면, wK 를 w 로 한다.
   wK 가 미등록이면, w 에 대응하는 사전 참조 번호를 출력해, wK 를 사전 등록한다. 다음에, K 를 w 로 한다.
3. 2. 의 처리를 입력이 종료할 때까지 반복한다.

LZW 부호의 각종 개량판을 실제로 사용한 압축 프로그램으로서는, MS-DOS에 있어 PKARC, UNIX 의 compress 커멘드, Macintosh 의 StfuuIt 등이 있어, 컴퓨터나 OS의 종류를 불문하고, 넓게 이용되고 있다. 또, 호- 무페이지에 넓게 이용되고 있는 GIF 이미지 파일에, 압축 알고리즘 (으)로서 채용되고 있다.