복구 손상된 gz 또는 tar.gz 압축 파일 의 원리 편

머리말: UNIX/LINUX 다음 대부분 다 gzip 형식 해 파일 압축 방안, 때문에 gzip 파일 손상 상황도 드물지 않다, 흔히 볼 수 있는 어떤 만난 불량 섹터, 압축 프로세스 io 체증 또는 복구 후에 압축 파일 파괴될 등. 때문에 최근 관한 연구 gzip 파일 복구 하고, 특히 나눌 세 장 이에 대한 설명이 성과, 각각 원리 편을 방법 편, 사례 편. 이 위해 첫 부분 원리 편.

gzip압축 알고리즘 실제로 deflate (zip 도 거의 다 써서) 이 알고리즘 사실 by LZ77 알고리즘 더하기 하나 변형했어 哈夫曼 코드 구성. 아마 알고리즘 흐름: "원본 데이터 ---> LZ77---> 哈夫曼" 이 세 가지 절차. 무엇 때문에 수도 夫曼 나무 여전히 진행 압축, 그래서 실질적 및 절차: "원본 데이터 ---> LZ77---> (哈夫曼 나무 -> CL 압축) "

먼저 좀 "원본 데이터 ---> LZ77" 이 한 층 사상.관련 문서 봐 LZ77 상세한 알고리즘, 본문 하지 토톨로지 겨우 설명 관련된 본문 테마 일부 사상.본질적으로 보고 LZ77 기반 연속 반복 바이트 세션을 대한 지향 방식으로 유지될 압축 밝혔다.예: 한마디 영어 이름이 있다business is business, 为了简化这个句子(注意有空格), 我们用business is (12,8)来表示, 意思是括号内的数字并非原始数据, 而是代表从当前位置向前12个字节, 并且连续了8个字节的那段文字. 这样一来, 文字部分就变得简短了. 当然, 我们一定会注意到, 对于每个句子, 要额外有信息表示到底是原始数据, 还是指针类的数据. 그래서, 整个压缩后的数据, 由三类不同的信息元素组成: 本来就是这样的文字, 指向的位置, 指向的长度, 这三个元素即是lz77算法中的literal, distance和length.

주어진 어떤 한동안 바이트 흐른다, 만약 사용 LZ77 알고리즘 대해 압축, 꼭 받을 단 by literal · 행성distance 및 length 구성된 바이트 흐른다, 그럼 어떻게 구분 이 세 가지 요소? 행성distance 및 length 자꾸 나타나는 쌍쌍이 날다., 所以, 사실 어떻게 구분 이 2 클래스: 1, 2, literal 행성distance 및 length. 적절한 방법을 통해 이 지역 떨어져 2 클래스 멤버, 완수했다 LZ77 알고리즘 전체 방법.

LZ77 완료 후 을 형성 한동안 비교적 짧은 바이트 흐르다.그러나 이 모자라서 또 거쳐 인코딩 진행할 수 있다 哈夫曼 두 번 압축 하여금 더 이상을 위해 압축.

같은 이유로 哈夫曼 인코딩 원리에 대한 안 해. 너무 많이 설명 겨우 관련된 본문 테마 일부 원리에 대한 개요를 성 설명하다. 관한 哈夫曼 코드, 예를 들어 설명해: 만약 좀 바이트 흐름 (by 바이트 위해 최소 단위 구성) 이 바이트 흐름 속에서 모든 종류의 바이트 값 나타난 확률 것은 다르다. 그러나 모든 바이트 모두 사용할 8비트 감은사와 는 확률 각도 알 수 있다, 이 꼭 다시 할 수 있는 최적화 건. 哈夫曼 바로 대한 이 사상을 최 적화 를 간단하게 있으면 마치 생성 하나 일일이 대응 맵 사전 일부 짧은 분이 대신 자주 빈번하게 나타난 바이트 일부 긴 분이 대신 자주 나오는 바이트, 이렇게 전체적으로 대해 다시 한 번 압축. (본문 전재 때 좀 유보 전체 판권 정보: www.sjhf.net 北亚 데이터 복구 센터 장)

그럼 어떻게 구분 어느 자리에 시작한 것은 짧은 분 아직 긴 분이세요? 간단해 하면 약속: 짧은 분 쓰고, 그보다 긴 더 이상 이걸로 짧은 사람 앞에 할 수 있다. 예를 들면, 만약 영어 속 안 쓰려고 공백 간격 열다, 단어, 만 필요 이렇게 디자인: I 만약 내 뜻은 그게 다른 모든 단어 융합되지 으로 I 시작. AM 만약 표현 "는" 의 의미, 그 이미 없다 는 A 시작하는 단어 없고 으로 AM 시작하는 더 긴 단어를. 이로써 유추하다. 혹시 Iamchinese 돼 가 공백 있어도 주기 시작했다.

때문에 LZ77 압축 후 데이터 요소 중 literal · 행성distance 및 length 위해 유효 구분, deflate 알고리즘 줌 literal 및 length 아우르다 한 개의 哈夫曼 나무 사용. 나무 속에 인코딩 설명이 수치 만약 < 255 즉 표시 literal 가 본 것과 같다; 만약 / 압축 블록 끝; 만약 크다 256 / length (필요한 빼기 254 얻은); 만약 length, 다시 뒤를 조르르 행성distance 인코딩, 행성distance 사용 한 哈夫曼 나무, 실현 방법 만나 관련 문서.

literal, 행성distance 및 length 사용하는 哈夫曼 나무 자체도 역시 큰 부담 때문에 더욱 압축 공간 을 deflate 또 이 두 개의 哈夫曼 나무 대해 한 번 압축 마찬가지로, 주체 에서 도 채택 哈夫曼 알고리즘, 이렇게 바로 제 세 개의 哈夫曼 나무.

간단한 구조 下图 같다.:

63918611gw1ek74ec1r6gj20hj08kwfc.jpg[1]


그림 중에 구조 모른다 따라 한 gzip 구조 대체로 같다 下图 채 주시기 바랍니다:

1_thumb7


볼 수 있습니다, 모든 압축 가방 모두 독자적으로 존재하는 그 자체가 사용된 동적 哈夫曼 나무 등 도 겨우 존재, 그 범위 압축 가방 안에.그러므로, 찾으면 모든 압축 가방 시작 위치, 만약 이 가방 안 파괴될 곧 해 낸 그 대응 내용.

일반적으로 말하면 때문에 gzip 압축 작업 창 겨우 32K. 그래서 모든 가방의 크기가 모두 크지 않을 경우 일부 가방 찾으면 않습니다. 다음 가방 시작, 바로 정확한 푼 후속 데이터.

만약 gzip 압축 것은 여러 개의 파일을 (결코 tar 후에 다시 gzip) 은 이런 상황에 비교적 쉽다. gzip 대해 말하자면 파일 안에 포함 여 개 원본 파일, 안돼. 여러 개의 파일을 공용 한 압축 가방, 즉, 만약 한 파일 손상, 결코 영향을 다른 파일. 이런 사고는 쉽게 실현 수도 사용 linux 아래 gzip recover 완성해야 복구.

우리 주안점을 토론 만일 단일 파일 (예 TAR 가방) gzip 후 만약 그 중간 손상, 어떻게 정확한 푼 다음 데이터가 나온다.이 사고는 만약 이해, gzip recover 및 그냥 아주 쉽게 이해할 수 없고, 그 알고리즘 것 좀 약해.

상세한 것은 다음 문장.

글쓴이 준서 작성일 2014-12-25 01:30