我正在尝试为我的个人项目创建加密和解析器。
假设我加密拉丁字母如下:
a=a;
B=AB;
c=aab;
....
z=a…ab
在这种情况下,字符串“aaab”可以通过多种方式解密:
AC、AAB
但如果我按如下方式加密阿尔哈贝特:
a=a;
b=ab;
c=abb公司;
....
Z=A…BB
在这种情况下,任何字符串都可以用唯一的方式解密。
有没有一个算法或定理来描述这种行为?这是一个正确的加密还是对于一个很长的字符串,我可以通过某种方式获得模糊性。
最佳答案
你在寻找uniquely decodable代码。
唯一可解码代码的一个例子是prefix-free代码。也就是说,没有两个字符A
和B
使得encode(A)
是encode(B)
的前缀这比较容易检查。
如果您的代码没有前缀,则可以很容易地对其进行解码:只需获取与某个字符对应的编码字符串的唯一前缀。例如,Huffman code是用于压缩的无前缀代码的一个流行示例。
但是,相反的说法并不正确,因为第二个代码不是前缀自由的,但仍然是唯一可解码的有一些算法可以检查代码是否是唯一可解码的(例如in this presentation),但我不知道任何漂亮的重新格式化代码唯一可解码的一个要求是Kraft–McMillan inequalily,但对于非唯一可解码的代码(例如,您的第一个代码)也是如此。