企业官网建设流程全解析

做餐厅网站的需求分析报告,带你做网站毕设,anydrag建站专家网站建设系统,网页怎么发布唯一可译码的判定 1.什么是唯一可译码 唯一可译码#xff1a; 码对于任意一个由编码符号组成的字符串#xff0c;都只能被唯一地翻译成对应的原始信源符号序列#xff0c;不存在两种及以上的不同解码结果 举例#xff1a; 我们用 3 类典型场景 举例#xff0c;清晰区分唯一…唯一可译码的判定1.什么是唯一可译码唯一可译码码对于任意一个由编码符号组成的字符串都只能被唯一地翻译成对应的原始信源符号序列不存在两种及以上的不同解码结果举例我们用3 类典型场景举例清晰区分唯一可译码和非唯一可译码同时覆盖「前缀码」「非前缀但唯一可译」「非唯一可译」三种情况方便你理解差异。一、 例子 1前缀码最典型的唯一可译码前缀码的核心规则任意一个编码都不是其他编码的前缀天然满足唯一可译性。场景设定信源符号S{A,B,C,D}编码方案信源符号编码A0B10C110D111唯一可译性验证任取一个编码串只能拆分成唯一的原始符号序列编码串010110→ 拆分0 | 10 | 110→ 对应符号A B C编码串111100→ 拆分111 | 10 | 0→ 对应符号D B A无任何歧义因为短编码如0不会是长编码如10的前缀解码时读到完整编码就能立即判定无需等待后续符号。哈夫曼编码就是这类前缀码也是工程中最常用的唯一可译码。二、 例子 2非前缀码但仍是唯一可译码这类编码不满足前缀码规则但通过 Sardinas-Patterson 算法判定后依然是唯一可译码解码无歧义。场景设定信源符号S{A,B,C}编码方案信源符号编码A01B10C001关键特征不满足前缀码编码01不是001的前缀10也不是其他编码的前缀 → 看起来不违反再换一个例子另一个经典非前缀唯一可译码C{01,11,011,111}编码01是011的前缀但它依然是唯一可译码唯一可译性验证取编码串0111只有一种拆分方式拆分 101 | 11→ 对应A B尝试拆分 2011 | ...→ 编码集合中没有011此例中011是编码那对应C但原串0111拆011后剩1无对应符号无其他有效拆分方式 → 无歧义。注这类编码的唯一可译性需要用Sardinas-Patterson 算法严格判定不能凭直觉判断。三、 例子 3非唯一可译码解码有歧义这类编码的核心问题同一个编码串可以拆分成两种及以上的原始符号序列。场景设定信源符号S{A,B}编码方案信源符号编码A0B01歧义验证取编码串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}$010$ → A B✅ 是非前缀码唯一可译{01,10,001}$010$ → 无效无0/ 无有效拆分✅ 是无歧义非唯一可译码{0,01}$01$无效/010101B❌ 否核心结论前缀码一定是唯一可译码但唯一可译码不一定是前缀码非唯一可译码的关键问题是「编码串存在多种有效拆分方式」工程中优先使用前缀码如哈夫曼编码因为解码效率高无需复杂算法判定。2.判定唯一可译码Sardinas-Patterson 算法一、 算法核心规则回顾给定编码集合 C0构造子集序列 C1,C2,C3…判定规则如下构造C1C1 是所有满足以下条件的非空后缀s的集合存在 ci,cj∈C0,ci\cj使得 cicj⋅scj 是 ci 的前缀 或 cjci⋅sci 是 cj 的前缀。构造Ck1k≥1Ck1是所有满足以下条件的非空后缀 **s′**的集合① 存在 c∈C0,s∈Ck使得 cs⋅s′ 或 sc⋅s′② s′ 不在 ⋃i0kCi 中避免重复。终止条件若任意 *Ck∩C0∅*所有子集与原编码集合无交集则 C0 是唯一可译码若存在某个 *Ck∩C0\∅*则 C0 是非唯一可译码若子集序列出现循环如 CmCn,mn则停止构造判定为唯一可译#构造C_kdefbuild_equivalence_class(C_prev,original_code):C_kset()# 遍历所有c∈原码集x∈上一轮等价类forcinoriginal_code:forxinC_prev:# 情况1c是x的前缀 → x去掉c的剩余部分加入Ckifx.startswith(c):remainderx[len(c):]ifremainder:C_k.add(remainder)# 情况2x是c的前缀 → c去掉x的剩余部分加入Ckelifc.startswith(x):remainderc[len(x):]ifremainder:C_k.add(remainder)returnC_k#判断唯一可译码defis_unique_decoding(code_list):#SP算法判断唯一可译码#判断编码集是否有重复iflen(code_list)!len(set(code_list)):returnFalseoriginal_codeset(code_list)seen_classes[]# 构造C1C1set()forc1inoriginal_code:forc2inoriginal_code:ifc1c2:continue# 判断c1是否是c2的前缀ifc2.startswith(c1):# 将c2去掉前缀得到剩余部分remainderc2[len(c1):]# 将剩余部分加入C1ifremainder:C1.add(remainder)current_classC1 seen_classes.append(current_class)whileTrue:# 判断当前类是否与原码集有交集ifcurrent_classoriginal_code:returnFalse# 终止条件2判断当前类是否为空ifnotcurrent_class:returnTruenext_classbuild_equivalence_class(current_class,original_code)# 判断当前类是否与已处理的类有交集ifnext_classinseen_classes:returnTrueseen_classes.append(next_class)current_classnext_class