博耶Moore算法的理解和实例？ [英] Boyer Moore Algorithm Understanding and Example?

问题描述

我现在面临的理解博耶·摩尔字符串搜索算法的问题。

I am facing issues in understanding Boyer Moore String Search algorithm.

我下面下面的文档。 链接

I am following the following document. Link

我无法对我的工作方式，作为对什么是DELTA1和DELTA2的真正意义在这里，它们是如何被应用此找到字符串搜索算法。 语言显得有点含糊。

I am not able to work out my way as to exactly what is the real meaning of delta1 and delta2 here, and how are they applying this to find string search algorithm. Language looked little vague..

请，如果有人在那里可以帮助我理解这一点，这将是非常有益的。

Kindly if anybody out there can help me out in understanding this, it would be really helpful.

或者，如果您知道任何其他链接或提供的文件，是很容易理解的话，请分享一下。

Or, if you know of any other link or document available that is easy to understand, then please share.

在此先感谢。

推荐答案

第一条建议，深呼吸。你明确强调，当你感到有压力首先发生的事情是，你的大脑大块关闭。这使得很难理解，这增加了压力，和你有一个问题。

First piece of advice, take a deep breath. You're clearly stressed, and when you're stressed the first thing that happens is that large chunks of your brain shut down. This makes understanding hard, which increases stress, and you've got a problem.

5分钟的超时，以提高你的顶空似乎不可能采取，但也可以是出奇的帮助。

A 5 minute timeout to improve your headspace may seem impossible to take, but can be surprisingly helpful.

现在这么说，该算法是基于一个简单的原则。假设我想匹配长度的字符串 M 。我会先了解一下字符指数 M 。如果这个角色是不是在我的字符串，我知道我要的子不能在指数 1，2，...，M 启动字符。

Now that said, the algorithm is based on a simple principle. Suppose that I'm trying to match a substring of length m. I'm going to first look at character at index m. If that character is not in my string, I know that the substring I want can't start in characters at indices 1, 2, ... , m.

如果这个角色是我的字符串，我会认为，这是在我的字符串，它可以是最后的地方。然后我会跳回来，并开始尝试与我的字符串，用于可能的起点。这条信息是我的第一个表。

If that character is in my string, I'll assume that it is at the last place in my string that it can be. I'll then jump back and start trying to match my string from that possible starting place. This piece of information is my first table.

在我开始从子字符串的开始匹配，当我找到一个不匹配，我不能只是从头开始。我可以是部分地通过一匹配开始在不同的点。举例来说，如果我想匹配阿南德在 ananand 成功匹配，阿南，实现以下 A 不是 D ，但我只是匹配的，所以我要跳回设法满足我的第三个字符在我的子。这一点，如果我匹配的N位的字符失败后，我可能是对比赛的y'th字符信息存储在第二个表。

Once I start matching from the beginning of the substring, when I find a mismatch, I can't just start from scratch. I could be partially through a match starting at a different point. For instance if I'm trying to match anand in ananand successfully match, anan, realize that the following a is not a d, but I've just matched an, and so I should jump back to trying to match my third character in my substring. This, "If I fail after matching x characters, I could be on the y'th character of a match" information is stored in the second table.

请注意，当我不匹配第二个表知道我走多远的比赛可能是基于我刚才的匹配。第一个表知道如何追溯到我可能基于我刚才看到我没有匹配的字符。你想使用更悲观的这两部分信息。

Note that when I fail to match the second table knows how far along in a match I might be based on what I just matched. The first table knows how far back I might be based on the character that I just saw which I failed to match. You want to use the more pessimistic of those two pieces of information.

考虑到这一点的算法是这样的：

With this in mind the algorithm works like this:

start at beginning of string
start at beginning of match
while not at the end of the string:
    if match_position is 0:
        Jump ahead m characters
        Look at character, jump back based on table 1
        If match the first character:
            advance match position
        advance string position
    else if I match:
        if I reached the end of the match:
           FOUND MATCH - return
        else:
           advance string position and match position.
    else:
        pos1 = table1[ character I failed to match ]
        pos2 = table2[ how far into the match I am ]
        if pos1 < pos2:
            jump back pos1 in string
            set match position at beginning
        else:
            set match position to pos2
FAILED TO MATCH

这篇关于博耶Moore算法的理解和实例？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！