逆霍夫曼算法？ [英] Reverse Huffman's algorithm?

问题描述

我有类似霍夫曼编码的问题，我不确定该如何解决，或者不确定霍夫曼编码是反向的。但这绝对可以用贪婪的方法解决。

---

考虑一组长度，每个长度与一个概率相关。即

  X = {a1 =（100,1 / 4），a2 =（500,1 / 4），a3 = （200,1 / 2）} 
  

显然，所有概率之和= 1 。

将长度从起点开始依次排列。

例如： {a2，a1，a3} 从头到尾的顺序。

定义元素 a_i 的成本，即元素从起始行到末尾的总长度乘以其概率。

因此根据先前的安排：

  cost（a2）=（500）*（1 / 4）
成本（a1）=（500 + 100）*（1/4）
成本（a3）=（500 + 100 + 200）*（1/2）
  

将总费用定义为所有费用之和。例如成本（X）=成本（a2）+成本（a1）+成本（a3）。给出一个算法，该算法可以找到使 cost（X）

---

<我已经试过形成一些霍夫曼树，但这是行不通的。

按概率排序将失败（考虑X = {（100,0.4），（300,0.6）}）。

按长度排序也将失败（考虑X = {（100,0.1），（300,0.9）}）。

如果有人可以帮助或暗示最佳求解算法，那就太好了。

解决方案

考虑一下交换两个相邻元素会发生什么。这两个元素之前和之后的计算相同，因此仅取决于两个元素。

将两个元素孤立地考虑，成本为P1L1 + P2（L1 + L2）和P2L2 + P1（L1 + L2）。如果您减去这个并简化我是否有代数的权利，那么您想在L1 / P1< P≤1时首先交换1。 L2 / P2。检查-当L1 = 0时，至少可以得到正确的答案。

所以我认为您想按Li / Pi的升序对元素进行排序，因为不能通过交换相邻元素来改善答案。

I have a problem simlar to Huffman's encoding, I'm not sure exactly how it can be solved or if it is a reverse Huffman's encoding. But it definitely can be solved using a greedy approach.

---

Consider a set of length, each associated with a probability. i.e.

X={a1=(100,1/4),a2=(500,1/4),a3=(200,1/2)}

Obviously, the sum of all the probabilities = 1.

Arrange the lengths together on a line one after the other from a starting point.

For example: {a2,a1,a3} in that order from start to finish.

Define the cost of an element a_i as its the total length from the starting line to the end of this element multiplied by its probability.

So from the previous arrangement:

cost(a2) = (500)*(1/4)
cost(a1) = (500+100)*(1/4)
cost(a3) = (500+100+200)*(1/2)

Define the total cost as the sum of all costs. e.g. cost(X) = cost(a2) + cost(a1) + cost(a3). Give an algorithm that finds an arrangement that minimizes cost(X)

---

I've tried forming some alternative huffman trees but it doesn't work.

Sorting by probability will fail (consider X={(100,0.4),(300,0.6)}).

Sorting by length will also fail (consider X={(100,0.1),(300,0.9)}).

If anyone can help or hint towards an optimal solution algorithm, it would be great.

解决方案

Consider what happens if you swap two adjacent elements. The calculations before and after the two elements are the same, so it just depends on the two elements.

Taking two elements in isolation, the costs are P1L1 + P2(L1 + L2) and P2L2 + P1(L1 + L2). If you subtract this and simplify if I have got the algebra right you want to swap 1 to first when L1/P1 < L2/P2. Check - this at least gets the right answer when L1 = 0.

So I think you want to sort the elements into increasing order of Li/Pi, because if that is not the case you can improve the answer by swapping adjacent elements.

这篇关于逆霍夫曼算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！