串的匹配
串的匹配就是从大的字符串中找到字串，并且返回第一个字串的位置。
C语言库函数有一个strstr，是朴素的串匹配算法，也叫BF算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int BF(string source, string pattern)
{
int i = 0;
int j = 0;
while(i < source.size() && j < pattern.size())
{
if(source[i] == pattern[j])
{
++i;
++j;
}
else
{
i = i - j + 1;
j = 0;
}
}
if(j == pattern.size())
{
return i - j;
}
return -1;
}
|
KMP算法
是一个升级版的串匹配算法，名字取自三个人名（Knuth-Morris-Pratt）。
总地来说，KMP的核心效果就是让原串的指示器不用退回。如何达到这个效果？就是考虑和模式串已经匹配的部分。这一部分模式串的子串，如果后缀有和前缀相重复的部分，则就可以跳过这些部分，即跳过前缀，在前缀的后一个字符开始再次比对（实际操作中，原串指示器不动，而是模式串的指示器回退到当时子串前缀的后一个字符位置）。
于是，整个问题的核心，就从关注原串变到关注模式串本身了。需要找到模式串的不同长度（起点一致，不能从中间分割）下子串的前缀后缀相等的前缀（后缀）最大长度，从而建立一个所谓的next数组。
这个next数组，教科书的求法是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| int * getNext(string str)
{
int * next = new int[str.size()];
int j = 0;
int k = -1;
next[0] = -1;
while(j < str.size() - 1)
{
if(-1 == k || str[j] == str[k])
{
++j;
++k;
next[j] = k;
}
else
{
k = next[k];
}
}
}
int KMP(string source, string pattern)
{
int i = 0;
int j = 0;
int * next = getNext(pattern);
while(i < source.size() && j < pattern.size())
{
if(source[i] == pattern[j])
{
++i;
++j;
}
else
{
j = next[j];
}
}
if(j == pattern.size())
{
return i - j;
}
return -1;
}
|
上面这个求next数组的代码虽然看起来很简洁，但要彻底理解，还是比较难的，因为代码的细节处理得很巧妙，其中k = next[k]更是复用了KMP的next数组思想。
这个求getNext的函数可以优化，避免模式串中重复的字段：见ShiLei算法180节
比如：abcabc的next数组如果没有优化，则会成为-1 0 0 0 1 2，而经过优化以后：-1 0 0 -1 0 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| int * getNext(string str)
{
int * next = new int[str.size()];
int j = 0;
int k = -1;
next[0] = -1;
while(j < str.size() - 1)
{
if(-1 == k || str[j] == str[k])
{
++j;
++k;
if(str[k] == str[j])
{
next[j] = next[k];
}
else
{
next[j] = k;
}
}
else
{
k = next[k];
}
}
}
|
还有一个更直白的找模式串子串的前后缀最大长度的方法如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| int PMT[50] = {0};
void init_pmt(char const * pattern)
{
int len = strlen(pattern);
char sub[50] = {'\0'};
for(int i = 1; i <= len; ++i)
{
strncpy(sub, pattern, i);
sub[i] = '\0';
char prefix[50] = {'\0'};
char suffix[50] = {'\0'}
for(int j = 1; j <= i - 1; ++j)
{
strncpy(prefix, sub, j);
prefix[j] = '\0';
strcpy(suffix, sub + i - j);
if(strcmp(prefix, suffix) == 0)
{
PMT[i - 1] = j;
}
}
}
}
int kmp(char const * source, char const * pattern)
{
int i = 0, j = 0;
while(source[i] && pattern[j])
{
if(source[i] == pattern[j])
{
++i;
++j;
}
else
{
if(j == 0)
{
++i;
}
else
{
j = PMT[j - 1];
}
}
}
if(pattern[j] == '\0')
{
return i - j;
}
return -1;
}
|
Bayer Moore
坏字符
每次把目标字符串和原字符串从后往前比较，如果某位置对应不上，则原字符串的这个字符称为“坏（bad）”字符。需要在目标字符串从后往前继续寻找（已经在之前匹配上的字符跳过）与这个bad字符相等的字符，然后按照这个相等字符的位置与原字符串的坏字符位置对齐（后移目标字符串）；如果在目标字符串中没找到坏字符，则把目标字符串整体后移到坏字符位置的下一个位置。对齐之后，重新把目标字符串和原字符串从后往前比较。
找匹配串中下一个坏字符，需要告诉：当前坏字符是什么（原串中的字符），当前坏字符位置在哪（模式串中的下标值），以及目标串指针。即从匹配串中的坏字符的位置的前一个位置开始找下一个相同的字符。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int next_bad(char bad, char const * pattern, int wherebad)
{
int i = -1;
for (i = wherebad - 1; i >= 0; --i)
{
if (pattern[i] == bad)
{
break;
}
}
return i;
}
|
好后缀
在模式字符串从后往前与原串一一匹配的过程中，遇到了坏字符，那么坏字符之后的，即已经匹配上了的在后面的部分串称之为好后缀。那么，我们可以去寻找模式字符串中还是否存在好后缀。如果存在，则可以让模式字符串的下一个好后缀与原串的当前位置的好后缀对齐，从而达到让模式串快速前进。
好后缀的思想很类似于KMP算法，即找公共前后缀，让重复的前缀对齐原串的后缀位置。但是区别就在于，BM算法是从后往前去匹配的，找到好后缀的同时，顺带着也找到了坏字符的位置。
下一个坏字符与原串当前坏字符对齐，或者下一个好后缀与原串当前好后缀对齐，模式字符串前进的步数会不一样，那么，就可以去对比哪个可以前进得更多。
那么，类似于KMP地，去聚焦于模式字符串本身，不同点在于，每次寻找后缀都是从右向左寻找最近的下一个好后缀。（如果找的不是最近的而是靠左的下下个好后缀的话，那么模式字符串在BM算法前进过程中就会步子迈大了，跳过了可能完全成功匹配的机会）
去建立一个SUFFIX_TB表格，下标值i代表此位置开始的后缀字符串，内容值SUFFIX_TB[i]代表左边下一个最近的好后缀的下标位置。
SUFFIX_TB表格起初把全部值初始化为-1。表示当前i位置时没找到下一个好后缀。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| int SUFFIX_TB[50] = {0};
void init_suffix(char const * const pattern)
{
int pattern_len = strlen(pattern);
char sub[50] = {'\0'};
for(int i = 0; i < 50; ++i)
{
SUFFIX_TB[i] = -1;
}
for(int i = 1; i < pattern_len; ++i)
{
strcpy(sub, pattern + i);
for(int j = i - 1; j >= 0; --j)
{
if(strncmp(sub, pattern + j, pattern_len - i) == 0)
{
SUFFIX_TB[i] = j;
break;
}
}
}
}
|
封装到next_good函数，参数只需要一个wherebad，即坏字符的位置（模式串中的下标值），那么就可以确定好后缀的位置了（即坏字符的下一个位置）。
1
2
3
4
| int next_good(int wherebad)
{
return SUFFIX_TB[wherebad+1];
}
|
实现BM算法
每次比较选择坏字符和好后缀哪个可以让模式字符串走的更远。参数一个原串指针，一个模式串指针。返回值为匹配成功后，原串中目标子串的起始下标值。如果没找到则返回-1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| int boyer_moore(char const* const source, char const* const pattern)
{
init_suffix(pattern);
int src_len = strlen(source), pattern_len = strlen(pattern);
int i = pattern_len - 1, j = pattern_len - 1;
while (i < src_len)
{
while (source[i] == pattern[j] && j >= 0)
{
--i;
--j;
}
if (j < 0)
{
return ++i;
}
int next_bad_index = next_bad(source[i], pattern, j);
int next_good_index = next_good(j);
if (next_bad_index == -1 || next_good_index == -1)
{
if (next_bad_index == -1)
{
i += j + 1;
}
else if(next_good_index == -1)
{
i += pattern_len - 1 - next_bad_index;
}
}
else if (next_bad_index < next_good_index)
{
i += pattern_len - 1 - next_bad_index;
}
else if (next_good_index <= next_bad_index)
{
i += pattern_len - 1 - next_good_index + 1;
}
j = pattern_len - 1;
}
return -1;
}
|
测试
1
2
3
4
5
6
| int main()
{
int res = boyer_moore("GATTGCTAGATTAACTATACTAA", "CTATACTA");
return 0;
}
|
总结来说，
- 如果坏字符、好后缀都找到了。那么取最小值作为下一个的对齐点。
- 如果二者相等，则优先取好后缀。因为模式字符串重新对齐时，好后缀比坏字符更能多进1位。
- 如果至少有一个没找到：
- BM算法最大的易错点：如果找到了坏字符而没找到好后缀，则必须去对齐坏字符。因为好后缀有时候找不到是很正常的。如果跳过了这个坏字符，那么就会忽略中间的情况！
- 如果找到了好后缀而没找到坏字符，则忽略这个好后缀。因为模式串中根本就没有下一个坏字符，你去对齐好后缀是没意义的！所以，没找到坏字符就相当于二者都没找到！见2.3。
- 如果都没找到，则模式串起始点重新对齐到当前原串指示位置
i的下一个位置（实际上是调整i的值来做到对齐），j再挪到模式串的最后，重新从后向前一一匹配！
实际的场景
线上项目涉及到数据搜索、字符串匹配，如果数据量很大时，应用最多的其实是字典树、倒排索引的数据结构。例子：百度搜索、开源的Lucene、ElasticSearch（ElasticSearch是一个基于Lucene构建的开源项目）
1
2
3
4
5
6
7
8
9
| Lucene 和 Elasticsearch（ES）都主要基于倒排索引（Inverted Index）进行高效率搜索。
倒排索引是一种数据结构，用于快速查找包含特定词条（term）的文档。它将文档中的每个词条映射到包含该词条的文档列表，这样的索引结构使得搜索过程能够快速定位到包含特定词条的文档，而无需扫描整个文档集合。
在倒排索引中，每个词条都关联着一个包含该词条的文档列表（称为倒排列表），并且可以附加一些额外的信息，如词频、位置等。这使得搜索引擎可以快速定位到满足查询条件的文档，并根据相关度进行排序。
Lucene 是基于 Java 编写的搜索引擎库，提供了倒排索引的实现和管理功能，开发人员可以使用 Lucene 来构建自己的搜索引擎或搜索功能。而 Elasticsearch 是一个基于 Lucene 构建的分布式搜索和分析引擎，它使用 Lucene 的倒排索引作为核心数据结构，同时提供了分布式存储、查询和分析等功能，使得用户可以轻松地构建和管理大规模的搜索应用。
因此，倒排索引是 Lucene 和 Elasticsearch 实现高效率搜索的关键数据结构之一。
|
字典树
字典树是指基于树的一种数据结构，用于以一种能够高效搜索、插入和删除操作的方式存储一组键（通常是字符串）。Trie树（又称prefix tree）和三叉搜索树（Ternary Search Tree，又称T-tree、T树）是字典树的具体实现，各自具有其特点和优势。
- Trie树（前缀树）特别适用于需要进行前缀匹配和检索的任务，例如字典实现和自动完成系统。
- T树（三叉搜索树）在空间效率和快速字符串搜索操作之间提供了平衡。它们也适用于字典实现以及拼写检查和近似字符串匹配等任务。
总之，虽然Trie树和三叉搜索树是不同的实现，但它们都属于字典树类别，用于高效存储和检索键-值对，尤其是字符串。
其他树
B树
B树的全名是“Bayer–McCreight B树”。这是一种由Rudolf Bayer和Edward M. McCreight于1972年引入的数据结构。B树的名称来自于这两位作者姓氏的首字母。B树被广泛应用于数据库和文件系统中，用于高效地存储和检索数据，尤其是在处理大型数据集和基于磁盘的存储时。
T*树
T*树是B树数据结构的一种变体，旨在提高范围查询的性能，例如查找在给定范围内的所有值，与传统的B树相比。
在T*树中，每个节点可以有不同数量的子节点，通常范围在d到2d之间，其中d是树的最大度数。这允许更灵活地平衡树，并且可以使得树的高度相比传统的B树更浅，尤其是对于大型数据集而言。
T*树通过在其内部节点中存储额外的摘要信息来实现高效的范围查询性能，例如存储在其子树中的键的聚合值或范围。这样在范围查询期间可以更快地遍历和修剪不必要的子树。
总的来说，T*树旨在在保持B树的优点，如高效的插入、删除和搜索操作的同时，提供改进的范围查询性能。它们在数据库系统和其他需要高效范围查询的应用中被广泛使用。
B*树
B*树是B树的一种改进版本，旨在减少节点的分裂和合并操作，从而减少树的高度，提高查询性能。
与普通的B树不同，B*树在节点填满时不会立即进行分裂，而是等到达到阈值时才分裂，这样可以减少分裂的频率，减小树的高度。
B*树还通过在非叶节点中保留更多的键来减少合并操作的频率，从而进一步减小树的高度。
虽然B*树和T*树都是B树的变体，但它们的设计目标和实现方式略有不同。B*树的重点是减少树的高度，而T*树的重点是提高范围查询的性能。