从霍夫曼树中获得配对 [英] get pairs out of a huffman tree

问题描述

我正在尝试编写一个霍夫曼叶程序；该过程从已创建的霍夫曼树中返回配对列表. 有关其运行方式的示例

I'm trying to write a procedure Huffman-leaves; the procedure returns a list of pairs from a created huffman tree. Example on how it runs

  (huffman-leaves sample-tree) 
   ->((A . 8) (C . 5) (B . 1) (D . 1))

我想出了什么但被作家挡住了...

What I've comed up with but got writers block...

(define (huffman-leaves tree)
  (define (huffman-get-pairs current-branch pairs)
     (if (or (null? tree) (null? current-branch))
         pairs
         (let ((next-branch
                (get-branch (car current-branch) current-branch)))
           (not (member? next-branch pairs)
                (if (leaf? next-branch)
                    (cons (append  pairs next-branch)
                          (display pairs)
                          (huffman-get-pairs (cadr current-branch) pairs))
                    (huffman-get-pairs next-branch pairs))))))
  (huffman-get-pairs tree '()))

  (member? item 'list) #if item in list return #t else #false

我知道我做错了什么，但看不到. 如何在方案中的霍夫曼树中停止搜索?我应该做些不同的提示吗?

I know that I'm doing something wrong but I can't see it. How can I stop a search in a huffman-tree in scheme? Any tip that I should be doing different?

推荐答案

我建议:

1. 写霍夫曼树的数据定义

1. Write a data definition for Huffman Tree

使用输入霍夫曼树作为示例，这些树根据第1步中的数据定义进行编码，并输出预期结果(在这种情况下为叶子列表).

Make example input huffman trees, encoded according to your data definition from step 1, and expected outputs (lists of leaves, in this case).

按照设计秘诀建立huffman-leaves函数的基本模板.

Follow the design recipe to build a basic template for the huffman-leaves function.

根据您从第2步构建的示例，在模板的...中填充.

Fill in the ... in your template according to the examples you built from step 2.

将第2步中的示例转换为测试，并从第4步中测试代码.

Translate your examples from step 2. into tests, and test your code from step 4.

很抱歉，上面的内容含糊不清，但这是我迄今为止可以提供的关于细节(或缺乏细节)水平的最佳建议.如果您可以提供上述步骤的答案，并明确说出您被阻止的那一步，那么我们可以帮助您以更系统的方式克服您的作家的阻碍.

Sorry if the above seems vague, but it is the best advice I can give with the level of detail (or lack thereof) you have supplied in this question thus far. If you can provide answers for the steps above, and say explicitly which step you are blocked on, then we can help you get over your writers block in a more systematic way.

如果您喜欢真实的代码，可以按照以下说明为您的问题提供非常通用的解决方案:

If you prefer real code, here is one direction you could go in to make a very generic solution for your problem:

;; make-visitor : (X -> Y) (X -> [Listof X]) (Y [Listof Z] -> Z) -> Z
;; Very generic descend+map+recombine routine
;; (note X, Y, Z are implicitly universally quantified above).
(define (make-visitor transform children combine)
  (lambda (x)
    (let rec ((x x)) ;; rec : X -> Z
      (combine (transform x)
               (map rec (children x))))))

;; ... the hard bit is coming up with the appropriate lambda
;; expressions for `transform`, `children`, and `combine` above.

(define leaves
  (make-visitor (lambda (x) ...)
                (lambda (x) ...)
                (lambda (y zs) ...)))

实际上，我不建议您尝试直接跳转到这种形式的解决方案.如果您尝试遵循设计秘诀并直接解决问题，那么您会得到更好的选择.但是，一旦完成此操作，就可以进行教育性的练习，看看是否可以将自己的解决方案改型为上述通用例程.

I don't actually recommend trying to jump directly to a solution of this form; you will be better off if you try to follow the design recipe and make a direct solution to your problem. But once you have done that, it can be an educational exercise to see if you can retrofit your own solution onto the generic routine above.

这篇关于从霍夫曼树中获得配对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！