Boyer–Moore 字符串搜索算法的移位规则是什么?

2024-03-17

我一直在尝试理解轮班规则Boyer–Moore 字符串搜索算法但还没有理解他们。我读到这里维基百科 http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm但那太复杂了!

如果有人以简单的方式列出规则,将会有很大的帮助。


在 Boyer-Moore 算法中,您从模式末尾开始将模式字符与文本字符进行比较。如果您发现不匹配,则您拥有该类型的配置

....xyzabc....      <-text
  ....uabc          <- pattern
      ^
    mismatch

Now the 不良性格转变表示移动模式,以便不匹配的文本字符与模式初始部分中最后一次出现的该字符对齐(模式减去最后一个模式字符)(如果存在这样的情况),或者与模式之前的一个位置对齐如果不匹配的字符根本没有出现在模式的初始部分。

如果情况是这样的话,这可能会向左移动

     v
...xyzazc...
 ....uazc
 ..uazc

因此,仅凭这一点并不能保证取得进展。

另一个转变,好的后缀移位,对齐文本的匹配部分,m,该字符序列在模式中最右边出现的位置与匹配的后缀不同,该字符前面有一个不同的字符(如果匹配的后缀也是模式的前缀,则不包含任何字符)m模式的 - 如果发生这种情况。

例如

           v
....abcdabceabcfabc...
    ...xabcfabcfabc
        ...xabcfabcfabc

会导致后缀良好地移动四个位置,因为匹配的部分m = abcfabc出现在模式中其后缀出现左侧的四个位置,并且前面有一个不同的字符 (x代替f) 比后缀位置。

如果模式中没有完全出现前面有与后缀不同的字符的匹配部分,则良好的后缀移位会将文本的匹配部分的后缀与模式的前缀对齐,选择最大重叠,例如

      v
...robocab....
    abacab
        abacab

好的后缀移位总是将模式向右移动,因此保证了进展。

然后,在每次不匹配时,比较坏字符移位和好后缀移位的进展,并选择较大者。 Christian Charras 和 Thierry Lecroq 对其进行了更深入的解释here http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140,以及许多其他字符串搜索算法。


对于您在评论中提到的示例,

SSIMPLE EXAMPLE
EXAMPLE
  ^

匹配的后缀是MPLE,不匹配的文本字符是I。所以坏字符移位会寻找最后一次出现的I在模式的初始部分。没有,因此错误的字符转换会改变模式,从而导致不匹配I是模式开始之前的一个

SSIMPLE EXAMPLE
   EXAMPLE

好的后缀移位会寻找最右边出现的MPLE在图案中not前面有一个A,或最长的后缀MPLE这是模式的前缀。模式中的匹配部分在后缀之前没有完全出现,因此匹配部分的最长后缀(同时也是模式的前缀)决定了良好的后缀移位。在这种情况下,匹配部分的两个后缀(即模式的前缀)是单字符串E和空字符串。最长的显然是非空字符串,所以好的后缀移位对齐单字符后缀E在文本的匹配部分与模式的单字符前缀

SSIMPLE EXAMPLE
      EXAMPLE

好的后缀移位会将模式进一步向右移动,因此这就是所选的移位。

然后在最后一个模式位置立即出现不匹配,然后错误的字符移位与P在文本中与P在模式中(如果不匹配发生在最后一个模式字符处,则根本不需要考虑好后缀移位,因为在这种情况下,它永远不会产生比坏字符移位更大的移位)。

然后我们就有了完整的比赛。

在带有图案的变体中TXAMPLE,好的后缀移位发现匹配部分的非空后缀没有一个是模式的前缀(并且模式中没有出现完整的匹配部分not之前是A),所以好的后缀移位会对齐文本匹配部分的空后缀(E和空格)以及模式的空前缀(前面的空字符串T), 导致

SSIMPLE EXAMPLE
       TXAMPLE

(然后在下一步中,坏字符移位将两个字符对齐Ls,此后步骤中的下一个不匹配发生在初始位置T的模式)。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

Boyer–Moore 字符串搜索算法的移位规则是什么? 的相关文章

  • 为无向无权图实现推重标签算法 s-t 最小割边

    我正在寻找一个好的解决方案来在无向和未加权图中找到 s t 最小切割边 我想使用推送重新标记算法 但我不确定如何实现它以在无向和未加权图上找到最小割 在每对顶点之间有两条反向边 并在所有边上赋予相同的权重 并应用推送重新标记算法 我可以用这
  • Bellman-Ford 算法检测什么?负重还是负循环?

    如果给定一个图 现在我们要从源头计算最短路径 现在 如果一条边具有负权重 但在到达目的地时有边到后边返回到该边 我的意思是如果没有循环 那么我们就没有负循环 但是here http en wikipedia org wiki Bellman
  • 如何设置K-means openCV c++的初始中心

    我正在尝试使用 OpenCv 和 Kmeans 对图像进行分割 我刚刚实现的代码如下 include opencv2 objdetect objdetect hpp include opencv2 highgui highgui hpp i
  • 交换两个向量之间的值,使两个向量的 max_element 之和最小

    这是 Codechef 的问题 但请耐心等待 https www codechef com ZCOPRAC problems ZCO16001 https www codechef com ZCOPRAC problems ZCO16001
  • 合并字符数组中的最小重复次数

    假设我有两个数组 我想合并它们 以便合并后的数组具有最小重复次数 例如 x x 是重复 arr1 x d d m f m arr2 d d x f f m 唯一的条件是在合并数组中 元素来自arr1 and arr2必须出现在各自的订单中a
  • 反转二进制网络

    如何反转二元方程 以便找到哪些输入将产生给定的输出 Example Inputs i0 through i8 Outputs o0 through o8 Operators XOR AND 二元方程 1 i0 1 i1 0 i2 1 i3
  • C 中的菱形数组排序

    我有以下 C 语言作业 我基本上需要一种方法而不是解决方案 我们有一个 13 x 13 的数组 在数组中 我们有一个需要考虑的菱形形状 该菱形之外的所有内容都初始化为 1 不重要 下面的 5 x 5 数组示例 x x 1 x x x 2 2
  • Python 给定 k 个分区的整数分区

    我正在尝试寻找或开发Python 的整数分区代码 仅供参考 整数分区将给定整数 n 表示为小于 n 的整数之和 例如 整数5可以表示为4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 我为此找到了许多解决方案 ht
  • 在 O(n) 时间内找到 n x n 矩阵中的局部最小值

    所以 这不是我的家庭作业问题 而是取自 coursera 算法和数据结构课程的未评分作业 现已完成 You are given an n by n grid of distinct numbers A number is a local m
  • 编程 Pearls - 随机选择算法

    Programming Pearls 第一版第 120 页介绍了从 N 个整数总体中选择 M 个等概率随机元素的算法 InitToEmpty Size 0 While Size lt M do T RandInt 1 N if not Me
  • 将嵌套字典中的所有键从camelCase转换为snake_case

    我有一本类似这样的字典 firstName abc lastName xyz favoriteMovies Star Wars The lone ranger favoriteCountries country China capitalC
  • 检索受“rowspan”影响的行的列索引的最有效方法是什么?

    考虑下表 table thead tr th th th A th th B th th C th tr thead tbody tr th 1 th td Apples td td Oranges td td Pears td tr tb
  • 如何从一组重叠的圆计算多边形集?

    这个问题是一些计算细节的扩展这个问题 https stackoverflow com questions 1667310 combined area of overlapping circles 假设有一组 可能重叠的 圆 并且希望计算这组
  • 图中的后边

    I m having a hard time understanding Tarjan s algorithm for articulation points I m currently following this tutorial he
  • 快速搜索压缩文本文件

    我需要能够在大量压缩文件 txt 中搜索文本 压缩可能会改变为其他东西 甚至成为专有的 我想避免解压所有文件并压缩 编码 搜索字符串并在压缩文件中搜索 这应该可以通过对所有文件使用相同的码本使用霍夫曼压缩来实现 我不想重新发明轮子 所以 任
  • 如何求小于给定数的最大2次方

    我需要找到小于给定数字的最大 2 次幂 我陷入困境 找不到任何解决方案 Code public class MathPow public int largestPowerOf2 int n int res 2 while res lt n
  • 寻找将集合映射到整数的双射函数

    对于任意两个序列 a b 其中 a a1 a2 an 且 b b1 b2 bn 0a b具有相同的元素 而不关心它们的顺序 例如 如果 a 1 1 2 3 b 2 1 3 1 c 3 2 1 3 则 f a f b f a f b 我知道有
  • 关于在字典中查找所有有效单词的算法问题

    给定一个字典 只是一个字符串列表 您收到来自外部来源的未知数量的信件 给定字母串 您将如何列出您可以通过这些字母的任意组合组成的所有有效单词 来自字典 因此 如果您收到 applead 你应该找到apple bad pad lead等 我知
  • URL路径相似度/字符串相似度算法

    我的问题是我需要比较 URL 路径并推断它们是否相似 下面我提供了要处理的示例数据 GROUP 1 robots txt GROUP 2 bot html GROUP 3 phpMyAdmin 2 5 6 rc1 scripts setup
  • 使用并集查找(又名不相交集)检测图是否是二分图

    我正在 Spoj 上做一个问题 基本上可以简化为检测图是否是二分图 我正在尝试使用 dfs 为图表着色 但它太慢了 有人评论这个 没有 bfs 没有 dfs 没有二部图 简单的并查集就可以做到 确实速度很快 提示 1 偶数长度的环不会影响两

随机推荐

  • 使用 ws4py 创建自己的应用程序

    我使用 ws4py 创建了一个 Web 服务器套接字 它使用了cherrypy 当我使用连接到服务器时ip port它连接完美 并且能够通过多个浏览器聊天 但是当我尝试连接时ip port ws它也有效 但是 在我不使用连接后ws 我无法握
  • jQuery 中的多个选择器

    我正在尝试运行这段代码 input value OK value Recrutar value Criar id attack name btn click 因此 如您所见 我正在尝试选择一个值等于 OK 或 Recrutar 或 Cria
  • 为什么IntelliJ Idea找不到GO SDK的位置?

    我下载了go1 4 darwin amd64 osx10 8 tar gz https golang org dl 并将其解压到我的本地目录中 基于什么安装到自定义位置 https golang org doc install说我在环境变量
  • jQuery - 专注于 TR

    好的 所以我正在制作一个插件 允许在我的网站中内联编辑表格 到目前为止进展顺利 我已经完成了大部分工作 但我似乎无法正确地将焦点移出表格 因此 如果有人完成编辑并开始编辑新行或只是单击该行之外的内容 则应该保存并恢复正常 但是 如果我在行上
  • Android NumberPicker 隐藏递增和递减按钮

    我正在使用一个数字选择器 http developer android com reference android widget NumberPicker html并且目标是 API 11 及更高版本 3 0 及更高版本 因此我使用受支持的
  • 如何在 R 中加载以 HDF5 文件形式保存在 pandas 中的数据帧?

    我将 pandas 中的数据帧保存在 HDF5 文件中 import numpy as np import pandas as pd np random seed 1 frame pd DataFrame np random randn 4
  • 如何使用 Perl 的 XML::Twig 向子元素添加属性?

    我有一个像这样的 XML 字符串
  • phpstorm symfony2 缺少服务警告

    我已经为 Phpstorm 安装了 Symfony2 插件 但我无法让 IDE 查看这些现有服务或其他注入的对象 能否以某种方式修复这些问题 从而使警告消失 我遇到了类似的问题 建议仔细检查以下内容 正如 Marcel建议的 检查你的Sym
  • AngularJS v1.3 打破翻译过滤器

    在 Angular v1 2 中 我使用以下代码在应用程序中提供本地化字符串 var i18n angular module i18n i18n service i18n function http timeout A dictionary
  • pyplot.subplots:python 和 jupyter 笔记本中的不同行为

    在参加 Kaggle 比赛时 我遇到了一些奇怪的问题 基本上 我正在尝试将 am 图像的矢量表示形式转换为 png 文件 它在 iPython 中完美运行 代码如下 def drawing to np prepare data drawin
  • 为什么 .Net 没有 Thread.Start() 的通用版本?

    我想知道为什么 Net 没有启动线程的通用方法 例如 我们启动一个像下面这样的线程 Thread th new Thread SayHello th Start Hello private static void SayHello obje
  • 具有单一选择的列表框,并且单击时也取消选择...?

    我需要一个在第一次单击时选择并在第二次单击时取消选择的列表框 以便任何时候只选择零个或一个项目 当您按住 crtl 时 选择 取消选择是在列表框中实现的 SelectionMode Single 但不幸的是 我的用户都不知道这一点 使用 S
  • 自定义 Django 管理索引页面以显示模型对象

    在 Django 管理索引页面中 通常会列出应用程序及其模型 模型对象如何也列在该索引页中 我不仅想显示应用程序 还想显示其模型对象 应该如何定制呢 我希望我的网站具有相同的功能 并通过对核心 django 系统进行轻微修改来添加它 Ste
  • appium - 如何获取本机 Android 应用程序中元素的背景颜色

    我正在尝试使用自动化应用程序appium 如何获取 Android 应用程序中元素的背景颜色 我尝试使用 element getCssValue background color 但我面临以下异常 java lang ClassCastEx
  • 数据流图构建

    我被要求编写一个程序 在给定抽象语法树的情况下构建输入程序代码的数据流图 我在网上搜索了数据流图的定义 发现在代码段的数据流分析中发生了很多事情 我想知道我到底需要绘制什么来为给定的代码构建数据流图 很感谢任何形式的帮助 给定 AST 要生
  • char类型可以归类为整数吗?

    刚才我读到 char是Java中唯一的无符号整型原始类型 这是否意味着 char 是 Java 中的整型类型之一 和C一样 最近我读到C类型包括标量类型 函数类型 联合类型 聚合类型 标量类型包括指针类型和算术类型 那么算术类型包括整型和浮
  • 查找特定元素之前和之后的元素

    我有一个列表 其中包含我与选项卡一起使用的链接 它看起来像这样 ul li a href First tab a li li a href Second tab a li li class active a href Active tab
  • google/guava 库出现 Spark 错误:java.lang.NoSuchMethodError: com.google.common.cache.CacheBuilder.refreshAfterWrite

    我有一个简单的spark项目 其中在pom xml依赖只是基本的scala scalatest junit and spark
  • 字符串中的前两个单词 - sql server

    我有这样的字符串 这是一个 hello world 示例 现在我想要该句子的前两个单词作为 SQL Server 中的输出 即这是 另一个例子 原句 完整的单词练习 输出 完整的单词 您可以按如下方式使用查询 DECLARE d nvarc
  • Boyer–Moore 字符串搜索算法的移位规则是什么?

    我一直在尝试理解轮班规则Boyer Moore 字符串搜索算法但还没有理解他们 我读到这里维基百科 http en wikipedia org wiki Boyer E2 80 93Moore string search algorithm