1 의 전체 이름은 무엇입니까? LZW 요?
렌펠-지프-웰치 (LZW) 입니다.
2.LZW 의 도입 및 압축 원리는 무엇입니까?
LZW 압축 알고리즘은 라임푸르-지프 웰치가 창립하여 그들의 이름을 따서 지은 새로운 압축 방법이다. 고급 문자열 테이블 압축을 사용하여 각 첫 번째 문자열을 문자열 테이블에 배치하고 숫자를 사용하여 문자열을 나타냅니다. 압축된 파일은 숫자만 저장하고 문자열은 저장하지 않으므로 이미지 파일의 압축 효율성이 크게 향상됩니다. 신기하게도 이 문자열 테이블은 압축 또는 압축 해제 중에 올바르게 설정되고 압축 또는 압축 해제 후 폐기될 수 있습니다.
LZW 알고리즘에서 먼저 문자열 테이블을 설정하고, 각 첫 번째 문자열을 문자열 테이블에 배치하고, 문자열 테이블에서의 문자열 위치와 관련된 숫자로 표시하고, 압축 파일에 숫자를 저장합니다. 문자열이 다시 나타나면 해당 문자열을 나타내는 숫자로 바꿀 수 있으며 파일에 저장됩니다. 압축 후 문자열 테이블을 삭제합니다. 예를 들어, 압축할 때 "print" 문자열이 266 으로 표시되는 경우 다시 나타날 때마다 266 으로 표시되며 "print" 문자열은 문자열 테이블에 저장됩니다. 이미지 디코딩 중 숫자 266 이 발생하면 문자열 테이블에서 266 으로 표시된 문자열 "print" 를 찾을 수 있으며 압축 해제 시 압축 데이터에서 문자열 테이블을 재생성할 수 있습니다.
3. 알고리즘을 상세하게 소개하기 전에 알고리즘과 관련된 몇 가지 개념과 어휘를 나열하십시오.
1) "문자": 일반 텍스트 파일에서 1 개별 바이트를 차지하는 문자, 기본 데이터 요소이지만 이미지에서는 주어진 픽셀 색상을 나타내는 인덱스 값입니다.
2) "char stream": 데이터 파일의 문자 스트림.
3) 접두어: 접두어. 이 단어의 의미와 마찬가지로, 그것은 문자 앞에 가장 직접적인 문자를 나타낸다. 접두어 문자의 길이는 0 일 수 있으며 접두어와 문자는 문자열을 구성할 수 있습니다.
4) "접미어": 한 문자인 접미어입니다. 문자열은 (a, b) 로 구성될 수 있습니다. A 는 접두사이고 b 는 접미사입니다. A 의 길이가 0 이면 루트를 나타냅니다.
5)' 코드: 문자열의 위치 코드를 나타내는 코드.
6) "항목", 코드 및 해당 코드가 나타내는 문자열.
4. 압축 알고리즘의 간단한 예는 lzw 알고리즘을 완전히 구현하는 것이 아니라 가장 직관적인 관점에서 LZW 알고리즘의 사상을 바라보는 것입니다.
원시 데이터의 LZW 압축.
원시 데이터에서 4 자 (a, b, c, d) 만 2-2 자리 숫자 0-A, 1-B, 2-C, 3-D 로 표시할 수 있습니다
5.5. 적용 범위. LZW 알고리즘
문자열을 나타내는 값 (코드) 과 원래 단일 데이터 값 (문자열) 을 구분하려면 해당 숫자 필드가 일치하지 않도록 해야 합니다. A-D 를 나타내는 0-3 이므로 AB 를 3 보다 큰 숫자로 바꿔야 합니다. 또한 원래 숫자 범위는 8 비트로 표시할 수 있으므로 원래 숫자 범위는 0 ~ 255 로 간주되고 압축 프로그램에서 생성된 레이블 범위는 0 ~ 이 될 수 없습니다. 우리는 256 에서만 시작할 수 있지만, 이것은 8 비트 표현의 범위를 넘어설 것입니다. 따라서 최소한 한 자리 이상의 데이터 자릿수를 확장해야 합니다. 그러나 1 자가 차지하는 공간을 늘리지 않습니까? 그러나 한 문자는 여러 문자를 나타낼 수 있습니다. 예를 들어, 255 는 과거 8 자리였지만 지금은 256 을 사용하여 두 숫자, 즉 254 와 255 를 나타낼 가치가 있습니다. 이 원리에서 볼 수 있듯이 LZW 알고리즘은 원본 데이터 문자열에 여러 번 반복되는 하위 문자열이 많이 있어야 하며 반복 횟수가 많을수록 압축 효과가 좋아진다는 것을 알 수 있습니다. 반대로, 상황이 더 나빠질수록, 실제로는 감소하는 것이 아니라 증가할 수 있다.
6.6 호 특별 로고. LZW 알고리즘
새 문자열이 발견됨에 따라 레이블은 계속 증가할 것이다. 원본 데이터가 너무 크면 결과 레이블 테이블이 점점 커집니다. 이 시점에서 이 컬렉션을 조작하면 효율성 문제가 발생할 수 있습니다. 어떻게 이 문제를 피할 수 있습니까? Gif 는 lzw 알고리즘을 사용합니다. 태그 세트가 충분히 크면 증가하지 않으므로 처음부터 시작하기만 하면 됩니다. 이 위치에 태그를 삽입했습니다. 즉, 사전 구성을 다시 시작했습니다. 이전의 모든 태그는 유효하지 않고 새 태그를 사용하기 시작했습니다.
이때 또 다른 문제가 발생했다. 얼마나 큰가요? 이 태그 세트의 적당한 크기는 얼마입니까? 이론적으로 레이블 세트가 클수록 압축비는 높아지지만 비용도 높아진다. 일반적으로 처리 속도와 메모리 공간에 따라 선택됩니다. GIF 사양은 12 비트를 규정하고 표현식 범위가 12 비트를 초과하면 다시 만들어집니다. 압축률을 높이기 위해 GIF 는 가변 문자 길이를 사용합니다. 예를 들어, 원시 데이터는 8 비트이므로 처음에는 한 자리를 추가하고, 초기 글자 길이는 9 자리가 된 다음 레이블 추가를 시작합니다. 레이블이 5 12 에 추가되면, 즉 9 를 초과하는 것이 표현할 수 있는 최대 데이터인 경우, 다음 레이블은 10 비트로만 표현될 수 있으므로 여기서부터 다음 단어 길이는 10 입니다. 이런 식으로 2 12, 즉 4096 에 도달하면 여기에 명확한 기호가 삽입되고 뒤에서 시작하여 9 자리 숫자로 시작됩니다.
GIF 에서 지정한 지우기 플래그의 값은 원시 데이터 문자 길이의 최대값에 1 을 더한 값입니다. 원본 데이터 문자 길이가 8 이면 정리 플래그는 256 이고, 원본 데이터 문자 길이가 4 이면 16 입니다. 또한 GIF 는 지우기 플래그에 1 을 더한 값으로 끝 플래그 END 를 지정합니다. GIF 에 지정된 자릿수는 1 (단색 이미지), 4( 16 색상) 및 8(256 색상) 이기 때문에 1 비트인 경우/kloc 만 확장됩니다 다른 두 가지 경우 초기 글자 길이는 각각 5 자리와 9 자리입니다. /whycadi/
7.lzw 알고리즘은 원시 데이터의 예제 분석을 압축합니다.
입력 스트림, 즉 원시 데이터는 255, 24, 54, 255, 24, 255, 24, 5, 123, 45, 255, 24, 5, 입니다 .........................................................................
이는 gif 파일에 있는 픽셀 배열의 일부일 뿐입니다. 어떻게 압축합니까?
원시 데이터는 8 비트로 표시할 수 있으므로 지우기 플래그는 Clear=255+ 1 =256 이고 끝 플래그는 End=256+ 1=257 이고 현재 레이블 세트는 입니다
012 3 ..................................................................................................................................... 255 정리 종료
첫 번째 단계는 첫 번째 문자를 255 로 읽고 태그 테이블에서 찾는 것입니다. 255 는 이미 존재하고, 우리는 이미 255 를 알고 있기 때문에, 우리는 그것을 처리하지 않는다.
두 번째 단계에서는 접두사가 A 이고 현재 항목이 (255,24) 인 두 번째 문자를 취합니다. 이 항목은 레이블 세트에 존재하지 않습니다. 우리는 255,24 를 모른다. 이번에는, 당신의 소년이 올 때, 나는 당신을 기억하고, 태그 세트에 258 로 표시한 다음, 접두어 A 를 출력하고, 접미어 24 를 유지하고, 다음 접두사로 사용합니다 (접미사 변경 접두어).
세 번째 단계에서 세 번째 문자는 54, 현재 항목 (24,54), 레코드 (24,54) 는 숫자 259, 출력 24, 접미사는 접두사로 바뀐다.
네 번째 부분: 네 번째 문자 255, entry = (54,255), 나도 몰라, 레코드 (54,255) 는 참조 번호 260, 출력 54, 접미사를 접두사로 변경합니다.
다섯 번째 단계는 다섯 번째 문자 24, entry =(255, 24), 아, 나는 너를 안다. 이것은 오래된 258 이 아니기 때문에 문자열을 258 로 지정하고 접두사로 사용한다.
6 단계: 여섯 번째 문자 255, entry = (258,255), 나도 몰라, 레코드 (258,255) 는 26 1, 출력 258, 접미사를 접두사로 변경합니다.
.....
마지막 문자까지 처리합니다.
표로 이 과정을 기록하다.
선택 취소 =256, 종료 =257
첫 번째 단계 접두어 접미어 입력 알려진 (Y/N) 출력 레이블.
1 255 (,255)
N 255 258
24 54 (24,54) n 24 259
N 54 260
255 24(255, 24)Y
6 258 255(258 255)N 258 26 1
N 255 262
.....
위의 몇 가지 예는 완전히 반영되지 않는다. 또 다른 예는
원시 입력 데이터는 ABBA ABBA ABBA ABBA ABBA ABBA ABBA ABBA ABBA ABBA ABBA ABBA 입니다. .....
LZW 알고리즘을 사용하여 압축합니다. 압축 프로세스는 테이블로 표시됩니다.
원시 데이터에는 a, b, c, d, b, c, d 의 네 문자만 포함됩니다.
그것은 두 자리로 표현할 수 있다. Lzw 알고리즘에 따르면 먼저 한 명을 3 으로 확장하고, Clear 의 2 차 = 2+1= 4 로 확장합니다. End = 4+1= 5;
초기 레이블 세트는 다음과 같아야 합니다
0 1 2 3 4 5
또렷한 결말
압축 과정은 다음과 같습니다.
첫 번째 단계 접두어 접미어 입력 알려진 (Y/N) 출력 레이블.
1 A (,a)
2 A B(A, B)N a6
3 B A(B, A)N B 7
4a B(A, B)Y
56 A(6, A)N 6 8
6a B(A, B)Y
7 6a(6, A)Y
8 8 B(8, B)N 8 9
9 B B(B, B)N B 10
10 B B(B, B)Y
1110a (10, a) n10/kloc-
12 A B(A, B)Y
.....
12 단계로 이동할 때 레이블 세트는 다음과 같아야 합니다
012 3 4 5 6 7 8 91011
6A 8B BB 10A
8.8 의 의사 코드 구현 LZW 알고리즘
1STRING = 입력 문자 가져오기
2 여전히 입력 문자가 있을 때
3 자 = 입력 문자 가져오기
4 문자열+문자가 문자열 테이블에 있는 경우
5 문자열 = 문자열+문자
6 기타
7 문자열 코드 출력
8 문자열 테이블에 문자열+문자를 추가합니다
9 문자열 = 문자
10 IF 끝
1 1 WHILE 종료
12 문자열을 출력하는 코드
13