0

在许多使用 Boyer moore 算法的示例中，有一个 256 个字符的声明，我不知道这个数字表示什么......请帮助

来自（ https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm）的示例：

function preprocess(pattern)
    T ← new table of 256 integers
    for i from 0 to 256 exclusive
        T[i] ← length(pattern)
    for i from 0 to length(pattern) - 1 exclusive
        T[pattern[i]] ← length(pattern) - 1 - i
    return T
4

1 回答 1

0

它声明字母表中有256字符。

这一字节限制对 ASCII 来说效果很好。但是如果您需要 Unicode，那么您还需要在表格中留出更多空间T。事实上，这种空间依赖性对于算法的分析是必不可少的。

正如维基百科文章所说：

该算法以空间换时间以获得O(n)随机文本的平均情况复杂度，尽管O(nm)在最坏的情况下，模式m的长度为 ，搜索字符串的长度为n。

Boyer-Moore是O(n+m)平均的，所以理论上更快。在最好的情况下它们是相同的，在病理情况下，BMH 可能比 BM 更容易出轨。但在实践中，Boyer-Moore-Horspool 的实现速度更快，因为它明智地使用了空间。这让我们回到那张桌子T。

固定尺寸的桌子已经过时了。您可能会使用 adict或 aHashMap或任何您选择的语言来代替。

对于捕获所有 Unicode 字符的情况，这大大降低了表格的成本。事实上，它将空间使用率从 降低O(v)到O(min(v, n+m)).

请小心使用哈希支持的数据结构，这样您就不会意外log(v)地在运行时添加一些因素（或更糟）。

于 2020-04-18T07:12:53.910 回答