是否有一种算法可以为给定范围内的每个条目找到最短的二进制表示?
Is there an algorithm to find the shortest binary representation for every entry within a given range?
我有一个编码方案,但我不知道它的名称。我知道必须有一种算法可以将 encode/decode 整数放入这个二进制方案中。方案如下:
1 2 3 4 5 6 7 8 9 etc.
0 - 0 0 00 00 00 00 000 000
1 1 10 01 01 01 010 001 001
2 11 10 10 100 011 010 010
3 11 110 101 100 011 011
4 111 110 101 100 100
5 111 110 101 101
6 111 110 110
7 111 1110
8 1111
etc.
示例:
当你有 6 个整数(0 到 5)的范围时,你可以使用第 6 列。这样你可以在数字 0 和 1 上节省一点。当使用第 9 列时,你将在除 7 和 1 之外的每个数字上节省一点8.
'you will save a bit'反对使用2、3、4或N位字。
我试过 Google 这个,但找不到合适的搜索关键字。有人能给我指出正确的方向吗?
谢谢!
这似乎是 Huffman Encoding,假定在任何给定范围内的所有值均匀分布。
因此,例如,第 5 列只是字符集 [0-5](含)的哈夫曼编码,它假定所有 6 个数字出现的概率相同。
我有一个编码方案,但我不知道它的名称。我知道必须有一种算法可以将 encode/decode 整数放入这个二进制方案中。方案如下:
1 2 3 4 5 6 7 8 9 etc.
0 - 0 0 00 00 00 00 000 000
1 1 10 01 01 01 010 001 001
2 11 10 10 100 011 010 010
3 11 110 101 100 011 011
4 111 110 101 100 100
5 111 110 101 101
6 111 110 110
7 111 1110
8 1111
etc.
示例: 当你有 6 个整数(0 到 5)的范围时,你可以使用第 6 列。这样你可以在数字 0 和 1 上节省一点。当使用第 9 列时,你将在除 7 和 1 之外的每个数字上节省一点8.
'you will save a bit'反对使用2、3、4或N位字。
我试过 Google 这个,但找不到合适的搜索关键字。有人能给我指出正确的方向吗?
谢谢!
这似乎是 Huffman Encoding,假定在任何给定范围内的所有值均匀分布。
因此,例如,第 5 列只是字符集 [0-5](含)的哈夫曼编码,它假定所有 6 个数字出现的概率相同。