单线程下单串全匹配算法比较

发表于
本文字数： 5.5k 阅读时长 ≈ 5 分钟

基本介绍

单串全匹配的常用算法有朴素查找,Knuth-Morris-Pratt(kmp),boyer moore(bm), boyer moore horspool(bmh), boyer moore horspool sunday(sunday)等算法，本文也是对这个几个算法在不同场景下的比较。

  • 朴素查找

优点是不需要辅助空间，缺点就是效率可能较低。朴素查找的实现通常有字符比对，内存比对，优化过的库函数，本文中的对应实现分别为bf,find_str,sys_str。

bf容易扩展，实现大小写的忽略及特殊类型序列的查找。
find_str利用内存比较函数，导致不易扩展。
库函数strstr，功能单一，常常无法适合场景，比如忽略大小写没有结尾符的数据。

  • kmp是利用匹配串的特性，每次比较后尽可能多的移动下标。需要匹配串长度*sizeof(类型)的辅助空间, 时间复杂度O(m+n)

  • bm也是利用匹配串的特性，每次比较后尽可能多的移动下标。bm设计了坏字符，好后缀的规则来加快移动下标。通常需要(匹配串长度+字符集大小)*sizeof(类型)的辅助空间。一般情况下，比KMP算法快3-5倍。该算法常用于文本编辑器中的搜索匹配功能，比如大家所熟知的GNU grep命令使用的就是该算法，这也是GNU grep比BSD grep快的一个重要原因。

  • bmh改变了bm的坏字符的规则，相比bm实现起来容易一些。通常需要字符集大小*sizeof(类型)的辅助空间。

  • sunday再次改变了bm的移动规则，相比bm更加简易。通常需要字符集大小*sizeof(类型)的辅助空间。

场景测试

测试场景的解释：

sys_str是在有结尾符时的匹配结果，sys_str_是无结尾符又不能修改原数据时模拟拷贝一遍数据后的匹配。

未预处理是所有数据重新计算的测试。

已预处理是在循环测试时，sys_str_只拷贝一次数据，其他算法只计算一次辅助数组的测试。

测试html场景,匹配项在头部 循环100000次

样本示例

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
...

<link rel="dns-prefetch" href="https://avatars1.githubusercontent.com">
  <link rel="dns-prefetch" href="https://avatars2.githubusercontent.com">
  <link rel="dns-prefetch" href="https://avatars3.githubusercontent.com">
  <link rel="dns-prefetch" href="https://github-cloud.s3.amazonaws.com">
  <link rel="dns-prefetch" href="https://user-images.githubusercontent.com/">

  <!-- This is my head pattern -->

  <link crossorigin="anonymous" media="all" integrity=
  "sha512-/YEVWs7BzxfKyUd6zVxjEQcXRWsLbcEjv045Rq8DSoipySmQblhVKxlXLva2G\\
  tNd5DhwCxHwW1RM0N9I7S2Vew=="
  rel="stylesheet" href="https://github.githubassets.com/assets/framewo\\
  rks-481a47a96965f6706fb41bae0d14b09a.css" />
  
    <link crossorigin="anonymous" media="all" integrity=
    "sha512-ZeXRnWYCu8+fvsUFY0/VTPql8vwvSfrBVUoZlQNG17AZTnz1N3mvsz8dmX7\\
    05rPZPJYQ/ekLzym0eof+ity3Ew=="
    rel="stylesheet" href="https://github.githubassets.com/assets/github\\
    -4aa6c31d1652b09080e404b2bf72f75c.css" />
    

  <meta name="viewport" content="width=device-width">
  
  ...
  • 未预处理
sys_str sys_str_ bf find_str kmp bm bmh sunday
0.215000 19.888000 0.366000 0.866000 0.806000 0.658000 0.157000 0.165000
  • 已预处理
sys_str sys_str_ bf find_str kmp bm bmh sunday
0.203000 0.253000 0.338000 0.731000 0.785000 0.062000 0.063000 0.062000

测试html场景,匹配项在中部 循环10000次

  • 未预处理
sys_str sys_str_ bf find_str kmp bm bmh sunday
1.099000 2.923000 1.485000 3.148000 2.777000 0.336000 0.140000 0.222000
  • 已预处理
sys_str sys_str_ bf find_str kmp bm bmh sunday
0.848000 0.848000 1.448000 3.352000 2.961000 0.219000 0.173000 0.175000

测试html场景,匹配项在尾部 循环1000次

  • 未预处理
sys_str sys_str_ bf find_str kmp bm bmh sunday
0.234000 0.435000 0.419000 0.914000 0.761000 0.069000 0.047000 0.034000
  • 已预处理
sys_str sys_str_ bf find_str kmp bm bmh sunday
0.290000 0.219000 0.428000 0.855000 0.812000 0.078000 0.047000 0.031000

测试html场景，长匹配项 循环1000次

  • 未预处理
sys_str sys_str_ bf find_str kmp bm bmh sunday
0.124000 0.331000 0.188000 0.376000 0.369000 2.005000 0.016000 0.000000
  • 已预处理
sys_str sys_str_ bf find_str kmp bm bmh sunday
0.110000 0.109000 0.188000 0.400000 0.380000 0.015000 0.000000 0.000000

测试碱基对序列场景-重复字符多场景 循环10000次

样本示例

...
>NM_001195662
AAGCTCAGCCTTTGCTCAGATTCTCCTCTTGATGAAACAAAGGGATTTCTGCACATGCTT
GAGAAATTGCAGGTCTCACCCAAAATGAGTGACACACCTTCTACTAGTTTCTCCATGATT
CATCTGACTTCTGAAGGTCAAGTTCCTTCCCCTCGCCATTCAAATATCACTCATCCTGTA
GTGGCTAAACGCATCAGTTTCTATAAGAGTGGAGACCCACAGTTTGGCGGCGTTCGGGTG
GTGGTCAACCCTCGTTCCTTTAAGACTTTTGACGCTCTGCTGGACAGTTTATCCAGGAAG
GTACCCCTGCCCTTTGGGGTAAGGAACATCAGCACGCCCCGTGGACGACACAGCATCACC
...
  • 未预处理
sys_str sys_str_ bf find_str kmp bm bmh sunday
0.047000 0.078000 0.063000 0.176000 0.093000 0.098000 0.031000 0.032000
  • 已预处理
sys_str sys_str_ bf find_str kmp bm bmh sunday
0.047000 0.032000 0.078000 0.153000 0.112000 0.016000 0.016000 0.031000

测试碱基对序列场景-重复字符多场景，长匹配项 循环10000次

样本示例

  • 未预处理
sys_str sys_str_ bf find_str kmp bm bmh sunday
0.047000 0.094000 0.063000 0.171000 0.125000 1.663000 0.046000 0.047000
  • 已预处理
sys_str sys_str_ bf find_str kmp bm bmh sunday
0.047000 0.035000 0.079000 0.166000 0.109000 0.016000 0.031000 0.034000

测试大文件场景 循环1次

长度为157,615,301

样本示例

...
/proc/registry/HKEY_LOCAL_MACHINE/SOFTWARE/Microsoft/Windows/CurrentVersion/\\
Component Based Servicing/Packages/Package_for_KB2552343_SP1~31bf3856ad364e35\\
~amd64~~6.1.1.0/InstallName
/proc/registry/HKEY_LOCAL_MACHINE/SOFTWARE/Microsoft/Windows/CurrentVersion/\\
Component Based Servicing\\
/Packages/Package_for_KB2552343_SP1~31bf3856ad364e35~amd64~~6.1.1.0/InstallL\\
ocation
/proc/registry/HKEY_LOCAL_MACHINE/SOFTWARE/Microsoft/Windows/CurrentVersion/\\
Component \\
Based Servicing/Packages/Package_for_KB2552343_SP1~31bf3856ad364e35~amd64~~6\\
.1.1.0/CurrentState
/proc/registry/HKEY_LOCAL_MACHINE/SOFTWARE/Microsoft/Windows/CurrentVersion/\\
Component \\
Based Servicing/Packages/Package_for_KB2552343_SP1~31bf3856ad364e35~amd64~~6\\
.1.1.0/SelfUpdate
/proc/registry/HKEY_LOCAL_MACHINE/SOFTWARE/Microsoft/Windows/CurrentVersion/\\
Component \\
Based Servicing/Packages/Package_for_KB2552343_SP1~31bf3856ad364e35~amd64~~6\\
.1.1.0/Visibility
...
  • 未预处理
sys_str sys_str_ bf find_str kmp bm bmh sunday
0.478000 0.999000 0.840000 1.490000 0.989000 0.034000 0.032000 0.081000
  • 已预处理
sys_str sys_str_ bf find_str kmp bm bmh sunday
0.421000 0.893000 0.767000 1.534000 1.078000 0.045000 0.031000 0.107000

总结

通常情况下库函数strstr要比bf,find_str方式要快一些。而kmp在理论上较快，但是也有慢的情况。bm算法通常情况表现的比kmp快一些，但也有慢的情况。bmh和sunday在不同情况下表现较为均衡。在重复测试时，可以观察到，做了预处理后，对效率有了显著的提升。

实际情况往往具有不同程度特殊性，如果像优化的更好，就要根据特殊性选择算法或者改进算法。

多线程情况下，可以将数据进行分段，分段后又变成这样的子问题。