Recherche de mots sur PDF/site Web

Question

Quel algorithme est utilisé par les navigateurs Web et les lecteurs de PDF pour rechercher un mot donné dans un document texte volumineux? Pour clarifier, quand je lis un e-book, et appuyez sur Ctrl-F, et entrez un terme de recherche, il trouve les mots correspondants assez rapidement. Quel algorithme est utilisé et quelle structure de données est utilisée pour stocker le texte entier du livre/site?

Answer 1

Le texte est probablement une simple chaîne, et la recherche elle-même est probablement KMP ou Boyer-Moore. Le texte normal n'est généralement pas très volumineux et les requêtes de recherche dans ces cas sont à «vitesse humaine» (lent, peu fréquent), donc les index ne sont pas souvent utilisés, sauf lorsque de nombreuses requêtes de recherche sur le même texte sont attendues (comme dans le texte bases de données). Par exemple, même un livre plus grand que la moyenne comme la Bible King James a moins de 4 millions de lettres, ce qui n'est pas du tout un ordinateur de nos jours. Pour les textes volumineux, la recherche prend parfois du temps. Pour les textes plus volumineux (peut-être un génome, mais ils sont généralement recherchés approximativement, par exemple avec FASTA ou BLAST), vous pouvez utiliser un index FM ou un tableau de suffixes compressés (un suffixe normal est possible, mais plus grand que le texte source, donc probablement trop gros).

Pour effectuer une recherche particulièrement rapide dans du texte de taille normale, vous pouvez utiliser par exemple un tableau de suffixe, un index inversé ou un dictionnaire trigramme.