허프만 트리를 그리지 않고 문자 당 "비트 수"를 찾는 방법이 있습니까? 즉, 문자의 "빈도"또는 "확률"을 통해 문자의 코드 길이를 찾는 방법이 있습니까?허프만 코드 가변 길이 문자 당 길이
참고 : "가변 길이 코드"를 사용하고 싶습니다. 다음 설명문을 사용하십시오.
"이것은 호프만 트리의 예입니다" 예를 들어 "a"허프만 코드의 길이는 3 비트입니다. 당신은 기호의 집합에서 각 심볼의 대략 제로 주문 엔트로피를 계산할 수 http://en.wikipedia.org/wiki/Huffman_coding
:
다음 사이트는이 문장의 허프만 트리, 허프만 코드와 주파수를 가지고있다. 각 심볼의 확률이 p_i (p_i의 합이 1이되도록) 인 심볼 집합 a_i가 주어지면 비트 단위의 a_i의 엔트로피는 -log2 (p_i)입니다. 여기서 log2는 대수 2입니다. 비트의 평균 엔트로피는 -p_i log2 (p_i)의 i에 대한 합계입니다.
이것은 허프만 또는 그 기호의 산술 0 차 코딩에서 얻을 수있는 대략적인 예상치를 제공합니다. 견적은 하프 만 (Huffman)과 산술 모두 견적으로 인해 한계에 도달하지 못하고 허프만의 경우 비트가 약간의 해상도로 제한되는 하한선을 제공합니다.
감사합니다. 따라서 정확한 비트 수를 계산할 방법이 없습니다. – user3184352
호프만 코드가 정확히 얼마나 많은 비트를 계산하는지 알고 싶다면 효과적으로 호프만 트리를 만들어야합니다. –
인코딩 된 심볼 당 정확한 비트 수를 원한다면 내 생각에 그 대답은 다음과 같다. - 허프 먼 트리를 만들고 정확한 비트 인코딩을 얻으려면 심볼 빈도 테이블 (히스토그램)을 사용해야한다. 각 기호에 대해 ...하지만이 추측에 대한 수학적 증거는 생각할 수 없습니다. –
설명해 주셔서 감사합니다 – user3184352