漫画:如何优化 “字符串匹配算法”?

:2020年02月18日 脚本之家
分享到:

说起“字符串匹配”,恐怕算得上是计算机领域应用最多的功能之一,为了满足这一需求,聪明的计算机科学家们发明了许多巧妙的算法。在上一篇漫画中,我们介绍了BF算法和RK算法,没看过的小伙伴可以先补补...

说起“字符串匹配”,恐怕算得上是计算机领域应用最多的功能之一,为了满足这一需求,聪明的计算机科学家们发明了许多巧妙的算法。

在上一篇漫画中,我们介绍了BF算法RK算法,没看过的小伙伴可以先补补课:

漫画:什么是字符串匹配算法?

今天,我们来介绍一种性能大大优化的字符串匹配算法。

BF算法是如何工作的?

正如同它的全称BruteForce一样,BF算法使用简单粗暴的方式,对主串和模式串进行逐个字符的比较。

比如给定主串和模式串如下:

它们的比较过程是什么样的呢?

第一轮,模式串和主串的第一个等长子串比较,发现第0位字符一致,第1位字符一致,第2位字符不一致:

第二轮,模式串向后挪动一位,和主串的第二个等长子串比较,发现第0位字符不一致:

第三轮,模式串继续向后挪动一位,和主串的第三个等长子串比较,发现第0位字符不一致:

以此类推,一直到第N轮:

当模式串挪动到某个合适位置,逐个字符比较,发现每一位字符都是匹配时,比较结束:

坏字符规则

“坏字符” 是什么意思?就是指模式串和子串当中不匹配的字符。

还以上面的字符串为例,当模式串和主串的第一个等长子串比较时,子串的最后一个字符T就是坏字符:

当检测到第一个坏字符之后,我们有必要让模式串一位一位向后挪动和比较吗?并不需要。

因为只有模式串与坏字符T对齐的位置也是字符T的情况下,两者才有匹配的可能。

不难发现,模式串的第1位字符也是T,这样一来我们就可以对模式串做一次“乾坤大挪移”,直接把模式串当中的字符T和主串的坏字符对齐,进行下一轮的比较:

坏字符的位置越靠右,下一轮模式串的挪动跨度就可能越长,节省的比较次数也就越多。这就是BM算法从右向左检测的好处。

接下来,我们继续逐个字符比较,发现右侧的G、C、G都是一致的,但主串当中的字符A,是又一个坏字符:

我们按照刚才的方式,找到模式串的第2位字符也是A,于是我们把模式串的字符A和主串中的坏字符对齐,进行下一轮比较:

接下来,我们继续逐个字符比较,这次发现全部字符都是匹配的,比较公正完成:

  1. //在模式串中,查找index下标之前的字符是否和坏字符匹配

  2. private

  3. static

  4. int

  5. findCharacter

  6. (

  7. String

  8. pattern

  9. ,

  10. char

  11. badCharacter

  12. ,

  13. int

  14. index

  15. )

  16. {

  17. for

  18. (

  19. int

  20. i

  21. =

  22. index

  23. -

  24. 1

  25. ;

  26. i

  27. >=

  28. 0

  29. ;

  30. i

  31. --){

  32. if

  33. (

  34. pattern

  35. .

  36. charAt

  37. (

  38. i

  39. )

  40. ==

  41. badCharacter

  42. ){

  43. return

  44. i

  45. ;

  46. }

  47. }

  48. //模式串不存在该字符,返回-1

  49. return

  50. -

  51. 1

  52. ;

  53. }

  54. public

  55. static

  56. int

  57. boyerMoore

  58. (

  59. String

  60. str

  61. ,

  62. String

  63. pattern

  64. )

  65. {

  66. int

  67. strLength

  68. =

  69. str

  70. .

  71. length

  72. ();

  73. int

  74. patternLength

  75. =

  76. pattern

  77. .

  78. length

  79. ();

  80. //模式串的起始位置

  81. int

  82. start

  83. =

  84. 0

  85. ;

  86. while

  87. (

  88. start

  89. <=

  90. strLength

  91. -

  92. patternLength

  93. )

  94. {

  95. int

  96. i

  97. ;

  98. //从后向前,逐个字符比较

  99. for

  100. (

  101. i

  102. =

  103. patternLength

  104. -

  105. 1

  106. ;

  107. i

  108. >=

  109. 0

  110. ;

  111. i

  112. --)

  113. {

  114. if

  115. (

  116. str

  117. .

  118. charAt

  119. (

  120. start

  121. +

  122. i

  123. )

  124. !=

  125. pattern

  126. .

  127. charAt

  128. (

  129. i

  130. ))

  131. //发现坏字符,跳出比较,i记录了坏字符的位置

  132. break

  133. ;

  134. }

  135. if

  136. (

  137. i

  138. <

  139. 0

  140. )

  141. {

  142. //匹配成功,返回第一次匹配的下标位置

  143. return

  144. start

  145. ;

  146. }

  147. //寻找坏字符在模式串中的对应

  148. int

  149. charIndex

  150. =

  151. findCharacter

  152. (

  153. pattern

  154. ,

  155. str

  156. .

  157. charAt

  158. (

  159. start

  160. +

  161. i

  162. ),

  163. i

  164. );

  165. //计算坏字符产生的位移

  166. int

  167. bcOffset

  168. =

  169. charIndex

  170. >=

  171. 0

  172. ?

  173. i

  174. -

  175. charIndex

  176. :

  177. i

  178. +

  179. 1

  180. ;

  181. start

  182. +=

  183. bcOffset

  184. ;

  185. }

  186. return

  187. -

  188. 1

  189. ;

  190. }

  191. public

  192. static

  193. void

  194. main

  195. (

  196. String

  197. []

  198. args

  199. )

  200. {

  201. String

  202. str

  203. =

  204. "GTTATAGCTGGTAGCGGCGAA"

  205. ;

  206. String

  207. pattern

  208. =

  209. "GTAGCGGCG"

  210. ;

  211. int

  212. index

  213. =

  214. boyerMoore

  215. (

  216. str

  217. ,

  218. pattern

  219. );

  220. System

  221. .

  222. out

  223. .

  224. println

  225. (

  226. "首次出现位置:"

  227. +

  228. index

  229. );

  230. }

好后缀规则

“好后缀” 又是什么意思?就是指模式串和子串当中相匹配的后缀。

让我们看一组新的例子:

对于上面的例子,如何我们继续使用“坏字符规则”,会有怎样的效果呢?

从后向前比对字符,我们发现后面三个字符都是匹配的,到了第四个字符的时候,发现坏字符G:

接下来我们在模式串找到了对应的字符G,但是按照坏字符规则,模式串仅仅能够向后挪动一位:

这时候坏字符规则显然并没有起到作用,为了能真正减少比较次数,轮到我们的好后缀规则出场了。由于好后缀规则的实现细节比坏字符规则要难理解得多,所以我们这里只介绍一个大概思路:

我们回到第一轮的比较过程,发现主串和模式串都有共同的后缀“GCG”,这就是所谓的“好后缀”。

如果模式串其他位置也包含与“GCG”相同的片段,那么我们就可以挪动模式串,让这个片段和好后缀对齐,进行下一轮的比较:

显然,在这个例子中,采用好后缀规则能够让模式串向后移动更多位,节省了更多无谓的比较。

文/  王振袢
关键词: 说起 字符串匹配 恐怕 得上 计算机

来源:本文内容搜集或转自各大网络平台,并已注明来源、出处,如果转载侵犯您的版权或非授权发布,请联系小编,我们会及时审核处理。
声明:江苏教育黄页对文中观点保持中立,对所包含内容的准确性、可靠性或者完整性不提供任何明示或暗示的保证,不对文章观点负责,仅作分享之用,文章版权及插图属于原作者。

您在阅读:漫画:如何优化 “字符串匹配算法”?

Copyright©2013-2020 JSedu114 All Rights Reserved. 江苏教育信息综合发布查询平台保留所有权利

苏公网安备32010402000125苏ICP备14051488号-3南京思必达教育科技有限公司版权所有

技术支持:南京博盛蓝睿网络科技有限公司  

最热文章
最新文章
  • 卡尔蔡司镜片优惠店,镜片价格低
  • 苹果原装手机壳