Какой алгоритм использует в поиске Chrome? - PullRequest
8 голосов
/ 20 ноября 2010

Предположим, вы используете Chrome, когда я нажимаю Cmd + F или Ctrl + F ... Я набираю символ, он просматривает всю страницу и выделяет текст для меня. Он ищет мгновенно. Какой алгоритм использует Chrome? Почему он может печатать и искать так быстро? есть идеи на этот счет? Спасибо.

Ответы [ 4 ]

20 голосов
/ 20 ноября 2010

Более подробную информацию об архитектуре можно найти здесь: http://www.chromium.org/developers/design-documents/find-bar

Я постараюсь объяснить более подробный ответ, который поможет вам перейти к источнику Chromium в следующий раз, когда вам понадобится что-то еще.

Когда пользователь инициирует поиск в Chromium, мы в основном регистрируем уведомление для наблюдателя о результатах.Каждый вызов поиска является асинхронным, и результаты поиска отправляются в виде уведомляющего сообщения средством визуализации.Это обрабатывается в FindBarController :: Observe

Первое, что происходит, когда вы нажимаете следующий / предыдущий / ввод, FindBarView :: ButtonPressed сообщает текущую вкладкуСодержимое для начала поиска TabContents :: StartFinding .Вы заметите, что в этом фрагменте кода он отправляет асинхронный запрос в IPC.Вы можете посмотреть, как мы отправляем его здесь: RendererViewHost :: StartFinding

Поскольку Chromium является многопроцессной архитектурой , мы отправляем сообщения через обработчик сообщений IPC.Вы можете просмотреть ссылку выше, чтобы увидеть, как отправляются сообщения.Узлы рендеринга отправляют сообщение в представление рендера, RenderView :: OnFind .С этого момента вы знаете, что логика поиска явно в исходном коде WebKit, а не в Chromium. WebFrameImpl :: find

Теперь в ленте WebKit логика, в которой он находит строку, находится в Editor :: findString и, если вы заметили, что такое алгоритм, в основномобход DOM через заданный диапазон с использованием WebKit / WebCore / edit / TextIterator.h Комментарии в WebKit не так хороши по сравнению с Chromium, но качество кода довольно высокое, поэтому у вас не возникнет проблемчтение 3000+ loc.

Причина, по которой я говорю вам все это, в ваших интересах, поэтому, если вы хотите узнать больше о Chromium / WebKit, вы знаете, как просматривать исходный код :)рекомендуем http://dev.chromium.org/developers

2 голосов
/ 20 ноября 2010

Я не знаю, какой алгоритм использует Chrome, но я думаю, что вы можете найти ответ в Chromium источниках

Edit:

После небольшого изучения источников я также хотел бы предложить связаться с разработчиками хрома напрямую ...

1 голос
/ 20 ноября 2010

Чистое предположение, но вполне вероятно, что он разбивает страницу на слова (с соответствующими диапазонами), затем помещает эти слова либо в Radix Tree , либо в Trie и делает поиск префикса в дереве.

0 голосов
/ 20 ноября 2010

Почему бы вам не взглянуть на исходный код Chrome и посмотреть, что они делают для себя?

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...