사전 코드
Dictionary coder |
치환 코더라고도 불리는 사전 코더는 압축되는 텍스트와 인코더에 의해 유지되는 데이터 구조('사전'이라고 불린다)에 포함되는 문자열 세트 사이의 일치를 검색함으로써 동작하는 무손실 데이터 압축 알고리즘의 클래스입니다.인코더는 이러한 일치를 발견하면 데이터 구조에서 문자열 위치에 대한 참조를 대체합니다.
방법 및 응용 프로그램
일부 사전 코더는 부호화가 시작되기 전에 문자열의 전체 세트가 결정되며 부호화 과정 동안 변경되지 않는 정적 사전'을 사용합니다.이 접근법은 부호화할 메시지 또는 메시지 세트가 고정적이고 큰 경우에 가장 많이 사용됩니다. 예를 들어, PDA의 제한된 저장 공간에 책의 내용을 저장하는 애플리케이션은 일반적으로 텍스트의 일치로부터 정적 사전을 구축한 다음 그 사전을 사용하여 구절을 압축합니다.인덱스를 일치로 표현하기 위해 Huffman 부호화를 사용하는 이 방식을 "Huffword"[1]라고 부릅니다.
관련된 보다 일반적인 방법에서 사전은 데이터 환경(다양한 입력 스트림)에서 추출된 용장성으로부터 구축되며, 사전은 정적으로 사용되어 추가 입력 스트림을 압축한다.예를 들어, 사전은 오래된 영어 원문으로 만들어진 다음 책을 [2]압축하는 데 사용된다.
보다 일반적인 방법은 사전이 미리 정해진 상태에서 시작되지만 이미 인코딩된 데이터에 따라 인코딩 프로세스 중에 내용이 변경되는 방법입니다.LZ77 알고리즘과 LZ78 알고리즘은 모두 이 원리로 동작합니다.LZ77에서는 "슬라이딩 윈도우"라고 불리는 순환 버퍼는 처리된 데이터의 마지막 N바이트를 유지합니다.이 창은 사전으로 기능하며 과거 N바이트에 나타난 모든 하위 문자열을 사전 엔트리로 효과적으로 저장합니다.사전 엔트리를 식별하는 단일 인덱스 대신 일치하는 텍스트의 길이를 나타내는 길이와 현재 텍스트보다 앞의 슬라이딩 윈도우 시작 오프셋바이트에서 일치가 발견되었음을 나타내는 오프셋(거리라고도 함)의 두 가지 값이 필요합니다.
LZ78은 보다 명시적인 사전 구조를 사용합니다.인코딩 프로세스의 선두에는 사전이 비어 있습니다.인덱스 값 0은 문자열의 끝을 나타내기 위해 사용되므로 사전의 첫 번째 인덱스는 1입니다.부호화 프로세스의 각 단계에서 일치하지 않는 경우 마지막 일치 인덱스(또는 제로)와 문자가 모두 사전에 추가되어 압축 스트림에 출력됩니다.일치하는 경우 작업 인덱스는 일치하는 인덱스로 업데이트되고 아무것도 출력되지 않습니다.
LZW는 LZ78과 비슷하지만 사전은 가능한 모든 기호로 초기화됩니다.일반적인 구현은 8비트 기호로 작동하므로 16진수 00 ~ 16진수 FF(10진수 255)의 사전 "코드"가 미리 정의되어 있습니다.사전 엔트리는 코드 값 16진수 100부터 추가됩니다.LZ78과 달리 일치가 발견되지 않으면(또는 데이터의 끝인 경우), 사전 코드만 출력됩니다.이로 인해 디코더 출력이 사전보다 한 단계 늦기 때문에 잠재적인 문제가 발생합니다.이 처리 방법에 대해서는, 「LZW」를 참조해 주세요.LZW의 기능 향상에는 8비트 이외의 심볼 사이즈를 취급하고 사전을 리셋하고 데이터의 끝을 나타내기 위해 예약된 코드를 갖는 것이 포함됩니다.
레퍼런스
- ^ Ian H. Witten, Alistair Moffat, Timothy C.벨, 기가바이트를 관리하고 있어뉴욕: Van Nostrand Reinhold, 1994. ISBN9780442018634.
- ^ 로드니 J. 스미스동적 연결 그룹을 사용한 스트리밍 압축 시스템, 미국 특허 5,748,955, 우선일 1993년 12월 20일.
