오늘은 무손실 압축의 대표적인 알고리즘인 허프만 알고리즘에 대해서 알아보겠습니다.
허프만 부호화, 허프만 압축, 허프만 알고리즘등으로 불리우는 이 알고리즘은 문자들의 빈도수에 따라 서로 다른 길이의 부호를 부여하여 압축하는 방식으로, 1952년 당시 박사과정 학생이던 데이비드 허프만이 A Method for the Construction of Minimum-Redundancy Codes란 제목의 논문으로 처음 발표했습니다.
허프만 알고리즘은 JPEG이나 MPEG 같은 영상처리에서 많이 사용되고 있으며 우리가 많이 쓰는 알집 역시 허프만 알고리즘으로 한번 압축을 한 다음에 Lempel 이라는 알고리즘으로 압축을 합니다.
허프만 알고리즘은 그렇게 어렵지 않은 알고리즘이면서도 꽤 괜찮은 압축율을 보입니다.
이번 포스팅에서는 허프만 알고리즘의 원리와 절차에 대해서 알아보고 다음 포스팅 쯤에서 실제로 구현해보도록 하겠습니다.
=======================================================================================================
허프만 부호화로 위키에서 검색을 해보면 간략한 설명과 함께 아래와 같은 간략한 절차가 나와있습니다.
문서를 허프만 알고리즘으로 압축하기 위해서는 먼저 문서안에 포함된 문자들의 빈도수를 조사하여 정렬하는 절차가 필요합니다.
만약 다음과 같은 데이터가 있다고 한다면 다음과 같은 빈도수를 줄 수 있습니다.
데이터: ACABFEAFDE
위의 결과를 빈도수에 따라 오름차순으로 정렬을 합니다.
이제 이 값들을 이용하여 이진트리를 생성합니다.
먼저 가장 작은 빈도수의 값을 두개 선택해서 리프노드를 두개 만들고 두 노드의 가중치를 더해서 부모노드를 만듭니다. 그리고 정렬된 리스트에서 선택된 두개의 노드를 삭제하고 부모노드를 추가 시킵니다.
위의 과정을 리스트에 노드가 1.0 하나만 남을 때까지 반복합니다. (모든 빈도수 확률을 더하면 1.0이 되기 때문에)
이렇게 완성된 이진트리를 루트노드부터 왼쪽은 0, 오른쪽은 1을 부가해줍니다.
이렇게 완성된 허프만 트리를 가지고 각 문자에 대한 비트를 부가합니다.
A의 경우는 루트노드에서 왼쪽으로 한번 갔다가 다시 한번 왼쪽으로 갔기때문에 00 이 됩니다.
마찬가리로 B는 0110이 되겠지요.
이것을 정리하면 아래의 표와 같습니다.
이 표를 보고 눈치채신 분도 있으실텐데 허프만 알고리즘의 핵심은 바로 이 표에 있습니다.
가장 많은 빈도수의 데이터는 적은 비트, 상대적으로 적은 빈도수의 데이터들은 더 긴 비트를 서로 접두어가 겹치지 않도록 부가하여 압축하는 것입니다.
즉, 비트의 앞에서부터 순서대로 탐색했을 때 유일의 리프노드로 갈 수 있도록 비트의 등장 순서를 유일하도록 해주는 것입니다.(말이 어려운가;;; 압축을 풀 때 트리를 탐색해보시면 이해하실 수 있을 겁니다=ㅅ=)
그런데 위의 경우는 같은 빈도수의 노드들이 몇개 있기 때문에 다른 모양의 트리로 만들어질 수도 있습니다. 같은 노드가 존재할 때 어떤 순서로 트리에 추가하느냐나 트리의 왼쪽, 오른쪽 어느쪽에 붙이느냐에 따라 조금 달라질 수도 있습니다. 하지만 결과적으로 부가되는 비트의 개수는 같기때문에 압축율은 같습니다.
이제 처음에 압축하려고 했던 데이터를 압축하면 다음과 같아질 것입니다.
처음의 데이터는 10글자이므로 10바이트 = 80비트 입니다. 압축된 데이터는 25글자이지만 비트데이터이므로 25비트 입니다. 25 / 80 * 100 = 31.25% 의 압축율을 보이는 군요.
물론 위의 예는 텍스트 문서일 때이고, 다른 종류의 파일이라면 약간 달라질 수 도 있습니다. 실제로는 트리정보에 대한 헤더도 추가해야되고 하니 조금 더 늘어나겠지만, 그래도 꽤 괜찮은 압축율을 보입니다.
압축을 해제하는 것은 아주 쉽습니다.
비트데이터를 허프만 트리에 넣고 루트노드부터 탐색해서 리프노드가 나오면 치환해주고, 다시 루트부터 탐색하는 식으로 데이터를 끝까지 읽으면 됩니다. 디코딩 과정은 생략하도록 하겠습니다.
허프만 부호화, 허프만 압축, 허프만 알고리즘등으로 불리우는 이 알고리즘은 문자들의 빈도수에 따라 서로 다른 길이의 부호를 부여하여 압축하는 방식으로, 1952년 당시 박사과정 학생이던 데이비드 허프만이 A Method for the Construction of Minimum-Redundancy Codes란 제목의 논문으로 처음 발표했습니다.
허프만 알고리즘은 JPEG이나 MPEG 같은 영상처리에서 많이 사용되고 있으며 우리가 많이 쓰는 알집 역시 허프만 알고리즘으로 한번 압축을 한 다음에 Lempel 이라는 알고리즘으로 압축을 합니다.
허프만 알고리즘은 그렇게 어렵지 않은 알고리즘이면서도 꽤 괜찮은 압축율을 보입니다.
이번 포스팅에서는 허프만 알고리즘의 원리와 절차에 대해서 알아보고 다음 포스팅 쯤에서 실제로 구현해보도록 하겠습니다.
=======================================================================================================
허프만 부호화로 위키에서 검색을 해보면 간략한 설명과 함께 아래와 같은 간략한 절차가 나와있습니다.
- 초기화 : 모든 기호를 출현 빈도수에 따라 나열한다.
- 단 한 가지 기호가 남을 때까지 아래 단계를 반복한다.
- 목록으로부터 가장 빈도가 낮은 것을 2개 고른다.
- 그 다음 허프만이 두가지 기호를 부모 노드를 가지는 부트리를 구성하고 자식노드를 생성한다. 부모 노드 단 기호들의 빈도수를 더하여 주 노드에 할당하고 목록의 순서에 맞도록 목록에 삽입한다.
- 목록에서 부모노드에 포함된 기호를 제거한다.
문서를 허프만 알고리즘으로 압축하기 위해서는 먼저 문서안에 포함된 문자들의 빈도수를 조사하여 정렬하는 절차가 필요합니다.
만약 다음과 같은 데이터가 있다고 한다면 다음과 같은 빈도수를 줄 수 있습니다.
데이터: ACABFEAFDE
| 데이터 |
빈도수 |
등장확률(가중치) |
| A |
3 |
0.3 |
| B |
1 |
0.1 |
| C |
1 |
0.1 |
| D |
1 |
0.1 |
| E |
2 |
0.2 |
| F |
2 |
0.2 |
위의 결과를 빈도수에 따라 오름차순으로 정렬을 합니다.
이제 이 값들을 이용하여 이진트리를 생성합니다.
먼저 가장 작은 빈도수의 값을 두개 선택해서 리프노드를 두개 만들고 두 노드의 가중치를 더해서 부모노드를 만듭니다. 그리고 정렬된 리스트에서 선택된 두개의 노드를 삭제하고 부모노드를 추가 시킵니다.
위의 과정을 리스트에 노드가 1.0 하나만 남을 때까지 반복합니다. (모든 빈도수 확률을 더하면 1.0이 되기 때문에)
=============================================================
=============================================================
=============================================================
=============================================================
=============================================================
이렇게 완성된 이진트리를 루트노드부터 왼쪽은 0, 오른쪽은 1을 부가해줍니다.
이렇게 완성된 허프만 트리를 가지고 각 문자에 대한 비트를 부가합니다.
A의 경우는 루트노드에서 왼쪽으로 한번 갔다가 다시 한번 왼쪽으로 갔기때문에 00 이 됩니다.
마찬가리로 B는 0110이 되겠지요.
이것을 정리하면 아래의 표와 같습니다.
| 데이터 |
치환될 비트 |
| A |
00 |
| B |
0110 |
| C |
0111 |
| D |
010 |
| E |
10 |
| F |
11 |
이 표를 보고 눈치채신 분도 있으실텐데 허프만 알고리즘의 핵심은 바로 이 표에 있습니다.
가장 많은 빈도수의 데이터는 적은 비트, 상대적으로 적은 빈도수의 데이터들은 더 긴 비트를 서로 접두어가 겹치지 않도록 부가하여 압축하는 것입니다.
즉, 비트의 앞에서부터 순서대로 탐색했을 때 유일의 리프노드로 갈 수 있도록 비트의 등장 순서를 유일하도록 해주는 것입니다.(말이 어려운가;;; 압축을 풀 때 트리를 탐색해보시면 이해하실 수 있을 겁니다=ㅅ=)
그런데 위의 경우는 같은 빈도수의 노드들이 몇개 있기 때문에 다른 모양의 트리로 만들어질 수도 있습니다. 같은 노드가 존재할 때 어떤 순서로 트리에 추가하느냐나 트리의 왼쪽, 오른쪽 어느쪽에 붙이느냐에 따라 조금 달라질 수도 있습니다. 하지만 결과적으로 부가되는 비트의 개수는 같기때문에 압축율은 같습니다.
이제 처음에 압축하려고 했던 데이터를 압축하면 다음과 같아질 것입니다.
데이터: ACABFEAFDE
압축된 데이터: 0001110001101110001101010
압축된 데이터: 0001110001101110001101010
처음의 데이터는 10글자이므로 10바이트 = 80비트 입니다. 압축된 데이터는 25글자이지만 비트데이터이므로 25비트 입니다. 25 / 80 * 100 = 31.25% 의 압축율을 보이는 군요.
물론 위의 예는 텍스트 문서일 때이고, 다른 종류의 파일이라면 약간 달라질 수 도 있습니다. 실제로는 트리정보에 대한 헤더도 추가해야되고 하니 조금 더 늘어나겠지만, 그래도 꽤 괜찮은 압축율을 보입니다.
압축을 해제하는 것은 아주 쉽습니다.
비트데이터를 허프만 트리에 넣고 루트노드부터 탐색해서 리프노드가 나오면 치환해주고, 다시 루트부터 탐색하는 식으로 데이터를 끝까지 읽으면 됩니다. 디코딩 과정은 생략하도록 하겠습니다.
개인적으로 관심이 좀 있는 분야이기도 해서 공부를 해볼까해서 나름 공부하는 내용들을 정리하는 식으로 포스팅 해볼까 합니다.
=======================================================================================================
우리는 알게 모르게 데이터 압축을 아주 많이 사용하고 있습니다.
알집이나 win zip, win rar 같은 압축 프로그램을 이용해서 파일의 용량을 줄이는 것부터, 정말 많이 쓰이고 있는 mp3나 jpeg같은 것도 데이터 압축이지요.
압축 기술은 오래전 하드웨어의 한계상 많은 용량을 다룰 수 없었을 때 효율적으로 데이터를 보관, 이동등을 하기 위해 사용되어 왔으며, 하드웨어가 비약적으로 발달된 현재에도 그 유용성은 여전히 뛰어납니다.
데이터 압축을 위키 백과사전에서 검색해보면 다음과 같이 나옵니다.
네, 뭐 따로 정의하지 않더라도 이미 다 알고 있는 이야기 같습니다 =ㅅ=;;
데이터 압축은 크게 두 종류로 나눌 수 있습니다. 바로 무손실 압축과 손실 압축인데요.
예를 들자면 알집으로 파일을 압축하면 나중에 압축을 풀었을 때 원본의 데이터가 손상되지 않습니다. 이런 압축 방식을 무손실 압축이라고 합니다. 대표적인 무손실 압축 알고리즘에는 반복 길이 부호화와 허프만 부호화 등이 있습니다.
손실 압축은 압축 이후에는 원래의 데이터의 일부분을 손실했기 때문에 다시 복원할 수 없는 방식인데, 사람이 들을 수 없는 영역을 삭제하여 압축하는 방식인 mp3가 대표적이라 할 수 있습니다.
무손실 압축과 손실 압축을 예를 들어 더 자세하게 알아보도록 하죠.
무손실 압축
압축 알고리즘에 가장 간단한 반복 길이 부호화에 대해 알아보겠습니다.
하얀색 모니터에 검은색 점이 찍혀있는 데이터에 대해 생각해봅시다. 하얀색 픽셀을 w라고 쓰고 검은색 점을 b라고 표현한다면 다음과 같을 것입니다.
위의 데이터를 봤을 때 자세히 보면 반복되는 데이터를 알 수 있습니다. 바로 w가 반복되다가 b가 반복되고 w가 다시 반복되는 식으로 데이터가 이루어져있습니다.
따라서 다음과 같이 표현할 수도 있을 것 같습니다.
w가 5개있고 b가 1개 있고 그뒤로 w가 5개가 있고....이런 식으로 표현을 하게 되면 원래 기존의 데이터는 20개의 글자가 필요했지만 아래의 데이터에서는 14개 글자만 있으면 원래의 데이터를 다시 만들어 낼 수 있습니다.
여기에서 w와 b는 0과 1로 이루어진 비트 데이터일 때도 똑같이 적용될 수 있겠지요.
물론 데이터가 저런식으로 반복되는 경우는 그렇게 많지 않을테고 이를 위한 확장된 여러가지 알고리즘들이 있지만, 기본적으로는 위의 방식과 비슷합니다.
반복 길이 부호화를 사용하는 대표적인 파일 형식으로 PCX, BMP, ILBM 등이 있습니다.
손실 압축
위의 데이터를 다시 살펴봅시다.
위의 데이터는 모니터에 표시된 픽셀이라고 가정했는데, 자세히 보면 b가 하나 인 곳이 있습니다. 만약 모니터가 아주 크고 위의 데이터는 그 중 일부의 데이터라고 한다면, 하나의 픽셀이 검은 것은 없어지더라도 별로 표시가 나지 않을 수 있습니다. 마찬가지로 가장 마지막에 있는 w도 옆의 b로 바꾼다고 해도 그다지 표시가 나지 않을 수 있겠지요.
그렇다면 다음과 같이 바꿀 수도 있을 것 같습니다.
이것을 다시 반복 길이 부호화로 줄인다고 하면, 다음과 같을 것입니다.
무손실 압축에서는 압축이후에 14개의 글자가 필요했지만 이 경우에는 9개만 있으면 됩니다. 물론 이를 원래 데이터로 복원할 방법은 없겠지만, 대신 데이터가 훨씬 더 줄어드는 장점이 있습니다.
손실압축은 멀티미디어에서 아주 많이 쓰이고 있으며, 대표적으로는 JPEG과 mp3, mp4등으로 잘 알려진 MPEG 계통의 압축기술이 있습니다.
참고 사항
위키 백과사전에서 데이터 압축으로 검색을 해보면 여러 압축 기술들의 압축율에 대한 순위가 나와있는데, 잘 알려진 압축 기술들도 있고(zip이라던지 rar, arj 같은), 생소한 기술들도 있습니다.
압축은 텍스트 파일이나 html같은 파일에는 아주 높은 압축율을 보이지만, 이미 압축되어 있는 파일인 mp3나 jpg같은 파일은 그다지 크기가 줄어들지 않으며, 헤더의 추가로 오히려 늘어나는 경우도 있습니다.
순위들을 보면 rk, rar, 7-zip 이 대체적으로 높은 순위에 랭크되어 있습니다. rk와 rar는 사용 프로그램이고, 7-zip은 오픈소스로 윈도우는 물로 리눅스에서도 동작합니다.
개인적으로는 7-zip을 써보고 정말 높은 압축율에 놀랐는데, 압축하는데 무지하게 오래 걸린다는 단점이 좀 있었습니다.
=======================================================================================================
우리는 알게 모르게 데이터 압축을 아주 많이 사용하고 있습니다.
알집이나 win zip, win rar 같은 압축 프로그램을 이용해서 파일의 용량을 줄이는 것부터, 정말 많이 쓰이고 있는 mp3나 jpeg같은 것도 데이터 압축이지요.
압축 기술은 오래전 하드웨어의 한계상 많은 용량을 다룰 수 없었을 때 효율적으로 데이터를 보관, 이동등을 하기 위해 사용되어 왔으며, 하드웨어가 비약적으로 발달된 현재에도 그 유용성은 여전히 뛰어납니다.
데이터 압축을 위키 백과사전에서 검색해보면 다음과 같이 나옵니다.
데이터 압축은 데이터를 더 적은 저장 공간에 효율적으로 기록하기 위한 기술, 또는 그 기술의 실제 적용을 가리킨다.
네, 뭐 따로 정의하지 않더라도 이미 다 알고 있는 이야기 같습니다 =ㅅ=;;
데이터 압축은 크게 두 종류로 나눌 수 있습니다. 바로 무손실 압축과 손실 압축인데요.
예를 들자면 알집으로 파일을 압축하면 나중에 압축을 풀었을 때 원본의 데이터가 손상되지 않습니다. 이런 압축 방식을 무손실 압축이라고 합니다. 대표적인 무손실 압축 알고리즘에는 반복 길이 부호화와 허프만 부호화 등이 있습니다.
손실 압축은 압축 이후에는 원래의 데이터의 일부분을 손실했기 때문에 다시 복원할 수 없는 방식인데, 사람이 들을 수 없는 영역을 삭제하여 압축하는 방식인 mp3가 대표적이라 할 수 있습니다.
무손실 압축과 손실 압축을 예를 들어 더 자세하게 알아보도록 하죠.
무손실 압축
압축 알고리즘에 가장 간단한 반복 길이 부호화에 대해 알아보겠습니다.
하얀색 모니터에 검은색 점이 찍혀있는 데이터에 대해 생각해봅시다. 하얀색 픽셀을 w라고 쓰고 검은색 점을 b라고 표현한다면 다음과 같을 것입니다.
wwwwwbwwwwwbbwwwbbbw
위의 데이터를 봤을 때 자세히 보면 반복되는 데이터를 알 수 있습니다. 바로 w가 반복되다가 b가 반복되고 w가 다시 반복되는 식으로 데이터가 이루어져있습니다.
따라서 다음과 같이 표현할 수도 있을 것 같습니다.
5w1b5w2b3w3b1w
w가 5개있고 b가 1개 있고 그뒤로 w가 5개가 있고....이런 식으로 표현을 하게 되면 원래 기존의 데이터는 20개의 글자가 필요했지만 아래의 데이터에서는 14개 글자만 있으면 원래의 데이터를 다시 만들어 낼 수 있습니다.
여기에서 w와 b는 0과 1로 이루어진 비트 데이터일 때도 똑같이 적용될 수 있겠지요.
물론 데이터가 저런식으로 반복되는 경우는 그렇게 많지 않을테고 이를 위한 확장된 여러가지 알고리즘들이 있지만, 기본적으로는 위의 방식과 비슷합니다.
반복 길이 부호화를 사용하는 대표적인 파일 형식으로 PCX, BMP, ILBM 등이 있습니다.
손실 압축
위의 데이터를 다시 살펴봅시다.
위의 데이터는 모니터에 표시된 픽셀이라고 가정했는데, 자세히 보면 b가 하나 인 곳이 있습니다. 만약 모니터가 아주 크고 위의 데이터는 그 중 일부의 데이터라고 한다면, 하나의 픽셀이 검은 것은 없어지더라도 별로 표시가 나지 않을 수 있습니다. 마찬가지로 가장 마지막에 있는 w도 옆의 b로 바꾼다고 해도 그다지 표시가 나지 않을 수 있겠지요.
그렇다면 다음과 같이 바꿀 수도 있을 것 같습니다.
wwwwwwwwwwwbbwwwbbbb
이것을 다시 반복 길이 부호화로 줄인다고 하면, 다음과 같을 것입니다.
11w2b3w4b
무손실 압축에서는 압축이후에 14개의 글자가 필요했지만 이 경우에는 9개만 있으면 됩니다. 물론 이를 원래 데이터로 복원할 방법은 없겠지만, 대신 데이터가 훨씬 더 줄어드는 장점이 있습니다.
손실압축은 멀티미디어에서 아주 많이 쓰이고 있으며, 대표적으로는 JPEG과 mp3, mp4등으로 잘 알려진 MPEG 계통의 압축기술이 있습니다.
참고 사항
위키 백과사전에서 데이터 압축으로 검색을 해보면 여러 압축 기술들의 압축율에 대한 순위가 나와있는데, 잘 알려진 압축 기술들도 있고(zip이라던지 rar, arj 같은), 생소한 기술들도 있습니다.
압축은 텍스트 파일이나 html같은 파일에는 아주 높은 압축율을 보이지만, 이미 압축되어 있는 파일인 mp3나 jpg같은 파일은 그다지 크기가 줄어들지 않으며, 헤더의 추가로 오히려 늘어나는 경우도 있습니다.
순위들을 보면 rk, rar, 7-zip 이 대체적으로 높은 순위에 랭크되어 있습니다. rk와 rar는 사용 프로그램이고, 7-zip은 오픈소스로 윈도우는 물로 리눅스에서도 동작합니다.
개인적으로는 7-zip을 써보고 정말 높은 압축율에 놀랐는데, 압축하는데 무지하게 오래 걸린다는 단점이 좀 있었습니다.
Prev
Rss Feed