问题标签 [boyer-moore]

我需要三个 fast-on-large-strings 函数：快速搜索、快速搜索和替换以及字符串中子字符串的快速计数。

我在 C++ 和 Python 中遇到过 Boyer-Moore 字符串搜索，但是我发现的唯一用于实现快速搜索和替换的 Delphi Boyer-Moore 算法是 Peter Morris 的 FastStrings 的一部分，Peter Morris 以前是 DroopyEyes 软件和他的网站和电子邮件不再工作。

我已经将FastStrings向前移植，以便在 Delphi 2009/2010 中非常适合 AnsiStrings，其中一个字节等于一个 AnsiChar，但让它们也适用于 Delphi 2010 中的字符串 (UnicodeString) 似乎并不简单。

使用这种 Boyer-Moore 算法，应该可以轻松地进行不区分大小写的搜索，以及不区分大小写的搜索和替换，无需任何临时字符串（使用 StrUpper 等），也无需调用比 Boyer 慢的 Pos() -需要对相同文本进行重复搜索时的摩尔搜索。

（编辑：我有一个部分解决方案，写成这个问题的答案，它几乎 100% 完成，它甚至有一个快速的字符串替换功能。我相信它必须有错误，特别是认为因为它假装是 Unicode能够因为未实现 Unicode 承诺而出现故障。）

（Edit2：有趣且出乎意料的结果；堆栈上 unicode 代码点表的大堆栈大小 - 下面代码中的 SkipTable 严重阻碍了您可以在 unicode string boyer 中执行的双赢优化量-moore 字符串搜索。感谢 Florent Ouchet 指出我应该立即注意到的内容。）

KMP (Knuth–Morris–Pratt) 算法执行的比较是否比简化的 Boyer-Moore 算法少？

Boyer-Moore 可能是已知最快的非索引文本搜索算法。所以我在 C# 中为我的Black Belt Coder网站实现它。

我让它工作了，与String.IndexOf(). 但是，当我将StringComparison.Ordinal参数添加到 时IndexOf，它开始优于我的 Boyer-Moore 实现。有时，数量相当可观。

我想知道是否有人可以帮助我找出原因。我明白为什么StringComparision.Ordinal会加快速度，但它怎么能比 Boyer-Moore 更快呢？是因为 .NET 平台本身的开销，可能是因为必须验证数组索引以确保它们在范围内，或者完全是其他原因。某些算法在 C#.NET 中不实用吗？

下面是关键代码。

编辑：我已经在http://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-moore上发布了我所有的测试代码和结论。

C 中是否有 Boyer-Moore 字符串搜索算法的工作示例？我查看了一些网站，但它们看起来很糟糕，包括维基百科。

谢谢。

我即将实现 Boyer-Moore 模式匹配算法的变体（具体来说是星期日算法），我问自己：我的字母大小是多少？

它取决于编码（= 可能的字符数）还是我可以假设我的字母表由 256 个符号组成（= 可以用一个字节表示的符号数）？

在许多其他情况下，将字符视为字节将是一个问题，因为根据编码，一个字符可以由多个字节组成，但如果在我的情况下，两个字符串都具有相同的编码，那么相等的字符由相等的字节序列表示，所以我假设没关系。

所以：我是否必须考虑编码并假设一个由实际字符组成的字母表（对于 Unicode 而言 > 90000），还是我可以将文本和模式作为字节流处理？

请帮助我理解 Boyer-Moore 字符串搜索算法的"Good Suffix Shift"-Table。

什么时候发生了什么i==3？

模式中没有子字符串“_MAN”。所以移位值应该是 8（就像 时一样i==1）。

为什么呢6？

有没有更快的方法来搜索文件中的字符串？

首先，我对算法知之甚少，所以请耐心等待。

据我了解，Boyer Moore 算法在长密钥时速度最快。那么，如果我有一个非常短的键（例如 10 个字符）和大量要搜索的文本（超过 10,000 个字符）怎么办。Boyer Moore 会是这种情况下的最佳搜索算法吗？

如果不是，那会是什么？

我已经在编程网站上完成了一个与一个不匹配的字符串比较的程序。它给了我错误的答案。我已经广泛地研究它，但是我找不到我的代码失败的测试用例。有人可以提供我的代码失败的测试用例吗？我已经使用 Boyer Moore Horspool k-mismatches 算法进行了比较，因为它是最快的搜索算法

代码是这样的

我正在尝试调整 Boyer-Moore c(++) Wikipedia 实现以获取字符串中模式的所有匹配项。实际上，Wikipedia 实现返回第一个匹配项。主要代码如下所示：

我试图在if (j < 0)将索引添加到数组/向量并让外循环继续之后修改块，但它似乎没有工作。在测试修改后的代码时，我仍然只得到一个匹配项。也许这个实现并不是为了返回所有匹配项而设计的，并且它需要不止一些快速更改才能做到这一点？我不太了解算法本身，所以我不确定如何使这项工作。如果有人能指出我正确的方向，我将不胜感激。

注意：函数 make_delta1 和 make_delta2 在源代码中定义较早（查看维基百科页面），而 max() 函数调用实际上也是在源代码中较早定义的宏。