3

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

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

如果不是，那会是什么？

4

2 回答 2

2

根据字符串搜索算法，“Boyer-Moore 字符串搜索算法已成为实用字符串搜索文献的标准基准。” 它并不总是最快的，但总的来说这是要走的路。

当您谈论像 10,000 个字符这样的小型文本缓冲区时，Knuth-Morris-Pratt 和 Boyer-Moore 在运行时间上非常接近。在现代计算机上运行时，即使是幼稚的字符串搜索在 10K 缓冲区上也会非常快。我怀疑您会发现 KMP 和 Boyer-Moore 两者在 10,000 个字符的缓冲区中搜索 10 个字符的字符串之间的差异将在纳秒级。

在这种情况下最好的搜索算法？这将取决于您需要调用它的频率。如果它每秒被调用几次（最多），我可能会写一个幼稚的搜索并将其留在那里。与程序的运行时间相比，Boyer-Moore 和在那个小缓冲区上的朴素搜索之间的差异将是微不足道的，您的优化工作最好花在其他地方。如果我必须每秒调用数百或数千次，我会花时间编写优化的 Boyer-Moore 搜索。

于 2011-09-28T15:58:05.230 回答
0

要回答您的问题，您只需访问一个链接：http: //www.codeproject.com/Articles/250566/Fastest-strstr-like-function-in-C

事实上，最快的文本搜索器的主页是这样的：http: //www.sanmayce.com/Railgun/index.html

>那么，如果我有一个非常短的键（例如 10 个字符）和大量要搜索的文本（超过 10,000 个字符）怎么办。 正是这个关键范围（10-11 个字符）在我的重型（1TB）strstr 摊牌中进行了测试。在 300,000 个单词中搜索了 400,000 个单词，ONE-BY-ONE，一个 strstr 函数的极好负载！

> Boyer Moore 会是这种场景的最佳搜索算法吗？ 根据我的测试，最快的文本搜索器（使用 Microsoft V16 /Ox）是Railgun_Quadruplet_7Gulliver，但是当使用 /Ox 和 Intel 12.1 时它是第二好的，你可以自己测试它，见下文。

如果你有一台速度很快的机器，比如 i7 37*，我想看看我最新的控制台基准测试包的结果（测试 Microsoft v16 与 Intel 12.1 编译器）： http:
//www.sanmayce.com/Downloads/_KAZE_Benchmark_2013.zip

在我的 T7500 2200Mhz 笔记本上测试：

E:\_KAZE_Benchmark_2013>RUNME.bat

E:\_KAZE_Benchmark_2013>SKYFALL_TXT2HTML_MicrosoftV16.exe MIX_Tesla_BABAJI_Castaneda_Poirot_Holmes_Sunnah_Hadith_Quran_Bible_Patanjali_Dao_Simplici
ssimus.wrd.txt MASAKARI_General-Purpose_Grade_English_Wordlist_r3_316423_words.wrd /Gulliver
SKYFALL_TXT2HTML, revision 2, written by Kaze.
Size of 1st input file: 8916987
Size of 2nd input file: 3869529

Doing Search for each word with Railgun_Quadruplet_7Gulliver ...
Railgun_Quadruplet_7Gulliver performance: 1944+KB/clock
Average Pattern Length: 11
Function Invocations: 420,640
Function Inner-Loop Iterations: 131,873,881,926
Function Really Traversed: 1,142,740,439KB

E:\_KAZE_Benchmark_2013>SKYFALL_TXT2HTML_MicrosoftV16.exe MIX_Tesla_BABAJI_Castaneda_Poirot_Holmes_Sunnah_Hadith_Quran_Bible_Patanjali_Dao_Simplici
ssimus.wrd.txt MASAKARI_General-Purpose_Grade_English_Wordlist_r3_316423_words.wrd
SKYFALL_TXT2HTML, revision 2, written by Kaze.
Size of 1st input file: 8916987
Size of 2nd input file: 3869529

Doing Search for each word with Railgun_Quadruplet_7 ...
Railgun_Quadruplet_7 performance: 1747+KB/clock
Average Pattern Length: 11
Function Invocations: 420,640
Function Inner-Loop Iterations: 146,826,792,351
Function Really Traversed: 1,142,740,439KB

E:\_KAZE_Benchmark_2013>SKYFALL_TXT2HTML_MicrosoftV16.exe MIX_Tesla_BABAJI_Castaneda_Poirot_Holmes_Sunnah_Hadith_Quran_Bible_Patanjali_Dao_Simplici
ssimus.wrd.txt MASAKARI_General-Purpose_Grade_English_Wordlist_r3_316423_words.wrd /Hasherezade
SKYFALL_TXT2HTML, revision 2, written by Kaze.
Size of 1st input file: 8916987
Size of 2nd input file: 3869529

Doing Search for each word with Railgun_Hasherezade ...
Railgun_Hasherezade performance: 1774+KB/clock
Average Pattern Length: 11
Function Invocations: 420,640
Function Inner-Loop Iterations: 128,900,655,391
Function Really Traversed: 1,142,740,439KB

使用 32 位和 64 位代码时会有一些起伏，微软和英特尔之间也有很大的差距。

Gulliver的“引擎”是我调整的 2 BM-Horspool订单。

正如您在我简陋的笔记本电脑上看到的那样，Gulliver以1898MB/s 的速度搜索模式（平均模式长度：11），即使是超级漂亮的BNDM 也会在这里屈膝。

于 2013-01-11T15:09:21.937 回答