浏览器用于在网页中搜索单词的算法

Question

在浏览器中使用哪种数据结构或算法来搜索单词？浏览器会构建一个trie或后缀树吗？

谢谢
Bala

Answer 1

使用 trie/后缀树进行搜索速度很快，但从开始构建 trie 的速度要慢得多。这意味着它们仅在您希望对相同数据执行大量搜索时才有意义，因此您可以将构建 trie 的时间分摊到多次搜索上。

网页内的平均搜索次数可能是分数（即您希望用户在进行一次搜索之前加载多个页面）。即使您确实搜索了一个页面，在同一页面中进行大量搜索的情况也可能很少见。

这意味着线性搜索总体上几乎总是比特里树或后缀树更有效。我的猜测是，如果他们费心去优化它，而不仅仅是简单的调用，strstr()那么他们只会进行 Boyer-Moore 系列字符串搜索中的某些操作。考虑到您期望在网页中进行的搜索数量，这通常会在您完成特里树的初始构建之前完成所有搜索，以便您可以开始使用它进行搜索。

对于交互式使用，您主要关心的是生成结果的速度足够快，以便即时出现。这通常意味着 100 毫秒左右即可得到结果。通过 Boyer-Moore-Horspool 的良好实现，有足够的时间来搜索要包含在单个网页中的大量文本（大约数百兆字节或千兆字节）。

如果您想对其进行测试，我建议您使用 Ray Gardner 的 Boyer-Moore-Horspool 实现（Bmhsrch.C，来自 Bob Stout 的Snippets站点）。我真的不愿意看到一个网页大到足以让它占用 20 毫秒，更不用说 100 毫秒了（尽管我是第一个承认这个特定实现速度非常快的人）。