The Number of Huffman Codes, Compact Trees, and Sums of Unit Fractions

Source

• Evernote/Papers/The Number of Huffman Codes, Compact Trees, and Sums of Unit Fractions.md

Summary

이 논문은 알파벳 크기 $t$와 길이 $r$을 가지는 ‘비동치(non-equivalent)’ 컴팩트 허프만 코드의 수, 즉 완전 $t$-진 트리의 수를 세는 문제를 다룹니다. 기존 문헌을 통합하여 여러 독립적인 접근법을 정리한 후, 이전 연구보다 정밀한 점근적 결과를 증명합니다. 이 결과는 두 개의 주요 항과 오차 항으로 구성됩니다.

Key Points

• 비동치 컴팩트 허프만 코드 및 완전 $t$-진 트리의 개수 세기 문제 연구
• 기존 문헌의 다양한 접근법 통합 및 서술
• 두 개의 주요 항과 오차 항을 포함하는 정밀한 점근적 카운팅 함수 증명

Related

• Classification of Homogeneous Data With Large Alphabets

• Approximation Algorithms for the Directed k-Tour and k-Stroll Problems

• Fast Near-Duplicate Image Detection Using Uniform Randomized Trees

• 리만 가설 (Riemann Hypothesis)

• 프로그래머를 위한 유니코드 소개 (Nathan Reed)

• k-parity 테스트의 비적응적 쿼리 복잡도

• 종성 분리 알고리즘

• Fluent 2016: 불변 데이터 구조 (Immutable Data Structure)

• 코딩 인터뷰 필수 알고리즘 10 가지 (Top 10 Algorithms for Coding Interview)

• 집합의 크기와 카디널리티(Cardinality)의 개념