What Algorithm is using in Chrome search? What Algorithm is using in Chrome search? google-chrome google-chrome

What Algorithm is using in Chrome search?


You can find more information regarding the architecture here:http://www.chromium.org/developers/design-documents/find-bar

I will try to explain a more detailed response that will help you navigate through the Chromium source next time you need something more.

When a user initiates a find in Chromium, we basically register a notification to the observer for results. Every find call is asynchronous, and the results of the search is sent as a notification message by the renderer. This is handled in FindBarController::Observe

The first thing that happens when you press the next/previous/enter, FindBarView::ButtonPressed it tells the current Tab Contents to start finding TabContents::StartFinding. You will notice that in that piece of code it sends an asynchronous request to the IPC. You can view how we send it here: RendererViewHost::StartFinding

Since Chromium is a multi-process architecture, we send messages through the IPC message handler. You can view the link above to see how messages are being sent. The render hosts sends a message to the render view, RenderView::OnFind. From that point on, you know that the find logic is clearly in WebKit source code, not in Chromium. WebFrameImpl::find

Now in WebKit land, the logic where it finds the string is in Editor::findString and if you notice what the algorithm is, basically traversing DOM through a given range using WebKit/WebCore/editing/TextIterator.h The comments in WebKit are not that great in comparison to Chromium, but the quality of the Code is pretty high so you will have no problem reading 3000+ loc.

The reason why I am telling you all this is for your benefit, so if you want to know more about Chromium/WebKit, you know how to look through the source code :) I highly recommend http://dev.chromium.org/developers


I don't know what algorithm Chrome uses, but I guess that you can research the answer in the Chromium sources

Edit:

After looking at the sources for a short while, I would also like to suggest to contact the chromium developers directly...


Pure speculation, but quite likely that it tokenizes the page into words (with their associated ranges), then it puts those words into either a Radix Tree or a Trie and does a prefix search within the tree.