Firefox的'真棒'栏如何匹配字符串？

问题是如何通过firefox 3 url栏查找匹配条目进行字符串匹配.每个条目的子串匹配可能很慢.什么算法可用于快速匹配任何位置？

1> sdwilsh..：

---

Firefox 3.0中位置栏的算法有点复杂.它将从两个(Firefox 3.5及更高版本的三个)不同查询中获取数据:

对于第一个查询,它检查moz_inputhistory表以查看当前搜索字符串是否存储在该表中.这些结果按"rank"排序,"rank"是一个确定最近使用时间的数字.这个数字每天降低一次.此搜索使位置栏适应您随时间选择的内容(在错误95739中实现).

在Firefox 3.5及更高版本中,它会在moz_keyword表中检查具有与搜索文本完全匹配的关键字的书签.

最后一个查询,它遍历moz_places中的每个条目,其中包括所有历史记录访​​问和书签.这些结果是通过frecency排序的.

对于所有这三种情况,以下算法用于匹配标签,标题和URL(下面称为"可搜索文本").这有点难以用文字解释,因此查看源代码可能更容易.

搜索字符串被分成由空格确定的标记(每个非空格"字"是标记).

对于每个令牌,开始以Unicode,不区分大小写的方式比较可搜索文本和令牌的每个字符,直到它完全匹配.如果一组字符不匹配,请前进到可搜索文本中的下一个" 字边界 ",然后重试.

如果我们匹配任何一个可搜索的文本,它将显示在位置栏中.

如果我们没有足够的结果(默认值为12),我们将重新搜索每个书签和历史记录访​​问的查询,并以Unicode,不区分大小写的方式测试可搜索的文本,以便在任何地方(不仅仅是在字边界).

希望以一种可以理解的方式解释它!

2> Antti Huima..：

---

正常的方式来做到快速串匹配是创建包含所有你想要搜索字符串的所有后缀的数据结构.根据组织,这可以称为"后缀树"或"后缀数组".举例来说,如果你有1000个字符串,每个人都为50个字符长,你有1.000×50平凡的后缀,即你的后缀阵列将有50.000项.

然后,为了进行匹配,您可以进行二分查找(如果是数组)或树搜索(如果是树),以查找数据结构中的所有后缀,这些后缀的开头与搜索框中写入的字符串相匹配.因为它是您匹配的后缀的开头,所以您可以使用标准搜索过程(二进制搜索,树下降)来快速获得结果.每个后缀都链接到它出现的字符串.

示例:您有两个字符串"CAT"和"DOT".你的后缀数组看起来像这样(注意lexiographic =字母顺序):

#1 AT  --> CAT
#2 CAT --> CAT
#3 DOT --> DOT
#4 OT  --> DOT
#5 T   --> DOT, CAT

请注意,有六个后缀,但两个是相同的(最后一个"T"中的"猫"和"DOT")和均由同一条目表示(#5).

现在当用户键入搜索时,例如"OT"(应与"DOT"匹配),您可以在日志时间内进行简单的词法排序查找,因为您现在正在后缀数组中搜索开始匹配.

当搜索模式不包含通配符时,这是快速文本搜索的基本原则.

---

虽然这是一个很好的解释,但根本不是Firefox如何做到这一点.对于大多数用户来说,内存使用量和磁盘使用量会非常大.假设有1000个历史条目(非常保守),典型的URL长度为100-1000个字符,1,000,000 - 10,000,000个数组条目.有了这些数字,你会看到至少50MB的桌子.

---

50MB是保守估计,可能看起来不多.但是,当您仅应用[通常使用大约100-200MB] [1]时,您会看到内存使用量增加50-25%.人们已经抱怨Firefox使用了太多内存.所有这些仍然没有改变这不是Firefox如何进行查找的事实.[1]:http://blog.pavlov.net/2008/03/11/firefox-3-memory-usage/

---

基于我自己的测试,'firefo'非常快速地(并且递增地)产生结果,而'irefo'需要一段时间.我猜测它会使用反向索引,如果没有返回任何内容,则执行整个数据库的强力扫描.

3> RuudKok..：

---

awesomebar通过名为The Places frecency algorithm的算法建议URLS .

根据Mozilla开发者网站:

"frecency"这个词本身就是"频率"和"新近"这两个词的组合.

---

这就是数据的排序方式,与显示的结果几乎没有关系.