LZ 77 압축 알고리즘 원리 에 대한 이해

LZ 77 압축 알고리즘 원리 에 대한 이해
데이터 압축 은 데이터 저장 공간 을 줄 이 는 과정 으로 현재 소프트웨어 공학 의 각 지역 에 응용 되 고 그 원 리 를 이해 하여 우리 가 압축 방안 을 더욱 잘 선별 하 는 데 편리 하 다.
압축 방안 은 여러 가지 가 있 는데 흔히 볼 수 있 는 것 은 손실 과 무 손실 압축 이다.호 프 만 인 코딩 과 LZ 77(Lempel-Ziv-177)은 모두 무 손실 압축 이다.그 중에서 호 프 만 은 최소 중복 인 코딩 알고리즘 으로 압축 하고 LZ 77 은 사전 방식 으로 압축 한다.호 프 만 인 코딩 알고리즘 에 대해 인터넷 에서 상세 한 설명 이 많 습 니 다.우 리 는 이 지면 에서 자세히 말 하지 않 고 주로 LZ 77 압축 알고리즘 방식 을 도해 해서 어떤 장단 점 이 있 는 지 보 겠 습 니 다.
 정보 엔트로피
데 이 터 는 왜 압축 할 수 있 습 니까?데 이 터 는 일정한 특성 을 나타 내 고 엔트로피 라 고 부 르 기 때 문 입 니 다.절대 다수의 데이터 가 나타 내 는 용량 은 엔트로피 가 건의 하 는 최 적 용량 보다 크다.예 를 들 어 모든 데 이 터 는 일정한 지루 성 을 가진다.우 리 는 불필요 한 데 이 터 를 더 적은 비트 로 자주 나타 나 는 문 자 를 표시 할 수 있 고 데이터 의 일부 특성 을 바탕 으로 사전 인 코딩 을 바탕 으로 불필요 한 단 어 를 반복 하 는 것 을 대체 할 수 있다.
  LZ 77 알고리즘 원리
LZ 77 압축 알고리즘 은 사전 방식 으로 압축 하여 간단 하지만 매우 효율 적 인 데이터 압축 알고리즘 이다.그 방식 은 데이터 에서 구문(최 장 문자)으로 구성 할 수 있 는 문 자 를 사전 에 추가 한 다음 에 같은 문자 가 나타 나 면 사전 에 있 는 단 어 를 대체 하여 표 시 를 통 해 반복 되 는 방식 으로 압축 하 는 것 이다.이러한 알고리즘 을 이해 하려 면 먼저 세 가지 키 워드 를 알 아 보 겠 습 니 다.구문 사전,미끄럼 창 과 앞으로 버퍼.
키워드:
1.전방 향 버퍼
데 이 터 를 읽 을 때마다 일부 데 이 터 를 전방 향 버퍼 에 미리 불 러 옵 니 다.미끄럼 창 으로 이동 하기 위 한 준비
2.슬라이딩 창
데이터 가 버퍼 를 통과 하면 미끄럼 창 으로 이동 하여 사전 의 일부분 이 됩 니 다.
3.단어 사전
문자 시퀀스 S1...Sn 에서 n 개의 구 를 구성 합 니 다.예 를 들 어 문자(A,B,D),조합 할 수 있 는 단 어 는{(A),(A,B),(A,B,D),(B),(B,D),(D)}이다.이 문자 들 이 미끄럼 창 에 있 으 면 현재 의 구문 사전 으로 기록 할 수 있다.미끄럼 창 이 계속 앞으로 미 끄 러 지기 때문에 구문 사전 도 끊임없이 변화 한다.
LZ 77 의 주요 알고리즘 논 리 는 먼저 전방 향 버퍼 를 통 해 데 이 터 를 미리 읽 은 다음 슬라이딩 창 으로 이동(슬라이딩 창 은 일정한 길이 가 있 음)하고 사전에 있 는 단어 와 일치 할 수 있 는 최 장 구 를 끊임없이 찾 은 다음 태그 부 호 를 통 해 표시 하 는 것 이다.우 리 는 또한 문자 ABD 를 예 로 들 어 다음 과 같은 그림 을 봅 니 다.

현재 이전 버퍼 에서 미끄럼 창 과 일치 할 수 있 는 가장 긴 단 어 는(A,B)이 고 앞으로 이동 할 때 다시(A,B)를 만 났 을 때 태그 로 대체 합 니 다.
압축 하 다.
데 이 터 를 압축 할 때 전방 향 버퍼 와 이동 창 사이 에 구 를 만 들 면 다음 과 같은 두 가지 상황 이 발생 합 니 다.

일치 하 는 기 호 를 찾 을 수 없 을 때:일치 하지 않 는 기 호 를 기호 로 인 코딩 합 니 다(대부분 문자 자체)

4.567917.일치 하 는 것 을 찾 았 을 때:가장 긴 일치 하 는 인 코딩 을 구문 으로 표시 합 니 다

구문 표 시 는 세 가지 정 보 를 포함 합 니 다.(미끄럼 창의 오프셋(일치 하 는 곳 에서 계산),일치 하 는 기호 갯 수,일치 하 는 끝 난 전방 향 버퍼 의 첫 번 째 기호)

 n 개의 기 호 를 인 코딩 하고 응답 하 는 표 시 를 만 들 면 이 n 개의 기 호 를 미끄럼 창의 한 끝 에서 옮 기 고 버퍼 에 있 는 똑 같은 수량의 기호 로 대체 합 니 다.그러면 미끄럼 창 에는 항상 최신 구문 이 있 습 니 다.
우 리 는 도 례 를 채택 하여 본다.
 1.시작

2.슬라이딩 창 에 데이터 가 없 기 때문에 구문 과 일치 하지 않 습 니 다.문자 A 를 A 로 표시 합 니 다.

3.슬라이딩 창 에 A 가 있 고 버퍼 에 있 는 문자(BABC)에서 구문 과 일치 하지 않 으 며 B 를 B 로 표시 합 니 다.

4.버퍼 문자(ABCB)는 슬라이딩 창의 위치 이동 6 위치 에서 AB 를 찾 아 구문 AB 에 성공 하고 AB 를(6,2,C)로 인 코딩 합 니 다.

5.버퍼 문자(BABA)는 슬라이딩 창 에서 4 번 위 치 를 구문 BAB 와 일치 시 키 고 BAB 를(4,3,A)로 인 코딩 합 니 다.

6.버퍼 문자(BCAD)는 슬라이딩 창 에서 2 로 이동 하 는 위치 에서 구문 BC 와 일치 하고 BC 인 코딩 을(2,2,A)

7.버퍼 문자 D,슬라이딩 창 에서 일치 하 는 단 어 를 찾 지 못 했 습 니 다.D 로 표 시 됩 니 다.

8.버퍼 에 데이터 가 들 어 오지 않 았 습 니 다.끝

 스트레스 를 풀다
압축 해제 와 유사 한 역방향 과정 은 디 코딩 태그 와 미끄럼 창 에 있 는 기 호 를 통 해 압축 해제 데 이 터 를 업데이트 합 니 다.
디 코딩 문자 표시:표 시 를 문자 로 인 코딩 하여 미끄럼 창 에 복사 합 니 다.
디 코딩 구문 태그:미끄럼 창 에서 응답 오프셋 을 찾 고 지정 한 장단 점 을 찾 아 교체 합 니 다.
우 리 는 그래도 도 례 를 채택 하여 보 자.
1.시작

2.기호 표시 A 디 코딩

3.기호 표시 B 디 코딩

4.구문 태그(6,2,C)디 코딩

5.구문 태그(4,3,A)디 코딩

6.구문 태그(2,2,A)디 코딩

7.기호 표시 D 디 코딩

 장단 점
대부분의 경우 LZ 77 압축 알고리즘 의 압축 비율 이 상당히 높 습 니 다.물론 미끄럼 창 크기 와 전방 향 버퍼 크기,그리고 데이터 엔트로피 와 관계 가 있 습 니 다.압축 과정 은 시간 이 많이 걸 립 니 다.미끄럼 창 에 있 는 구문 과 일치 하 는 것 을 찾 는 데 많은 시간 이 걸 리 지만 압축 을 푸 는 과정 은 매우 빠 릅 니 다.모든 태그 가 어느 위치 에서 읽 을 수 있 는 지 명확 하 게 알려 주기 때 문 입 니 다.
이상 은 LZ 77 압축 알고리즘 원리 에 대한 이해 입 니 다.궁금 한 점 이 있 으 시 면 메 시 지 를 남기 거나 본 사이트 의 커 뮤 니 티 에 가서 토론 을 하 십시오.읽 어 주 셔 서 감사합니다. 도움 이 되 셨 으 면 좋 겠 습 니 다.본 사이트 에 대한 지지 에 감 사 드 립 니 다!