LZW

LZW(Lempel-Ziv-Welch)는 아브라함 렘펠과 제콥 지브, 테리 웰치가 만든 공통 비손실 데이터 압축 알고리즘이다. 1978년에 렘펠과 지브가 공개한 LZ78 알고리즘을 1984년에 웰치가 개선해 공개하였다. 이 알고리즘은 빠른 이식을 위해 고안되었지만 데이터의 제한된 분석만 수행하기 때문에 그리 최적으로 동작하지는 않는다. 허프먼의 아이디어에서 조금 더 응용된 형태이다.

 알고리즘 
압축 프로그램 알고리즘:
    w = NIL;
    add all possible charcodes to the dictionary
    for (every character c in the uncompressed data) do
        if ((w + c) exists in the dictionary) then
            w = w + c;
        else
            add (w + c) to the dictionary;
            add the dictionary code for w to output;
            w = c;
        endif
    done
    add the dictionary code for w to output;
    display output;

압축 해제 프로그램 알고리즘:
    add all possible charcodes to the dictionary
    read a char k;
    entry = dictionary entry for k
    output entry;
    w = entry;
    while (read a char k) do
       if (index k exists in dictionary) then
           entry = dictionary entry for k;
       else if (k == currSizeDict)
           entry = w + w[0];
       else
           signal invalid code;
       endif
       output entry;
       add w+entry[0] to the dictionary;
       w = entry;
    done

 종류 
 LZMW (1985년, V. Miller, M. Wegman)David Salomon, Data Compression - The complete reference, 4th ed., page 209
 LZAP (1988년, James Storer)David Salomon, Data Compression - The complete reference, 4th ed., page 212 - LZMW의 수정판
 LZWL는 음절 기반의 LZW이다.

 같이 보기 
 LZ77과 LZ78
 LZMA
 LZSS
 LZJB

 각주 

 외부 링크 
 SharpLZW - C# open source implementation

분류:아카이브 포맷
분류:무손실 압축 알고리즘