LZW

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

알고리즘[편집]

압축 프로그램 알고리즘:

   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)[1]
  • LZAP (1988년, James Storer)[2] - LZMW의 수정판
  • LZWL는 음절 기반의 LZW이다.

같이 보기[편집]

주석[편집]

  1. David Salomon, Data Compression - The complete reference, 4th ed., page 209
  2. David Salomon, Data Compression - The complete reference, 4th ed., page 212

바깥 고리[편집]