普林斯顿算法讲义（三）（4)

普林斯顿算法讲义（三）(3)https://developer.aliyun.com/article/1484208

上述示例是人为的，但它们展示了大多数正则表达式库中的一个令人担忧��缺陷。在实践中确实会出现不良输入。根据Crosby 和 Wallach的说法，以下正则表达式出现在 SpamAssassin 的一个版本中，这是一个功能强大的垃圾邮件过滤程序。

[a-z]+@[a-z]+([a-z\.]+\.)+[a-z]+

它试图匹配某些电子邮件地址，但在许多正则表达式库中，包括 Sun 的 Java 1.4.2 中，匹配某些字符串需要指数级的时间。

java Validate "[a-z]+@[a-z]+([a-z\.]+\.)+[a-z]+" spammer@x......................

这尤其重要，因为垃圾邮件发送者可以使用一种病态的返回电子邮件地址来拒绝服务攻击一个运行 SpamAssassin 的邮件服务器。这个特定的模式现在已经修复，因为 Perl 5 正则表达式使用内部缓存来在回溯过程中在相同位置短路重复匹配。

这些缺陷不仅限于 Java 的实现。例如，GNU regex-0.12 对于匹配形式为aaaaaaaaaaaaaac的字符串与正则表达式(a*)*|b*需要指数级的时间。Sun 的 Java 1.4.2 同样容易受到这个问题的影响。此外，Java 和 Perl 正则表达式支持反向引用 - 对于这些扩展正则表达式的正则表达式模式匹配问题是NP 难的，因此在某些输入上这种指数级的增长似乎是固有的。

这是我实际写的一个，用来找到字符串NYSE之前的最后一个单词：regexp = “([\w\s]+).*NYSE”;

参考：正则表达式匹配可以简单快速（但在 Java、Perl、PHP、Python、Ruby 等中很慢）。比较了 Thompson NFA 和回溯方法。包含了一些针对 Thompson NFA 的性能优化。还有一些历史注释和参考资料。

Q + A

Q. Java 正则表达式库的文档？

A. 这里是 Oracle 关于使用正则表达式的指南。它包括更多操作，我们不会探索。还请参阅String方法matches()、split()和replaceAll()。这些是使用Pattern和Matcher类的简写。这里有一些常见的正则表达式模式。

Q. 用于电子邮件地址、Java 标识符、整数、小数等的工业级别正则表达式？

A. 这里有一个有用的正则表达式库，提供了工业级别的模式，用于匹配电子邮件地址、URL、数字、日期和时间。试试这个正则表达式工具。

Q. 我困惑为什么(a | b)*匹配所有的 a 和 b 的字符串，而不仅仅是所有 a 的字符串或所有 b 的字符串？

A. *操作符复制正则表达式（而不是匹配正则表达式的固定字符串）。因此，上述等同于ε | (a|b) | (a|b)(a|b) | (a|b)(a|b)(a|b) | …

Q. 历史？

A. 在 1940 年代，沃伦·麦卡洛克和沃尔特·皮茨将神经元建模为有限自动机来描述神经系统。1956 年，史蒂夫·克利纳发明了一种数学抽象称为正则集来描述这些模型。神经网络和有限自动机中事件的表示，《自动机研究》，3-42 页，普林斯顿大学出版社，新泽西州普林斯顿，1956 年。

Q. 有哪些可视化正则表达式的工具？

A. 尝试Debuggerx。

练习

1. 为以下每组二进制字符串编写正则表达式。只使用基本操作。

1. 0 或 11 或 101
   
2. 只有 0
   

2. 答案：0 | 11 | 101, 0*
   
3. 为以下每组二进制字符串编写正则表达式。只使用基本操作。

1. 所有二进制字符串
   
2. 所有二进制字符串，除了空字符串
   
3. 以 1 开头，以 1 结尾
   
4. 以 00 结尾
   
5. 包含至少三个 1
   

4. 答案：(0|1), (0|1)(0|1), 1 | 1(0|1)*1, (0|1)*00, (0|1)1(0|1)1(0|1)1(0|1)或 010101(0|1)。
   
5. 编写一个正则表达式描述字母表{a, b, c}上按排序顺序的输入。答案：abc*。
   
6. 为以下每组二进制字符串编写正则表达式。只使用基本操作。

1. 包含至少三个连续的 1
   
2. 包含子串 110
   
3. 包含子串 1101100
   
4. 不包含子串 110
   

7. 答案：(0|1)111(0|1), (0|1)110(0|1), (0|1)1101100(0|1), (0|10)1。最后一个是最棘手的。
   
8. 为至少有两个 0 但不连续的 0 的二进制字符串编写正则表达式。
   
9. 为以下每组二进制字符串编写正则表达式。只使用基本操作。

1. 至少有 3 个字符，并且第三个字符为 0
   
2. 0 的数量是 3 的倍数
   
3. 以相同字符开头和结尾
   
4. 奇数长度
   
5. 以 0 开头且长度为奇数，或以 1 开头且长度为偶数
   
6. 长度至少为 1 且最多为 3
   

10. 答案：(0|1)(0|1)0(0|1), 1 | (1010101), 1(0|1)1 | 0(0|1)0 | 0 | 1, (0|1)((0|1)(0|1)), 0((0|1)(0|1)) | 1(0|1)((0|1)(0|1)), (0|1) | (0|1)(0|1) | (0|1)(0|1)(0|1)。
    
11. 对于以下每个问题，指出有多少长度为 1000 的位字符串与正则表达式匹配：0(0 | 1)*1，0*101*，(1 | 01)*。
    
12. 编写一个正则表达式，匹配字母表{a, b, c}中包含的所有字符串：

1. 以 a 开头且以 a 结尾
   
2. 最多一个 a
   
3. 至少有两个 a
   
4. 偶数个 a
   
5. a 的数量加上 b 的数量为偶数
   

13. 找出字母按字母顺序排列的长单词，例如，almost和beefily。答案：使用正则表达式’^abcdefghijklmnopqrstuvwxyz$'。
    
14. 编写一个 Java 正则表达式，匹配电话号码，带有或不带有区号。区号应为(609) 555-1234 或 555-1234 的形式。
    
15. 找出所有以nym结尾的英语单词。
    
16. 找出所有包含三连字母bze的英语单词。答案：subzero。
    
17. 找出所有以 g 开头，包含三连字母pev且以 e 结尾的英语单词。答案：grapevine。
    
18. 找出所有包含三个 r 且至少有两个 r 的英语单词。
    
19. 找出可以用标准键盘顶行写出的最长英语单词。答案：proprietorier。
    
20. 找出所有包含字母 a、s、d 和 f 的单词，不一定按照顺序。解决方案：cat words.txt | grep a | grep s | grep d | grep f。
    
21. 给定一个由 A、C、T 和 G 以及 X 组成的字符串，找到一个字符串，其中 X 匹配任何单个字符，例如，CATGG 包含在 ACTGGGXXAXGGTTT 中。
    
22. 编写一个 Java 正则表达式，用于 Validate.java，验证形式为 123-45-6789 的社会安全号码。提示：使用\d表示任何数字。答案：[0-9]{3}-[0-9]{2}-[0-9]{4}。
    
23. 修改上一个练习，使-成为可选项，这样 123456789 就被视为合法输入。
    
24. 编写一个 Java 正则表达式，匹配包含恰好五个元音字母且元音字母按字母顺序排列的所有字符串。 答案: [^aeiou]*a[^aeiou]*e[^aeiou]*i[^aeiou]*o[^aeiou]*u[^aeiou]*
    
25. 编写一个 Java 正则表达式，匹配有效的 Windows XP 文件名。这样的文件名由除了冒号以外的任意字符序列组成。

/ \ : * ? " < > |

1. 此外，它不能以空格或句号开头。
2. 编写一个 Java 正则表达式，描述有效的 OS X 文件名。这样的文件名由除冒号以外的任意字符序列组成。此外，它不能以句点开头。
   
3. 给定一个代表 IP 地址的名称为s的字符串，采用dotted quad表示法，将其分解为其组成部分，例如，255.125.33.222。确保四个字段都是数字。
   
4. 编写一个 Java 正则表达式，描述形式为Month DD, YYYY的所有日期，其中Month由任意大写或小写字母字符串组成，日期是 1 或 2 位数字，年份正好是 4 位数字。逗号和空格是必需的。
   
5. 编写一个 Java 正则表达式，描述形式为 a.b.c.d 的有效 IP 地址，其中每个字母可以表示 1、2 或 3 位数字，句点是必需的。是：196.26.155.241。
   
6. 编写一个 Java 正则表达式，匹配以 4 位数字开头并以两个大写字母结尾的车牌。
   
7. 编写一个正则表达式，从 DNA 字符串中提取编码序列。它以 ATG 密码子开头，以停止密码子（TAA、TAG 或 TGA）结尾。参考
   
8. 编写一个正则表达式来检查序列 rGATCy：即，它是否以 A 或 G 开头，然后是 GATC，最后是 T 或 C。
   
9. 编写一个正则表达式来检查一个序列是否包含两个或更多次重复的 GATA 四核苷酸。
   
10. 修改 Validate.java 使搜索不区分大小写。 提示: 使用(?i)嵌入式标志。
    
11. 编写一个 Java 正则表达式，匹配利比亚独裁者穆阿迈尔·卡扎菲姓氏的各种拼写，使用以下模板：(i)以 K、G、Q 开头，(ii)可选地跟随 H，(iii)后跟 AD，(iv)可选地跟随 D，(v)可选地跟随 H，(vi)可选地跟随 AF，(vii)可选地跟随 F，(vii)以 I 结尾。
    
12. 编写一个 Java 程序，读取类似(K|G|Q)[H]AD[D][H]AF[F]I的表达式，并打印出所有匹配的字符串。这里的符号[x]表示字母x的 0 或 1 个副本。
    
13. 为什么s.replaceAll("A", "B");不会替换字符串s中所有出现的字母 A 为 B？
    答案：使用s = s.replaceAll("A", "B");代替。replaceAll方法返回结果字符串，但不会改变s本身。字符串是不可变的。
    
14. 编写一个程序 Clean.java，从标准输入中读取文本并将其打印出来，在一行上去除任何尾随空格，并用 4 个空格替换所有制表符。
    提示: 使用replaceAll()和正则表达式\s匹配空格。
    
15. 编写一个正则表达式，匹配在文本a href ="和下一个"之间的所有文本。 答案: href=\"(.*?)\"。?使.*变得不贪婪而是懒惰。在 Java 中，使用Pattern.compile("href=\\\"(.*?)\\\"", Pattern.CASE_INSENSITIVE)来转义反斜杠字符。
    
16. 使用正则表达式提取在<title>和<\title>标签之间的所有文本。(?i)是另一种使匹配不区分大小写的方法。$2指的是第二个捕获的子序列，即title标签之间的内容。

String pattern = "(?i)(<title.*?>)(.+?)(</title>)"; 
String updated =  s.replaceAll(pattern, "$2");

1. 编写一个正则表达式来匹配在<TD …>和标签之间的所有文本。 答案：<TD[^>]*>([^<]*)</TD>
   

创意练习

1. FMR-1 三联重复区域。 “人类 FMR-1 基因序列包含一个三联重复区域，在该区域中序列 CGG 或 AGG 重复多次。三联体的数量在个体之间高度变化，增加的拷贝数与脆性 X 综合征相关，这是一种导致 2000 名儿童中的一名智力残疾和其他症状的遗传疾病。”（参考：Durbin 等人的《生物序列分析》）。该模式由 GCG 和 CTG 括起来，因此我们得到正则表达式 GCG (CGG | AGG)* CTG。
   
2. 广告拦截。 Adblock 使用正则表达式来阻止 Mozilla 和 Firebird 浏览器下的横幅广告。
   
3. 解析文本文件。 一个更高级的例子，我们想要提取匹配输入的特定部分。这个程序代表了解析科学输入数据的过程。
   
4. PROSITE 到 Java 正则表达式。 编写一个程序，读取 PROSITE 模式并打印出相应的 Java 正则表达式。PROSITE 是蛋白质家族和结构域的“第一个和最著名”的数据库。其主要用途是确定从基因组序列翻译而来的未知功能蛋白质的功能。生物学家使用PROSITE 模式语法规则在生物数据中搜索模式。这是CBD FUNGAL（访问代码 PS00562）的原始数据。每行包含各种信息。也许最有趣的一行是以 PA 开头的行 - 它包含描述蛋白质基序的模式。这些模式很有用，因为它们通常对应于功能或结构特征。

PA   C-G-G-x(4,7)-G-x(3)-C-x(5)-C-x(3,5)-[NHG]-x-[FYWM]-x(2)-Q-C.

1. 每个大写字母对应一个氨基酸残基。字母表由对应于 2x 氨基酸的大写字母组成。连字符-表示连接。例如，上面的模式以 CGG（Cys-Gly-Gly）开头。符号x扮演通配符的角色 - 它匹配任何氨基酸。这对应于我们符号中的.。括号用于指定重复：x(2)表示恰好两个氨基酸，x(4,7)表示 4 到 7 个氨基酸。这对应于 Java 符号中的.{2}和.{4,7}。花括号用于指定禁止的残基：{CG}表示除 C 或 G 之外的任何残基。星号具有其通常的含义。
2. 文本转语音合成。 grep 的原始动机。“例如，如何处理发音多种不同的二连音 ui：fruit, guile, guilty, anguish, intuit, beguine？”
   
3. 具有挑战性的正则表达式。为以下每组二进制字符串编写一个正则表达式。只使用基本操作。

1. 除了 11 或 111 之外的任何字符串
   
2. 每个奇数符号是 1
   
3. 包含至少两个 0 和最多一个 1
   
4. 没有连续的 1s
   

4. 二进制可被整除。为以下每组二进制字符串编写一个正则表达式。只使用基本操作。

1. 以二进制数解释的比特串可被 3 整除
   
2. 以二进制数解释的比特串可被 123 整除
   

5. 波士顿口音。 编写一个程序，将所有的 r 替换为 h，将句子翻译成波士顿版本，例如将“Park the car in Harvard yard”翻译为波士顿版本的“Pahk the cah in Hahvahd yahd”。
   
6. 文件扩展名。 编写一个程序，以文件名作为命令行参数，并打印出其文件类型扩展名。扩展名是跟在最后一个.后面的字符序列。例如，文件sun.gif的扩展名是gif。提示：使用split("\\.")；请记住.是一个正则表达式元字符，因此您需要转义它。
   
7. 反向子域。 为了进行网络日志分析，方便地根据子域（如wayne.faculty.cs.princeton.edu）组织网络流量。编写一个程序来读取域名并以反向顺序打印出来，如edu.princeton.cs.faculty.wayne。
   
8. 银行抢劫。 你刚刚目睹了一起银行抢劫案，并且得到了逃跑车辆的部分车牌号。它以ZD开头，中间有一个3，以V结尾。帮助警官写出这个车牌的正则表达式。
   
9. 排列的正则表达式。 找到 N 个元素的所有排列集合的最短正则表达式（仅使用基本操作），其中 N = 5 或 10。例如，如果 N = 3，则语言是 abc，acb，bac，bca，cab，cba。*答案：*困难。解决方案的长度与 N 呈指数关系。
   
10. 解析带引号的字符串。 读取一个文本文件并打印出所有带引号的字符串。使用类似"[^"]*"的正则表达式，但需要担心转义引号。
    
11. 解析 HTML。 一个>，可选地跟随空格，后跟a，后跟空格，后跟href，可选地跟随空格，后跟=，可选地跟随空格，后跟"http://，后跟字符直到"，可选地跟随空格，然后是一个<。

< \s* a \s+ href \s* = \s* \\"http://[^\\"]* \\" \s* >

1. 子序列。 给定一个字符串s，确定它是否是另一个字符串t的子序列。例如，abc 是 achfdbaabgabcaabg 的一个子序列。使用正则表达式。现在不使用正则表达式重复这个过程。答案：(a) a.*b.c.，(b) 使用贪婪算法。
   
2. 亨廷顿病诊断。 导致亨廷顿病的基因位于染色体 4 上，并且具有可变数量的 CAG 三核苷酸重复。编写一个程序来确定重复次数并打印不会患 HD，如果重复次数少于 26，则打印后代有风险，如果数字为 37-35，则打印有风险，如果数字在 36 和 39 之间，则打印将患 HD。这就是遗传测试中识别亨廷顿病的方式。
   
3. 基因查找器。 基因是基因组的一个子字符串，以起始密码子（ATG）开始，以终止密码子（TAG，TAA，TAG 或 TGA）结束，并由除起始或终止密码子之外的密码子序列（核苷酸三联体）组成。基因是起始和终止密码子之间的子字符串。
   
4. 重复查找器。 编写一个程序Repeat.java，它接受两个命令行参数，并查找指定由第二个命令行参数指定的文件中第一个命令行参数的最大重复次数。
   
5. 字符过滤器。 给定一个包含坏字符的字符串t，例如t = "!@#$%^&*()-_=+"，编写一个函数来读取另一个字符串s并返回删除所有坏字符后的结果。

String pattern = "[" + t + "]";
String result  = s.replaceAll(pattern, "");

1. 通配符模式匹配器。 不使用 Java 内置的正则表达式，编写一个程序 Wildcard.java 来查找与给定模式匹配的字典中的所有单词。特殊符号匹配任意零个或多个字符。因此，例如模式"ward"匹配单词"ward"和"wildcard"。特殊符号.匹配任何一个字符。您的程序应将模式作为命令行参数读取，并从标准输入读取单词列表（由空格分隔）。
   
2. 通配符模式匹配器。 重复上一个练习，但这次使用 Java 内置的正则表达式。*警告：*在通配符的上下文中，*的含义与正则表达式不同。
   
3. 搜索和替换。 文字处理器允许您搜索给定查询字符串的所有出现并用另一个替换字符串替换每个出现。编写一个程序 SearchAndReplace.java，它接受两个字符串作为命令行输入，从标准输入读取数据，并用第一个字符串替换所有出现的第一个字符串，并将结果发送到标准输出。*提示：*使用方法String.replaceAll。
   
4. 密码验证器。 假设出于安全原因，您要求所有密码至少包含以下字符之一

~ ! @ # $ % ^ & * | 

1. 为String.matches编写一个正则表达式，如果密码包含所需字符之一，则返回true。答案：“^[~!@#%^&*|]+”
2. 字母数字过滤器。 编写一个程序 Filter.java，从标准输入中读取文本，并消除所有不是空格或字母数字的字符。答案 这是关键行。

String output = input.replaceAll("[^\\s0-9a-zA-Z]", "");

1. 将制表符转换为空格。 编写一个程序，将 Java 源文件中的所有制表符转换为 4 个空格。
   
2. 解析分隔文本文件。 存储数据库的一种流行方式是将其存储在一个文本文件中，每行一个记录，每个字段由称为分隔符的特殊字符分隔。

19072/Narberth/PA/Pennsylvania
08540/Princeton/NJ/New Jersey

1. 编写一个程序 Tokenizer.java，它读取两个命令行参数，一个是分隔符字符，另一个是文件名，并创建一个标记数组。
2. 解析分隔文本文件。 重复上一个练习，但使用String库方法split()。
   
3. 检查文件格式。
   
4. 拼写错误。 编写一个 Java 程序，验证这个常见拼写错误列表中只包含形式为的行

misdemenors (misdemeanors)
mispelling (misspelling)
tennisplayer (tennis player)

1. 第一个单词是拼写错误，括号中的字符串是可能的替换。
2. 有趣的英语单词
   
3. DFA 的大小与 RE 的大小呈指数关系。 给出一个 RE，用于表示所有最后一个字符为 1 的比特串集合。RE 的大小应该与 k 成线性关系。现在，给出同一组比特串的 DFA。它使用了多少个状态？
   提示：对于这组比特串，每个确定有限自动机（DFA）至少需要有 2^k 个状态。
   

5.5 数据压缩

原文：algs4.cs.princeton.edu/55compression

译者：飞龙

协议：CC BY-NC-SA 4.0

本节正在大规模施工中。

数据压缩：将文件大小缩小以节省空间存储和在传输时节省时间。摩尔定律：芯片上的晶体管数量每 18-24 个月翻一番。帕金森定律：数据会扩张以填满可用空间。文本、图像、声音、视频等。维基百科提供公共转储以供学术研究和再发布。使用 bzip 和 SevenZip 的 LZMA。对 300GB 数据进行压缩可能需要一周的时间。

古代思想。

摩尔斯电码，十进制数系统，自然语言，旋转电话（较低的号码拨号速度更快，所以纽约是 212，芝加哥是 312）。

二进制输入和输出流。

我们使用 BinaryStdIn.java、BinaryStdOut.java、BinaryDump.java、HexDump.java 和 PictureDump.java。

固定长度编码。

需要 ceil(lg R) 位来指定 R 个符号中的一个。Genome.java。使用 Alphabet.java。

运行长度编码。

RunLength.java。

变长编码。

希望有唯一可解码的编码。实现这一目标的一种方法是向每个码字附加一个特殊的停止符号。更好的方法是前缀无码：没有字符串是另一个字符串的前缀。例如，{ 01, 10, 0010, 1111 } 是前缀无码，但 { 01, 10, 0010, 1010 } 不是，因为 10 是 1010 的前缀。

给出传真机的例子。

Huffman 编码。

构建最佳前缀无码的特定方式。由 David Huffman 在 1950 年在 MIT 时发明。Huffman.java 实现了 Huffman 算法。

属性 A. 没有前缀无码使用更少的比特。

LZW 压缩。

使用 TST.java 中的前缀匹配代码，LZW.java 实现了 LZW 压缩。

现实世界：Pkzip = LZW + Shannon-Fano，GIF，TIFF，V.42bis 调制解调器，Unix 压缩。实际问题：

• 将所有内容编码为二进制。
  
• 限制符号表中元素的数量（GIF = 丢弃并重新开始，Unix 压缩 = 不起作用时丢弃）。
  
• 最初字典有 512 个元素（其中填充了 256 个 ASCII 字符），因此我们每个整数传输 9 位。当填满时，我们将其扩展到 1024 并开始每个整数传输 10 位。
  
• 只遍历树一次（可能会破坏我们的字符串表抽象）。
  

实际问题：限制符号表中元素的数量。

总结。

Huffman：固定长度符号的变长编码。LZW：变长字符串的固定长度编码。

通用压缩算法。

不可能压缩所有文件（通过简单计数论证）。直观论证：压缩莎士比亚的生平作品，然后压缩结果，再次压缩结果。如果每个文件都严格缩小，最终将只剩下一个比特。

参考文献。

卡内基梅隆大学的 Guy Blelloch 在 数据压缩 方面有一章非常出色。

错误校正/检测。

假设用于发送信息的信道存在噪声，每个比特以概率 p 翻转。发送每个比特 3 次；解码时取 3 个比特的大多数。解码比特的正确概率为 3p² - 2p³。这小于 p（如果 p < 1/2）。可以通过多次发送每个比特来减少解码比特错误的概率，但这在传输速率方面是浪费的。

Reed-Solomon 编码。

参考资料。用于大容量存储系统（CD 和 DVD）和卫星传输（旅行者号探测器，火星探路者）当错误是突发性的时候。将要发送的数据视为一个度为 d 的多项式。只需要 d+1 个点来唯一指定多项式。发送更多点以实现纠错/检测错误。如果我们要发送的编码是 a0，a1，…，am-1（每个元素在有限域 K 上），将其视为多项式 p(x) = a0 + a1x + … + am-1 x^m-1。发送 p(0)，p(b)，p(b²)，…，其中 b 是 K 上的乘法循环群的生成元。

香农编码定理。

大致来说，如果信道容量为 C，则我们可以以略低于 C 的速率发送比特，使用编码方案将解码错误的概率降低到任意所需水平。证明是非构造性的。

问答

练习

1. 以下哪些编码是前缀自由的？唯一可解码的？对于那些唯一可解码的编码，给出编码为 1000000000000 的编码。

code 1    code 2    code 3   code 4
A     0         0          1       1
B     100       1         01      01
C     10       00        001     001
D     11       11       0001     000

1. 给出一个不是前缀自由的唯一可解码编码的例子。
   解决方案。 任何无后缀编码都是唯一可解码的，例如，{ 0, 01 }。
   
2. 给出一个不是前缀自由或无后缀的唯一可解码编码的例子。
   解决方案。 { 0011, 011, 11, 1110 }或{ 01, 10, 011, 110 }。
   
3. { 1, 100000, 00 }，{ 01, 1001, 1011, 111, 1110 }和{ 1, 011, 01110, 1110, 10011 }是唯一可解码的吗？如果不是，找到一个具有两个编码的字符串。解决方案。 第一组编码是唯一可解码的。第二组编码不是唯一可解码的，因为 111-01-1110-01 和 1110-111-1001 是 11101111001 的两种解码方式。第三组编码不是唯一可解码的，因为 01110-1110-011 和 011-1-011-10011 是 011101110011 的两种解码方式。
   
4. 唯一可解码性测试。实现 Sardinas-Patterson 算法，用于测试一组编码词是否是唯一可解码的：将所有编码词添加到一个集合中。检查所有编码词对，看看是否有一个是另一个的前缀；如果是，提取悬挂后缀（即，长字符串中不是短字符串前缀的部分）。如果悬挂后缀是一个编码词，则编码不是唯一可解码的；否则，将悬挂后缀添加到列表中（前提是它尚未存在）。重复此过程直到没有剩余的新悬挂后缀为止。该算法是有限的，因为添加到列表中的所有悬挂后缀都是有限一组编码词的后缀，并且悬挂后缀最多只能添加一次。

• { 0, 01, 11 }。编码词 0 是 01 的前缀，因此添加悬挂后缀 1。{ 0, 01, 11, 1 }。编码词 0 是 01 的前缀，但悬挂后缀 1 已经在列表中；编码词 1 是 11 的前缀，但悬挂后缀 1 已经在列表中。没有其他悬挂后缀，因此得出该集合是唯一可解码的结论。
  
• { 0, 01, 10 }。编码词 0 是 01 的前缀，因此将悬挂后缀 1 添加到列表中。{ 0, 01, 10, 1 }。编码词 1 是 10 的前缀，但悬挂后缀 0 是一个编码词。因此，得出该编码不是唯一可解码的结论。
  

5. Kraft-McMillan 不等式。 考虑一个具有长度为 n1, n2, …, nN 的 N 个编码词的编码 C。证明如果编码是唯一可解码的，则 K© = sum_i = 1 to N 2^(-ni) ≤ 1。
   
6. Kraft-McMillan 构造。 假设我们有一组满足不等式 sum_i = 1 to N 2^(-ni) ≤ 1 的整数 n1, n2, …, nN。证明总是可以找到一个编码长度为 n1, n2, …, nN 的前缀自由编码。因此，通过将注意力限制在前缀自由编码上（而不是唯一可解码编码），我们不会失去太多。
   
7. Kraft-McMillan 最优前缀自由编码等式。 证明如果 C 是一个最优前缀自由编码，那么 Kraft-McMillan 不等式是一个等式：K© = sum_i = 1 to N 2^(-ni) = 1。
   
8. 假设所有符号概率都是 2 的负幂次方。描述哈夫曼编码。
   
9. 假设所有符号频率相等。描述哈夫曼编码。
   
10. 找到一个哈夫曼编码，其中概率为 pi 的符号的长度大于 ceil(-lg pi)。
    解决方案. .01 (000), .30 (001), .34 (01), .35 (1)。码字 001 的长度大于 ceil(-lg .30)。
    
11. 真或假。任何最优前缀自由编码都可以通过哈夫曼算法获得。
    解决方案. 错误。考虑以下符号和频率集合（A 26, B 24, C 14, D 13, E 12, F 11）。

C1   C2   C3
A 26   01   10   00
B 24   10   01   01
C 14  000  111  100
D 13  001  110  101
E 12  110  001  110
F 11  111  000  111

1. 在任何哈夫曼编码中，字符 A 和 B 的编码必须以不同的位开始，但是代码 C3 没有这个属性（尽管它是一个最优前缀自由编码）。
2. 以下输入的 LZW 编码是什么？

• T O B E O R N O T T O B E
  
• Y A B B A D A B B A D A B B A D O O
  
• A A A A A A A A A A A A A A A A A A A A A
  

3. 描述 LZW 编码中的棘手情况。
   解决方案. 每当遇到 cScSc，其中 c 是一个符号，S 是一个字符串，cS 在字典中但 cSc 不在字典中。
   
4. 作为 N 的函数，编码 N 个符号 A 需要多少位？N 个序列 ABC 需要多少位？
   
5. 让 F(i) 为第 i 个斐波那契数。考虑 N 个符号，其中第 i 个符号的频率为 F(i)。注意 F(1) + F(2) + … + F(N) = F(N+2) - 1。描述哈夫曼编码。
   解决方案. 最长的码字长度为 N-1。
   
6. 显示对于给定的 N 个符号集合，至少有 2^(N-1) 种不同的哈夫曼编码。
   解决方案. 有 N-1 个内部节点，每个节点都可以任意选择其左右子节点。
   
7. 给出一个哈夫曼编码，其中输出中 0 的频率远远高于 1 的频率。
   解决方案. 如果字符 ‘A’ 出现一百万次，字符 ‘B’ 出现一次，那么 ‘A’ 的码字将是 0，‘B’ 的码字将是 1。
   
8. 证明有关哈夫曼树的以下事实。

• 两个最长的码字长度相同。
  
• 如果符号 i 的频率严格大于符号 j 的频率，则符号 i 的码字长度小于或等于符号 j 的码字长度。
  

9. 描述如何在一组符号 { 0, 1, …, N-1 } 上传输哈夫曼编码（或最优前缀自由编码），使用 2N - 1 + N ceil(lg N) 位。
   提示：使用 2N-1 位来指定相应 trie 的结构。
   
10. 假设在一个扩展 ASCII 文件（8 位字符）中，最大字符频率最多是最小字符频率的两倍。证明固定长度的 8 位扩展 ASCII 码是最优的。
    
11. 香农-范诺编码。 证明哈夫曼算法的以下自顶向下版本不是最优的。将码字集合 C 分成两个子集 C1 和 C2，其频率（几乎）相等。递归地为 C1 和 C2 构建树，从 0 开始为 C1 的所有码字，从 1 开始为 C2 的所有码字。为了实现第一步，香农和范诺建议按频率对码字进行排序，并尽可能地将集合分成两个子数组。
    解决方案. S 32, H 25, A 20, N 18, O 5。
    
12. LZMW 编码（米勒-韦格曼 1985）。 LZ 变种：在字典中搜索最长的已经存在的字符串（当前匹配）；将前一个匹配与当前匹配的连接添加到字典中。字典条目增长更快。当字典填满时，也可以删除低频率条目。难以实现。
    
13. LZAP 编码。 类似于 LZMW：不仅添加前一个匹配与当前匹配的连接，还添加前一个匹配与当前匹配的 所有前缀 的连接。比 LZMW 更容易实现，但字典条目更多。
    
14. 确定一个不是前缀自由的最优编码。
    提示：只需要 3 个具有相等频率的符号。
    
15. 确定对于相同输入的两个最优前缀自由编码，其码字长度分布不同。
    提示：只需要 4 个符号。
    
16. 最小方差 Huffman 编码。 由于与打破平局相关的不确定性，Huffman 算法可能生成具有不同码字长度分布的编码。在生成压缩流时传输，希望以（近）恒定速率传输比特。找到最小化 sum_i (p_i (l_i - l_average(T)) ²) 的 Huffman 编码。
    解决方案。 在组合 tries 时，通过选择具有最小概率的最早生成的 trie 来打破平局。
    
17. 用于 Huffman 编码的双队列算法。 证明以下算法计算出 Huffman 编码（如果输入符号已按频率排序，则在线性时间内运行）。维护两个 FIFO 队列：第一个队列包含输入符号，按频率升序排列，第二个队列包含组合权重的内部节点。只要两个队列中有超过一个节点，就通过检查两个队列的前端出队两个权重最小的节点。创建一个新的内部节点（左右子节点 = 两个节点，权重 = 两个节点的权重之和）并将其加入第二个队列。
    要获得最小方差的 Huffman 编码，通过从第一个队列中选择节点来打破平局。
    提示：证明第二个队列按频率升序排列。
    
18. 兄弟属性。 如果（i）每个节点（除了根节点）都有一个兄弟节点，且（ii）二叉树可以按概率的非递增顺序列出，使得在列表中所有兄弟节点都相邻，则二叉树具有 兄弟属性。证明二叉树表示 Huffman 树当且仅当它具有兄弟属性。
    
19. 相对编码。 不是压缩图像中的每个像素，而是考虑像素与前一个像素之间的差异并对差异进行编码。直觉：通常像素变化不大。与颜色表字母上的 LZW 一起使用。
    
20. 可变宽度 LZW 编码。 在第 2^p 个码字插入表后，将表的宽度从 p 增加到 p+1。与颜色表字母一起使用。
    
21. 自适应 Huffman 编码。 一次通过算法，不需要发送前缀自由码。根据迄今为止读入的字符的频率构建 Huffman 树。在读入每个字符后更新树。编码器和解码器需要协调处理平局的约定。
    
22. 香农熵。具有可能值 x1, …, xN 且以概率 p1, …, pN 出现的离散随机变量 X 的熵 H 定义为 H(X) = -p1 lg p1 - p2 lg p2 - … - pN lg pN，其中 0 lg 0 = 0 与极限一致。

• 一个公平硬币的熵是多少？
  
• 一个硬币的熵是什么，其中两面都是正面？
  
• 一个六面骰子的熵是多少？
  解决方案。 -lg (1/6) 大约为 2.584962。
  
• 两个公平骰子的和的熵是多少？
  
• 给定一个取 N 个值的随机变量。什么分布使熵最大化？熵是信息论中的一个基本概念。香农的源编码定理断言，要压缩来自一系列独立同分布随机变量流的数据，至少需要每个符号 H(X) 位。例如，发送一系列公平骰子投掷结果至少需要每次骰子投掷 2.584962 位。
  

23. 经验熵。 经验熵 是通过计算每个符号出现频率并将其用作离散随机变量的概率来获得的一段文本的熵。计算你最喜欢小说的经验熵。将其与 Huffman 编码实现的数据压缩率进行比较。
    
24. 香农实验。 进行以下实验。给一个主体一段文本（或 Leipzig 语料库）中的 k 个字母序列，并要求他们预测下一个字母。估计主体在 k = 1, 2, 5, 100 时答对的比例。
    
25. 真或假。固定长度编码是���一可解码的。
    解决方案。 真，它们是前缀自由的。
    
26. 给出两棵不同高度的 Huffman 树字符串 ABCCDD。
    
27. 前缀自由编码。 设计一个高效的算法来确定一组二进制码字是否是前缀自由的。提示：使用二进制 trie 或排序。
    
28. 唯一可解码编码。 设计一个唯一可解码的编码，它不是前缀自由编码。提示：后缀自由编码 = 前缀自由编码的反向。后缀自由编码的反向是前缀自由编码 -> 可以通过以相反顺序读取压缩消息来解码。不太方便。
    
29. 哈夫曼树。 修改 Huffman.java，使得编码器打印查找表而不是先序遍历，并修改解码器以通过读取查找表构建树。
    
30. 真或假。在最佳前缀自由三进制编码中，出现频率最低的三个符号具有相同的长度。
    解答。 False.
    
31. 三进制哈夫曼编码。 将哈夫曼算法推广到三进制字母表（0, 1 和 2）上的码字，而不是二进制字母表。也就是说，给定一个字节流，找到一个使用尽可能少的三进制位（0、1 和 2）的前缀自由三进制编码。证明它产生最佳前缀自由三进制编码。
    解答。 在每一步中合并最小的 3 个概率（而不是最小的 2 个）。当有 3 + 2k 个符号时，这种方法有效。为了将其减少到这种情况，添加概率为 0 的 1 或 2 个虚拟符号。（或者，如果符号数量不是 3 + 2k，则在第一步中合并少于 3 个符号。）例如：{ 0.1, 0.2, 0.2, 0.5 }。
    
32. 非二进制哈夫曼编码。 将哈夫曼算法扩展到 m 进制字母表（0, 1, 2, …, m-1）上的码字，而不是二进制字母表。
    
33. 考虑以下由 3 个 a、7 个 c、6 个 t 和 5 个 g 组成的 21 个字符消息。

a a c c c c a c t t g g g t t t t c c g g 

1. 以下的 43 位是否是上述消息的可能哈夫曼编码？

0000001111000101010010010010101010111001001 

1. 尽可能简洁而严谨地证明你的答案。
   解答。 对于一条消息的哈夫曼编码会产生使用最少位数的编码，其中 2 位二进制码 a = 00, c = 01, g = 10, t = 11 是一个使用 21 * 2 = 42 位的前缀自由编码。因此，哈夫曼编码将使用少于 43 位。
2. 如果一个二叉树是满的，则除了叶子节点外的每个节点都有两个子节点。证明与最佳前缀自由编码对应的任何二叉树都是满的。
   提示：如果内部节点只有一个子节点，请用其唯一子节点替换该内部节点。
   
3. Move-to-front 编码（Bentley, Sleator, Tarjan 和 Wei 1986）。 编写一个名为 MoveToFront 的程序，实现 move-to-front 编码和解码。维护符号字母表的列表，其中频繁出现的符号位于前面。一个符号被编码为列表中在它之前的符号数。编码一个符号后，将其移动到列表的前面。参考
   
4. Move-ahead-k 编码。 与 move-to-front 编码相同，但将符号向前移动 k 个位置。
   
5. 等待-c-并移动。 与 move-to-front 编码相同，但只有在符号在上次移动到前面后遇到 c 次后才将其移动到前面。
   
6. 双哈夫曼压缩。 找到一个输入，对该输入应用 Huffman.java 中的 compress() 方法两次比仅应用 compress() 一次导致输出严格较小。
   
7. 合并 k 个排序数组。 你有 k 个已排序的列表，长度分别为 n1、n2、…、nk。假设你可以执行的唯一操作是 2 路合并：给定长度为 n1 的一个已排序数组和长度为 n2 的另一个已排序数组，用长度为 n = n1 + n2 的已排序数组替换它们。此外，2 路合并操作需要 n 个单位的时间。合并 k 个已排序数组的最佳方法是什么？
   解决方案. 将列表长度排序，使得 n1 < n2 < … < nk。重复地取最小的两个列表并应用 2 路合并操作。最优性的证明与哈夫曼编码的最优性证明相同：重复应用 2 路合并操作会产生一棵二叉树，其中每个叶节点对应于原始排序列表中的一个，每个内部节点对应于一个 2 路合并操作。任何原始列表对总体成本的贡献是列表长度乘以其树深度（因为这是其元素参与 2 路合并的次数）。
   

6. 上下文

原文：algs4.cs.princeton.edu/60context

译者：飞龙

协议：CC BY-NC-SA 4.0

本章节正在大规模施工中。

概述。

本章中的 Java 程序。

以下是本章节中的 Java 程序列表。点击程序名称以访问 Java 代码；点击参考编号以获取简要描述；阅读教材以获取详细讨论。