[IR] String Matching

为了提高检索效率，大概有两种思路：

• 对文本做预处理，比如：BWT
• 对字符串做预处理，比如：KMP、Boyer-Moore

---

 

BWT

[IR] BWT+MTF+AC 中已经介绍了BWT (Burrows–Wheeler_transform)数据转换算法，

这种变换方式不仅方便压缩，同时对pattern search也带来了意想不到的好处。

 

事实上，BWT形式的数据，可以仅还原局部数据，而非必须还原完整的文件。

这个完整的搜索过程叫做：FM-index，包括三部分，①BWT（T），②checkpoint data，③一个简化了的SA[]数组。

 

Left

Symbol	#Less Than
A	0
B	3
N	4
[	6
]	7

 

Right

Position	Symbol		#Matching(idx)
0	B	3+0->3:[	0
1	N	0+4->4:A	0
2	N	4+1->5:A	1
3	[	E	0
4	A	0+0->0:B	0
5	A	0+1->1:N	1
6	]	S->7:A	0
7	A	0+2->2:N	2

 

图示化以上搜索过程(其中一步Postion:5)：

匹配的过程，实际就是搜索范围逐渐缩小的过程(backward search)，如下：

若能持续搜索到Pattern最后一个字符，则说明该字符串（pattern）在文本中。

时间复杂度就是O(len(pattern))。

 

若使用Run-length FM-Index压缩后，搜索的过程中要伴随着解码。

Continue: [IR] BWT+MTF+AC

 

index	Last	B	S	B'	Front	C
1	e	1	e	1	$	$
2	e	0	d	1	_	_
3	d	1	_	1	_	_
4	_	1	n	1	a	a
5	n	1	r	1	d	d
6	r	1	h	1	e	e
7	r	0	t	0	e	e
8	h	1	$	1	e	h
9	h	0	a	0	e	n
10	t	1	e	1	h	r
11	$	1	_	0	h	t
12	a	1		1	n
13	e	1		1	r
14	e	0		0	r
15	_	1		1	t

 

若不使用RLFM，原本的搜索方式如下（只考虑Last,Front列）

问题：index:13:e 的下一个是谁？（Notice：这里Last列与Front列左右位置与通常相反）

过程：

（1）‘右边’找‘左边’对应的index

     (i) index:13:e 先找‘左边’e block的首，也就是index:6。

     (ii)自己就是‘左边’e block的3rd e，故，‘左边’就是index:(6+3-1)=8,

（2）‘左边“相应的index对应的‘右边’是谁

     (i) 那么，index:8对应的‘右边’就是：h

 

若使用RLFM，搜索方式中伴随着解码（需还原出Last,Front列）

【红色字体部分现在需要解码才能得出】

（1）‘右边’找‘左边’对应的index

     (i) index:13:e 先找‘左边’e block的首，也就是index:6。（block定位）

         a: 如何由index:13解码出e？

            index:13通过B列数‘1’（包括自己）得出自己属于10th block。(index->block)

            10th block在S列中就是e。

         b: 如何解码找到‘左边’e block的首？　　 <--重大区别：e block这里变为"block1+block2"

            10th block在S列中就是e，且是第二个e(通过数一下前面的，包括自己)。

            先 e block定位，故，e在C列 --> 6th block

            6th block通过B'列数‘1’得出对应的‘左边’e₁:index:6。  (block->index)

     (ii)自己就是‘左边’e block的3rd e，故，‘左边’就是index:8,（block内部定位）

         a：为何是block中的3rd e？

            小block间位移：

            第二个e代表：e的block2在C列 --> 7th block

            7th block通过B'列数‘1’得出对应的‘左边’e₂:index:8。  (block->index)

            求block1->block2的位移：8-6=2

            小block间内部位移：

           ‘右边’的index=13或者14，在数'1'时（包括自己），前面都是有10个'1'。

            index:13所属block中的1st elem就是：上列中（包括自己）距离自己最近的‘1’的index，即：13

            显然index:13：e距离目前所属block中的1st e的距离是0（位移），故，自己就是‘e的block2’中的1st。

            最终，在‘左边’e block中的位移：

            答：2+1st=3rd e。

         b：为何是index:8(在‘左边’)？

            ‘左边’e Block内部定位：e₁:index:6 + 3rd - 1 = 8

 

（2）‘左边“相应的index对应的‘右边’是谁

     (i) 那么，index:8对应的右边就是：h

             与(1)(i)(a)同理,

             index:8通过B列数‘1’（包括自己）得出自己属于6th block。(index->block)

             6th block在S列中就是h.

 

(确实比较绕，呵呵呵呵)

 

---

 

Knuth-Morris-Pratt (KMP)

因为brute Force太蠢，所以有了该算法。

• Brute force pattern matching runs in time O(mn) in the worst case.
• But most searches of ordinary text take O(m+n), which is very quick.

 

 

那么，剩下的唯一问题就是，如何构造《部分匹配表》(Partial Match Table)

 

P[j]: The largest prefix of P[0 .. j-1] that is a suffix of P[1 .. j-1].

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

[0] ABACAB－　P[0 .. -1]的前缀和P[1 .. -1]的后缀为“非法”，共有元素的长度为-1；

[1] ABACAB－　P[0 .. 0]的前缀和P[1 .. 0]的后缀为空，共有元素的长度为0；

[2] ABACAB－　P[0 .. 1]的前缀为{A}，P[1 .. 1]的后缀为空，共有元素的长度为0；

[3] ABACAB－　P[0 .. 2]的前缀为{A, AB}，P[1 .. 2]的后缀为{A}，共有元素的长度为1；

[4] ABACAB－　P[0 .. 3]的前缀为{A, AB, ABA}，P[1 .. 3]的后缀为{AC, C}，共有元素的长度为0；

[5] ABACAB－　P[0 .. 4]的前缀为{A, AB, ABA, ABAC}，P[1 .. 4]的后缀为{ACA, CA, A}，共有元素的长度为1；

 

但，也有缺陷：

KMP doesn’t work so well as the size of the alphabet increases
– more chance of a mismatch (more possible mismatches)
– mismatches tend to occur early in the pattern, but KMP is faster when the mismatches occur later

 

---

 

Boyer-Moore Algorithm

算是一种改进形式，跟重视后缀；头部对齐，从尾部比较。 

Most text processors use BM for “find” (&“replace”) due to its good performance for general text documents.

Ref: 字符串匹配的Boyer-Moore算法

Link: http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

特点：《好字符规则》和《坏字符规则》，以最大移动值为准。

 

一个简单的示例：

Step 1

首先，"字符串"与"搜索词"头部对齐，从尾部开始比较。

这是一个很聪明的想法，因为如果尾部字符不匹配，那么只要一次比较，就可以知道前7个字符（整体上）肯定不是要找的结果。

我们看到，"S"与"E"不匹配。这时，"S"就被称为"坏字符"（bad character），即不匹配的字符。

我们还发现，"S"不包含在搜索词"EXAMPLE"之中，这意味着可以把搜索词直接移到"S"的后一位。如下：

 

Step 2

依然从尾部开始比较，发现"P"与"E"不匹配，所以"P"是"坏字符"。

但是，"P"包含在搜索词"EXAMPLE"之中。所以，将搜索词后移两位，两个"P"对齐。（利用了pattern内部的信息）

这个两位是怎么来的呢？

Ans:《坏字符规则》

后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置

 

OK，根据这个规则，再重新审视Step1 and Step2。

Step 1: 后移位数=6-(-1)=7　　// -1：在pattern中未发现坏字符

Step 2: 后移位数=6-4=2　　   //  4：在pattern中idx=4发现坏字符

 

However，这样是不够的，在某种情况下还不能达到更优的移动策略。

 

 

继续我们的示例：

Step 1

依然从尾部开始比较，"E"与"E"匹配；接下来，匹配了更多。

比较前面一位，"MPLE"与"MPLE"匹配。我们把这种情况称为"好后缀"（good suffix），即所有尾部匹配的字符串。

注意，"MPLE"、"PLE"、"LE"、"E"都是好后缀。

但接下来，继续比较前一位，发现"I"与"A"不匹配。所以，"I"是"坏字符"。

根据"坏字符规则"，此时搜索词应该后移 2 - （-1）= 3 位。如下：

但，看上去这个move不是很聪明的样子，显然可以一次性移动更多步。

初步看上去，并没有利用到Pattern中两次出现的E。

 

如何利用？

Ans:《好后缀规则》

后移位数 = 好后缀的位置 - Pattern中的上一次出现位置

 

OK，根据这个规则，再重新审视Step1。

 

Step 1: 后移位数=6-0=6　　// 0："好后缀"（MPLE、PLE、LE、E）之中[Ref:KMP"部分匹配表"]，只有"E"在"EXAMPLE"出现在头部，idx=0

1. "好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀，则它的位置以"F"为准，即5（从0开始计算）。
2. 如果"好后缀"在搜索词中只出现一次，则它的上一次出现位置为 -1。也就是pattern靠前的位置没有再出现了呢。
3. 如果"好后缀"有多个，
5. 1. 最长的那个"好后缀"，位置灵活；靠前位置出现的话，优先选！否则，查看其他“好后缀”。
   2. 其他"好后缀"，上一次出现位置必须在头部。

 

比如，假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B"，这时"好后缀"的上一次出现位置是什么？

BABCDAB

BABCDAB

BABCDAB　　<----

回答是，此时采用的好后缀是"B"，它的上一次出现位置是头部，即第0位。

这个规则也可以这样表达：如果最长的那个"好后缀"只出现一次，则可以把搜索词改写成如下形式进行位置计算"(DA)BABCDAB"，即虚拟加入最前面的"DA"。

 

更巧妙的是，这两个规则的移动位数，只与搜索词有关，与原字符串无关。因此，可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时，只要查表比较一下就可以了。

那么，如何事前制表？

Ref: http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

 

---

 

 

补充：签名文件索引（Signature File Index）

作为一种常用的索引组织方式，它在很多领域得到了应用。下面从存储和查询两个阶段对它进行介绍。

1．存储阶段

对于每个关键字，分配一个固定大小的向量（k-bit），这个向量叫做签名（Signature）；

对于一个网页文件，经过词典切分后，形成由对应关键字序列构成的向量，即P=<key1,key2,…,keym>，对这些关键字的签名做OR运算，就形成了网页文件的签名。这个过程也被称为重叠编码（Superimposed Coding）。

签名(Signature) = k-bit OR k-bit OR k-bit OR ...

然后把网页文件的签名结果依次存入一个个独立的文件中，形成对应的签名文件，这样形成的签名文件比原文件小很多。(大小不就取决于k了么？)

 

例如：有一页网页分词后有这样一些关键字“文本”、“英语”、“单词”、“信件”，假设将这些关键字经某哈希表散列成固定位的数字向量（以6位为例），分别为：

hash(文本)= 000110，

hash(英语)= 110001，

hash(单词)= 001101，

hash(信件)= 000111，

这些数字向量即为关键字的签名，然后将这些签名做OR运算，得到网页文件的签名。

 

2．查询阶段

接受用户查询语句Q，首先把用户查询串字符串切分成关键字序列，形成查询向量，即A=<key1,key2,…,keyn>。

然后把关键字映射成相应的向量签名，再与网页签名文件进行按位与运算，得到最后的匹配结果。

 

3．优缺点

签名文件索引方式是一种比较有效的索引机制，文件组织简单，基本和原文件顺序一致；

维护容易，生成、插入、删除都很方便；

所需空间小，特别是采用重叠编码之后；

实现比较简单，更新比较容易；

适合并行处理和分布式存储。

但是签名向量的大小选择是一个需要研究的问题，而且对于大的文本文件，必须进行分块处理，检索速度慢，需要顺序扫描。