Move-to-Front transform

앞으로 쓰일 글의 내용은 http://en.wikipedia.org/wiki/Move-to-front_transform (이하 '위의링크' 라 함)에서 참고 하였습니다.

저작권을 침해 할 경우 댓글 또는 메일로 알려주시기 바랍니다.

안녕하세요 Geeks_Company입니다.

오늘 소개 시켜 드릴 알고리즘은 Move to front algorithm (이하 'MTF' 라 함)으로 파일 압축을 시킬때 사용되는 알고리즘 입니다.

Bzip2의 경우 Huffman-Coding 과 Move-to-front 를 사용하여 압축을 합니다.(http://en.wikipedia.org/wiki/Bzip2 참조)

MTF는 다른 알고리즘에 비해 구현이 간단합니다.

위의 링크에서 사용된 예제를 사용하여 설명 하겠습니다.

bananaaa 를 사용 하여 설명하겠습니다.

1. list(0-25)을 만든후 , 0 은 a, 1 은 b.... z 은 25 란 index가 할당 됩니다.
2. bananaaa의 b를 list에서 참조 하여 값을 리턴 합니다. ( a의 index는 0, b의 index 1 이므로, 1을 리턴 합니다.)
3. 1을 리턴 한후, list의 처음 구성 원소를 a가 아닌 b로 대체 한후, 이후 b 는 0 이 되고, a는 1이 됩니다.
4. 리턴된 값을 저장 한후 다시 다음 구성원소(a)를  과정 2-4까지 반복합니다.
5. 마지막 구성원소까지 처리 할경우 List는 anbcdefghijklmopqrstuvwxyz 이고  리턴 값은 1,1,13,1,1,1,0,0 이 됩니다.

간략한 순서를 표로 나타내면 이러 합니다.( 자세한 부분은 이곳 를 참조 하세요)

Iteration	Sequence	List
bananaaa	1	(abcdefghijklmnopqrstuvwxyz)
bananaaa	1,1	(bacdefghijklmnopqrstuvwxyz)
bananaaa	1,1,13	(abcdefghijklmnopqrstuvwxyz)
bananaaa	1,1,13,1	(nabcdefghijklmopqrstuvwxyz)
bananaaa	1,1,13,1,1	(anbcdefghijklmopqrstuvwxyz)
bananaaa	1,1,13,1,1,1	(nabcdefghijklmopqrstuvwxyz)
bananaaa	1,1,13,1,1,1,0	(anbcdefghijklmopqrstuvwxyz)
bananaaa	1,1,13,1,1,1,0,0	(anbcdefghijklmopqrstuvwxyz)
Final	1,1,13,1,1,1,0,0	(anbcdefghijklmopqrstuvwxyz)

결과값에서 확인 할 수 있듯이, Sequence의 구성 원소중 하나(13)을 제외 하고는 1 과 0 으로 이뤄지게 됩니다.


위의 결과 값을 사용 하여 압축을 할경우 빈도수가 높은 구성원소가 서로 연이어 모이게 되므로, 

연속된 동일한 케릭터를 압축 시킬 확률이 더 커지게 됩니다.


이것으로 MTF의 알고리즘의 설명을 마치겠습니다.