데이터 압축에 쓰인다는(?) 허프만 코드... Huffman code

 이번 것은 과제는 아니였는데, 오기로(?) 해 버렸다. 크루스칼 알고리즘을 힘들게 해결한 이후에, 이제는 슬슬 인터넷에서 소스를 찾기보다는 내 자신이 교재(참고자료 참고)의 pseudo code(의사 코드)를 보고, 몇시간을 감이 잡힐 때까지 그림을 그려보거나 골똘히 생각하다가 조금씩 실마리가 잡히면 코딩을 시작하는 형태가 되어 가고 있다.
 (참고로 나는 프로그램을 잘하거나 소질이 있는 것이 아니라서 이 정도의 프로그램을 짜려면 며칠이 걸린다. 이 허프만 코드의 경우 코딩을 시작 하기까지 두시간 정도를 책을 보면서 어떻게 구현할 수 있을까 생각한 후에, 코딩을 시작했고 꼬박 앉은 자리에서 열시간 정도를 삽질을 하면서 프로그램을 트리 구성까지 완성시켰다. 그리고 마지막 결과 트리 출력 부분을 만들기 위해 추가로 서너시간 가량이 걸렸다.)
  이렇게 최근 알고리즘에 열을 올리면서 이전에는 왜 알고리즘이나 자료구조 책에는 바로 컴파일을 할 수 있는 소스가 아니고, pseudo code만 나와있어서 이렇게 사람을 힘들게 하냐고 생각 했는데... 최근 1~2주 사이에는 힘들어도 pseudo code를 보면서 내 입맛에 맞춰서 코딩(요리)을 하는 재미도 나름대로 솔솔하다는 생각도 든다.

 그리고 지금 보고 있는 교재의 pseudo code가 다른 알고리즘이나 자료구조 책보다 깔끔하게 정리가 잘 되어 있다는 생각이 든다. 필요한 부분만 쉽게 설명해주고 pseudo code로 보여준다는 느낌이다.

 허프만 코드는 기존의 영문자 ASCII 코드가 7비트(8비트)로 문자를 표현하고 있지만, 실재로는 하나의 문서에서 몇백개나 되는 문자를 모두 쓰는 경우는 매우 드문다는 점에 착안해서, 쓰는 문자만 뽑아내고 그 문자에 가중치(빈도수)를 주어서, 자주 나오는 문자를 짧게 부호화(이진코드화)해서, 하나의 문자로 봤을때나 전체의 문자열로 봤을 때나, ASCII 코드보다 적은 비트로 표현이 가능해져서 압축을 하는 효과가 된다는 개념이다.

   지금 학교에서 배우는 교재(참고자료 참고)에서는 이번 알고리즘 역시 탐욕적인 방법으로 분류되어 나온다. 지금까지 탐욕적인 알고리즘을 몇가지 봤는데, 분할정복법의 요점이 재귀, 동적계획법의 요점이 행렬(배열)이였다면 탐욕적인 알고리즘의 요점은 정렬이라고 느꼈다. 크루스칼이나 프림의 알고리즘도 그 순간에 최적인 방법을 택하기 위해서는 정렬이 필수였고, 지금 보는 허프만 코드 역시 이진 트리를 구성하기 위해서는 정렬된 우선순위 대기열을 사용한다.

 허프만 코드에서 이진 트리를 어떻게 만드는지와 같은 알고리즘이 돌아가는 방식에 대해서는 인터넷에서 검색하면 많이 나오므로 생략한다. 소스는 철절히 교재의 pseudo code의 리듬으로 짰으므로, 교재가 있다면 이해하는데 어렵지 않으리라 생각된다.

 이건 개인적인 얘기이고 지난번에도 얘기 했지만, 알고리즘 관련 포스팅의 경우 조회수는 참 높은데, 조회수에 비해 댓글은 거의 없다. 뭔가 댓글을 좀 달아주셨으면 좋겠다. 이 부분은 이렇게 하는게 더 좋다라든지... 소스의 어느 부분이 문제라든지.. 아니면 잘 가져가서 쓴다라는 댓글이라도 좋다. 자기 블로그(홈페이지)가 있다면 주소도 좀 남겨주셨으면 좋겠다. 아니면 리퍼러에 남도록 방문해 주면 알아서 찾아갈터인데...

허프만 코드 알고리즘에서 쓰일 텍스트 파일 파일(huffman.txt)
b:5 e:10 c:12 a:16 d:17 f:25
주어진 문자와 가중치로 트리를 구성해서 허프만 부호를 뽑아내는 허프만 코드 알고리즘
#include <stdio.h>
#include <stdlib.h>

typedef struct nodetype
{
char symbol; // 문자값
int frequency; // 파일에 있는 문자의 빈도수

struct nodetype* left;
struct nodetype* right;
}node;

typedef struct pq // 우선순위 대기열
{
node* Node; // 대기열에 있는 node
struct pq* next; // 다음 node
}pq;

#define ROOT -1 // 부호화 함수 출력시 초기값

pq* insert(node* r); // 우선순위 대기열에 노드를 정렬하여 삽입
node* huffman(int n); // 허프만 코드 트리를 만드는 함수
node* Remove(); // 우선 순위 대기열에서 노드를 삭제
void print_PQ(); // 우선 순위 대기열 출력
void print_tree(node* r, int n, char* code); // 결과 허프만 부호화 출력
void freetree(node* r); // 메모리 해제

pq* PQ = NULL; // 우선순위 대기열
FILE* file; // 파일 식별자

int main()
{
int n = 1;
node* result = (node*) malloc(sizeof(node)); // 결과를 돌려받을 노드
char* code = (char*) malloc(sizeof(char));

file = fopen("huffman.txt", "r"); // 입력이 되는 문자와 빈도수
if(file == NULL) {
perror("File open error");
return 0;
}


while(1) {
node* r = (node*) malloc(sizeof(node));
if( ( fscanf(file, "%c:%d ", &r->symbol, &r->frequency)) == -1) {
break; // 파일에 더 이상 값이 없으면 while 끝내기
}
r->left = NULL;
r->right = NULL;
insert(r); // 노드를 삽입 하면서 정렬함
n++;
}

printf("### Huffman Algorithm ###\n\n");
print_PQ(); // 입력이 끝난 우선순위 대기열

result = huffman(n); // 허프만 알고리즘

printf("\n-- Result Huffman code tree\n");
print_tree(result, ROOT, code);
printf("\n");

freetree(result); // 메모리 해제
fclose(file);

return 0;
}

void freetree(node* r) // 메모리 해제
{
if(r) {
freetree(r->left);
freetree(r->right);
free(r);
}
}


pq* insert(node* r) // 우선순위 대기열에 노드 삽입
{
pq* tmp = NULL;
pq* new = NULL;

// 우선순위 대기열 추가할 새로운 공간 할당
new = (pq*) malloc(sizeof(pq));
new->Node = r; // 대기열에 추가할 새로운 공간에 r 노드값 삽입
new->next = NULL;

if(PQ == NULL){ // 대기열이 비여있으면 새로운 공간이 리스트의 head가 됌
PQ = new;
return PQ;
} else if(PQ->Node->frequency > new->Node->frequency) {
new->next = PQ; // 루트 노드에 대한 비교 및 정렬
PQ = new;
}else { // 대기열에 리스트가 들어 있다면..
tmp = PQ; // tmp는 head
while(tmp->next != NULL) { // 다음 노드가 없을때까지..
if(tmp->next->Node->frequency <= new->Node->frequency)
tmp = tmp->next; // 우선순위 대기열 정렬을 위한 비교
else { // new의 빈도수가 tmp 보다 크고,
new->next = tmp->next; // tmp->next의 빈도수보다 작으면..
tmp->next = new; // 두 노드 사이에 새 노드를 삽입
break;
}

}
if(tmp->next == NULL) // 다음 대기열이 비어 있으면 삽입
tmp->next = new;

return tmp;
}
return 0;
}

node* huffman(int n) // 허프만 알고리즘
{
node* p;
node* q;
node* r;

int i;

for(i = 1; i < n-1; i++) {
p = Remove(); // 우선 순위 대기열에서 하나의 노드를 빼와서 p에 삽입
q = Remove(); // 우선 순위 대기열에서 하나의 노드를 빼와서 q에 삽입

r = (node*) malloc(sizeof(node)); // 새로운 부분 트리를 위한 공간 할당
r->left = p;
r->right = q;
r->frequency = p->frequency + q->frequency;
r->symbol = '*'; // 부분 트리의 뿌리임을 나타냄
insert(r); // 만들어진 부분 트리를 우선 순위 대기열에 삽입

printf("-- Create sub tree (%d/%d)\n ", i, n-2);
printf("%c:%d = %c:%d + %c:%d\n",
r->symbol, r->frequency, p->symbol, p->frequency, q->symbol, q->frequency);
print_PQ();
}

r = Remove(); // 우선 순위 대기열에 있는 트리의 뿌리를 빼와서 r에 대입
return r;
}

node* Remove() // 우선 순위 대기열에서 하나의 노드를 빼서 리턴값으로 넘긴다
{
node* pq_firstnode = NULL;

pq_firstnode = PQ->Node;
PQ = PQ->next;

return pq_firstnode;
}

void print_PQ() // 우선순위 대기열 출력
{
pq* tmp = PQ;
printf("-- Priority Queue\n | ");
while(tmp != NULL){
printf("%c:%d | ", tmp->Node->symbol, tmp->Node->frequency);
tmp = tmp->next;
}
printf("\n\n");
}

void print_tree(node* r, int n, char* code) // 결과 허프만 알고리즘 트리 출력
{
if(r) {
n++; // 트리의 깊이를 표시

code[n] = '0'; // 트리의 좌측
print_tree(r->left, n, code);

code[n] = '1'; // 트리의 우측
print_tree(r->right, n, code);

code[n] = '\0'; // 찌꺼기 제거
if(r->left == NULL || r->right == NULL) // 자식이 있는 노드는 출력하지 않음
printf(" - %c:%d\t= %s\n", r->symbol, r->frequency, code);
}
}

결과는 다음과 같다.
 생각보다 마지막에 결과인, 허프만 코드(부호)를 출력하는데 무지하게 애를 먹었다. 어떻게 트리를 순회하면서, 노드의 값이 아닌, 노드와 노드사이를 연결한 방향을 나타내는 부호인 0과 1을 출력할 수 있을까? 하고...
    참고자료
  • 알고리즘(Foundatations of Algorithms Using C++ Pseudocode) - Neapolitan, Naimipour 저 / 도경구 역

by sakuragi | 2007/05/17 02:39 | :: R space :: 과제 | 트랙백 | 핑백(1) | 덧글(72)

트랙백 주소 : http://sakuragis.egloos.com/tb/3414465
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Linked at sakuragi's misce.. at 2008/01/17 16:48

... (Programmer's Moe Life)알고리즘 (sakuragi's miscellaneous space)가장 많이 읽힌 글은 데이터 압축에 쓰인다는(?) 허프만 코드... Huffman code (10월부터 집계)가장 적게 읽힌 글은 명작은 아니더라도 이정도면 수작... 캐러비안의 해적 3 - At World's End&nb ... more

Commented by A.J at 2007/05/17 11:37
일단 허프만 코드에 대해서는 공부를 해봐야 알겠군요 ㅎㅎ

전에 플로이드 알고리즘에 대해 올리셨는데 그 알고리즘으로 지하철

최소경로 프로그램을 짜려니 맵데이터가 난감하더군요...

더 효과적인게 없을까 같이 생각해 보아요~
Commented by 환상경 at 2007/05/17 21:10
천재 ......
Commented by nidev at 2007/05/19 00:44
흠. 저도 썩 잘하는 편이 아니라서.....
그래도 알고리즘은 재밌는것 같다는 :)

ps. 터미널 글꼴이 무엇인지 물어봐도 될까요? ;)
Commented by sakuragi at 2007/05/20 00:51
AJ, 확실히 행렬로 데이터를 입력하는데 난감하겠군요.
하지만 문제는 플로이드 알고리즘을 쓰려면 행렬 데이터를 써야 하니, 이것도 문제네요. :(
비효율적이고, 난감해도 배열에 넣는 것 말고는 딱히 방법이 떠오르지 않네요. :)
환상경, 전 그저 평범해요.. :)
nidev, 네.. 저도 잘하지 못하지만 재미있는 점도 많은 것 같아요. :D
터미널 글꼴은 반달체(Bandal) 입니다. 크기는 9이구요.
Commented by A.J at 2007/05/21 01:39
지하철 알고리즘에 쓸 맵을 만드는 프로그램을 또 짜는수밖에는 없겠네요.. :(
Commented by 방문자 at 2007/05/21 22:17
담아갑니다..
Commented by sakuragi at 2007/05/21 23:01
AJ, 좀 비효율적이라도 모든 역에 대한 정보를 그냥 행렬에 넣으면 안되나요?
방문자, 네~ 출처만 밝혀주세요~ :D
Commented by A.J at 2007/05/22 00:07
그 모든역에 대한 행렬을 만드는 프로그램을 만드는게 어떨까 해서 ㅎㅎ

몬까 꼬이는 느낌 ~_~
Commented by sakuragi at 2007/05/22 05:47
AJ, 거기까지 생각해보진 않았네요. 개인적인 생각으로는 지하철의 역이라는 것이 항상 바뀌는 데이터가 아님을 생각 할 때, 그 입력을 위한 프로그램을 만들 필요가 있는 지도 고민하게 되네요. 지하철 노선이 추가되는 것은 몇년 주기가 되니까요. :D 하지만 길게 바라본다면 나쁘지는 않겠네요.
Commented by bk at 2007/06/06 19:42
저 코드대로 햇는데..
왜 코드값출력할때 메모리 에러가 생기죠???

아공~~머리아포~~
Commented by sakuragi at 2007/06/07 00:46
bk, 음.. MS Visual Stdio에서는 컴파일과 실행시 약간의 문제가 있었군요.
MS Visual Stdio에서도 정상적으로 동작하도록 소스 코드 수정했습니다.
Commented by 지나가던사람 ㅎ at 2007/06/07 03:09
멋지군요..
레포트가 허프만트리인데
참고하겠습니다
Commented by sakuragi at 2007/06/09 09:22
지난가던사람, 넵! 레포트 제출 잘하세요~ :)
Commented by zrab at 2007/06/11 01:30
지나가던사람님 처럼.. 리포트로 작성하다가 막히는 부분이 있어서 알고리즘 찾을려고 구글에서 검색했더니 사쿠라기님 이글루가 나와버렸네요'-'..
소스 코드를 직접 보고 참조하는 건 미친 짓이라는 생각도 듭니다만..

시간도 시간인데다..
시험이 더 중한 마당이라..

끝까지 정독 후 참조해서 리포트를 작성할까 생각이 드네요...;ㅁ;


여하튼.. 죄송합니다만..
리포트 쓰는 데 참조좀 하겠습니다..
(왠지 죄 짓는 기분..;ㅁ;)
Commented by sakuragi at 2007/06/11 13:00
zrab, 넵, 참조하세요~ ^^
이렇게 올린 이유 중에는 많은 분들께 도움이 되었으면 하는 마음도 있으니까요 :)
Commented by 에이쥬어 at 2007/08/08 20:53
이야, 말은 초심자라고 하셔도 잘 짜셨는데요 :)

일단 AJ님께 조언하자면, 지하철 최단경로 알고리즘은 Floyd보다는 Dijkstra를 이용하는 편이 더 쉬울 거라고 봅니다. 이건 데이터가 반드시 인접행렬로 주어져야 하지는 않거든요. Floyd도 인접행렬 안 사용하고 할 수는 있지만 -,.-; 복잡하고, 지하철 경로 계산 프로그램에선 모든 쌍에 대해서 최단경로를 구해야 할 까닭이 없거든요.
Commented by sakuragi at 2007/08/09 19:46
에이쥬어, 감사합니다. 그저 책에 있는 pseudo code를 프로그램으로 옮긴 것 뿐이라 쑥스럽네요. :)
Commented by sakuragi at 2007/11/16 20:09
yhwhite, 주석은 이미 달려 있는데요. :)
참고자료에 적혀 있는 책의 내용과 그 책의 pseudo code를 바탕으로 짠 것이기 때문에 참고자료에 있는 책을 보시면 이해가 쉬우실 껍니다. 아마 도서관에 가면 있으리라 예상됩니다.
소스를 보시다가 어떤 부분이 잘 이해가 되지 않는다던지 하다면 제가 그 부분에 대해서 설명을 해 드릴 용의는 있으나, 소스를 첨부터 끝까지 분석해달라고 하시는 거면 그렇게는 못하겠네요. :)
Commented by yhwhite at 2007/11/18 14:46
제가 좀 무리한 부탁을 드린거 같네요 ^ ^;;
위에 소스를 직접 쳐 가면서 파악을 해봤는데 역시 초보다 보니 이해가 되는 부분도 있고 안되는 부분도 있고 그렇네요. 근데 비쥬얼 C++ 에서 컴파일 시켜보니 에러가 뜨더군요;;
메시지를 살펴보면
파일경로huffman.cpp(157) : fatal error c1010 : unexpected end of file while looking for precompiled header directive Error executing cl.exe.
huffman.obj -1 error(s), 0 warning(s)

이유가 뭘까요? 첨에 프로젝트 설정할때 win32 colsol application 하고 simpleAppliction 선택을 했거든요 답변 부탁드릴께요
Commented by sakuragi at 2007/11/18 17:11
yhwhite, 위의 댓글들을 읽어 보시면 아시겠지만 이미 Visual C++에서 테스트 해서 소스코드를 수정했습니다. :)
Win32 Console Application -> An empty project 를 선택하신 후, 새롭게 huffman.c와 같은 C 소스 파일을 만들어서 위의 허프만 코드 소스를 그대로 넣으면 에러 없이 컴파일이 되실 껍니다.
Commented by sakuragi at 2007/11/18 21:22
yhwhite, 본문에도 나와 있듯이 '허프만 코드 알고리즘에서 쓰일 텍스트 파일 파일(huffman.txt)'이 필요합니다. 아래의 내용으로 huffman.txt 파일을 만드시면 이것이 입력이 됩니다. 즉, 따로 입력을 받는 것이 아니고, 이미 만들어 놓은 텍스트 파일로 입력을 받는 방식으로 프로그램을 짰습니다.

b:5 e:10 c:12 a:16 d:17 f:25
Commented by 대학생 at 2008/05/30 14:15

허프만 알고리즘에 대한 과제가 있었는데 .. 감사 합니다 ㅜ.ㅠ 혼자서 노력해서 과제를 하여야 하나 .
아직 실력이 .. ㅜ.ㅠ 님 덕분에 .. 좋은 자료 .. 좀 업어 가도 되겠지요 ㅡㅡ? 안된다면 흑흑흑..

위에 언급 하신 책도 지금 도서관에 빌리러 간답니다 ..
아무튼 감사 합니다 ..
Commented by sakuragi at 2008/06/06 19:37
넵, 그 책을 보시면 제 소스가 다 그 책에 나오는 내용이라는 걸 아실 수 있으실 껍니다.
좋은 자료라고 생각되시면 언젠가는 더 좋은 자료를 만들어서 다른 분들께 도움을 주세요~ :)
Commented by 허접한 학생 at 2008/06/02 21:45
레포트였는데,,, 정말 감사합니다.....
그리고 Microsoft Visual C++에서는 에러가 왕창 뜨는데,,,,
변수 이름 중에 new가 있더군요..... 에러는 new가 키워드라서 그렇습니다....
코드에서 new를 다른 변수명으로 바꿔 주시면 잘 돌아갑니다.... ^*^
마지막으로 sakuraki 님께 감사의 말씀 한번더 올립니다...... ㅎㅎ
Commented by sakuragi at 2008/06/06 19:39
제가 짠 소스 코드는 C 소스코드라서 그 부분에 문제가 있군요. :)
Commented by fishorange at 2008/10/13 22:37
허프만/다익스트라/프림/크루스칼. 모드 개념 정리 잘 하고 갑니다. ^^
1년 전에 포스팅 된 것인데도 정말 핵심만 잘 꼽아서 정리 해주셨어요.
다시 한 번 머리 숙여 감사~...
Commented by sakuragi at 2008/10/20 13:17
워낙 오래되고 유명한 알고리즘들이니까요. 그래서 몇십년이 지나도 보는 거겠죠.
부족한 글에 칭찬해주셔서 감사합니다. ( __)
Commented by 지나가는학생 at 2009/04/26 22:53
복호화 를 어떻게 해야할지 막막했는데 .. 많은 도움이 되었습니다. 고맙습니다.^^
Commented by sakuragi at 2009/05/06 01:11
넵.. 저도 막막해서 고민 많이 했었죠~ ^^ 도움이 되서 다행이네요~
Commented by 아웅 at 2010/04/06 18:07
b:5 e:10 c:12 a:16 d:17 f:25 <- 이 내용으로 huffman.txt 파일을 만들었습니다. 그럼 이 파일을 어디에 넣어야 되는것인지;; 디버그파일안에 넣어도 읽지를 못하네요ㅜㅜ
Commented by sakuragi at 2010/04/06 18:10
실행파일이 있는 디렉토리에 넣으시면 될껍니다.
Visual Studio를 쓰지 않아서 정확한 답변은 못 드리겠네요.
Commented by hd5535 at 2010/04/27 13:55
감사합니다, 많은 도움이 되었어요 :)
Commented by sakuragi at 2010/04/29 17:55
넵~ 별 말씀을요~ 다시 또 시간은 흐르고 흘러 과제의 시즌인가 보군요~ ^^
Commented by 이누기 at 2010/05/19 16:14
허프만코드출력에서 막혔었는데 여기에서 출력문보고 해결했습니다.
출력문만 퍼갈게요.
Commented by sakuragi at 2010/11/09 18:35
네~ 도움이 되서 다행이네요~ ^^
Commented by 라이언 at 2011/03/23 14:11
좋은글 감사합니다.~
Commented by sakuragi at 2011/04/04 10:28
도움이 되셨기를...
Commented by JW at 2011/09/21 11:28
잘보고 갑니다.
저도 요즘 데이터 압축에 관심이 많은뎅
저는 VHDL로 짜봐야겠네요 ^^;;;
Commented by sakuragi at 2011/09/27 01:13
VHDL 학부 4학년, 임베디드 수업 시간에 들었었는데...
기억이 가물가물 해지려고 하네요~ ㅜ_ㅜ
Commented by sady at 2011/10/21 03:40
좋은 글 잘 읽었습니다....코드 이해하는데도 오래걸렸습니다...전 아직 많이 모자라네요...

궁금한게 있는데요...각 문자마다 코드가 출력되는데 이것을 붙여서 보여줄 순 없을까요...?

예를들면... txt파일에 'adf' 라고 입력하여 저장한 후 실행하면 '000110'가 나올 수 있게요...
Commented by sakuragi at 2011/10/24 09:40
결과를 붙여서 보여주는 것은
void print_tree(node* r, int n, char* code) 함수의
printf에서 code만 출력하도록 수정하면 됩니다.
Commented by 학생 at 2011/10/29 13:04
txt파일을 입력으로넣어서 encoding한후 출력을 하는부분은 성공을했는데요,
decoding하는 과정에서 어떻게해야댈지 막막하네요...
혹시 decoding하는 과정도 좀 설명해주실수 있나요?
Commented by sakuragi at 2011/12/08 20:37
언젠가 Decoding하는 걸 짜보고 싶다거나 마음이 내키면 포스팅 하도록 하죠.
이건 학교 다닐 때 과제로 짠거라 짜는 김에 포스팅한 것입니다만..
지금은 딱히 알고리즘 관련 포스팅 할만한 이유가 없다보니...
Commented by Traeper at 2011/12/10 04:20
모대학교 컴공 2학년 학생입니다.
자료구조 공부를 하다가 우선순위의 개념을 이용한 허프만 코드에
흥미가 생겨서 인터넷으로 찾아보던 중.. 좋은 글을 찾게되어 영광입니다.
혹시 페이스북 하시면 친구 부탁드려도 될까요???
Commented by sakuragi at 2011/12/10 14:55
페이스북은 거의 하지 않고 트위터만 간간히 합니다만, 일단 친구 추가는 하였습니다.
Commented by 잉여컴공학생 at 2012/10/15 01:41
좋은자료감사합니다 읽어도 이해는 안되지만 이해될때까지공부하겠습니다.

Commented by sakuragi at 2012/10/30 23:50
저도 잘 몰라요. 그냥 학생 때 책 보고 했던 거죠~ :)
Commented by 지나가던 나그네 at 2012/11/14 00:15
c++에 넣으니 new라고 지정하신 포인터가 에러나요 ㅋ
바꾸면 돌아가네요






Commented by sakuragi at 2012/12/09 00:00
제가 Visual Studio를 쓰지 않기 때문에, 소스는 Linux에서 gcc로 컴파일 한 소스 입니다.
c++에서 문제가 생길 수도 있습니다.
Commented by signfang at 2012/11/30 14:33
감사합니다. 컴퓨터프로그래밍 과제 할 때 참고했습니다.
Commented by sakuragi at 2012/12/09 00:01
많은 도움이 되셨길...
Commented by 김선호 at 2012/12/17 02:47
좋은 자료 감사합니다 ^^
Commented by sakuragi at 2013/02/17 23:23
많은 도움이 되셨길...
Commented by Tamen at 2013/04/05 13:43
제가 실행했을 경우에는 빈도수가 쓰레기값이 나옵니다..ㅠ 직접 쳐보면서 해봤는데

안되길래 복사를 해도 그러네요.

중간에 뭐가 문제가된거지 ㄷㄷ
Commented by sakuragi at 2013/04/17 02:27
이런 저런 문제는 댓글로 많은 분들이 말씀해주셨으니. 참고하세요.
Commented by 0bin at 2013/05/28 12:34
과제로 huffman code 구현중인데. 정말 책의 알고리즘을 바탕으로 그대로 하셨군요!
저 같은 경우는 문자열을 쭉 주고 거기서 빈도수를 계산 -> 트리구현 -> 코드생성 단계로 갈려고 하는데 트리에서 막혀있었거든요.
우선순위 큐 쓰셔서 구현하신거 참고 많이 됬습니다!!
Commented by sakuragi at 2013/05/28 13:14
넵, 도움이 되셨다니 다행이군요. 6년이 지나도 항상 찾아주는 분이 계셔서 뿌듯하네요.
Commented by 0bin at 2013/05/28 12:55
아. 코드를 보다보니 궁금했던게
main 함수 내에 pq에 삽입하기 위해 node* r을 생성했는데 이거는 whilde문 내에서 삽입용으로만 사용하는거죠? 그렇다면 while문이 끝나면 해제해주는게 좋지 않나요? r을 해제해주는 free가 안보이네요. 윗분들 답변중에 잇는지 모르겠네요 ㅎ;
Commented by sakuragi at 2013/05/28 13:14
넵. 시간이 나면 보도록 하겠습니다.
Commented by 방문객A at 2013/06/06 08:35
insert할 때 메모리가 복제되지 않고 pq는 node의 포인터값만 가지기 때문에
while 안에서 malloc한 영역은 while 끝난 뒤에도 계속 사용됩니다.
[PQ [node] ] 이런 식인데 안의 [node]는 while 안에서 r 생성한 것을 그대로 가지고 있어야 하니
PQ와 트리를 다 쓸 때 까지 free하면 안되고 마지막에 freeTree하면서 일괄로 해제되므로 문제 없고
제 생각에는 오히려 insert에서 동적할당한 저 [PQ ]들을 free하는 부분이 필요한 거 같습니다.
Commented by 어린왕자 at 2013/11/02 16:01
염치없지만 질문 하나만 해도 될까요?
파일을 따로 저장하는 방식이 아닌 scanf 를 통해 문자열을 입력받고 해석하려면
어느 부분을 수정해야 할까요? file 관련 부분이 이곳저곳 흩어져있어서 함부로 건드리기가 겁나네요
Commented by sakuragi at 2013/11/04 11:03
file 관련 부분이 이곳 저곳에 흩어져 있지 않습니다. fopen, fscanf, fclose 뿐입니다.
while 문 시작 전에 fopen 대신에 scanf로 문자열을 받으시면 될 것 같고요.
while 문 안에서 fscanf(file, "%c:%d ", &r->symbol, &r->frequency) 대신 할 코드를 짜시면 될 것 같습니다.
Commented by 꿈놈 at 2013/12/03 03:35
안녕하세요. 일단 감사하다는 말씀 부터 드리구요.
공부하는 방법을 알려주셔서 감사합니다.

제가 배우는 책에는 최소히프를 이용해서 만들었는데, 우선순위큐로도 할 수 있군요?
훨씬 깔끔해보이는게 해봐야만 할것 같네요.

그리구요 궁금한게 있습니다.
print_tree에 쓰이는 마지막 매개변수 code부분이요.
main함수에서 malloc으로 char 포인터만 생성해주셨잖아요.
이걸 이대로 print_tree함수에 넣으면, 함수에서 자동으로 새로운 공간을 할당하나요?

제가 보기에는 code[0]을 제외한 나머지 부분은 할당되지 않은 메모리를 참조하고 있는것으로 생각되는데,
제가 잘못알고 있는걸까요?

변수 하나로 모든 child의 값을 출력하는 방법은 오늘 처음 보는데 되게 신기하네요 ㅎㅎ
Commented by sakuragi at 2013/12/03 16:58
궁금하신 부분에 대해서는 저도 딱히 답변을 못 드리겠네요.
제가 이 코드를 짠 게 6년도 더 지난 옛날(?)이고, 졸업 이후에 C, C++ 개발을 하고 있지 않아서 제 앎의 깊이가 더 깊어지지는 못했거든요.
근데 gcc가 좀 관대 한건지. visual c에서는 컴파일 에러가 나거나 문제가 생기는 부분도 정상적으로 컴파일이 되기도 하더라구요.

그리고 제가 이 소스를 공개하게 된 계기는 그 당시 과제를 할 때 돈을 주고 사지 않으면 참고할 소스가 딱히 없었기 때문에, 그냥 내가 열심히 짜서 공개하겠다는 생각이 강했던 것이지 제가 짠 코드가 완벽하다라고 생각해서 공개한 건 아니라는 점을 알아주셨으면 합니다. ^^
Commented by 꿈놈 at 2013/12/03 19:53
코드의 완벽성을 지적하려고 한건 아니었어요 ^^
C의 관대함이 참아주고 있는건 알고 있었는데,
혹시 제가 모르는 무언가가 있었나 싶어서요 ㅎ

저 상태에서 code변수 이후에 새로운 변수가 추가되면 아마 해당 변수에 문제가 생길거에요.
소스 보시는 분들 참고 하시라고 남겨둡니다.

도움 잘 받았습니다.
감사합니다.(--)(__)(--)
Commented by 뿅뿅 at 2014/02/12 09:24
너무 잘봤습니다!! 혼자 짜보려다가 아이디어가 너무 안나와서 sakuragi님 소스 참조했네요~ 정말 큰 도움 됐습니다^^
Commented by sakuragi at 2014/02/25 15:49
도움이 되서 다행이네요~ :D
Commented by qingfro9 at 2014/04/26 16:37
잘보고갑니다` :)
Commented by 장장이 at 2014/12/06 20:39
잘 보고 갑니당!
Commented by 느금마해녀 at 2015/12/09 16:58
과제하는데 도움이 되어서 많은 부분 참고할게요 감사합니다~~
Commented by 젤로 at 2016/05/29 18:38
허프만 함수에서 r->symbol = '*' 이것 부분 트리의 뿌리가 왜 필여한가여???
Commented at 2017/05/30 18:03
비공개 덧글입니다.

:         :

:

비공개 덧글

◀ 이전 페이지          다음 페이지 ▶

:+: sakuragi's Steam :+: