Boyer-Moore可能是已知的最快的非索引文本搜索算法.所以我在C#中为我的Black Belt Coder网站实现它.
我有它工作,它显示大致预期的性能改进相比String.IndexOf().但是,当我添加StringComparison.Ordinal参数时IndexOf,它开始优于我的Boyer-Moore实现.有时,相当数量.
我想知道是否有人可以帮助我找出原因.我理解为什么StringComparision.Ordinal可能加快速度,但它怎么能比Boyer-Moore更快？是因为.NET平台本身的开销,可能是因为必须验证数组索引以确保它们在范围内,或者完全不同.有些算法在C#.NET中不实用吗？
以下是关键代码.
// Base for search classes
abstract class SearchBase
{
public const int InvalidIndex = -1;
protected string _pattern;
public SearchBase(string pattern) { _pattern = pattern; }
public abstract int Search(string text, int startIndex);
public int Search(string text) { return Search(text, 0); }
}
/// <summary>
/// A simplified Boyer-Moore implementation.
///
/// Note: Uses a single skip array, which uses more memory than needed …我目前正在学习模式匹配算法,并且遇到了这两种算法.我有以下一般想法:
KMP
BM
我遇到了以下引发这个问题的问题(正确还是错误):
如果我们想要在许多不同的文本中重复搜索相同的模式,那么Knuth-Morris-Pratt(KMP)算法是一个很好的选择.
所以我认为答案是正确的,因为假设每次在不同文本上运行算法时,预处理只是O(n),对于BM,它是O(n +字母表大小).但是,我不确定我是否正在做出正确的假设,即每次重新运行算法时都会重新计算新表.因为说文字总是落在英文字母表中.我只需要计算一次表,只需重用表.那么在一天结束的时候,这个问题的答案是否依赖于这样的事实:算法都是在包含在同一字母表中的文本上运行,还是有一些其他可能影响它的因素？
我需要三个快速大字符串函数:快速搜索,快速搜索和替换,以及字符串中子字符串的快速计数.
我在C++和Python中遇到过Boyer-Moore字符串搜索,但是用于实现快速搜索和替换的唯一Delphi Boyer-Moore算法是由Peter Morris(前身为DroopyEyes软件)及其网站的FastStrings的一部分.和电子邮件不再有效.
我已经将FastStrings移植到Delphi 2009/2010的AnsiStrings中,其中一个字节等于一个AnsiChar,但是使它们也可以在Delphi 2010中使用String(UnicodeString)显得非常重要.
使用这个Boyer-Moore算法,应该可以轻松地进行不区分大小写的搜索,以及不区分大小写的搜索和替换,没有任何临时字符串(使用StrUpper等),并且不调用比Boyer更慢的Pos()需要在重复搜索同一文本时进行摩尔搜索.
(编辑:我有一个部分解决方案,写作这个问题的答案,几乎100%完成,它甚至有一个快速的字符串替换功能.我相信它必须有bug,特别是认为,因为它假装是Unicode由于未实现的Unicode承诺,它必须存在故障.)
(编辑2:有趣和意外的结果;堆栈上的unicode代码点表的大堆栈大小 - 下面的代码中的SkipTable严重阻碍了你可以在unicode字符串boyer中完成的双赢优化量 - 摩尔字符串搜索.感谢Florent Ouchet指出我应该立即注意到的内容.)
我理解不良角色启发式的工作方式.当您找到不匹配的字母时x,只需移动图案,使图案中最右边的字母x与x字符串中的最右边对齐.并且它很容易在代码中实现.
我想我也明白了后缀启发式的工作方式.当我们找到一个好的后缀时s,在模式中的不同位置找到相同的后缀并移动它,以便s模式s中的字符串与字符串中的字符串对齐.但我不明白如何在代码中这样做.我们如何找到模式中另一个地方是否存在相同的后缀？我们怎么知道它的位置？代码:
void bmPreprocess1()
{
int i=m, j=m+1;
f[i]=j;
while (i>0)
{
while (j<=m && p[i-1]!=p[j-1])
{
if (s[j]==0) s[j]=j-i;
j=f[j];
}
i--; j--;
f[i]=j;
}
}
来自http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bmen.htm对我来说没有意义......有人可以为此任务编写尽可能简单的伪代码吗？还是以某种方式解释？
我一直试图理解Boyer-Moore字符串搜索算法中的移位规则,但还没有理解它们.我在这里阅读维基百科,但这太复杂了!
如果有人以简单的方式列出规则,那将是非常有帮助的.
我想从a读取,std::istream直到找到一定数量的字符,即,我想实现以下接口:
void read_until (std::istream &is, std::string_view needle);
使用std::istreambuf_iterator,我相信这相当于std::search单通道迭代器的组合.不幸的是,std::boyer_moore_searcher需要随机访问迭代器.
使用C++标准库(以及与大小成比例的一点内存sv)是否有上述接口的简单实现,或者我是否必须自己编写代码？
这是我对BMH算法的实现(它就像一个魅力):
public static Int64 IndexOf(this Byte[] value, Byte[] pattern)
{
if (value == null)
throw new ArgumentNullException("value");
if (pattern == null)
throw new ArgumentNullException("pattern");
Int64 valueLength = value.LongLength;
Int64 patternLength = pattern.LongLength;
if ((valueLength == 0) || (patternLength == 0) || (patternLength > valueLength))
return -1;
Int64[] badCharacters = new Int64[256];
for (Int64 i = 0; i < 256; ++i)
badCharacters[i] = patternLength;
Int64 lastPatternByte = patternLength - 1;
for (Int64 i = 0; i < lastPatternByte; ++i)
badCharacters[pattern[i]] = …请帮我理解Boyer-Moore字符串搜索算法的"Good Suffix Shift"-Table.
发生了什么事i==3？
模式中没有子串"_MAN".所以移位值应该是8(就像当时一样i==1).
为什么6？
我真的想了解一个如何为给定模式构造一个好的后缀表的例子.问题是,我无法绕过它.我看了很多例子,但不知道数字的来源.
所以这里是:下面的示例演示了如何使用ANPANMAN模式构造一个Good Suffix Table:
Index | Mismatch | Shift | goodCharShift
-----------------------------------------------
0 | N| 1 | goodCharShift[0]==1
1 | AN| 8 | goodCharShift[1]==8
2 | MAN| 3 | goodCharShift[2]==3
3 | NMAN| 6 | goodCharShift[3]==6
4 | ANMAN| 6 | goodCharShift[4]==6
5 | PANMAN| 6 | goodCharShift[5]==6
0 | NPANMAN| 6 | goodCharShift[6]==6
0 | ANPANMAN| 6 | goodCharShift[7]==6
对此事的任何帮助都非常感谢.我根本不知道如何得到这些数字.谢谢!
boyer-moore ×10
algorithm ×6
c# ×3
.net ×2
c ×2
search ×2
c++ ×1
c++17 ×1
delphi ×1
delphi-2010 ×1
iterator ×1
performance ×1
replace ×1
suffix-array ×1