算法工作原理
Chapter 6 Strings

第 6 章：算法中的字符串

字符串是计算机科学中的一种基本数据类型,表示字符序列。研究处理字符串的算法和数据结构是任何计算机科学课程的重要组成部分。在本章中,我们探讨了几种重要的字符串处理算法,包括字符串排序、字典树、子字符串搜索、正则表达式和数据压缩。这些算法有许多实际应用,从文本编辑和文档检索到生物信息学和自然语言处理。

字符串排序

排序是计算机科学中的一个基本操作,对字符串进行排序是许多应用中的常见任务。虽然通用的排序算法如快速排序和归并排序可用于对字符串进行排序,但也有更高效的算法,利用字符串的特殊属性。

键索引计数

键索引计数是一种简单高效的算法,用于对由少量不同字符组成的字符串进行排序。基本思想是统计每个字符出现的次数,然后使用这些计数来确定每个字符串在排序后的位置。

下面是键索引计数的一个示例:

输入:  ["dab", "cab", "fad", "bad", "dad", "ebb", "ace"]
输出: ["ace", "bad", "cab", "dab", "dad", "ebb", "fad"]

该算法的工作过程如下:

  1. 统计每个字符在字符串中的频率。
  2. 计算每个字符在排序后数组中的起始索引。
  3. 将字符串复制到排序后的数组中,使用计数来确定位置。

键索引计数的时间复杂度为 O(n + R),其中 n 是字符串中的总字符数,R 是字母表的大小(不同字符的数量)。这使得它成为一种非常高效的算法,适用于字母表较小的字符串排序。

LSD 基数排序

最低有效位优先(LSD)基数排序是键索引计数的扩展以下是该 Markdown 文件的中文翻译。对于代码部分,仅翻译注释,不翻译代码本身。

可以对等长字符串进行排序的计数排序。基本思想是从最后一个字符开始,逐个字符对字符串进行排序。

以下是 LSD 基数排序的示例:

输入:  ["4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720", "1OHV845", "1OHV845", "2RLA629", "2RLA629", "3ATW723"]
输出: ["1ICK750", "1ICK750", "1OHV845", "1OHV845", "1OHV845", "2IYE230", "2RLA629", "2RLA629", "3ATW723", "3CIO720", "3CIO720", "4JZY524", "4PGC938"]

算法的工作过程如下:

  1. 使用键索引计数法按最后一个字符对字符串进行排序。
  2. 重复步骤 1,逐个字符向前移动。

LSD 基数排序的时间复杂度为 O(w * n),其中 w 是字符串的长度,n 是字符串的数量。这使其成为一种高效的固定长度字符串排序方法。

MSD 基数排序

最高有效位优先(MSD)基数排序是基数排序的一种递归变体,可以处理长度不同的字符串。与快速排序类似,MSD 基数排序将数组划分为可以独立排序的子数组。

以下是 MSD 基数排序的示例:

输入:  ["she", "sells", "seashells", "by", "the", "sea", "shore", "the", "shells", "she", "sells", "are", "surely", "seashells"]
输出: ["are", "by", "sea", "seashells", "seashells", "sells", "sells", "she", "she", "shells", "shore", "surely", "the", "the"]

算法的工作过程如下:

  1. 根据每个字符串的第一个字符将数组划分为子数组。
  2. 递归地对每个子数组进行排序。

MSD 基数排序的最坏情况时间复杂度为 O(n * w),但在实践中,它通常比 LSD 基数排序更快,因为它可以处理长度不同的字符串。

字典树

字典树(trie)是一种树状数据结构,用于存储字符串,可以高效地进行前缀匹配和字符串搜索。字典树中的每个节点代表一个字符,从根节点到某个节点的路径表示一个字符串的前缀。以下是该 Markdown 文件的中文翻译。对于代码部分,仅翻译注释,不翻译代码本身。

字符串存储在字典树中

这里有一个例子,展示了一个字典树存储了字符串 "sea"、"sells"、"she"、"shells" 和 "shore":

     (根节点)
    /  |  \
   s   h   o
  / \     / \
 e   h   r   t
 |   |   |   |
 a   e   e   h
     |       |
     l       e
     |       |
     l       r
     |
     s

字典树支持以下操作:

  • 将一个字符串插入字典树。
  • 在字典树中搜索一个字符串。
  • 从字典树中删除一个字符串。
  • 找到所有具有给定前缀的字符串。

这些操作的时间复杂度为 O(w),其中 w 是被插入、搜索或删除的字符串的长度。这使得字典树成为处理字符串相关任务的非常高效的数据结构。

子串搜索

子串搜索是在一个较大的文本字符串中找到一个模式字符串所有出现位置的问题。这是字符串处理中的一个基本问题,在文本编辑、生物信息学等许多领域都有应用。

暴力搜索

最简单的子串搜索方法是暴力算法,它检查文本中的每个可能位置是否与模式匹配。

这里有一个暴力搜索的例子:

文本:    "abacadabrabracabracadabrabrabracad"
模式: "abracadabra"
输出:  [13]

暴力算法的最坏情况时间复杂度为 O(n * m),其中 n 是文本长度,m 是模式长度。虽然实现简单,但对于大文本和大模式来说可能效率较低。

Knuth-Morris-Pratt 算法

Knuth-Morris-Pratt (KMP) 算法是一种高效的子串搜索算法,它使用预先计算的"失败函数"来避免不必要的比较。

失败函数告诉我们,已经匹配的模式子串的最长真前缀也是后缀的长度。这允许我们在发现不匹配时"跳过"文本,而不是回溯。

这里有一个 KMP 算法的例子:

文本:    "abacadabrabr以下是该 Markdown 文件的中文翻译。对于代码部分,仅翻译注释,不翻译代码。

"acabracadabrabrabracad"
模式: "abracadabra"
输出: [13]

KMP 算法的运行时间为 O(n + m),使其比暴力搜索方法在大文本和模式中更加高效。

Boyer-Moore 算法

Boyer-Moore 算法是另一种高效的子字符串搜索算法,它通过预处理模式字符串来工作。与从模式开头开始比较的 KMP 不同,Boyer-Moore 从末尾开始并向后工作。

Boyer-Moore 背后的关键思想是使用两个预先计算的函数:好后缀函数和坏字符函数。这些函数允许我们在发现不匹配时跳过文本,类似于 KMP。

下面是 Boyer-Moore 算法的一个示例:

文本:    "abacadabrabracabracadabrabrabracad"
模式: "abracadabra"
输出:  [13]

Boyer-Moore 的最佳情况运行时间为 O(n/m),最坏情况运行时间为 O(n * m),但在实践中,它通常是大字母表中最快的子字符串搜索算法。

正则表达式

正则表达式是描述字符串模式的强大工具。它们提供了一种简洁灵活的符号来匹配、搜索和操作文本。

正则表达式是一个字符序列,定义了一个搜索模式。最简单的正则表达式形式是字面字符串,如 "hello",它精确匹配字符串 "hello"。但是,正则表达式也包括特殊字符和结构,允许更复杂的模式:

  • . (点) 匹配任意单个字符。
  • * (星号) 匹配前一个字符或组的零个或多个出现。
  • + (加号) 匹配前一个字符或组的一个或多个出现。
  • ? (问号) 匹配前一个字符或组的零个或一个出现。
  • ^ (脱字符) 匹配行的开头。
  • $ (美元符) 匹配行的结尾。
  • [] (方括号) 定义一个字符类,匹配任意单个字符。

这里是一些正则表达式的示例及其匹配的模式:

- `a.b` 匹配以 "a" 开头、以 "b" 结尾的任意三个字符的字符串,例如 "acb"、"a5b" 或 "a b"。
- `a*b` 匹配由零个或多个 "a" 字符后跟一个 "b" 字符组成的任意字符串,例如 "b"、"ab"、"aab" 或 "aaab"。
- `a+b` 匹配由一个或多个 "a" 字符后跟一个 "b" 字符组成的任意字符串,例如 "ab"、"aab" 或 "aaab",但不包括 "b"。
- `a?b` 匹配 "ab" 或 "b"。
- `^a` 匹配以 "a" 开头的任意字符串。
- `a$` 匹配以 "a" 结尾的任意字符串。
- `[aeiou]` 匹配任意单个元音字符。

正则表达式受到许多编程语言和工具的支持,包括 Java、Python 和 Unix 实用程序 grep 和 sed。它们广泛用于数据验证、文本处理和日志分析等任务。

## 数据压缩

数据压缩是使用比原始表示更少的位来编码信息的过程。这有助于减少存储需求和传输时间。主要有两种类型的压缩:无损压缩和有损压缩。无损压缩允许从压缩数据中完全重建原始数据,而有损压缩允许以更高的压缩比为代价牺牲一些信息。

### 游程编码

游程编码 (RLE) 是一种简单的无损压缩技术,它将相同符号的重复序列 (游程) 替换为单个实例和重复次数。

下面是一个 RLE 的示例:

输入: "AAAABBBCCCDDDEEE" 输出: "4A3B3C3D3E"


当数据中有许多长游程时,RLE 很有效。但是,如果没有或很少有游程,它实际上可能会增加数据的大小。

### 哈夫曼编码

哈夫曼编码是一种无损压缩算法,它根据符号的频率为其分配可变长度的编码。以下是该 Markdown 文件的中文翻译。对于代码部分,仅翻译注释,不翻译代码。

# 哈夫曼编码

哈夫曼编码是一种基于字符频率的无损数据压缩算法。它通过分配较短的编码给出现频率较高的字符,较长的编码给出现频率较低的字符,从而达到压缩数据的目的。

该算法通过自底向上构建一棵二叉树(称为哈夫曼树)来实现。每个叶子节点代表一个字符及其频率,而每个内部节点代表其子节点频率之和。该树是通过不断合并频率最低的两个节点而构建的,直到只剩下一个节点。

一旦构建完成,每个字符的编码由从根节点到对应叶子节点的路径决定,左分支表示"0",右分支表示"1"。

下面是一个哈夫曼编码的例子:

输入: "AAAABBBCCCDDDEEE" 输出: "000010011001011100101"

哈夫曼树: (15) /
(7) (8) / \ /
(4) (3) (3) (5) /\ /\ /\ /
A B C D E


在这个例子中, "A" 被编码为 "00", "B" 被编码为 "01", "C" 被编码为 "10", "D" 被编码为 "110", "E" 被编码为 "111"。压缩后的输出通过用对应的编码替换输入中的每个字符而得到。

哈夫曼编码是一种最优前缀码,这意味着没有任何一个编码是另一个编码的前缀。这允许对压缩数据进行无歧义的解码。哈夫曼编码广泛应用于各种文件格式和压缩工具中,如 JPEG、MP3 和 ZIP。

### LZW 压缩

Lempel-Ziv-Welch (LZW) 压缩是一种基于字典的压缩算法,它在压缩输入的同时构建一个字典(或代码本)。LZW 广泛应用于文件压缩实用程序,并曾用于 GIF 图像格式。

LZW 的关键思想是用单个代码替换一串字符。它逐字符读取输入字符串,并通过用变长代码替换固定长度的代码来对其进行编码。字符串越长,编码为单个数字所节省的空间就越多。

下面是一个...以下是该 Markdown 文件的中文翻译。对于代码部分,我只翻译了注释,而没有翻译代码本身。

LZW 压缩算法的逐步描述:

1. 将字典初始化为包含所有单字符字符串。
2. 在字典中找到与当前输入最长匹配的字符串 W。
3. 输出 W 在字典中的索引,并从输入中删除 W。
4. 将 W 后跟输入中的下一个符号添加到字典中。
5. 转到步骤 2。

让我们看一个例子。假设我们想使用 LZW 压缩字符串 "ABABABABA"。

1. 将字典初始化为包含 "A" 和 "B"。
2. 最长匹配是 "A"。输出其索引 (0) 并从输入中删除它。字典现在包含 "A"、"B" 和 "AB"。
3. 最长匹配是 "B"。输出其索引 (1) 并从输入中删除它。字典现在包含 "A"、"B"、"AB" 和 "BA"。
4. 最长匹配是 "AB"。输出其索引 (2) 并从输入中删除它。字典现在包含 "A"、"B"、"AB"、"BA" 和 "ABA"。
5. 最长匹配是 "ABA"。输出其索引 (4) 并从输入中删除它。字典现在包含 "A"、"B"、"AB"、"BA"、"ABA" 和 "ABAB"。
6. 最长匹配是 "BA"。输出其索引 (3)。输入现在为空。

"ABABABABA" 的压缩表示是索引序列 [0, 1, 2, 3, 4]，这比原始 ASCII 表示需要更少的位。

解压缩的工作方式类似,但是方向相反:

1. 将字典初始化为包含所有单字符字符串。
2. 从输入中读取一个代码 X。
3. 从字典中输出 X 对应的字符串。
4. 如果前一个代码存在,则将前一个字符串连接上 X 对应字符串的第一个字符添加到字典中。
5. 转到步骤 2。

LZW 压缩简单快速,适用于许多应用场景。但它也有一些局限性。字典的大小可能会变得非常大,占用大量内存。此外,字典在每个输入块后都会重置,这可能会降低小文件的压缩率。

尽管存在这些限制,但 LZW 压缩仍然是一种非常有用的压缩算法。尽管 LZW 压缩算法的压缩率可能不是最高的,但它仍然是一种广受欢迎和有效的压缩算法,特别是在速度比最高压缩率更重要的应用中。

## 结论

在本章中,我们探讨了几种重要的字符串处理算法,包括字符串排序、字典树、子字符串搜索、正则表达式和数据压缩。这些算法构成了许多现实世界应用的基础,是任何处理文本数据的程序员必备的工具。

我们首先讨论了字符串排序,这是优化的排序算法,利用了字符串的特殊属性。键索引计数、LSD 基数排序和 MSD 基数排序提供了高效的基于字符排序字符串的方法。

接下来,我们研究了字典树,这是一种用于存储和检索字符串的树状数据结构。字典树可以实现快速的前缀匹配,常用于自动完成和 IP 路由表等应用中。

子字符串搜索算法,如 Knuth-Morris-Pratt 和 Boyer-Moore 算法,使我们能够有效地在较大的字符串中搜索模式。这些算法在文本编辑、计算生物学和信息检索等领域有广泛应用。

正则表达式提供了一种强大而灵活的方式来描述字符串模式。我们讨论了正则表达式的基本语法,以及它们如何在各种编程语言和工具中用于模式匹配和字符串操作。

最后,我们探讨了数据压缩算法,这些算法通过利用输入中的冗余和模式来减小数据的大小。我们介绍了游程编码、霍夫曼编码和 Lempel-Ziv-Welch 压缩,每种算法都有自己的优势和应用场景。

理解这些字符串处理算法和数据结构对于任何处理文本数据的人来说都是至关重要的。随着非结构化数据的不断增加,高效地操作、搜索和压缩数据的能力变得越来越重要。以下是该 Markdown 文件的中文翻译。对于代码部分,请不要翻译代码,只翻译注释。

压力字符串将变得更加宝贵。通过掌握本章涵盖的技术,您将能够很好地应对自己项目和应用程序中各种字符串处理挑战。
Chapter 5 GraphsChapter 7 Context