[자료구조] 01 알고리즘과 허프만코딩트리

✔️ 알고리즘이란

주어진 문제 해결에 필요한 절차 (procedure)를 체계적으로 구성해 놓은 명령어들의 모음

 

✔️ 알고리즘의 조건

-입력 (input) : 명시적 입력은 없어도 된다

-출력 (output) : 하나 이상의 출력이 있어야 된다

-명확성 (definiteness) : 모호하지 않은 명령문으로 표현되어야 하다

-유한성 (finiteness) : 유한한 수의 명령어 실행 이흐 종료되어야 한다

-유효성 (effectiveness) : 실행 가능한 명령어로 구성되어야 한다

 

 

 

📌 < 허프만 코딩트리 > 이용해서 자료구조가 어떻게 쓰이는지 확인해보자!

허프만 코딩 트리 

Time and Tide waits no man => 이 문장을 이용하여 어프만 코딩 트리를 해보자

 

트리의 최상위 루트에서 단말 노드까지

왼쪽 자식으로 갈 땐 0, 오른쪽 자식으로 갈 땐 1을 부여

 

각 문자에 해당하는 허프만 코드 생성 가능 (Huffman code)

각 문자 위에 주어진 숫자 1,2,3,8은 각 문자가 몇번 출현했는지 빈도수를 의미한다

 

빈도수가 가장 낮은 w 는 00000, 빈도수가 가장 높은 공백 ' '은 11을 나타낸다

이 그림으로 보면 '0110011100100011'은 'time'을 의미한다

 

 

원래 주어진 문장을 저장하는 데 필요한 공간은 총 12 종류의 문자가 29번 나오므로

29 문자 * 8비트 ( 1바이트 ) = 233비트 

허프만 코드로 이 문장을 표현하면 각 문자의 출현빈도 * 비트의 합인 100비트만 소요되서 공간을 줄일 수 있다

 

233비트 👉 100비트 (133비트 절약)

 

 

✔️즉, 데이터를 자료구조에 잘 표현하면 데이터 압축 효과가 생긴다는 것