노력 LZW 압축

Question

http://giflib.sourceforge.net/whatsinagif/lzw_image_data.html

나는 노력의 LZW 압축을 이해하기 위해이 페이지를 읽고 있었다. 그것의 샘플 이미지로부터 인코딩 코드를 나타낸다 : 가변 길이를 바이트로 압축 한 후

# 4 # 1 # 6 # 6 # 2 # 9 # 9 ..

을가된다 :

8C 2D 99 ..

의미 :

# 4 - 3 비트

# 1 - 3 비트

# 6 - 3 비트

# 6 - 3 비트

# 2 - 4 비트

# 9 - 난 기후 샘플 생성 된 4 비트

이 압축 화상 데이터는 정확 Photoshop을 사용하여 이미지를 확인하고 바이너리 내용을 확인했습니다. 출력 코드 # 그러나이

는,이 때

그것은 분명히 비트 크기의 증가를 보여줍니다 발생 방법 비트 크기 증가에 대한 페이지 회담 : When you are encoding the data, you increase your code size as soon as your write out the code equal to 2^(current code size)-1

Jumping back to our sample image, we see that we have a minimum code size value of 2 which means out first code size will be 3 bits long. Out first three codes, #1 #6 and #6, would be coded as 001 110 and 110. If you see at Step 6 of the encoding, we added a code of #7 to our code table. This is our clue to increase our code size because 7 is equal to 2^3-1 (where 3 is our current code size). Thus, the next code we write out, #2, will use the new code size of 4 and therefore look like 0010.

그러나 그 인코딩 테이블에서 6 단계는 항목 # 7이 LZW 사전에 추가되지만 출력을 위해 추가 된 코드는 첫 번째 # 6입니다. 알고리즘에 따르면, 두 # 6은 각각 4 비트가되어야하지만 실제로 어떻게 3 비트입니까? 이 페이지 https://www.eecis.udel.edu/~amer/CISC651/lzw.and.gif.explained.html

는 비트 크기에 대한 같은 일이 그렇게 잘못된 것입니다 If you're encoding, you start with a compression size of (N+1) bits, and, whenever you output the code (2**(compression size)-1), you bump the compression size up one bit

말한다에 따라

?

Answer 1

다시 연결 한 페이지에서 주어진 예를보세요. 이미지는 4 색만 있습니다. 즉, LZW 압축기는 3 비트 코드로 시작됩니다. 사전에는 여섯 개의 항목이 있습니다. 리터럴 0..3, 일반 코드 4 및 EOI 코드 5입니다. 처음 두 코드 출력은 명확한 코드 4와 리터럴 1입니다. 모든 GIF LZW 스트림이 시작되는 방식입니다. 이제 이미지가 1의 런으로 시작하기 때문에 압축이 시작됩니다. 스트림에 2 개의 코드가 쓰여지면 사전 슬롯 8 개가 고갈되고 코드 크기가 4로 증가합니다. 따라서 다음 코드 인 리터럴 2는 4 비트 숫자로 기록됩니다.

알다시피, 아무 것도 잘못되었습니다. 그것은 GIF가 4 색 이미지를 사용하는 방식입니다.