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
종류
같이 보기
- LZ77과 LZ78
- LZMA
- LZSS
- LZJB
각주
외부 링크
- SharpLZW - C# open source implementation
![]() | 이 글은 소프트웨어에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다. |