近似字符串匹配 - 行式位并行算法（BPR）

引言

近似字符串匹配，也称为“允许错误的字符串匹配”，是在文本T中查找模式p的问题，允许模式和文本中其出现之间存在有限数量k的差异。

解决方案

该问题的最古老的解决方案依赖于动态规划。例如，请参阅 Code Project 上的 Levenstein 距离实现 (www.codeproject.com/KB/recipes/fuzzysearch.aspx) 或 Wikipedia (http://en.wikipedia.org/wiki/Fuzzy_string_searching)。

考虑近似搜索问题的另一种非常有用的方法是使用非确定有限自动机 (NFA) 对搜索进行建模。考虑k = 2 错误的 NFA。每一行表示看到的错误数。每一列表示匹配模式前缀。水平箭头表示匹配一个字符（即，如果模式和文本字符匹配，则在模式和文本中前进）。所有其他箭头通过移动到下一行来增加错误数：垂直箭头在模式中插入一个字符（我们在文本中前进，但不前进模式），短对角箭头替换一个字符（我们在文本和模式中前进），长对角箭头删除模式的一个字符（它们是e-transitions，因为我们在模式中前进，但不前进文本）。初始自环允许在文本中的任何位置开始出现。当活动的最右侧状态时，自动机发出（出现）的信号。

BPR 算法

位并行算法是一种简单快速的方法，可以利用它们更高的引用局部性来编码 NFA 状态。以下是本书“字符串中的灵活模式匹配”（请参阅“参考文献”了解更多信息）中描述的此算法的伪代码。

BPR (p = p1p2...pm, T = t1t2...tn, k)
1.    Preprocessing
2.        For c e S Do B[c] <- 0m
3.        For j e 1 ... m Do B[pj] <- B[pj] | 0m-j10j-1
4.    Searching
5.       For i e 0 ... k Do Ri <- 0m-i1i
6.       For pos e 1 ... n Do
7.            oldR <- R0
8.            newR <- ((oldR << 1) | 1) & B[tpos]
9.            R0 <- newR
10.           For i e 1 ... k Do
11.              newR <- ((Ri << 1) & B[tpos]) | oldR | ((oldR | newR) << 1)
12.              oldR <- Ri, Ri <- newR
13.           End of for
14.           If newR & 10m-1 <> 0 Then report an occurrence at pos
15.      End of for

例如，让我们在“brain”文本中搜索模式“rain”，允许 2 个错误。我们从 B= 开始

r	0001
a	0010
i	0100
n	1000
*	0000

和 { R0=0000 R1=0001 R2=0011 }。以下是逐步运行

b - 0000

R0- 0000

R1- 0000

R2- 0011

r - 0001

R0- 0001

R1- 0010

R2- 0100

a - 0010

R0- 0010

R1- 0111

R2- 1110

在位置 3 处出现

i - 0100

R0- 0100

R1- 1110

R2- 11111

在位置 4 处出现

n - 1000

R0- 1000

R1- 1100

R2- 1110

在位置 5 处出现

C# 实现

public static void BPR(string pattern, string text, int errors)
        {
            int[] B = new int[ushort.MaxValue];
            for (int i = 0; i < ushort.MaxValue; i++) B[i] = 0;
            // Initialize all characters positions
            for (int i = 0; i < pattern.Length; i++)
            {
                B[(ushort)pattern[i]] |= 1 << i;
            }
            // Initialize NFA states
            int[] states = new int[errors+1]; 
            for(int i= 0; i <= errors; i++)
            {
                states[i] = (i == 0) ? 0 : (1 << (i - 1) | states[i-1]);
            }
            //
            int oldR, newR;
            int exitCriteria = 1 << pattern.Length -1;

            for (int i = 0; i < text.Length; i++)
            {
                oldR = states[0];
                newR = ((oldR << 1) | 1) & B[text[i]];
                states[0] = newR;

                for (int j = 1; j <= errors; j++)
                {
                    newR = ((states[j] << 1) & B[text[i]]) | oldR | ((oldR | newR) << 1);

                    oldR = states[j];
                    states[j] = newR;
                }
            
                if ((newR & exitCriteria) != 0) 
                    Console.WriteLine("Occurrence at position {0}", i+1);

            }
      } 

参考文献

• 字符串中的灵活模式匹配：文本和生物序列的实用在线搜索算法 由 Gonzalo Navarro 和 Mathieu Raffinot 著，剑桥大学出版社 © 2002 (221 页)