Scheme 2 huffman BST의 최소값

Question

좋아요. 문자가 들어있는 쌍의 목록과 빈도 또는 텍스트에서 본 횟수가 주어졌습니다. (# \ a. 4) (# \ b. 2) (# \ c. 9)) 두 개의 최저 주파수를 어떻게 찾을 수 있습니까? 이걸 찾는 데 도움이되는 기능이 있습니까?

Answer 1

SICP 책의 §2.3.4 섹션을 살펴보면 처음부터 허프만 인코딩 트리를 구현하는 방법에 대한 완전한 설명을 찾을 수 있습니다. 만 주파수의 정렬되지 않은리스트 표현을 사용

이

(define frequencies '((#\a . 4) (#\b . 2) (#\c . 9))) 

(take 
(sort frequencies 
     (lambda (x y) 
     (< (cdr x) (cdr y)))) 
2) 

=> '((#\b . 2) (#\a . 4)) 

Answer 2

아마도 이에 대한 올바른 접근되지 않습니다 : 질문에 대해서는

는

, 여기에 지정된 형식 목록에서 두 가장 낮은 주파수를 찾기 위해 하나의 가능한 방법 문제. 이유는 다음과 같습니다. 반복적으로 최소값을 찾는 것이 허프만 인코딩 트리를 계산하는 주요 작업입니다. 이 최소 검색 작업을 반복하면서 전체 목록을 계속 검색하고 싶지는 않습니다.

문제의 첫 번째 공격은 최소 빠른 작업을 찾는 방법으로 정렬을 고려하십시오.

그러나이 특정 문제의 경우 컬렉션을 나타내는 데이터 구조 인 이진 heap을 사용해야합니다. 그것은 힙에서 최소 요소를 끌어내는 것이 정말 싼 속성을 가지고 있습니다. 호프만 트리 제작 과정에서 컬렉션에 새로운 요소를 넣으면 끝나게됩니다. 당신은 명부를 계속해서 또 다시 의지하고는 싶지 않다.

라켓에는 표준 라이브러리에있는 data/heap 컬렉션의 바이너리 힙 구현이 있습니다. 허프 먼 트리 구축에 대한 적용은 매우 간단합니다. 다음은 힙의 기본 알고리즘을 구현합니다

(require data/heap) 

;; ... 

;; make-huffman-tree: (listof leaf) -> node 
(define (make-huffman-tree leaves) 
    (define a-heap (make-heap node<=?)) 
    (heap-add-all! a-heap leaves) 
    (for ([i (in-range (sub1 (length leaves)))]) 
    (define min-1 (heap-min a-heap)) 
    (heap-remove-min! a-heap) 
    (define min-2 (heap-min a-heap)) 
    (heap-remove-min! a-heap) 
    (heap-add! a-heap (merge (+ (frequency min-1) (frequency min-2)) 
          min-1 min-2))) 
    (heap-min a-heap)) 

자유 변수 node<=?이 주파수에 의해 비교하는 방법을 알고하기위한 것입니다, 그리고 merge이 두 가지를 가지고 함께 할 수 있도록하기위한 것입니다.

make-huffman-tree에서 허프만 트리 구조의 핵심을 볼 수 있습니다. 힙을 사용하여 두 개의 최소 요소를 추출하고 병합 한 다음 결과를 다시 힙에 넣습니다. 우리가 하나의 나무가 남을 때까지 반복하십시오.