[javascript] 허프만 트리 (Huffman Tree) 데이터 구조

08 Dec 2023

javascript

허프만 트리는 데이터 압축에 매우 유용한 데이터 구조 중 하나입니다. 이 트리는 각 문자 또는 문자열의 빈도를 기반으로 생성됩니다. 허프만 트리는 주어진 문자 빈도에 따라 각 문자에 대한 고유한 이진 코드를 생성하여 데이터를 압축합니다.

허프만 트리 알고리즘

허프만 트리 알고리즘은 다음 단계로 구현됩니다:

주어진 문자열 내 각 문자의 빈도를 계산합니다.
모든 문자를 단일 노드로 하는 트리를 생성합니다.
가장 빈도가 적은 두 노드를 찾아 이를 자식 노드로 하는 새로운 노드를 생성합니다.
이 과정을 반복하여 단일 노드가 하나만 남을 때까지 트리를 확장합니다.

허프만 압축

허프만 트리를 사용하여 데이터를 압축하려면 다음 단계를 따릅니다:

문자열의 각 문자에 해당하는 이진 코드를 허프만 트리에서 찾습니다.
이진 코드를 사용하여 원래 데이터를 비트 스트림으로 변환합니다.

자바스크립트 예시

class Node {
  constructor(char, freq) {
    this.char = char;
    this.freq = freq;
    this.left = null;
    this.right = null;
  }
}

function buildHuffmanTree(str) {
  // 문자 빈도 계산
  const freqMap = {};
  for (let char of str) {
    freqMap[char] = (freqMap[char] || 0) + 1;
  }

  // 트리 노드 생성
  const nodes = Object.keys(freqMap).map(char => new Node(char, freqMap[char]));

  while (nodes.length > 1) {
    nodes.sort((a, b) => a.freq - b.freq);
    const left = nodes.shift();
    const right = nodes.shift();
    const merge = new Node(null, left.freq + right.freq);
    merge.left = left;
    merge.right = right;
    nodes.push(merge);
  }

  return nodes[0];
}

위의 코드는 주어진 문자열을 기반으로 허프만 트리를 구축하는 간단한 자바스크립트 예시입니다.

허프만 트리는 데이터 압축 뿐만 아니라 무손실 압축, 패턴 매칭, 코딩 이론 등 많은 분야에서 유용하게 활용될 수 있는 데이터 구조입니다.

자세한 내용은 Huffman coding을 참조할 수 있습니다.