Trie

Trie?

• Retrieve에서 따옴.
• 하나의 문자 코드가 다른 문자 코드의 접두부가 되지 않는 것을 보장하는 자료구조
• 비트 스트링을 유일하게 디코드할 수 있음.
• 하나의 문자열로부터 여러 개의 트라이를 생성할 수 있음.

Example

ABRACADABRA 에 대한 두 가지 인코딩 트라이

• 다른 prefix에 포함되지 않도록 이루어져 있음.

Huffman Encoding

Huffman Encoding?

• 여러 트라이 중 가장 좋은 트라이를 결정하는 일반적인 기법
• 우선순위 큐를 사용해 빈도수가 가장 작은 문자부터 차례로 트라이를 만듦.
• 인코딩된 메시지의 길이
  • 허프만 빈도수 트리의 가중치 외부 경로 길이(Weighted external path length)와 같게 됨.
  • 동일한 빈도수 → Huffman Tree가 최적해
• Prefix Code
  • 한 문자의 코드가 다른 문자의 코드 워드의 prefix가 될 수 없음.
  • Ex) a의 코드가 01이면 011은 b의 코드가 될 수 없음.

Huffman Encoding Algorithm