【讨论】秘文的歧义到底有多少种？
将A-Z编码1－26，
甲编码：1111 送给乙，乙可以解释为：AAAA,AKA,AAK,KAA,KK四种情况
问对与甲的任意一个编码，乙一共有多少种输出？
这种情况大家怎么做哪？
我想用HUFFMAN编码的道理来做，建立1－26编码的树。
好想用分治法也可以！还是感觉不理想！
大家的意见哪？
问题点数：20、回复次数：7Top
1 楼xdspower（杂食菜熊）回复于 2005-01-01 23:42:44 得分 5
你的到底是一个编码还是一串编码，编码长度呢？
比如只发送了一个1，那当然只有一个输出。Top
2 楼baryjim（吃饭－睡觉－打豆豆）回复于 2005-01-02 11:12:06 得分 0
一串编码啊！！就是把一个句子编码！Top
3 楼dengsf（drklnk@Radical_Dreamer）回复于 2005-01-02 18:18:58 得分 10
设编码长度为n，
设 N(m) 表示在编码的从m到n的子串中 不同的解释数，
则答案就是 N（1）。
而 N(i) =
1 (i=n)
N(i+1) ( N[i]N[i+1] 不是有效的编码 ）
N(i+1)+N(i+2) (其它情况）Top
4 楼baryjim（吃饭－睡觉－打豆豆）回复于 2005-01-02 19:44:09 得分 0
动态规划！！我怎么没想到啊，真是差距啊！Top
5 楼mathe（）回复于 2005-01-04 08:42:27 得分 5
具体问题具体分析。
比如同样长度为2的串
31只有一种可能，26有两种可能。Top
6 楼xdspower（杂食菜熊）回复于 2005-01-04 21:50:21 得分 0
问题是对于长于2的串，由于有结合关系等，可能性就太多了！如果是用于通信的话，判断歧义的成本可能很高的，当然，作为密文那就是要求的了。Top
7 楼mathe（）回复于 2005-01-05 09:58:27 得分 0
呵呵，这个只是一种游戏而已，根本不能作为密文。实际上如果原文是普通文本，
通过那么使用字典，是很容易翻译的。Top
