In Managing Gigabytes 과목 : 정보검색론 강의 : 부산대학교 권혁철 Text Compression In Managing Gigabytes 과목 : 정보검색론 강의 : 부산대학교 권혁철

Contents Compression Models and Coding Adaptive Model Huffman Coding Arithmetic Coding

Preview 일반적 추세 : 컴퓨터 저장 장치의 용량과 데이터 전송량은 계속해서 늘어나고 있고, 사람들은 더 많은 데이터를 컴퓨터 저장 장치에 넣고 싶어한다. 그래서, 컴퓨터 리소스의 향상에도 불구하고 압축 기법에 더 많은 관심을 보이고 있다. Text compression : 일반 데이터 압축과 구분된다. 텍스트 압축의 가장 큰 특징은 반드시 정확히 복원되어야 한다는 것이다. 이미지 데이터나 사운드 데이터는 어느 정도의 정보의 손실을 허용한다 압축 기법의 발전 50년대 초반 : Huffman coding (5bits/character) 70년대말: Adaptive model Ziv-Lempel compression(4bits/character) arithmetic coding 80년대 초반 : Prediction by Partial Matching(PPM)

Model과 Coding Model : 압축될 기본단위의 확률을 측정하는 방법. 높은 압축율을 위해서는 Modeling을 잘 해야 한다. <Example> static model semi-static model adaptive model Coding : 확률을 이용하여 실제로 압축을 행하는 것 Huffman coding Arithmetic coding

Compression Models 여러 가지 압축기법들은 압축될 데이터에 대해 좋은 모델이 형성되어야 높은 압축율을 보인다. 기본적으로 모델의 기능은 심볼을 예측하는 것이다. 심볼의 예측 → 확률 → sample text에서의 상대빈도( relative frequency ) Model encoder decoder text Compressed text

확률 분포의 entropy 확률 분포의 entropy(H) : 심볼들의 평균 정보량(비트수) H = ∑ Pr[s]·I(s) = ∑ -Pr[s]·log Pr[s] I(s) : s를 encode한 비트 수 Pr[s] : s가 발생할 확률 I(s) = -logPr[s] 낮은 확률 → 높은 entropy 높은 확률 → 낮은 entropy

Compression Model의 구분 - static model : 각 심볼에 대한 확률은 미리 결정되어 있다. - semi-static model : Compress될 파일 각각에 대해 새로운 확률 분포를 만든다. - adaptive model : 심볼 하나 하나를 압축할 때마다 확률 분포 가 달라진다. - finite-context model : 제한된 몇 개의 이전 심볼에 대해 다 음 심볼 예측 - finite-state model : 각 state에 따라 다음 심볼에 대한 예측 값이 다르다. - Symbolwise model : 심볼의 확률을 측정하고 이를 기준으 로 코드화 한다. 확률의 측정을 얼마나 정확하게 하느냐가 성 능을 좌우한다. - Dictionary model : 단어를 사전의 인덱스로 교체한다.

Adaptive Model static modeling : 텍스트의 내용에 관계없이 항상 같은 모델을 사용하는 방법. 다른 형태의 텍스트가 들어오면 효율 저하. semi-static modeling : Compress될 파일 각각에 대해 새로운 model을 만든다. adaptive modeling : 성격이 다른 텍스트 압축에 대한 문제 해결 - 평이한 확률 분포, 새로운 심볼을 만날 때마다 확률 분포가 점 차적으로 바뀐다. - 확률을 구하기 위해 이미 encode된 부분을 이용한다.

Adaptive Model(Cont.) zero-order model(character level model) 볼로서 작용한다. zero-frequency problem : 확률 0는 피해야 한다. - extra count를 둔다. - 빈도를 강제로 1씩 올려 준다. higher-order model : 현재 문맥에서 빈도를 찾음 - first-order model : 마지막 하나의 문자를 참고하여 확률 계산 - second-order model : 마지막 두 개의 문자를 참고하여 확률 계산

Coding Coding 목적 Huffman coding : full-text Retrieval에 유용 압축모델에 의해 제공되는 확률분포에 기반하여 심볼을 Code화하는 작업 목적 심볼에 대해 짧은 codeword를 생성 짧은 시간 내에 encode, decode Huffman coding : full-text Retrieval에 유용 random access가 가능 속도가 빠르다. Canonical Huffman Coding 많은 단어들을 포함한다. codeword의 길이를 포함한다. codeword의 길이 순으로 저장한다. decode tree가 없다. Arithmetic coding 높은 압축율 어떤 모델에서도 사용이 가능하다.

Huffman Coding 1.0 0.4 0.6 0.2 0.1 0.05 0.3 1 a b c d e f g

Arithmetic Coding Arithmetic coding의 원리 Prefix 제거 각 symbol은 각자 확률을 가지고 있다. Symbol stream을 하나의 실수로 압축한다. Prefix 제거 Coding된 실수가 너무 길어지는 것을 방지. 빠른 전송 속도. Prefix 제거의 예 low = 0.6546789 low = 0.789 high = 0.6546985 high = 0.985

Huffman Coding과 Arithmetic Coding의 비교