LZW

3. 종류

LZMW (1985년, V. 밀러, M. 웨그만)^[9]는 입력에서 사전에 이미 있는 가장 긴 문자열(현재 일치하는 문자열)을 검색한다. 이전 일치 문자열과 현재 일치 문자열을 연결하여 사전에 추가한다. (따라서 사전 항목이 더 빠르게 증가하지만, 이 방식은 구현하기가 훨씬 더 복잡하다.) 밀러와 웨그만은 또한 사전이 가득 찼을 때 빈도가 낮은 항목을 사전에서 삭제할 것을 제안했다.

LZAP (1988년, 제임스 스토러)^[10] - LZMW의 수정판: 이전 일치 문자열과 현재 일치 문자열을 연결한 것만 사전에 추가하는 대신, 이전 일치 문자열과 현재 일치 문자열의 각 초기 부분 문자열을 연결하여 추가한다("AP"는 "모든 접두사"를 의미한다). 예를 들어, 이전 일치 문자열이 "wiki"이고 현재 일치 문자열이 "pedia"이면 LZAP 인코더는 "wikip", "wikipe", "wikiped", "wikipedi", "wikipedia"의 5개의 새로운 시퀀스를 사전에 추가한다. 여기서 LZMW 인코더는 "wikipedia" 시퀀스 하나만 추가한다. 이는 더 많은 사전 항목을 추가하는 대신 LZMW의 복잡성을 일부 제거한다.

LZWL는 음절 기반의 LZW이다.

3. 1. LZMW

3. 2. LZAP

3. 3. LZWL

4. 구현 (Groovy)

다음은 Groovy에서의 구현이다. 먼저, 비트 열을 다루는 스트림을 준비한다.

```groovy

class BitStream {

BitSet bs = new BitSet(); int len = 0, pos = 0;

void write(int v, int bits) {

for (int i in 0..>> i) & 1) != 0 }

}

int read(int bits) {

int v = 0; for (int i in 0..
return v

}

String toString() { "length = $len, {" + (0..
}

```

압축은 다음과 같다.

```groovy

BitStream compress(byte[] data) {

BitStream bs = new BitStream(); List str = []; int maxCode = 255, maxCodeBits = 8;

Map table = [:]; for (int i in 0..maxCode) { table(byte) i = i }

for (byte c in data) {

str << c

if (!table.containsKey(str)) {

bs.write(table[str[0..(str.size() - 2)]], maxCodeBits)

table[str] = ++maxCode

if (maxCode == (1 << maxCodeBits)) maxCodeBits++

str = [c]

}

}

bs.write(table[str], maxCodeBits)

return bs

}

```

압축 해제는 다음과 같다.

```groovy

byte[] decompress(BitStream bs) {

List bytes = []; int maxCode = 255, maxCodeBits = 8, prevCode; byte c;

List table = []; for (byte v in 0..maxCode) { table << [v] }

bs.pos = 0

bytes << (c = prevCode = bs.read(maxCodeBits))

while (bs.pos < bs.len) {

if (++maxCode == (1 << maxCodeBits)) maxCodeBits++

int code = bs.read(maxCodeBits)

List str = (code == maxCode) ? table[prevCode] + c : table[code]

bytes.addAll(str)

table << table[prevCode] + (c = str[0])

prevCode = code

}

return bytes as byte[]

}

5. 예제

LZW 알고리즘의 작동 방식을 구체적인 예시를 통해 살펴본다. 아래 예제는 데이터의 인코딩 및 디코딩 과정에서 각 단계별 출력 상태와 사전의 변화를 보여준다.

== 인코딩 예제 ==

다음은 "TOBEORNOTTOBEORTOBEORNOT#" 문자열을 LZW 알고리즘으로 인코딩하는 과정을 나타낸 표이다. 초기 사전은 대문자 A-Z(1-26)와 '#' 문자(0)로 구성되며, 각 문자는 5비트로 표현된다.

인코딩 과정에서는 반복되는 문자열을 사전에 등록하고, 해당 문자열을 코드로 대체하여 출력한다.

== 디코딩 예제 ==

다음은 위에서 인코딩된 코드(20, 15, 11, 25, 15, 27, 11, 29, 28, 30, 11, 1, 34, 11, 21, 0)를 LZW 알고리즘으로 디코딩하는 과정을 나타낸 표이다. 디코더는 인코더와 동일한 초기 사전을 가지고 시작하며, 인코딩 과정과 유사하게 사전을 갱신하면서 디코딩을 수행한다.

== 특수한 경우의 디코딩 예제 ==

"TANBANANAS#" 문자열을 인코딩/디코딩하는 과정에서 발생하는 특수한 경우를 보여준다.

위의 예시에서 디코딩 중 입력 코드 31은 사전에 아직 추가되지 않은 상태이다. 이는 인코딩 과정에서 사전에 추가된 직후의 코드가 바로 사용되었기 때문이다. 디코딩에서는 사전에 추가하는 과정이 한 단계 늦기 때문에 발생한다. 이 경우, 코드 31에 해당하는 문자열은 이전 단계에서 디코딩된 문자열(AN)에 코드 31의 첫 글자(A)를 붙인 "ANA"임을 유추할 수 있다.

6. 특허 및 라이선스 문제

LZW에 대한 다양한 특허는 미국 및 기타 국가에서 발급되었다. LZ78은 1981년 8월 10일에 출원되어 렘펠(Lempel), 지브(Ziv), 콘(Cohn), 이스트만(Eastman)에 의해 로 특허를 받았으며, 스페리사(Sperry Corporation), 이후 유니시스사(Unisys Corporation)에 양도되었다. LZW 알고리즘에 대해 두 개의 미국 특허가 발급되었다. 빅터 S. 밀러(Victor S. Miller)와 마크 N. 웨그만(Mark N. Wegman)이 발명하고 IBM에 양도된 은 원래 1983년 6월 1일에 출원되었으며, 웰치(Welch)가 발명하여 스페리사, 이후 유니시스사에 양도된 는 1983년 6월 20일에 출원되었다.

상기 특허 외에도 웰치의 1983년 특허에는 그에 영향을 미친 다른 여러 특허에 대한 인용이 포함되어 있으며, 여기에는 NEC의 쥰 카나츠(Jun Kanatsu)가 발명한 두 개의 1980년 일본 특허([https://patents.google.com/patent/JPS5719857A/en JP9343880A] 및 [https://patents.google.com/patent/JPS57101937A/en JP17790880A]), 존 S. 호어닝(John S. Hoerning)의 (1974), 클라우스 E. 홀츠(Klaus E. Holtz)의 (1977), 카를 에크하르트 하인츠(Karl Eckhart Heinz)의 1981년 독일 특허([https://patents.google.com/patent/DE3118676C2/en DE19813118676])가 포함된다.<sup>[3]</sup>

1993-94년과 1999년에 유니시스사(Unisys Corporation)는 GIF 이미지에서 LZW에 대한 사용료를 징수하려 시도하면서 광범위한 비난을 받았다. 1993-1994년 유니시스-컴퓨서브(CompuServe) 논란(컴퓨서브(CompuServe)는 GIF 형식의 제작자)은 유즈넷(Usenet) comp.graphics 토론인 ''GIF 대체 파일 형식에 대한 생각''을 촉발시켰고, 이는 결국 1995년 특허에 얽매이지 않는 PNG(Portable Network Graphics) 파일 형식의 생성으로 이어진 이메일 교환을 촉진했다.

LZW 알고리즘에 대한 유니시스사의 미국 특허는 출원 후 20년이 지난 2003년 6월 20일에 만료되었다.<sup>[4]</sup> 영국, 프랑스, 독일, 이탈리아, 일본 및 캐나다에서 출원된 특허도 마찬가지로 출원 후 20년이 지난 2004년에 만료되었다.<sup>[4]</sup>

LZW는 1984년에 발표되었다. 처음에는 스페리사가 특허를 보유하고 있었다. 이후 스페리사는 배로우스사와 합병하여 1986년에 유니시스사가 되었고, 이 알고리즘의 특허권도 유니시스사에 승계되었다.

앞서 언급했듯이 GIF 이미지 압축에 사용되었으며, 그 특허료에 대한 유니시스사의 입장이 문제가 되었다. 자세한 내용은 GIF 특허 문제를 참조하십시오.

일본에서는 1984년 6월 20일에 특허가 출원되었고, 2004년 6월 20일에 만료되었다. 다음은 일본 특허청 산업 재산권 정보에서 발췌한 내용이다.

• 발명의 명칭: 압축 장치 및 압축 방법
• 출원일: 1984년 6월 20일
• * 출원 번호: 특허 출원 평7-341868
• 공개일: 1996년 9월 13일
• * 공개 번호: 특허 공개 평8-237138

6. 1. 대한민국에서의 특허 문제

6. 2. GIF, TIFF, PDF 등 파일 형식과의 관계

7. 활용

LZW 압축은 초기에 널리 사용된 범용 데이터 압축 방법으로, 큰 영어 텍스트 파일은 원래 크기의 절반 정도로 압축할 수 있었다. 1986년경 유닉스 시스템의 사실상 표준 유틸리티인 compress 프로그램에 사용되었으나, 이후 LZW 특허 침해 문제와 gzip이 DEFLATE 알고리즘을 사용하여 더 나은 압축률을 제공함에 따라 많은 배포판에서 사라졌다. 하지만 2008년 기준으로 FreeBSD는 compress와 uncompress를 배포판의 일부로 포함하고 있다. 다른 여러 인기 있는 압축 유틸리티도 LZW 또는 이와 밀접하게 관련된 방법을 사용했다.

LZW는 1987년 GIF 이미지 형식의 일부가 되면서 널리 사용되었으며, TIFF 및 PDF 파일에서도 선택적으로 사용할 수 있다. Adobe Acrobat 소프트웨어에서도 LZW를 사용할 수 있지만, Acrobat은 기본적으로 PDF 파일의 대부분의 텍스트 및 색상 테이블 기반 이미지 데이터에 DEFLATE를 사용한다.

7. 1. 파일 압축

7. 2. 이미지 압축

참조

<sub>[1]</sub> 간행물 A Technique for High-Performance Data Compression https://ieeexplore.i[...]
<sub>[2]</sub> 간행물 Compression of individual sequences via variable-rate coding http://www.cs.duke.e[...] 2009-03-03
<sub>[3]</sub> 특허
<sub>[4]</sub> 웹사이트 LZW Patent Information http://www.unisys.co[...] Unisys 2014-03-06
<sub>[5]</sub> 서적 Data Compression – The complete reference
<sub>[6]</sub> 서적 Data Compression – The complete reference
<sub>[7]</sub> 간행물 A Technique for High-Performance Data Compression http://www.cs.duke.e[...]
<sub>[8]</sub> 간행물 Compression of individual sequences via variable-rate coding http://www.cs.duke.e[...]
<sub>[9]</sub> 서적 Data Compression - The complete reference
<sub>[10]</sub> 서적 Data Compression - The complete reference