압축 알고리즘에서 가장 인기있는 알고리즘이라고 한다.
Mpeg 의 기본 압축 알고리즘으로도 쓰이고 알집 역시 허프만 알고리즘으로 한번 압축 후 Lempel 이라는 간단한 압축 알고리즘으로 한번 더 압축한다나 뭐라나~ 어쨋든 허프만 알고리즘.... 좋다.
이론적으론 쉽던데.....(옛날에 울형이 압축 프로그램 만들때 살짝 들었던거네)
자주 쓰는 문자에 가장 작은 bit를 할당하고 한두번 쓰이는 문자에는 큰 bit 를 할당~
간단하게 AAABBBCC 이렇게 있다면
영문자 하나의 byte 는 1byte 니까 총 7byte 가 되겠다.
사용된 문자의 횟수론
A 3번, B 3번, C 2번 이다.
이 문자열들에게 A에겐 0을 B에겐 10을 C에겐 11이라는 숫자를 부여해면
A(0)A(0)A(0)B(10)B(10)B(10)C(11)C(11) = 0001010101111
이렇게 되겠네.(가장 빈도수가 많은 수가 앞으로 적은 수가 뒤로 간다.)
그럼 7byte 를 13bit 로 줄일 수 있다.(7byte 를 bit로 바꾸면 56bit이다)
이게 이론....
실 전은 조금 어렵더라.
음.... 그러니까
BDCDBDADBDDBCBD
라는게 있다하면
A(1) B(5) C(2) D(7)
이렇게 빈도수가 있다고 할수 있겠다.
그러면 이 빈도 수대로 정렬하면.
7D 5B C2 A1
가 되겠다.(보기 쉽게 빈도수를 앞으로...)
그 후엔 가장 낮은 빈도수(여기선 C와 A) 를 합친다.
7D 5B 3
C2 A1
이런 식이 되는데 다시 빈도수가 높은 수부터 정렬하고(여기선 이대로...) 빈도 수 낮은 수대로 또 합친다.
7D 8
5B 3
C2 A1
다시 빈도수 높은 수부터 정렬
8 7D
5B 3
C2 A1
다시 합치고
15
8 7D
5B 3
C2 A1
이렇게 한 후에
위에서 부터는 빈도수 큰 수에 0을 작은 수에 1을 준다.(최종. 그러니까 여기서 15는 수를 주지 않는다.)
15
8(0) 7D(1)
5B(0) 3(1)
C2(0) A1(1)
이렇게 되는데 여기서 A는 001이 된다.(C는 000, B는 00, D는 1이다.)
그러면 처음 문자열을 할당된 비트로 치환해보자.
BDCDBDADBDDBCBD(초기)
00100010010011001100000001(할 당 된 비트로 치환)
이렇게 된다.
그러면 총 15byte 의 문자열이 27bit로 압축 되었다(얼마나 압축 됐는지 수식은 까먹었....;)
자 이게 압축하는 방식(?!) 이라고 한다면
푸는 방식을 알아봐야 한다.
디 코딩이라고 하는데
호프만 알고리즘을 이용하여 방금 할당시킨 비트를 다시 치환해야 한다.
BDC 를 치환해보자.(차례대로 00과 1그리고 000을 나타낸다)(00 1 000)
15
8(0) 7D(1)
5B(0) 3(1)
C2(0) A1(1)
이렇게 있다면
1. B를 찾기 위해서는 첫 자리가 0이니까 15에서 왼쪽으로 내려간다.(0)
2. 둘째 자리도 0이니까 5에서 멈춘다(이게 B다)(1)
3. D를 찾기 위해서는 그냥 15에서 1로 내려온다(D다)(1)
4. C를 찾기 위해서는 15에서 왼쪽 즉 8로 내려온다.(0)
5. 8에서 왼쪽으로 내려온다 즉 5로 내려온다.(0)
6. 5에서 왼쪽으로 내려온다 즉 2로 내려온다.(0)
이렇게 찾으면 된다. 오오오....... 이거 처음에 볼땐 어려웠는데 이곳저곳 찾아가니까 쉽네;;
근데 결국 막상 쓰려고 하면 복잡하겠지;;
흠... 나만 알아볼수 있겠구만 글이 ㅋㅋㅋㅋㅋ
Mpeg 의 기본 압축 알고리즘으로도 쓰이고 알집 역시 허프만 알고리즘으로 한번 압축 후 Lempel 이라는 간단한 압축 알고리즘으로 한번 더 압축한다나 뭐라나~ 어쨋든 허프만 알고리즘.... 좋다.
이론적으론 쉽던데.....(옛날에 울형이 압축 프로그램 만들때 살짝 들었던거네)
자주 쓰는 문자에 가장 작은 bit를 할당하고 한두번 쓰이는 문자에는 큰 bit 를 할당~
간단하게 AAABBBCC 이렇게 있다면
영문자 하나의 byte 는 1byte 니까 총 7byte 가 되겠다.
사용된 문자의 횟수론
A 3번, B 3번, C 2번 이다.
이 문자열들에게 A에겐 0을 B에겐 10을 C에겐 11이라는 숫자를 부여해면
A(0)A(0)A(0)B(10)B(10)B(10)C(11)C(11) = 0001010101111
이렇게 되겠네.(가장 빈도수가 많은 수가 앞으로 적은 수가 뒤로 간다.)
그럼 7byte 를 13bit 로 줄일 수 있다.(7byte 를 bit로 바꾸면 56bit이다)
이게 이론....
실 전은 조금 어렵더라.
음.... 그러니까
BDCDBDADBDDBCBD
라는게 있다하면
A(1) B(5) C(2) D(7)
이렇게 빈도수가 있다고 할수 있겠다.
그러면 이 빈도 수대로 정렬하면.
7D 5B C2 A1
가 되겠다.(보기 쉽게 빈도수를 앞으로...)
그 후엔 가장 낮은 빈도수(여기선 C와 A) 를 합친다.
7D 5B 3
C2 A1
이런 식이 되는데 다시 빈도수가 높은 수부터 정렬하고(여기선 이대로...) 빈도 수 낮은 수대로 또 합친다.
7D 8
5B 3
C2 A1
다시 빈도수 높은 수부터 정렬
8 7D
5B 3
C2 A1
다시 합치고
15
8 7D
5B 3
C2 A1
이렇게 한 후에
위에서 부터는 빈도수 큰 수에 0을 작은 수에 1을 준다.(최종. 그러니까 여기서 15는 수를 주지 않는다.)
15
8(0) 7D(1)
5B(0) 3(1)
C2(0) A1(1)
이렇게 되는데 여기서 A는 001이 된다.(C는 000, B는 00, D는 1이다.)
그러면 처음 문자열을 할당된 비트로 치환해보자.
BDCDBDADBDDBCBD(초기)
00100010010011001100000001(할 당 된 비트로 치환)
이렇게 된다.
그러면 총 15byte 의 문자열이 27bit로 압축 되었다(얼마나 압축 됐는지 수식은 까먹었....;)
자 이게 압축하는 방식(?!) 이라고 한다면
푸는 방식을 알아봐야 한다.
디 코딩이라고 하는데
호프만 알고리즘을 이용하여 방금 할당시킨 비트를 다시 치환해야 한다.
BDC 를 치환해보자.(차례대로 00과 1그리고 000을 나타낸다)(00 1 000)
15
8(0) 7D(1)
5B(0) 3(1)
C2(0) A1(1)
이렇게 있다면
1. B를 찾기 위해서는 첫 자리가 0이니까 15에서 왼쪽으로 내려간다.(0)
2. 둘째 자리도 0이니까 5에서 멈춘다(이게 B다)(1)
3. D를 찾기 위해서는 그냥 15에서 1로 내려온다(D다)(1)
4. C를 찾기 위해서는 15에서 왼쪽 즉 8로 내려온다.(0)
5. 8에서 왼쪽으로 내려온다 즉 5로 내려온다.(0)
6. 5에서 왼쪽으로 내려온다 즉 2로 내려온다.(0)
이렇게 찾으면 된다. 오오오....... 이거 처음에 볼땐 어려웠는데 이곳저곳 찾아가니까 쉽네;;
근데 결국 막상 쓰려고 하면 복잡하겠지;;
흠... 나만 알아볼수 있겠구만 글이 ㅋㅋㅋㅋㅋ
