Поскольку очень много вопросов возникло про общую функциональность поисковика вот небольшая вводная статья. Чтобы было немного понятно что такое поисковая система и что она должна делать, опишу в общих словах. Наверное для спецов программеров будет не очень интересно, не обессудьте
Но, к делу: поисковая машина по моему скромному мнению должна уметь находить максимально релевантные результаты по поисковому запросу. В случае текстового поиска, к которому мы все привыкли, поисковый запрос – набор слов, лично я ограничил его длину восемью словами. Ответ – набор ссылок на страницы которые наиболее релевантны поисковому запросу. Ссылки желательно снабдить аннотацией, чтобы человек знал чего ожидать и мог выбрать из результатов нужный – аннотация называется сниппет.
Надо сказать что задача поиска в общем виде не решается – для любого документа имеющего наибольшую релевантность например по слову «работа», можно создать модифицированную копию, которая будет иметь еще лучшую, с точки зрения поисковой машины, релевантность, однако будет полным бредом с точки зрения человека. Вопрос цены и времени, конечно. Из-за обширности Интернета на сегодняшний день таких страниц, мягко говоря, много. Разные системы борются с ними по-разному и с переменным успехом, когда-нибудь искусственный интеллект победит всех нас…
Тут помогли бы алгоритмы распознавания смысла, однако я знаком всего с одним из них (которые действительно распознают смысл, а не считают статистику) и мало представляю его применимость. Потому задачи решаются эмпирически – т.е. подбором некоторых манипуляций со страницами, чтобы отделить «зерна от плевел».
В реальном мире, прошерстить за секунду весь Интернет и найти результаты лучше всего подходящие, пока невозможно, поэтому поисковая машина хранит локальную копию того куска сети, который она успела собрать и обработать. Для того чтобы быстро получать из миллиарда страниц только те, которые содержат нужные слова строится «индекс» — база данных, в которой каждому слову соответствует список страниц которые это слово содержат. Естественно, в нем же надо хранить на каких местах были встречены искомые слова, как они были выделены в тексте, другие числовые метрики страницы, чтобы их использовать в процессе сортировки.
Скажем у меня 100 миллионов страниц. Среднее слово встречается на 1-1,5% страниц, т.е. 1 миллион страниц на каждое слово (есть слова которые встречаются на каждой второй странице, а есть более редкие). Всего скажем 3 миллиона встречающихся слов – остальные встречаются гораздо реже и это в основном описки и цифры. На хранение 1 записи что конкретное слово встречается на конкретной странице уходит id страницы – 4 байта, id сайта – 4 байта, упакованная информация о том в каком месте и как было выделено – 16-32 байта, 3 коэффициента ссылочного ранжирования – 12 байт, остальные метрики еще около 12-24 байт. Какого объема будет индекс – оставляю вам на прикидку:
3млн*1млн*суммарный объем записи.
Для того чтобы построить этот индекс есть 3 механизма:
индексация страниц – получение страниц из web и их начальная обработка
построение ссылочных метрик типа PageRank на основе первичной информации
обновление существующего индекса – внос туда новой информации и его сортировка по полученным метрикам, в частности PageRank.
Дополнительно надо сохранить тексты страниц – для построения аннотаций в процессе поиска
Процесс поиска
Можно выделять много метрик релевантности, одни зависят от «полезности» результата конкретному пользователю, другие от общего количества найденного, третьи – от показателей самих страниц – например, некоторые поисковые системы имеют некий «эталон» к которому стремятся.
Для того чтобы машина, т.е. сервер, мог бы отсортировать найденные результаты по какой-то метрике, используется набор чисел сопоставляемый каждой странице. Например – общее количество найденных слов в тексте данной страницы, их вес, расчитаный исходя из выделения этих слов в тексте страницы и тд. Другой род таких коэффициентов не всегда зависит от запроса – например количество страниц которые ссылаются на данную. Чем он больше тем более весома страница в выводе. Третий вид коэффициентов зависит от самого запроса – насколько редко используемые слова в нем встречаются, какие из них общеупотребительны, и их можно пропустить.
Исходя из большого количества этих коэффициентов у каждой страницы поиск должен вывести одно число – релевантность и отсортировать все результаты по нему.
Когда индекс уже построен, по нему можно искать:
разбить запрос на слова, выбрать кусочки индекса соответствующие каждому слову, пересечь или сделать что-то еще, в зависимости от выбранной политики
вычислить коэффициенты для каждой страницы – их количество, при желании, может быть далеко за тысячу
построить метрику релевантности исходя из коэффициентов, отсортировать, выбрать лучшие результаты
построить аннотации — снипеты и вывести результат
Полное содержание и список моих статей по поисковой машине будет обновлятся вот здесь: http://habrahabr.ru/blogs/search_engines/123671/
Но, к делу: поисковая машина по моему скромному мнению должна уметь находить максимально релевантные результаты по поисковому запросу. В случае текстового поиска, к которому мы все привыкли, поисковый запрос – набор слов, лично я ограничил его длину восемью словами. Ответ – набор ссылок на страницы которые наиболее релевантны поисковому запросу. Ссылки желательно снабдить аннотацией, чтобы человек знал чего ожидать и мог выбрать из результатов нужный – аннотация называется сниппет.
Надо сказать что задача поиска в общем виде не решается – для любого документа имеющего наибольшую релевантность например по слову «работа», можно создать модифицированную копию, которая будет иметь еще лучшую, с точки зрения поисковой машины, релевантность, однако будет полным бредом с точки зрения человека. Вопрос цены и времени, конечно. Из-за обширности Интернета на сегодняшний день таких страниц, мягко говоря, много. Разные системы борются с ними по-разному и с переменным успехом, когда-нибудь искусственный интеллект победит всех нас…
Тут помогли бы алгоритмы распознавания смысла, однако я знаком всего с одним из них (которые действительно распознают смысл, а не считают статистику) и мало представляю его применимость. Потому задачи решаются эмпирически – т.е. подбором некоторых манипуляций со страницами, чтобы отделить «зерна от плевел».
В реальном мире, прошерстить за секунду весь Интернет и найти результаты лучше всего подходящие, пока невозможно, поэтому поисковая машина хранит локальную копию того куска сети, который она успела собрать и обработать. Для того чтобы быстро получать из миллиарда страниц только те, которые содержат нужные слова строится «индекс» — база данных, в которой каждому слову соответствует список страниц которые это слово содержат. Естественно, в нем же надо хранить на каких местах были встречены искомые слова, как они были выделены в тексте, другие числовые метрики страницы, чтобы их использовать в процессе сортировки.
Скажем у меня 100 миллионов страниц. Среднее слово встречается на 1-1,5% страниц, т.е. 1 миллион страниц на каждое слово (есть слова которые встречаются на каждой второй странице, а есть более редкие). Всего скажем 3 миллиона встречающихся слов – остальные встречаются гораздо реже и это в основном описки и цифры. На хранение 1 записи что конкретное слово встречается на конкретной странице уходит id страницы – 4 байта, id сайта – 4 байта, упакованная информация о том в каком месте и как было выделено – 16-32 байта, 3 коэффициента ссылочного ранжирования – 12 байт, остальные метрики еще около 12-24 байт. Какого объема будет индекс – оставляю вам на прикидку:
3млн*1млн*суммарный объем записи.
Для того чтобы построить этот индекс есть 3 механизма:
индексация страниц – получение страниц из web и их начальная обработка
построение ссылочных метрик типа PageRank на основе первичной информации
обновление существующего индекса – внос туда новой информации и его сортировка по полученным метрикам, в частности PageRank.
Дополнительно надо сохранить тексты страниц – для построения аннотаций в процессе поиска
Процесс поиска
Можно выделять много метрик релевантности, одни зависят от «полезности» результата конкретному пользователю, другие от общего количества найденного, третьи – от показателей самих страниц – например, некоторые поисковые системы имеют некий «эталон» к которому стремятся.
Для того чтобы машина, т.е. сервер, мог бы отсортировать найденные результаты по какой-то метрике, используется набор чисел сопоставляемый каждой странице. Например – общее количество найденных слов в тексте данной страницы, их вес, расчитаный исходя из выделения этих слов в тексте страницы и тд. Другой род таких коэффициентов не всегда зависит от запроса – например количество страниц которые ссылаются на данную. Чем он больше тем более весома страница в выводе. Третий вид коэффициентов зависит от самого запроса – насколько редко используемые слова в нем встречаются, какие из них общеупотребительны, и их можно пропустить.
Исходя из большого количества этих коэффициентов у каждой страницы поиск должен вывести одно число – релевантность и отсортировать все результаты по нему.
Когда индекс уже построен, по нему можно искать:
разбить запрос на слова, выбрать кусочки индекса соответствующие каждому слову, пересечь или сделать что-то еще, в зависимости от выбранной политики
вычислить коэффициенты для каждой страницы – их количество, при желании, может быть далеко за тысячу
построить метрику релевантности исходя из коэффициентов, отсортировать, выбрать лучшие результаты
построить аннотации — снипеты и вывести результат
Полное содержание и список моих статей по поисковой машине будет обновлятся вот здесь: http://habrahabr.ru/blogs/search_engines/123671/
