Horspool算法

来自计算思维百科
跳转至: 导航搜索
Horspool算法1.png

Horspool算法是字符串匹配算法,用于在文本中查找字符串。

基本概念

Horspool算法的基本思想是从模式串(我们需要在文本中查找的字符串)的最后一个字符开始从右向左,比较模式串和文本中相应的字符。如果模式中所有的字符都匹配成功,就找到了一个匹配的字符串。如果我们遇到了一个不匹配的字符,我们需要把模式串右移,且移动的距离要尽可能大。假设文本中对齐模式最后一个字符的元素是字符c,Horspool算法可以根据c的不同情况来确定移动的距离:

情况1 如果模式串中不存在c,模式串移动的距离就是模式串的长度;

情况2 如果模式串中存在c,但它不是模式串最后一个字符,移动时应该把模式中最右边的c和文本中的c对齐;

情况3 如果c正好是模式中的最后一个字符,但是在模式的前面字符中不包含c,移动的距离就是模式串的长度;

情况4如果c是模式中的最后一个字符,而且在模式的前面字符中也包含c,移动时就应该把模式串的前面字符中最右边的c和文本中的c对齐。

下面通过例子来解释Horspool算法匹配的过程。

例如,在序列AGATACGATATATAC中搜索字符串ATATA

步骤一:先构造匹配失败时元素的移动距离表格,文本中有A、C、G、T,对每一个元素按照上述情况对应填写表格如下:

字符c

A

C

G

T

移动距离

2

5

5

1

步骤二:根据表格在文本中查找如下:

1)A G A T A C G A T A T A T A C

  A T A T A

  在主串的G处匹配失败,此时模式串向右移动的距离是2

2)A G A T A C G A T A T A T A C

     A T A T A

  又在主串G处失配,此时模式串向右移动的距离是5

3)A G A T A C G A T A T A T A C

              A T A T A

 此处发现了一个匹配,我们可以继续往下找,此时模式串向右移动的距离是2

4)A G A T A C G A T A T A T A C

             A T A T A

 又发现了一个匹配,再继续往下找吧,此时模式串向右移动的距离依然是2

5)A G A T A C G A T A T A T A C

                A T A T A

此时匹配结束,在文本中找出所有模式字符串。

 

应用范围

Horspool算法是字符串匹配算法,在计算机学科中常常用于在文本中查找需要的字符串。

使用方法及步骤

步骤一:构造匹配失败时模式串中元素的移动距离表格;

步骤二:根据移动距离表格进行匹配,找出模式串。

应用案例

应用1-Word

案例:在Office办公软件Word中同时按下Ctrl+F键会出现“查找和替换”对话框,我们可以在输入框中输入想要查找的字符串,然后它会帮我们在文档中标记出来。这个功能所用的算法就是字符串匹配算法。

应用2-搜索

案例:我们上网搜索信息时输入关键字后,搜索网站就会把输入的关键字和数据库中的资源进行匹配,找出我们需要的信息。

应用3-DNA鉴定技术

案例:目前DNA鉴定技术的使用越来越广泛,只要提取我们身上的任何东西都可以进行DNA鉴定。DNA鉴定用到的就是将两个DNA进行字符匹配。

可以体现的计算思维

Horspool算法中建立了移动距离表格,这个表格占用了更多的存储空间,但是提高了算法效率,这一做法体现计算思维中的“折中”特点。