PDF阅读器 - 查找单词的算法

Question

当您输入Ctrl+F时，pdf阅读器如何找到特定的单词/表达式？

有没有比线性搜索更快的算法来执行这样的任务？

Answer 1

它因不同的PDF阅读器而异，但我猜测它是一些已知的快速字符串匹配算法（可能是Rabin-Karp algorithm，Boyer-Moore algorithm或KMP algorithm）可能同时跨所有文档页面并行运行。对于简短的文本字符串，这应该是非常非常快的。

而且他们也很有可能使用他们自己的上述算法的混合/修改算法。

Answer 2

搜索算法能够在PDF中查找单词的速度与所使用的特定算法很少有关，而且更依赖于使用哪种算法确定哪些算法用于确定哪些绘图指令构成第一个单词地点和他们应该进入的顺序。一些PDF创建工具将创建一条指令，将整行文本设置为单个指令，每个单词之间有空格。但是，如果在创作工具中将任何类型的非标准间距应用于该行，则PDF可能会逐个字符地放置每个单词，而根本没有空格。还有一些人会尝试避免加载字体和创建PDF的内存负担，使所有普通文本首先被渲染，然后是所有粗体文本，然后是所有斜体文本，字体由字体。因此，如果您只是按照其绘制的顺序提取文本，则无法获得真实的阅读顺序。

更好的工具需要更长的时间，但会使这个过程正确。之后，搜索的时间是微不足道的。