浏览器如何在网页上“找到”东西？

Question

现在这可能是一个非常琐碎的问题，但是现代浏览器如何处理网页上的find（Ctrl + F）操作？

他们是否通过将网页中的所有HTML / CSS / JS正则表达式转换为某种纯文本表示形式，然后运行递归查找？

Answer 1

我不知道其他浏览器，但谷歌浏览器使用Boyer Moore搜索算法在网页上查找单词。在这种算法中，浏览器从右到左扫描您输入的单词。

要搜索的字符串称为P，称为“模式”。

我们正在其中搜索的字符串称为T，或“测试”。

T和P的长度通常分别由m和n表示。该算法的优势在于，它无需使用蛮力进行搜索（本来会进行m - n - 1试验），而是对其进行了预处理P并跳过了​​尽可能多的可能性。

根据维基百科：

此算法的主要见解是，如果模式的结尾是相对于文字而言，沿着文字的跳跃更容易而不是检查文本的每个字符。起作用的原因是在将图案与文字对齐时，最后一个字符模式的字符与文本中的字符进行比较。如果字符不匹配，无需继续搜索沿文本倒退。如果文字中的字符不匹配模式中的任何字符，然后是要检查的文字位于沿文字更远的n个字符处，其中n是图案的长度。如果文字中的字符位于模式，然后将模式沿着文本进行部分移动以沿匹配字符排列，然后重复该过程。沿文本跳转进行比较，而不是检查每个文本文字中的字符减少了必须进行的比较次数进行，这是算法效率的关键。

Boyer-Moore算法采用两种方法：

• 不良字符启发式
• 良好的后缀启发式

P被处理，并且形成两种启发式的不同数组。

与T的当前字符不匹配的P的字符被称为坏字符。

T的子字符串与P的子字符串已成功匹配时，将出现一个很好的后缀。>>

在这两种方法或启发式方法中，都遵循一些规则，您可以详细阅读here和here。来自不同网站的复制粘贴文章毫无意义。