唯一可译码的判定
1.什么是唯一可译码
唯一可译码：
码对于任意一个由编码符号组成的字符串，都只能被唯一地翻译成对应的原始信源符号序列，不存在两种及以上的不同解码结果
举例：
我们用3 类典型场景举例，清晰区分唯一可译码和非唯一可译码，同时覆盖「前缀码」「非前缀但唯一可译」「非唯一可译」三种情况，方便你理解差异。
一、 例子 1：前缀码（最典型的唯一可译码）
前缀码的核心规则：任意一个编码都不是其他编码的前缀，天然满足唯一可译性。
场景设定
信源符号：S={A,B,C,D}
编码方案：
| 信源符号 | 编码 |
|---|---|
| A | 0 |
| B | 10 |
| C | 110 |
| D | 111 |
唯一可译性验证
任取一个编码串，只能拆分成唯一的原始符号序列：
- 编码串
010110→ 拆分：0 | 10 | 110→ 对应符号：A B C - 编码串
111100→ 拆分：111 | 10 | 0→ 对应符号：D B A
无任何歧义，因为短编码（如0）不会是长编码（如10）的前缀，解码时读到完整编码就能立即判定，无需等待后续符号。
哈夫曼编码就是这类前缀码，也是工程中最常用的唯一可译码。
二、 例子 2：非前缀码，但仍是唯一可译码
这类编码不满足前缀码规则，但通过 Sardinas-Patterson 算法判定后，依然是唯一可译码（解码无歧义）。
场景设定
信源符号：S={A,B,C}
编码方案：
| 信源符号 | 编码 |
|---|---|
| A | 01 |
| B | 10 |
| C | 001 |
关键特征（不满足前缀码）
编码
01不是
001的前缀，
10也不是其他编码的前缀 → 看起来不违反？再换一个例子：
另一个经典非前缀唯一可译码：
C={01,11,011,111}
- 编码
01是011的前缀，但它依然是唯一可译码！
- 编码
唯一可译性验证
取编码串0111，只有一种拆分方式：
- 拆分 1：
01 | 11→ 对应A B - 尝试拆分 2：
011 | ...→ 编码集合中没有011（此例中011是编码，那对应C，但原串0111拆011后剩1，无对应符号） - 无其他有效拆分方式 → 无歧义。
注：这类编码的唯一可译性需要用Sardinas-Patterson 算法严格判定，不能凭直觉判断。
三、 例子 3：非唯一可译码（解码有歧义）
这类编码的核心问题：同一个编码串可以拆分成两种及以上的原始符号序列。
场景设定
信源符号：S={A,B}
编码方案：
| 信源符号 | 编码 |
|---|---|
| A | 0 |
| B | 01 |
歧义验证
取编码串01，存在两种有效拆分方式：
直接匹配编码
01→ 对应符号B拆分为
0 | 1→ 前半段
0对应
A，后半段
1无对应符号（若补充编码
1→C，则变成
A C）
若编码集合改为 C={0,01,1}，则编码串
01可拆分为
A C或
B→ 完全歧义。
另一经典反例
编码方案：C={1,11,111}
编码串111的拆分方式：
1 | 1 | 11 | 1111 | 11114 种拆分方式
，完全不满足唯一可译性。
四、 例子总结对比表
| 编码类型 | 例子编码集合 | 编码串010的拆分结果 | 唯一可译性 | |
|---|---|---|---|---|
| 前缀码（唯一可译） | {0,10,110} | $0 | 10$ → A B | ✅ 是 |
| 非前缀码（唯一可译） | {01,10,001} | $01 | 0$ → 无效（无0）/ 无有效拆分 | ✅ 是（无歧义） |
| 非唯一可译码 | {0,01} | $0 | 1$（无效）/010101（B） | ❌ 否 |
核心结论
- 前缀码一定是唯一可译码，但唯一可译码不一定是前缀码；
- 非唯一可译码的关键问题是「编码串存在多种有效拆分方式」；
- 工程中优先使用前缀码（如哈夫曼编码），因为解码效率高，无需复杂算法判定。
2.判定唯一可译码
Sardinas-Patterson 算法
一、 算法核心规则回顾
给定编码集合 C0，构造子集序列 C1,C2,C3…，判定规则如下：
构造C1：
C1 是所有满足以下条件的非空后缀s的集合：
存在 ci,cj∈C0,ci\=cj，使得 ci=cj⋅s（cj 是 ci 的前缀） 或 cj=ci⋅s（ci 是 cj 的前缀）。
构造Ck+1（k≥1）：
Ck+1是所有满足以下条件的非空后缀 **s′**的集合：
① 存在 c∈C0,s∈Ck，使得 c=s⋅s′ 或 s=c⋅s′；
② s′ 不在 ⋃i=0kCi 中（避免重复）。
终止条件：
- 若任意 *Ck∩C0=∅*（所有子集与原编码集合无交集），则 C0 是唯一可译码；
- 若存在某个 *Ck∩C0\=∅*，则 C0 是非唯一可译码；
- 若子集序列出现循环（如 Cm=Cn,m<n），则停止构造，判定为唯一可译
#构造C_kdefbuild_equivalence_class(C_prev,original_code):C_k=set()# 遍历所有c∈原码集，x∈上一轮等价类forcinoriginal_code:forxinC_prev:# 情况1：c是x的前缀 → x去掉c的剩余部分加入Ckifx.startswith(c):remainder=x[len(c):]ifremainder:C_k.add(remainder)# 情况2：x是c的前缀 → c去掉x的剩余部分加入Ckelifc.startswith(x):remainder=c[len(x):]ifremainder:C_k.add(remainder)returnC_k#判断唯一可译码defis_unique_decoding(code_list):#SP算法判断唯一可译码#判断编码集是否有重复iflen(code_list)!=len(set(code_list)):returnFalseoriginal_code=set(code_list)seen_classes=[]# 构造C1C1=set()forc1inoriginal_code:forc2inoriginal_code:ifc1==c2:continue# 判断c1是否是c2的前缀ifc2.startswith(c1):# 将c2去掉前缀，得到剩余部分remainder=c2[len(c1):]# 将剩余部分加入C1ifremainder:C1.add(remainder)current_class=C1 seen_classes.append(current_class)whileTrue:# 判断当前类是否与原码集有交集ifcurrent_class&original_code:returnFalse# 终止条件2：判断当前类是否为空ifnotcurrent_class:returnTruenext_class=build_equivalence_class(current_class,original_code)# 判断当前类是否与已处理的类有交集ifnext_classinseen_classes:returnTrueseen_classes.append(next_class)current_class=next_class
