算法 – 字符串相似性：Bitap如何工作？

发布时间：2020-12-14 04:17:15 所属栏目：大数据来源：网络整理

导读：我试图围绕 Bitap算法,但是我无法理解算法的步骤背后的原因. 我理解算法的基本前提,这是(如果我错了,纠正我)： Two strings: PATTERN (the desired string) TEXT (the String to be perused for the presence of PATTERN)Two indices: i (currently processi

我试图围绕 Bitap算法,但是我无法理解算法的步骤背后的原因.

我理解算法的基本前提,这是(如果我错了,纠正我)：

Two strings:     PATTERN (the desired string)
                 TEXT (the String to be perused for the presence of PATTERN)

Two indices:     i (currently processing index in PATTERN),1 <= i < PATTERN.SIZE
                 j (arbitrary index in TEXT)

Match state S(x): S(PATTERN(i)) = S(PATTERN(i-1)) && PATTERN[i] == TEXT[j],S(0) = 1

如果前一个子字符串PATTERN.substring(0,i-1)成功匹配且PATTERN [i]中的字符与TEXT中的字符相同,PATTERN.substring(0,i)将匹配TEXT的子字符串[J].

我不明白的是这个位移的实现. The official paper detailing this algorithm basically lays it out,但我似乎无法想象应该怎么做.算法规范只是本文的前2页,但我将重点介绍重要的部分：

这是概念的位移版本：

这是一个示例搜索字符串的T [文本]：

这里是一个跟踪的算法.

具体来说,我不明白T表示什么,以及在当前状态下将条目置于其中的原因.

如果有人能帮助我了解究竟发生了什么,我将不胜感激

解决方法

T有点混乱,因为你通常会在位置上排名
从左到右的格局：

0 1 2 3 4
a b a b c

…而位通常从右到左编号.

但写作
在位之上向后的图案清楚：

  bit: 4 3 2 1 0

       c b a b a
T[a] = 1 1 0 1 0

       c b a b a
T[b] = 1 0 1 0 1

       c b a b a
T[c] = 0 1 1 1 1

       c b a b a
T[d] = 1 1 1 1 1

如果x出现在位置n,则T [x]的位n为0,如果不存在,则为1.

同样地,你可以想到这一点,如果现在的人物
在输入字符串中为x,您在T [x]的位置n中看到0,那么您就可以了
如果匹配开始n个字符,则只能匹配该模式
先前.

现在到匹配程序.状态的位n中的0表示我们开始匹配n个字符之前的模式(其中0是当前字符).最初没有什么比赛.

[start]
1 1 1 1 1

当我们消费字符试图匹配时,状态向左移动(将零移动)
到底部位,位0)并与当前字符的表条目进行OR-ed.第一个字符是向左移动,并在T [a]中进行OR运算：

a
1 1 1 1 0

被移入的0位被保留,因为可以的当前字符
开始一个匹配的模式.对于任何其他字符,该位将被设置为
1.

状态的位0现在为0意味着我们开始匹配模式
当前人物;继续,我们得到：

a b
1 1 1 0 1

…因为0位已经左移 – 想到这样说,我们开始匹配模式1个字符,而T [b]在同一个位置有一个0,告诉
如果我们开始匹配1个字符,我们现在看到一个b是好的
前.

a b d
1 1 1 1 1

d无法匹配;所有位都设置为1.

a b d a
1 1 1 1 0

像之前一样.

a b d a b
1 1 1 0 1

像之前一样.

b d a b a
1 1 0 1 0

如果匹配从2个字符以前或当前字符开始,a是好的.

d a b a b
1 0 1 0 1

如果匹配从1或3个字符开始,b是好的.位3中的0表示
我们几乎匹配了整个模式…

a b a b a
1 1 0 1 0

…但下一个字符是一个,如果匹配开始4个字符是不好的
前.然而,较短的比赛可能还是不错的.

b a b a b
1 0 1 0 1

还好看

a b a b c
0 1 1 1 1

最后,如果比赛开始4个角色,c是好的.事实上一个0已经使它一直到顶部位意味着我们有一个匹配.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!