What algorithm is used in Chrome search?

Question

Suppose you use Chrome when I press Cmd + F or Ctrl + F ... I type char, it scans the entire page and selects the text for me. He is looking instantly. What algorithm is using Chrome? Why can he print and search so fast? any ideas on this? Thanks.

Answer 1

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

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

When a user initiates a search in Chromium, we basically register a notification for the observer to get the results. Each search call is asynchronous, and the search results are sent as a notification using the visualization tool. This is handled in FindBarController :: Observe

The first thing that happens when you press next / previous / input, FindBarView :: ButtonPressed , it tells the current contents of the tab to find TabContents :: StartFinding . You will notice that in this piece of code it sends an asynchronous request to IPC. You can see how we ship it here: RendererViewHost :: StartFinding

Since Chromium is a multi-processor architecture , we send messages through the IPC message handler. You can view the link above to find out how messages are sent. Rendering hosts send a message in the rendering view, RenderView :: OnFind . From now on, you know that the search logic is clearly in the WebKit source code, not in Chromium. WebFrameImpl :: find

Now in the WebKit environment, the logic where it finds the string is in Editor :: findString , and if you notice what the algorithm is, basically traversing the DOM through the given range, using WebKit / WebCore / editing / TextIterator.h Comments in WebKit are wrong great compared to Chromium, but the quality of the code is quite high, so you will not have problems reading 3000+ loc.

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

Answer 2

I don’t know which algorithm Chrome uses, but I think you can research the answer in Chromium sources

Edit:

After looking at the sources for a short time, I would also suggest contacting the Chrome developers ... directly>

Answer 3

Pure speculation, but it is likely that it symbolizes the page in words (with their corresponding ranges), then it puts these words in a Radix Tree or Trie and searches for a prefix in the tree.

Answer 4

Why don't you take a look at the chrome source code and see what they do for themselves?

http://src.chromium.org/viewvc/chrome/