Supposons que vous utilisez Chrome, lorsque j'appuie sur Cmd + F ou Ctrl + F ... Je tape un caractère, il recherche toute la page et met en évidence le texte pour moi. Il recherche instantanément. Quel type d'algorithme Chrome utilise-t-il? Pourquoi il peut taper et rechercher si vite? des idées là-dessus? Je vous remercie.Quel algorithme utilise dans la recherche dans Chrome?
Vous pouvez trouver plus d'informations sur l'architecture ici: http://www.chromium.org/developers/design-documents/find-bar
Je vais essayer d'expliquer une réponse plus détaillée qui vous aidera à naviguer à travers la source de chrome prochaine fois que vous avez besoin quelque chose de plus.
Lorsqu'un utilisateur lance une recherche dans Chromium, nous enregistrons une notification à l'observateur pour obtenir des résultats. Chaque appel find est asynchrone et les résultats de la recherche sont envoyés en tant que message de notification par le moteur de rendu. La première chose qui se passe lorsque vous appuyez sur le suivant/précédent/entrée, FindBarView::ButtonPressed il indique le contenu de l'onglet en cours pour commencer à trouver TabContents::StartFinding. Vous remarquerez que dans cette partie du code, il envoie une requête asynchrone à l'IPC. Vous pouvez voir comment nous l'envoyons ici: RendererViewHost::StartFinding
Puisque Chromium est un multi-process architecture, nous envoyons des messages via le gestionnaire de message IPC. Vous pouvez voir le lien ci-dessus pour voir comment les messages sont envoyés. Les hôtes de rendu envoient un message à la vue de rendu, RenderView::OnFind. À partir de ce moment, vous savez que la logique de recherche est clairement dans le code source de WebKit, pas dans Chromium. WebFrameImpl::find
maintenant dans la terre WebKit, la logique où il trouve la chaîne est en Editor::findString et si vous remarquez ce que l'algorithme est, traversant essentiellement DOM à travers une plage donnée en utilisant WebKit/WebCore/editing/TextIterator.h Les commentaires WebKit ne sont pas exceptionnelles par rapport à Chrome , mais la qualité du code est assez élevée donc vous n'aurez aucun problème à lire 3000+ loc.
La raison pour laquelle je vous dis tout cela est à votre avantage, donc si vous voulez en savoir plus sur Chrome/WebKit, vous savez comment regarder à travers le code source :) Je recommande fortement http://dev.chromium.org/developers
Pourquoi ne pas jeter un oeil au code source de chrome et regarder pour voir ce qu'ils font pour vous-même?
Pure spéculation, mais tout à fait probable qu'il tokenizes la page en mots (avec leur fourchette), il met ces mots soit dans un Radix Tree ou Trie et fait une recherche de préfixe dans l'arborescence.
réponse Impressionnant :) – d11wtq
Pourriez-vous expliquer où je peux trouver l'ALGORITHME réel derrière la recherche de motif? Je suis curieux de savoir ce qu'il y a derrière parce que c'est incroyablement rapide. –
La plupart des liens ne fonctionnent pas. –