비트 패킹 LZW 문구 번호

Question

현재 저는 LZW 압축의 자바 구현 작업을하고 있습니다. 지금까지 내 인코더는 어떻게 작동해야합니다. 파일을 읽어서 비트 패커에 연결될 프레이즈 번호를 출력합니다.

이제이 문구 번호를 파일로 압축해야하는데이 과정을 어떻게 진행해야하는지 확신 할 수 없습니다. 또한 인코딩 할 수있는 최대 비트 수는 20입니다. 따라서 인코딩되는 숫자가 인코딩에 필요한 20 비트를 초과하면 트라이를 재설정하고 새 비트를 작성하기 시작합니다.

우리가 비트 팩해야하는 첫 번째 숫자 집합은 0-255 이고 256-511이 될 것이므로 일부는 8 비트와 9 비트 등으로 압축된다는 것을 알고 있습니다. 어떤 지침이 시작하고 무엇을 크게 할 것입니다 도움이 될 수 있습니다 그 동안 볼 수있는 위치에 제공 할 수 있다면

는

Answer 1

LZW 압축은 일반적으로 심볼의 크기 위를 계산 조금로 시작 감사합니다. 따라서 심볼이 8 비트 값인 경우 초기 비트 크기는 일반적으로 9입니다.이 값은 리터럴 값 0..255와 사전의 처음 256 코드에 충분합니다. 일반적으로 LZW에는 "Clear"코드와 "Stop"코드와 같은 특수 사전 정의 된 코드가 있으며 기호는 0x100 및 0x101 기호로 추가됩니다. 그것들은 꼭 필요한 것은 아니지만 아주 유용합니다.

또한 사전 성장을 제한 할 수있는 최대 비트 수가 있습니다. 귀하의 경우 20이므로 사전에 1048576 개의 항목을 저장할 수 있습니다. 가변 길이 비트 코드를 작성하려면 최대 비트 수를 보유 할만큼 충분히 넓은 레지스터를 사용하십시오. 귀하의 경우, 32 비트 또는 64 비트 부호없는 정수가 적합합니다. (64 비트 프로세서를 목표로한다면 후자를 사용하십시오.) 기본적으로 비트 시프트 카운터는 초기에 0으로 설정하고 비트가 오버 플로우 될 때까지 레지스터로 시프트/쓰기합니다. 그런 다음 전체 레지스터를 스트림에 쓰고 남은 비트를 이동/복사합니다. 마지막으로 레지스터의 최신 비트를 스트림에 플러시해야합니다 (있는 경우).

정말 쉽습니다. LZW 리더 및 라이터는 비트 수를 늘리는시기에 대해 합의했기 때문에 특별한 비트 수 처리가 필요하지 않습니다. 예를 들어 TIFF 6.0과 같은 일부 LZW 구현은 이전 크기 (소위 "초기 변경")에 맞는 마지막 코드를 작성하기 전에 카운트를 증가시킵니다. 기타 (예 : GIF) AFTERWARDS가 증가하므로 더 효율적입니다. 당신이 쓰는 기호의 비트 순서를 자유롭게 선택할 수 있습니다. 인코더와 디코더가 이에 동의한다는 것입니다. 다시 한번, 기존 LZW 구현은 다른 비트 순서를 사용합니다. GIF는 최소 중요도에서 가장 중요한 TIFF 6.0을 다른 방식으로 씁니다. LSB에서 MSB 로의 변형은 일반적으로 구현하기가 더 쉽습니다.

사전이 가득 차게되면 사전을 삭제해야한다는 일반적인 오해가 있습니다. 사실, 필자는 채워진 디렉토리를 계속해서 끝까지 최대 너비 코드를 방출하면 대부분의 경우 LZW 압축이 훨씬 더 나은 것으로 나타났습니다. 이것은 사전이 이제 입력 스트림의 통계 분포를 반영하고 효율적인 코드를 방출하기 때문입니다. 분명한 것은 시간이 지남에 따라 배포가 크게 변경 될 때만 필요하므로 사전이 부적합하게됩니다.

GIF 및 TIFF 용 일반 LZW 디코더는 빈칸이 채워지는 즉시 빈칸을 기다리지 않고 자주 자동으로 지 웁니다. 이는 "나쁜 습관"이며 심지어 가장 최근의 GIF 사양과 함께 제공되는 메모에서 명시 적으로 사용이 중단되지만, 아쉽게도 모든 독자와 호환되도록하려는 경우 엔코더가 명확한 코드로 도박을해서는 안됩니다.