字符串的匹配算法(一)

字符串的匹配算法(一)

BF(Brute Force)算法

基础概念:如果我们在A字符串中查找B字符串,那么A就是主串,B就是模式串.主串的长度设为n,模式串的长度设为m。

F算法就是拿模式串m,从主串n的第0位开始匹配,如果匹配不成功,则后移一位继续匹配,直到模式串每个字符与对应主串位置字符都相等,则返回主串对应下标,表示找到,否则返回 -1,表示没找到。

第一步

主串 :baddef (匹配不上后移一位

模式串:abc

第二步

主串 :baddef (匹配不上后移一位

模式串:abc

第三步

主串 :baddef (匹配不上后移一位

模式串:abc

第四步

主串 :baddef (匹配不上结束 def)

模式串:abc

BF 算法的时间复杂度最差是 O(n*m),意味着要模式串要移到主串 n-m 的位置上,并且模式串每个字符都要与子串比较。

尽管 BF 算法复杂度看起来很高,但是在日常开发中,如果主串和模式串规模不大的话,该算法依然比较常用,因为足够简单,实现起来容易,不容易出错。另外,在规模不大的情况下,开销也可以接受,毕竟 O(n*m) 是最差的表现,大部分时候,执行效率比这个都要高。


但是对于对时间要求比较敏感,或者需要高频匹配,数据规模较大的情况下,比如编辑器中的匹配功能、敏感词匹配系统等,BF 算法就不适用了

RK(Rabin-Karp)算法

数字的匹配比字符串快速,就把主串中的这n-m+1的子串分别求哈希值,然后在分别跟模式串的哈希值进行比较。
如果哈希值不一样那肯定不匹配,如果哈希值一样,因为哈希算法存在哈希冲突,这时候在拿模式串跟该子串对比一下就好了。

虽然模式串跟子串的对比速度提高了,但是我们事先需要遍历主串,逐个求子串的哈希值,这部分也挺耗时的,所以需要设计比较高效的哈希算法尽量的减少哈希冲突的产生。

RK复杂度通常被认为是O(n+m)

KMP算法



首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。




因为B与A不匹配,搜索词再往后移。



就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。



接着比较字符串和搜索词的下一个字符,还是相同。



直到字符串有一个字符,与搜索词对应的字符不相同为止。



这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把"搜索位置"移到已经比较过的位置,重比一遍。



一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。



怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。



已知空格与D不匹配时,前面六个字符"ABCDAB"是匹配的。查表可知,最后一个匹配字符B对应的"部分匹配值"

因此按照下面的公式算出向后移动的位数:

  移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4,所以将搜索词向后移动4位。



因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2("AB"),对应的"部分匹配值"为0。所以,移动位数 = 2 - 0,结果为 2,于是将搜索词向后移2位。



因为空格与A不匹配,继续后移一位。



逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 - 2,继续将搜索词向后移动4位。


逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 - 0,再将搜索词向后移动7位,这里就不再重复了。

《部分匹配表》是如何产生的

首先,要了解两个概念:"前缀"和"后缀"。
"前缀"指除了最后一个字符以外,一个字符串的全部头部组合;
"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例,

  - "A"的前缀和后缀都为空集,共有元素的长度为0;

  - "AB"的前缀为[A],后缀为[B],共有元素的长度为0;

  - "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

  - "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

  - "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;

  - "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;

  - "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。



"部分匹配"的实质是,有时候,字符串头部和尾部会有重复。比如,"ABCDAB"之中有两个"AB",那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候,第一个"AB"向后移动4位(字符串长度-部分匹配值),就可以来到第二个"AB"的位置。
KMP的整体时间复杂度为O(m + n)

tree树(前缀树)

Trie 树,也叫「前缀树」或「字典树」,顾名思义,它是一个树形结构,专门用于处理字符串匹配.
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质:

根节点不包含字符,除根节点外每一个节点都只包含一个字符。
从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。

Trie 树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起.

好比假设有b,abc,abd,bcd,abcd,efg,hii 这6个单词,构建的树就是如下图这样的:


这只是单个字符,如果是字符串则用前缀

如单词,inn, int, at, age, adv, ant, 可以得到下面的Trie:


Trie 树的复杂度

构建 Trie 树的过程比较耗时,对于有 n 个字符的字符串集合而言,需要遍历所有字符,对应的时间复杂度是 O(n),但是一旦构建之后,查询效率很高,如果匹配串的长度是 k,那只需要匹配 k 次即可,与原来的主串没有关系,所以对应的时间复杂度是 O(k),基本上是个常量级的数字。

Trie 树显然也是一种空间换时间的做法,构建 Trie 树的过程需要额外的存储空间存储 Trie 树,而且这个额外的空间是原来的数倍。

通过 Trie 树进行字符串匹配和之前介绍的 BF 算法和 KMP 算法有所不同,BF 算法和 KMP 算法都是在给定主串中匹配单个模式串,而 Trie 树是将多个模式串与单个主串进行匹配,因此,我们将 BF 和 KMP 这种匹配算法叫做单模式匹配算法,而将 Trie 树这种匹配算法叫做多模式匹配算法。
Trie 树适用于那些查找前缀匹配的字符串,比如敏感词过滤和搜索框联想功能。  
class TrieNode
{
public $data;
public $children = [];
public $isEndingChar = false;

public function __construct($data)
{
$this->data = $data;
}
}
class Tire {
private $root;

public function __construct() {
$this->root = new TrieNode('/'); //根节点
}

public function getRoot() {
return $this->root;
}

public function insert($text) {
$p = $this->root;
for ($i = 0; $i < mb_strlen($text); $i++) {
$index = $data = $text[$i];

if (empty($p->children[$index])) {
$newNode = new TrieNode($data);
$p->children[$index] = $newNode;
}
$p = $p->children[$index];
}
$p->isEndingChar = true;
}

public function find($pattern) {
$p = $this->root;
for ($i = 0; $i < mb_strlen($pattern); $i++) {
$index = $data = $pattern[$i];

if (empty($p->children[$index])) {
return false;
}
$p = $p->children[$index];
}
if ($p->isEndingChar == false) {
return false;
}
return true;
}
}

$trie = new Tire();
$strings = ['b','abc','abd','bcd','abcd','efg','hii'];
foreach ($strings as $str) {
$trie->insert($str);
}
if ($trie->find('bcd')) {
print "包含这个字符串\n";
} else {
print "不包含这个字符串\n";
}
print_r($trie->getRoot());