lzw 압축 예제

LZW 압축은 컴퓨터에서 처음으로 널리 사용되는 범용 데이터 압축 방법이되었습니다. 큰 영어 텍스트 파일은 일반적으로 LZW를 통해 원래 크기의 절반 정도로 압축할 수 있습니다. 손실 압축 방법은 DCT (신중한 Cosine 변환), 벡터 양자화 및 허프만 코딩을 포함하고 무손실 압축 방법은 RLE (실행 길이 인코딩), 문자열 테이블 압축, LZW (렘펠 Ziff Welch) 및 zlib를 포함한다. 거기에 여러 압축 알고리즘이 존재하지만, 우리는 LZW에 집중하고있다. 도 27-7은 LZW 압축을 위한 순서도를 나타낸다. 표 27-3은 45바이트, ASCII 텍스트 문자열로 구성된 예제 입력 파일에 대한 단계별 세부 정보를 제공합니다. LZW 알고리즘이 입력 파일에서 문자 “a”를 읽는다고 말할 때, 우리는 값을 읽는다는 것을 의미합니다 : 01100001 (97은 8 비트로 표현됨), 97은 ASCII에서 “a”입니다. 인코딩 된 파일에 문자 “a”를 쓴다고 말할 때 000001100001 (97은 12 비트로 표현)을 쓴다는 것을 의미합니다. 알고리즘이 실패하는 예외가 있으며, 코드가 아직 입력되지 않은 인덱스를 호출하는 경우(예: 인덱스 31이 현재 처리 중이므로 사전에 없는 인덱스 31을 호출). Sayood의 예는 이 점을 설명하는 데 도움이 됩니다. 당신이 문자열 아바밥을 했다고 가정해 봅시다…..

인덱스 0과 1이 있는 a & b의 초기 사전과 각각. 인코딩 프로세스가 시작됩니다: 컴퓨터의 거의 모든 데이터 파일을 문자별로 살펴보면 반복되는 패턴이 많다는 것을 알 수 있습니다. LZW는 이러한 반복을 활용하는 데이터 압축 방법입니다. 이 메서드의 원래 버전은 렘펠과 Ziv에 의해 1978 년 (LZ78)에 의해 만들어졌으며 1984 년 웰치에 의해 더욱 개선되었기 때문에 LZW 약어가 되었습니다. 모든 적응/동적 압축 방법과 마찬가지로(1) 초기 모델로 시작하고, (2) 데이터 조각을 조각으로 읽고, (3) 모델을 업데이트하고 데이터를 인코딩하는 것이 좋습니다. LZW는 “사전”기반 압축 알고리즘입니다. 즉, 문자 수를 표로 만들고 트리를 작성하는 대신(허프만 인코딩의 경우) LZW는 사전을 참조하여 데이터를 인코딩합니다. 따라서 하위 문자열을 인코딩하려면 사전의 해당 하위 문자열 인덱스에 해당하는 단일 코드 번호만 출력 파일에 기록해야 합니다. LZW는 텍스트 파일 압축의 맥락에서 종종 설명되지만 모든 유형의 파일에 사용할 수 있습니다.

그러나 일반적으로 텍스트 파일과 같은 반복된 하위 문자열이 있는 파일에서 가장 잘 수행됩니다. 이해 연습: 첫 번째 예제에 대 한 인코딩 된 데이터를 디코딩 하 고 “banana_bandana”를 다시 얻을 수 있는지 확인 합니다. 동일한 초기 사전으로 시작해야 합니다(예: 각 문자는 이전과 동일한 인덱스 슬롯에 있음). 자신을 돕기 위해, 위와 같은 디코딩 테이블을 합니다. 여기에 다른 (우아한) 코드를 확인 하스켈 위키 장난감 압축 불행하게도, 인코딩 알고리즘의 일부 초기 구현은 코드 폭을 증가한 다음 이전 너비 대신 새로운 폭에서 ω을 방출, 그래서 디코더에 보인다 너비가 너무 일찍 하나의 코드를 변경처럼. 이를 “초기 변경”이라고 합니다. Adobe가 이제 PDF 파일에서 두 버전을 모두 허용하지만 각 LZW 압축 스트림의 헤더에 명시적 플래그를 포함하여 초기 변경이 사용되고 있는지 여부를 나타내는 많은 혼란을 야기했습니다. LZW 압축을 사용할 수 있는 그래픽 파일 형식에서 TIFF는 초기 변경을 사용하지만 GIF와 대부분의 다른 형식은 변경하지 않습니다. 압축 알고리즘의 실행 시간은 일치하는 일치가 있는지 확인하기 위해 코드 테이블을 검색하여 제한됩니다. 비유로, 친구의 이름이 전화 번호부에 나열되어 있는지 알아보고 싶다고 상상해 보십시오.