LZ77

안녕하세요 Geeks_Company 입니다.

오늘 소개 시켜 드릴 알고리즘은 압축시 사용되는 알고리즘중 일부분인 LZ77 입니다.

이 글에서 사용되는 모든 자료는 http://en.wikipedia.org/wiki/LZ77_and_LZ78 에서 참조 하여 인용 하였습니다.

만약 저작권을 침해 하는 내용이 있으면, 저에게 메일 또는 댓글로 알려 주셨음 합니다.



LZ77 이란??

..LZ77 algorithms achieve compression by replacing portions of the data with references to matching data that have already passed through both encoder and decoder. A match is encoded by a pair of numbers called a length-distance pair, which is equivalent to the statement "each of the next length characters is equal to the character exactly distance characters behind it in the uncompressed stream." (The "distance" is sometimes called the "offset" instead.)

LZ77 알고리즘은 인코더와 디코더를 지난 동일한 데이터를 가르키는 레퍼런스를 교체 함으로써 압축을 시킵니다.
매치된 데이터는 길이-거리 쌍으로 인코딩이 되며, "각각의 다음 length 캐릭터는 정확히 distance 캐릭터만큼 압축이 풀린 데이터의 뒤에 있는것과 동일 하다" 와 같은 statement 입니다. (거리는 가끔 offset이라고도 불립니다.")



간단한 예시가 많은 정의를 한번에 설명할꺼 같습니다.


aaaaaaaaaaaaaaaaarrrrrrrrrrrrrgggggggggggh

위의 반복적인 스트링을 LZ77을 적용 시킬경우

이렇게 교체 될수 있습니다.

(0,0,a)(1,16,r)(1,12,g)(1,10,h)(종료)

순서를 적자면,

0. 처음 dictionary= empty
1. a 가 삽입됩니다.  (0,0,a)
2. 그후 dictionary에서 1 distance만큼 뒤로 간후 16번을 반복 한후 r을 삽입 합니다. (현재 dictionary에는 a a a a a a a a a a a a a a a a a r 이렇게 있습니다.)
3. 다시 dictionary로 가서 1 distance만큼 뒤로 간후, 12번을 반복 한후 g를 삽입합니다.
4. 다시 dictionary로 가서 1 distance만큼 뒤로 간후, 10번을 반복 한후 h를 삽입합니다.
5. 종료를 합니다.