PDFリーダー - 単語を見つけるアルゴリズム

Question

1つのタイプのCtrl+Fがある場合、PDFリーダーはどのように特定の単語/式を見つけるのですか？

このようなタスクを実行するには、線形探索よりも速いアルゴリズムがありますか？

Answer 1

それは別のPDFリーダーによって異なりますが、私はそれはおそらく一度にすべての文書のページにわたって並列に実行するいくつかの既知の高速文字列照合アルゴリズム（おそらくRabin-Karp algorithm、Boyer-Moore algorithm、またはKMP algorithm）があったことを推測します。短いテキスト文字列の場合、これは非常に速くなければなりません。

また、上述のアルゴリズムの独自のハイブリッド/修正アルゴリズムを使用する可能性も高くなります。

Answer 2

検索アルゴリズムがPDF内の単語を見つけることができる速度は、使用される特定のアルゴリズムとはほとんど関係がなく、どのアルゴリズムが最初のいくつかのPDF作成ツールは、テキスト全体を各単語の間にスペースを入れた単一の命令として設定する命令を作成します。ただし、オーサリングツールでその行に非標準のスペーシングが適用されている場合、PDFは空白のない単語ごとに各単語を配置することがあります。さらに、フォント読み込みのメモリ負担を避け、すべての通常のテキストが最初にレンダリングされた後、すべてが太字のテキスト、すべてが斜体のテキスト、フォントのフォントのようにPDFを作成しようとします。だから、それが描かれた順序でテキストを抽出すれば、本当の読み上げ順序は得られません。

ツールの方が時間がかかりますが、この処理が正しく行われます。その後、検索する時間は簡単です。