🌞 Tree: Huffman Decoding

🚊 문제 설명

• Huffman coding 은 주파수에 따라 가변 길이의 부호어들을 고정 길이 입력 문자에 할당한다.
• 빈도가 높은 문자일수록 짧은 부호어들이 할당되고 빈도가 낮은 문자일수록 긴 부호어들이 할당됩니다.
• 문자의 경로를 따라 있는 모든 가장자리에는 코드 번호가 포함되어 있습니다.
• 트리의 왼쪽에 있으면 0이 됩니다. 오른쪽에 있으면 1이 됩니다.
• 오직 leaf node만이 글자와 그 빈도수를 포함할 것이다. 다른 모든 node는 문자 대신 null을 포함하며, 모든 노드와 그 하위 문자의 빈도 수를 포함한다.

• 예를 들어 문자열 ABRACADABRA를 생각해 보자.
• 문자열에는 총 11개의 문자가 있고, 이 숫자는 최종적으로 결정된 트리의 루트에 있는 수와 일치해야 한다.
• 우리의 주파수는 A=5, B=2, R=2, C=1, B=1 이다.
• 가장 작은 두 개의 주파수는 C와 D에 해당하므로 둘 다 1로 값이 같으므로 이 두 주파수로 트리를 만든다.
• 루트 노드는 하위 노드 카운트의 합계(이 경우에는 1+1 =2)를 포함한다.
• 왼쪽 노드는 처음 접하는 문자 C를, 오른쪽 노드는 D를 포함합니다.
• 다음으로 우리는 방금 만든 트리, 문자 B, 문자 R의 3가지 항목을 가지고 있다.
• 트리가 먼저 왔기 때문에 새 루트 노드의 왼쪽에 있고, B는 오른쪽으로 가게 된다.
• 트리가 완료될 때까지 반복한 다음, 가장자리에 1과 0을 입력.
• 완성된 그래프는 다음과 같다.

• 입력된 문자는 오직 leaf node에만 있다.
• 내부 노드의 문자 값은 Null을 의미한다.
• 우리는 캐릭터에 대한 우리의 값이 다음과 같은 것을 확인할 수 있다.

      A - 0
      B - 111
      C - 1100
      D - 1101
      R - 10

• Huffman encoding된 문자열은 다음과 같다.

      A B    R  A C     A D     A B    R  A
      0 111 10 0 1100 0 1101 0 111 10 0
      or
      01111001100011010111100

• 모호성을 피하기 위해 Huffman encoding은 접두사 없는 인코딩 기법이다. 부호어는 다른 부호어의 접두사로 나타나지 않는다
• 인코딩된 문자열을 디코딩하려면 0과 1을 따라 leaf node까지 이동한 후 문자를 반환한다.
• Huffman tree의 루트에 대한 포인터와 디코딩할 이진 코드화된 문자열이 제공되며, 디코딩된 문자열을 출력해야 한다.

입력 예시

s="1001011"

출력 예시

ABACA

설명

S="1001011"
Processing the string from left to right.
S[0]='1' : we move to the right child of the root. We encounter a leaf node with value 'A'. We add 'A' to the decoded string.
We move back to the root.

S[1]='0' : we move to the left child. 
S[2]='0' : we move to the left child. We encounter a leaf node with value 'B'. We add 'B' to the decoded string.
We move back to the root.

S[3] = '1' : we move to the right child of the root. We encounter a leaf node with value 'A'. We add 'A' to the decoded string.
We move back to the root.

S[4]='0' : we move to the left child. 
S[5]='1' : we move to the right child. We encounter a leaf node with value C'. We add 'C' to the decoded string.
We move back to the root.

 S[6] = '1' : we move to the right child of the root. We encounter a leaf node with value 'A'. We add 'A' to the decoded string.
We move back to the root.

Decoded String = "ABACA"

🚢 기본 제공 Code

import queue as Queue

cntr = 0

class Node:
    def __init__(self, freq, data):
        self.freq = freq
        self.data = data
        self.left = None
        self.right = None
        global cntr
        self._count = cntr
        cntr = cntr + 1
    
    # lt (less than) : 두 객체의 값의 크기를 비교할 때 사용되는 함수
    def __lt__(self, other):
        if self.freq != other.freq:
            return self.freq < other.freq
        return self._count < other._count

def huffman_hidden():#builds the tree and returns root
    q = Queue.PriorityQueue()

    
    for key in freq:
        q.put((freq[key], key, Node(freq[key], key) ))
    
    while q.qsize() != 1:
        a = q.get()
        b = q.get()
        obj = Node(a[0] + b[0], '\0' )
        obj.left = a[2]
        obj.right = b[2]
        q.put((obj.freq, obj.data, obj ))
        
    root = q.get()
    root = root[2]#contains root object
    return root

def dfs_hidden(obj, already):
    if(obj == None):
        return
    elif(obj.data != '\0'):
        code_hidden[obj.data] = already
        
    dfs_hidden(obj.right, already + "1")
    dfs_hidden(obj.left, already + "0")

🚢 Input & Output

ip = input()
freq = {}#maps each character to its frequency

cntr = 0

for ch in ip:
    if(freq.get(ch) == None):
        freq[ch] = 1
    else:
        freq[ch]+=1

root = huffman_hidden()#contains root of huffman tree

code_hidden = {}#contains code for each object

dfs_hidden(root, "")

if len(code_hidden) == 1:#if there is only one character in the i/p
    for key in code_hidden:
        code_hidden[key] = "0"

toBeDecoded = ""

for ch in ip:
   toBeDecoded += code_hidden[ch]

decodeHuff(root, toBeDecoded) # 우리가 구현할 함수를 여기서 실행

📑 Code

def decodeHuff(root, s):
	# 현재 노드를 root로 지정
    current_node = root
    # 노드의 데이터를 쌓을 빈 문자열을 선언
    result = ''
    # s의 숫자들을 앞에서부터 확인하는 작업을 반복
    for num in s:
    	# 해당 숫자값이 0이라면
        if int(num) == 0:
        	# 탐색할 노드의 위치를 현재 노드의 왼쪽 노드로 변경
            current_node = current_node.left
        # 해당 숫자값이 1이라면
        else:
        	# 탐색할 노드의 위치를 현재 노드의 오른쪽 노드로 변경
            current_node = current_node.right
        # 만약 현재 노드의 왼쪽 노와 오른쪽 노드가 모두 없다면
        if current_node.left == None and current_node.right == None:
        	# 현재 노드의 데이터를 result에 추가
            result += current_node.data
            # 현재 노드를 다시 root로 지정
            # 반복문을 돌 때, 항상 root 노드부터 탐색을 시작하기 위함.
            current = root
            
    print(result)