Поисковая система — это база данных по определенной информации в интернете. Многие пользователи считают, что как только они вводят запрос в поисковую систему, тут же начинается сканирование всего интернета, но это совсем не так. Сканирование интернета происходит постоянно, многими программами, данные о сайтах заносятся в базу данных, где по определенным критериям все сайты и все их страницы распределяются в различного рода списки и базы данных. То есть это своего рода картотека данных, и поиск происходит не по интернету, а по этой картотеке.
Google — самая популярная поисковая система в мире.
Кроме поисковой системы, компания Google предлагает множество дополнительных сервисов, программ и аппаратного обеспечения, среди которых почтовый сервис , браузер Google Chrome , крупнейшая видеотека youtube и многие другие проекты. Компания Google уверено скупает многие проекты приносящие крупную прибыль. Большинство сервисов направлены не на прямого пользователя, а на заработок в интернете и интегрирована с уклоном на интересы европейских и американских пользователей.
Mail — поисковая система, популярная в основном из-за почтового сервиса.
Имеется множество дополнительных сервисов, ключевым из которых является почта Mail , на данный момент компании Mail принадлежит социальная сеть Одноклассники , собственная сеть «Мой мир», сервис Деньги-mail, множество онлайн игр, три практически одинаковых браузера с различными названиями. Во всех приложениях и сервисах очень много рекламного наполнения. Социальная сеть «ВКонаткте» блокирует прямые переходы в сервисы Mail, агрументируя большим количеством вирусов.
Википедия.
Википедия — поисковая справочная система.
Некоммерческая поисковая система, существующая на частные пожертвования, поэтому не наполняет страницы рекламой. Многоязычный проект, целью которого является создание полной справочной энциклопедии на всех языках мира. У нее нет определенных авторов, заполняется и управляется добровольцами со всех стран мира. Каждый пользователь может как написать, так и отредактировать статью.
Официальная страница — www.wikipedia.org.
Youtube — крупнейшая библиотека видеофайлов.
Видеохостинг с элементами социальной сети, где каждый пользователь может добавить видео. С момента приобретения их компанией Google Ink, отдельная регистрация для ютуба не требуется, достаточно зарегистрироваться в почтовом сервисе Google .
Официальная страница — youtube.com.
Yahoo! — вторая по значимости поисковая система в мире.
Имеются дополнительные сервисы, самым известным из которых является почта Yahoo. В рамках улучшения качества поисковой системы, Yahoo передает данные о пользователях и их запросах в компанию Microsoft. От этих данных формируется представление об интересах пользователей, а так же формируется рынок рекламного наполнения. Поисковая система Yahoo, так же как и , занимается поглощением других компаний, например, Yahoo принадлежат поисковой сервис Altavista и сайт электронной коммерции Alibaba.
Официальная страница — www.yahoo.com.
WDL — цифровая библиотека.
В библиотеке собираются книги предоставляющие культурную ценность в цифровом виде. Основная цель — повышение уровня культурного содержания интернета. Доступ к библиотеке осуществляется бесплатно.
Официальная страница — www.wdl.org/ru/.
Bing — поисковая система от компании Microsoft.
Официальная страница — www.baidu.com.
Поисковые системы России
Рамблер — «проамериканская» поисковая система.
Изначально создавался как медийный интернет-портал. Как и другие многие поисковые системы, имеет сервисы поиска по картинкам, видеофайлы, карты, прогноз погоды, новостной раздел и многое другое. Так же издатели предлагают бесплатный браузер Рамблер-Нихром .
Официальная страница — www.rambler.ru.
Nigma — интеллектуальная поисковая система.
Более удобная поисковая система из-за наличия множества фильтров и настроек. Интерфейс позволяет включать, либо исключать предлагаемые подобные значения в поиске для получения более качественных результатов. Так же, при получении результата поиска позволяет использовать информацию других крупных поисковиков.
Официальная страница — www.nigma.ru.
Aport — каталог товаров онлайн.
В прошлом поисковая система, но впоследсвии того, что разработки и нововведения были прекращены, быстро сдала позиции и . В настоящий момент Апорт является торговой площадкой, на которой представляются товары более 1500 фирм.
Официальная страница — www.aport.ru.
Спутник — национальная поисковая система и интернет-портал.
Создана компанией «Ростелеком». В настоящее время находится в стадии тестирования.
Официальная страница — www.sputnik.ru.
Metabot — развивающаяся поисковая система.
В задачах Metabot стоит создание поисковой системы по всем другим поисковым системам, создавая позиции выдачи результатов с учетом данных всего списка поисковых систем. То есть это поисковая система по поисковым системам.
Официальная страница — www.metabot.ru.
Работа поисковой системы приостановлена.
Официальная страница — www.turtle.ru.
KM — мультипортал.
Изначально сайт являлся мультипорталом с последующим внедрением поисковой системы. Поиск может проводиться как внутри сайта, так и по всем отслеженным сайтам рунета .
Официальная страница — www.km.ru.
Gogo — не работает, перенаправляет на поисковик .
Официальная страница — www.gogo.ru.
Российский мультипортал, не очень популярный, требует доработки. В поисковик включены новости, телевидение, игры, карта.
Официальная страница — www.zoneru.org.
Поисковая система не работает, разработчики предлагают воспользоваться поисковиком .
Что это
DuckDuckGo - это довольно известная поисковая система с открытым исходным кодом. Серверы находятся в США. Кроме собственного робота, поисковик использует результаты других источников: Yahoo, Bing, «Википедии».
Чем лучше
DuckDuckGo позиционирует себя как поиск, обеспечивающий максимальную приватность и конфиденциальность. Система не собирает никаких данных о пользователе, не хранит логи (нет истории поиска), использование файлов cookie максимально ограничено.
DuckDuckGo не собирает личную информацию пользователей и не делится ею. Это наша политика конфиденциальности.
Гэбриел Вайнберг (Gabriel Weinberg), основатель DuckDuckGo
Зачем это вам
Все крупные поисковые системы стараются персонализировать поисковую выдачу на основе данных о человеке перед монитором. Этот феномен получил название «пузырь фильтров»: пользователь видит только те результаты, которые согласуются с его предпочтениями или которые система сочтёт таковыми.
Формирует объективную картину, не зависящую от вашего прошлого поведения в Сети, и избавляет от тематической рекламы Google и «Яндекса», основанной на ваших запросах. При помощи DuckDuckGo легко искать информацию на иностранных языках, тогда как Google и «Яндекс» по умолчанию отдают предпочтение русскоязычным сайтам, даже если запрос введён на другом языке.
Что это
not Evil - система, осуществляющая поиск по анонимной сети Tor. Для использования нужно зайти в эту сеть, например запустив специализированный .
not Evil не единственный поисковик в своём роде. Есть LOOK (поиск по умолчанию в Tor-браузере, доступен из обычного интернета) или TORCH (один из самых старых поисковиков в Tor-сети) и другие. Мы остановились на not Evil из-за недвусмысленного намёка на Google (достаточно посмотреть на стартовую страницу).
Чем лучше
Ищет там, куда Google, «Яндексу» и другим поисковикам вход закрыт в принципе.
Зачем это вам
В сети Tor много ресурсов, которые невозможно встретить в законопослушном интернете. И их число будет расти по мере того, как ужесточается контроль властей над содержанием Сети. Tor - это своеобразная сеть внутри Сети со своими социалками, торрент-трекерами, СМИ, торговыми площадками, блогами, библиотеками и так далее.
3. YaCy
Что это
YaCy - децентрализованная поисковая система, работающая по принципу сетей P2P. Каждый компьютер, на котором установлен основной программный модуль, сканирует интернет самостоятельно, то есть является аналогом поискового робота. Полученные результаты собираются в общую базу, которую используют все участники YaCy.
Чем лучше
Здесь сложно говорить, лучше это или хуже, так как YaCy - это совершенно иной подход к организации поиска. Отсутствие единого сервера и компании-владельца делает результаты полностью независимыми от чьих-то предпочтений. Автономность каждого узла исключает цензуру. YaCy способен вести поиск в глубоком вебе и неиндексируемых сетях общего пользования.
Зачем это вам
Если вы сторонник открытого ПО и свободного интернета, не подверженного влиянию государственных органов и крупных корпораций, то YaCy - это ваш выбор. Также с его помощью можно организовать поиск внутри корпоративной или другой автономной сети. И пусть пока в быту YaCy не слишком полезен, он является достойной альтернативой Google с точки зрения процесса поиска.
4. Pipl
Что это
Pipl - система, предназначенная для поиска информации о конкретном человеке.
Чем лучше
Авторы Pipl утверждают, что их специализированные алгоритмы ищут эффективнее, чем «обычные» поисковики. В частности, приоритетными являются профили социальных сетей, комментарии, списки участников и различные базы данных, где публикуются сведения о людях, например базы судебных решений. Лидерство Pipl в этой области подтверждено оценками Lifehacker.com, TechCrunch и других изданий.
Зачем это вам
Если вам нужно найти информацию о человеке, проживающем в США, то Pipl будет намного эффективнее Google. Базы данных российских судов, видимо, недоступны для поисковика. Поэтому с гражданами России он справляется не так хорошо.
Что это
FindSounds - ещё один специализированный поисковик. Ищет в открытых источниках различные звуки: дом, природа, машины, люди и так далее. Сервис не поддерживает запросы на русском языке, но есть внушительный список русскоязычных тегов, по которым можно выполнять поиск.
Чем лучше
В выдаче только звуки и ничего лишнего. В настройках можно выставить желаемый формат и качество звучания. Все найденные звуки доступны для скачивания. Имеется поиск по образцу.
Зачем это вам
Если вам нужно быстро найти звук мушкетного выстрела, удары дятла-сосуна или крик Гомера Симпсона, то этот сервис для вас. И это мы выбрали только из доступных русскоязычных запросов. На английском языке спектр ещё шире.
Если серьёзно, специализированный сервис предполагает специализированную аудиторию. Но вдруг и вам пригодится?
Что это
Wolfram|Alpha - вычислительно-поисковая система. Вместо ссылок на статьи, содержащие ключевые слова, она выдаёт готовый ответ на запрос пользователя. Например, если ввести в форму поиска «сравнить население Нью-Йорка и Сан-Франциско» на английском, то Wolfram|Alpha сразу выведет на экран таблицы и графики со сравнением.
Чем лучше
Этот сервис лучше других подходит для поиска фактов и вычисления данных. Wolfram|Alpha накапливает и систематизирует доступные в Сети знания из различных областей, включая науку, культуру и развлечения. Если в этой базе находится готовый ответ на поисковый запрос, система показывает его, если нет - вычисляет и выводит результат. При этом пользователь видит только и ничего лишнего.
Зачем это вам
Если вы, например, студент, аналитик, журналист или научный сотрудник, то можете использовать Wolfram|Alpha для поиска и вычисления данных, связанных с вашей деятельностью. Сервис понимает не все запросы, но постоянно развивается и становится умнее.
Что это
Метапоисковик Dogpile выводит комбинированный список результатов из поисковых выдач Google, Yahoo и других популярных систем.
Чем лучше
Во-первых, Dogpile отображает меньше рекламы. Во-вторых, сервис использует особый алгоритм, чтобы находить и показывать лучшие результаты из разных поисковиков. Как утверждают разработчики Dogpile, их системы формирует самую полную выдачу во всём интернете.
Зачем это вам
Если вы не можете найти информацию в Google или другом стандартном поисковике, поищите её сразу в нескольких поисковиках с помощью Dogpile.
Что это
BoardReader - система для текстового поиска по форумам, сервисам вопросов и ответов и другим сообществам.
Чем лучше
Сервис позволяет сузить поле поиска до социальных площадок. Благодаря специальным фильтрам вы можете быстро находить посты и комментарии, которые соответствуют вашим критериям: языку, дате публикации и названию сайта.
Зачем это вам
BoardReader может пригодиться пиарщикам и другим специалистам в области медиа, которых интересует мнение массовой по тем или иным вопросам.
В заключение
Жизнь альтернативных поисковиков часто бывает скоротечной. О долгосрочных перспективах подобных проектов Лайфхакер спросил бывшего генерального директора украинского филиала компании «Яндекс» Сергея Петренко .
Сергей Петренко
Бывший генеральный директор «Яндекс.Украины».
Что касается судьбы альтернативных поисковиков, то она проста: быть очень нишевыми проектами с небольшой аудиторией, следовательно без ясных коммерческих перспектив или, наоборот, с полной ясностью их отсутствия.
Если посмотреть на примеры в статье, то видно, что такие поисковики либо специализируются в узкой, но востребованной нише, которая, возможно только пока, не выросла настолько, чтобы оказаться заметной на радарах Google или «Яндекса», либо тестируют оригинальную гипотезу в ранжировании, которая пока не применима в обычном поиске.
Например, если поиск по Tor вдруг окажется востребованным, то есть результаты оттуда понадобятся хотя бы проценту аудитории Google, то, конечно, обычные поисковики начнут решать проблему, как их найти и показать пользователю. Если поведение аудитории покажет, что заметной доле пользователей в заметном количестве запросов более релевантными кажутся результаты, данные без учёта факторов, зависящих от пользователя, то «Яндекс» или Google начнут давать такие результаты.
«Быть лучше» в контексте этой статьи не означает «быть лучше во всём». Да, во многих аспектах нашим героям далеко до и «Яндекса» (даже до Bing далековато). Но зато каждый из этих сервисов даёт пользователю нечто такое, чего не могут предложить гиганты поисковой индустрии. Наверняка вы тоже знаете подобные проекты. Поделитесь с нами - обсудим.
Наиболее популярным веб сервисом современности является именно поисковая система. Тут всё объяснимо, ведь те времена, когда представители первых пользователей интернета могли наблюдать новинки в сети уже давным-давно ушли.
Информации появляется и скапливается так много, что человеку стало очень трудно найти именно ту, которая ему была бы необходима. Представьте, как бы обстоял бы поиск в интернете, если бы рядовому пользователю пришлось бы искать информацию не пойми где. Именно не пойми где, потому как ручным поиском много информации не найдёшь.
Поисковая система, что это такое?
Хорошо если пользователю уже известны сайты, на которых возможно есть нужная информация, но что делать в противном случае? Для того, чтобы облегчить жизнь человеку в поиске нужной информации в интернете и были придуманы поисковые системы или просто поисковики. Поисковая система выполняет одну очень важную функцию, без которой интернет был бы не таким как мы его привыкли видеть - это поиск информации в сети.
Поисковая система - это специальный веб узел или по-другому сайт, который предоставляет пользователям по их запросам гиперссылки на страницы, сайтов, отвечающие на заданный поисковой запрос.
Если быть немного точнее, то поиск информации в интернете, осуществляющийся благодаря программно-аппаратному функциональному набору и веб интерфейсу для взаимодействия с пользователями.
Для взаимодействия человека с поисковой системой и был создан веб интерфейс, то есть видимая и понятная оболочка. Данный подход разработчиков поисковиков облегчает поиск многим людям. Как правило, именно в интернете осуществляется поиск при помощи поисковых систем, но также существуют системы поиска для FTP-серверов, отдельных видов товаров во всемирной паутине, либо новостной информации или же другие поисковые направления.
Поиск может осуществляться не только по текстовому наполнению сайтов, но и по другим типам информации, которые человек может искать: изображения, видео, звуковые файлы и т.д.
Как осуществляется поиск поисковой системой?
Сам поиск в интернете, ровно так же как просмотр веб сайтов возможен при помощи интернет обозревателя - браузера . Только после того, как пользователь задал свой запрос в строке поиска, осуществляется непосредственно и сам поиск.
Любая поисковая система содержит программную часть, на которой основан весь поисковой механизм, его называют поисковым движком - это программный комплекс и обеспечивающий возможность поиска информации. После обращению к поисковику, формирования человеком поискового запроса и ввода его в строку поиска, поисковая система генерирует страницу со списком результатов поиска, наиболее релевантные, по мнению поисковика тут располагаются выше.
Релевантность поиска - поиск наиболее отвечающих запросу пользователя материалов и расположение на них гиперссылок на странице выдачи с более точными результатами выше других. Само распределениерезультатов называется ранжированием сайтов.
Так как же поисковик подготавливает для выдачи свои материалы и как происходит поиск информации самим поисковиком? Сбору информации в сети способствует уникальный для каждой поисковой системы робот или по-другому бот, обладающий так же рядом других синонимов как краулер или паук, а саму работу системы поиска можно разделить на три этапа:
К первому этапу работы поисковой системы можно отнести сканирование сайтов в глобальной сети и сбор на свои собственные серверы копий веб страниц. Это образует огромное количество пока ещё не обработанной и не пригодной информации для поисковой выдачи.
Второй этап работы поисковика сводится к приведению в порядок полученной ранее, на первом этапе информации от сайтов. Производится такая сортировка, которая за наименьшее время будет благоприятствовать тому самому качественному поиску, которого собственно и ждут пользователи от поисковой системы. Этап называют индексацией, это значит, что страницы уже являются подготовленными к выдаче, а актуальная база будет считаться индексом.
Как раз третий этап и обуславливает поисковую выдачу, после приёма запроса от своего клиента, опираясь на ключевые или около ключевые слова, указанные в запросе. Это способствует отбору наиболее соответствующей запросу информации, и последующей её выдачи. Так как информации, очень и очень много, поисковая система выполняет ранжирование в соответствие со своими алгоритмами.
Лучшей поисковой системой считается та, которая сможет предоставить наиболее корректно отвечающий на запрос пользователя материал. Но и тут могут встречаться результаты, на которые повлияли люди, заинтересованные в продвижение своего сайта, такие сайты хоть и не всегда, но зачастую появляются в результатах поиска, но не на долго.
Хоть мировые лидеры уже во многих регионах определены, поисковые системы продолжаются развивать свой качественный, поиск. Чем качественней поиск они смогут предоставить, тем больше людей будут им пользоваться.
Как пользоваться поисковой системой?
Что такое поисковая система и как она работает уже понятно, но как ей правильно пользоваться? На большинстве сайтов всегда присутствует строка поиска, а рядом с ней находится кнопка Найти или Поиск. В поисковую строку вводится запрос, после чего нужно нажать кнопку поиска или же как это чаще бывает, нажать клавишу Enter на клавиатуре и за считанные секунды вы получаете результат запроса в виде списка.
А вот получить правильный ответ на запрос поиска, с первого раза удаётся не всегда. Для того, чтобы поиски желаемого не становились мучительными, необходимо правильно составлять поисковый запрос и следовать нижеописанным рекомендациям.
Составляем поисковый запрос правильно
Далее будут указаны советы по использованию поисковой системы. Следование некоторым хитростям и правилам при осуществлении поиска информации в поисковой системе даст возможность получить нужный результат гораздо быстрее. Следуйте данным рекомендациям:
- Грамотное написание слов обеспечивает максимальное количество совпадений с искомым информационным объектом (Хоть современный поисковые системы уже научились исправлять орфографические ошибки, но данным советом пренебрегать не стоит).
- Благодаря использованию синонимов в запросе, можно охватить более широкий поисковой диапазон.
- Иногда изменение слова в тексте запроса может принести больший результат осуществляйте переформирование запроса.
- Привносите в запрос конкретность, используйте точные вхождения фраз, которые должны определять главную суть поиска.
- Экспериментируйте с ключевыми словами. Использование ключевых слов и словосочетаний может помочь определить главную суть, и поисковая машина выдаст более релевантный результат.
Так что такое поисковая система - это ни что иное, как возможность найти интересующую информацию и обычно совершенно бесплатно ей воспользоваться, чему-то научиться, что-то понять или сделать правильный для себя вывод. Многие уже не представляют своей жизни без голосового поиска, при котором текст не приходится набирать, свой запрос нужно всего лишь произнести, а устройством ввода информации тут является микрофон. Всё это свидетельствует о постоянном развитие поисковых технологий в интернете и необходимости в них.
В июле прошлого года не стало Ильи Сегаловича , основателя и директора по технологиям «Яндекса», создателя первой версии поисковика и автора его названия. В память об этом выдающемся человеке и общественном деятеле, который помог многим, в том числе и COLTA . RU , мы републикуем его об информационном поиске и математических моделях, которые лежат в его основе. Илья Сегалович называл поисковые системы одним из двух новых чудес света. Во всяком случае, без них и в том числе без главного детища Сегаловича - «Яндекса» наша жизнь была бы совсем другой.
В мире написаны сотни поисковых систем, а если считать функции поиска, реализованные в самых разных программах, то счет надо вести на тысячи. И как бы ни был реализован процесс поиска, на какой бы математической модели он ни основывался, идеи и программы, реализующие поиск, достаточно просты. Хотя эта простота относится, по-видимому, к той категории, про которую говорят «просто, но работает». Так или иначе, но именно поисковые системы стали одним из двух новых чудес света, предоставив homo sapiens неограниченный и мгновенный доступ к информации. Первым чудом, очевидно, можно считать интернет как таковой с его возможностями всеобщей коммуникации.
Поисковые системы в исторической перспективе
Существует распространенное убеждение, что каждое новое поколение программ совершеннее предыдущего. Дескать, раньше все было несовершенно, зато теперь повсюду царит чуть ли не искусственный интеллект. Иная крайняя точка зрения состоит в том, что «все новое - это хорошо забытое старое». Думаю, что применительно к поисковым системам истина лежит где-то посередине.
Но что же поменялось в действительности за последние годы? Не алгоритмы и не структуры данных, не математические модели. Хотя и они тоже. Поменялась парадигма использования систем. Проще говоря, к экрану со строчкой поиска подсели домохозяйка, ищущая утюг подешевле, и выпускник вспомогательного интерната в надежде найти работу автомеханика. Кроме появления фактора, невозможного в доинтернетовскую эру, - фактора тотальной востребованности поисковых систем - стала очевидна еще пара изменений. Во-первых, стало ясно, что люди не только «думают словами», но и «ищут словами». В ответе системы они ожидают увидеть слово, набранное в строке запроса. И второе: «человека ищущего» трудно «переучить искать», так же как трудно переучить говорить или писать. Мечты 60-80-х об итеративном уточнении запросов, о понимании естественного языка, о поиске по смыслу, о генерации связного ответа на вопрос с трудом выдерживают сейчас жестокое испытание реальностью.
Алгоритм + структура данных = поисковая система
Как и любая программа, поисковая система оперирует структурами данных и исполняет алгоритм. Разнообразие алгоритмов не очень велико, но оно есть. Не считая квантовых компьютеров, которые обещают нам волшебный прорыв в «алгоритмической сложности» поиска и про которые автору почти ничего не известно, есть четыре класса поисковых алгоритмов. Три алгоритма из четырех требуют «индексирования», предварительной обработки документов, при котором создается вспомогательный файл, сиречь «индекс», призванный упростить и ускорить сам поиск. Это алгоритмы инвертированных файлов, суффиксных деревьев, сигнатур. В вырожденном случае предварительный этап индексирования отсутствует, а поиск происходит при помощи последовательного просмотра документов. Такой поиск называется прямым.
Прямой поиск
Простейшая его версия знакома многим, и нет программиста, который бы не написал хотя бы раз в своей жизни подобный код:
Несмотря на кажущуюся простоту, последние 30 лет прямой поиск интенсивно развивается. Было выдвинуто немалое число идей, сокращающих время поиска в разы. Эти алгоритмы подробно описаны в разнообразной литературе, есть их сводки и сопоставления. Неплохие обзоры прямых методов поиска можно найти в учебниках, например, Седжвика или Кормена. При этом надо учесть, что новые алгоритмы и их улучшенные варианты появляются постоянно.
Хотя прямой просмотр всех текстов - довольно медленное занятие, не следует думать, что алгоритмы прямого поиска не применяются в интернете. Норвежская поисковая система Fast использовала чип, реализующий логику прямого поиска упрощенных регулярных выражений (fastpmc ) , и разместила 256 таких чипов на одной плате. Это позволяло Fast обслуживать довольно большое количество запросов в единицу времени.
Кроме того, есть масса программ, комбинирующих индексный поиск для нахождения блока текста с дальнейшим прямым поиском внутри блока. Например, весьма популярный, в том числе и в рунете, Glimpse .
Вообще у прямых алгоритмов есть принципиально беспроигрышные отличительные черты. Например, неограниченные возможности по приближенному и нечеткому поиску. Ведь любое индексирование всегда сопряжено с упрощением и нормализацией терминов, а следовательно, с потерей информации. Прямой же поиск работает непосредственно по оригинальным документам безо всяких искажений.
Инвертированный файл
Эта простейшая структура данных, несмотря на свое загадочное иностранное название, интуитивно знакома как любому грамотному человеку, так и любому программисту баз данных, даже не имевшему дело с полнотекстовым поиском. Первая категория людей знает, что это такое, по «конкордансам» - алфавитно упорядоченным исчерпывающим спискам слов из одного текста или принадлежащих одному автору (например «Конкорданс к стихам А.С. Пушкина», «Словарь-конкорданс публицистики Ф.М. Достоевского»). Вторые имеют дело с той или иной формой инвертированного списка всякий раз, когда строят или используют «индекс БД по ключевому полю».
Проиллюстрируем эту структуру при помощи замечательного русского конкорданса - «Симфонии», выпущенной Московской патриархией по тексту синодального перевода Библии.
Перед нами упорядоченный по алфавиту список слов. Для каждого слова перечислены все «позиции», в которых это слово встретилось. Поисковый алгоритм состоит в отыскании нужного слова и загрузке в память уже развернутого списка позиций.
Чтобы сэкономить на дисковом пространстве и ускорить поиск, обычно прибегают к двум приемам. Во-первых, можно сэкономить на подробности самой позиции. Ведь чем подробнее задана такая позиции (например, в случае с «Симфонией» это «книга+глава+стих»), тем больше места потребуется для хранения инвертированного файла.
В наиподробнейшем варианте в инвертированном файле можно хранить и номер слова, и смещение в байтах от начала текста, и цвет и размер шрифта, да много чего еще. Чаще же просто указывают номер документа (скажем, книгу Библии) и число употреблений этого слова в нем. Именно такая упрощенная структура считается основной в классической теории информационного поиска - Information Retrieval (IR ) .
Второй (никак не связанный с первым) способ сжатия: упорядочить позиции для каждого слова по возрастанию адресов и для каждой позиции хранить не полный ее адрес, а разницу от предыдущего. Вот как будет выглядеть такой список для нашей странички в предположении, что мы запоминаем позицию вплоть до номера главы:
Дополнительно на разностный способ хранения адресов накладывают какой-нибудь простенький способ упаковки: зачем отводить небольшому целому числу фиксированное «огромное» количество байтов, ведь можно отвести ему почти столько байтов, сколько оно заслуживает. Здесь уместно упомянуть коды Голомба или встроенную функцию популярного языка Perl : pack («w ») .
В литературе встречается и более тяжелая артиллерия упаковочных алгоритмов самого широкого спектра: арифметический, Хафман, LZW и т.д. Прогресс в этой области идет непрерывно. На практике в поисковых системах они используются редко: выигрыш невелик, а мощности процессора расходуются неэффективно.
В результате всех описанных ухищрений размер инвертированного файла, как правило, составляет от 7 до 30 процентов от размера исходного текста, в зависимости от подробности адресации.
Занесены в «Красную книгу»
Неоднократно предлагались другие, отличные от инвертированного и прямого поиска, алгоритмы и структуры данных. Это, прежде всего, суффиксные деревья (Манбер, Гоннет), а также сигнатуры (Фалуцос).
Первый из них функционировал и в интернете, будучи запатентованным алгоритмом поисковой системы OpenText . Мне доводилось встречать суффиксные индексы в отечественных поисковых системах. Второй - метод сигнатур - представляет собой преобразование документа к поблочным таблицам хеш-значений его слов - «сигнатуре» и последовательному просмотру «сигнатур» во время поиска.
Широкого распространения ни тот, ни другой метод не получили, а следовательно, не заслужили и подробного обсуждения в этой небольшой статье.
Математические модели
Приблизительно три из пяти поисковых систем и модулей функционируют безо всяких математических моделей. Точнее сказать, их разработчики не ставят перед собой задачу реализовывать абстрактную модель и/или не подозревают о существовании оной. Принцип здесь прост: лишь бы программа хоть что-нибудь находила. Абы как. А дальше сам пользователь разберется.
Однако, как только речь заходит о повышении качества поиска, о большом объеме информации, о потоке пользовательских запросов, кроме эмпирически проставленных коэффициентов полезным оказывается оперировать каким-нибудь, пусть и несложным, теоретическим аппаратом. Модель поиска - это некоторое упрощение реальности, на основании которого получается формула (сама по себе никому не нужная), позволяющая программе принять решение: какой документ считать найденным и как его ранжировать. После принятия модели коэффициенты часто приобретают физический смысл и становятся понятнее самому разработчику, да и подбирать их становится интереснее.
Все многообразие моделей традиционного информационного поиска (IR ) принято делить на три вида: теоретико-множественные (булевская, нечетких множеств, расширенная булевская), алгебраические (векторная, обобщенная векторная, латентно-семантическая, нейросетевая) и вероятностные.
Булевское семейство моделей - по сути, первое, приходящее на ум программисту, реализующему полнотекстовый поиск. Есть слово - документ считается найденным, нет - не найденным. Собственно, классическая булевская модель - это мостик, связывающий теорию информационного поиска с теорией поиска и манипулирования данными.
Критика булевской модели, вполне справедливая, состоит в ее крайней жесткости и непригодности для ранжирования. Поэтому еще в 1957 году Джойс и Нидхэм предложили учитывать частотные характеристики слов, чтобы «... операция сравнения была бы отношением расстояния между векторами...» (Джойс, 1957). Векторная модель и была с успехом реализована в 1968 году отцом- основателем науки об информационном поиске Джерардом Солтоном (Gerard Salton ) в поисковой системе SMART (Salton "s Magical Automatic Retriever of Text ) .
Ранжирование в этой модели основано на естественном статистическом наблюдении, что чем больше локальная частота термина в документе (TF ) и больше «редкость» (т.е. обратная встречаемость в документах) термина в коллекции (IDF ) , тем выше вес данного документа по отношению к термину. Обозначение IDF ввела Карен Спарк-Джоунз в 1972 г. в статье про различительную силу (term specificity ) . С этого момента обозначение TF *IDF широко используется как синоним векторной модели.
Наконец, в 1977 году Робертсон и Спарк-Джоунз обосновали и реализовали вероятностную модель (предложенную еще в 1960-м (Марон)), также положившую начало целому семейству. Релевантность в этой модели рассматривается как вероятность того, что данный документ может оказаться интересным пользователю. При этом подразумевается наличие уже существующего первоначального набора релевантных документов, выбранных пользователем или полученных автоматически при каком-нибудь упрощенном предположении. Вероятность оказаться релевантным для каждого следующего документа рассчитывается на основании соотношения встречаемости терминов в релевантном наборе и в остальной, «нерелевантной» части коллекции. Хотя вероятностные модели обладают некоторым теоретическим преимуществом - ведь они располагают документы в порядке убывания «вероятности оказаться релевантным», - на практике они так и не получили большого распространения.
Я не собираюсь вдаваться в подробности и выписывать громоздкие формулы для каждой модели. Их сводка вместе с обсуждением занимает в сжатом виде 35 страниц в книжке «Современный информационный поиск» (Баэса-Ятес). Важно только заметить, что в каждом из семейств простейшая модель исходит из предположения о взаимонезависимости слов и обладает простым условием фильтрации: документы, не содержащие слова запроса, никогда не бывают найденными. Продвинутые («альтернативные») модели каждого из семейств не считают слова запроса взаимонезависимыми, а кроме того, позволяют находить документы, не содержащие ни одного слова из запроса.
Поиск «по смыслу»
Способность находить и ранжировать документы, не содержащие слов из запроса, часто считают признаком искусственного интеллекта или поиска по смыслу и относят априори к преимуществам модели. Вопрос о том, так это или нет, мы оставим за рамками данной статьи.
Для примера опишу лишь одну, пожалуй, самую популярную модель, работающую по смыслу. В теории информационного поиска данную модель принято называть латентно-семантическим индексированием (иными словами, выявлением скрытых смыслов). Эта алгебраическая модель основана на сингулярном разложении прямоугольной матрицы, ассоциирующей слова с документами. Элементом матрицы является частотная характеристика, отражающая степень связи слова и документа, например, TF *IDF . Вместо исходной миллионноразмерной матрицы авторы метода Фурнас и Дирвестер предложили использовать 50-150 «скрытых смыслов» , соответствующих первым главным компонентам ее сингулярного разложения.
Сингулярным разложением действительной матрицы A размеров m *n называется всякое ее разложение вида A = USV , где U m *m , V - ортогональная матрица размеров n *n , S - диагональная матрица размеров m *n , элементы которой sij = 0 , если i не равно j , и sii = si >= 0 . Величины si называются сингулярными числами матрицы и равны арифметическим значениям квадратных корней из соответствующих собственных значений матрицы AAT . В англоязычной литературе сингулярное разложение принято называть SVD -разложением.
Давным-давно доказано (Экарт), что если оставить в рассмотрении первые k сингулярных чисел (остальные приравнять к нулю), мы получим ближайшую из всех возможных аппроксимацию исходной матрицы ранга k (в некотором смысле ее «ближайшую семантическую интерпретацию ранга k »). Уменьшая ранг, мы отфильтровываем нерелевантные детали; увеличивая, пытаемся отразить все нюансы структуры реальных данных.
Операции поиска или нахождения похожих документов резко упрощаются, так как каждому слову и каждому документу сопоставляется относительно короткий вектор из k смыслов (строки и столбцы соответствующих матриц). Однако по причине малой осмысленности «смыслов» или по какой иной , но использование LSI в лоб для поиска так и не получило распространения. Хотя во вспомогательных целях (автоматическая фильтрация, классификация, разделение коллекций, предварительное понижение размерности для других моделей) этот метод, по-видимому, находит применение.
Оценка качества
«...проверка устойчивости показала, что перекрытие релевантных документов между любыми двумя асессорами примерно 40% в среднем <...> точность и полнота, измеренная между асессорами, около 65% <...> Это накладывает практическую верхнюю границу на качество поиска в районе 65%...»
(«What we have learned, and not learned, from TREC», Donna Harman)
Какова бы ни была модель, поисковая система нуждается в «тюнинге» - оценке качества поиска и настройке параметров. Оценка качества - идея, фундаментальная для теории поиска. Ибо именно благодаря оценке качества можно говорить о применимости или неприменимости той или иной модели и даже обсуждать их теоретические аспекты.
В частности, одним из естественных ограничений качества поиска служит наблюдение, вынесенное в эпиграф: мнения двух «асессоров» (специалистов, выносящих вердикт о релевантности) в среднем не совпадают друг с другом в очень большой степени! Отсюда вытекает и естественная верхняя граница качества поиска, ведь качество измеряется по итогам сопоставления с мнением асессора.
«...Я был потрясен, когда кто-то из Google сказал мне, что они вообще не используют ничего наработанного в TREC , потому что все алгоритмы, заточенные на дорожке “произвольных запросов”, спам расшибает вдребезги...»
Пора вернуться к теме, с которой началась эта статья: что же изменилось в поисковых системах за последнее время?
Прежде всего, стало очевидно, что поиск в вебе не может быть сколько-нибудь корректно выполнен, будучи основан на анализе (пусть даже сколь угодно глубоком, семантическом и т.п.) одного лишь текста документа. Ведь внетекстовые (off -page ) факторы играют не меньшую, а порой и бо́льшую роль, чем текст самой страницы. Положение на сайте, посещаемость, авторитетность источника, частота обновления, цитируемость страницы и ее авторов - все эти факторы невозможно сбрасывать со счета.
Cтав основным источником получения справочной информации для человеческого вида, поисковые системы стали основным источником трафика для интернет-сайтов. Как следствие, они немедленно подверглись «атакам» недобросовестных авторов, желающих любой ценой оказаться в первых страницах результатов поиска. Искусственная генерация входных страниц, насыщенных популярными словами, техника клоакинга, «слепого текста» и многие другие приемы, предназначенные для обмана поисковых систем, мгновенно заполонили интернет.
Кроме проблемы корректного ранжирования создателям поисковых систем в интернете пришлось решать задачу обновления и синхронизации колоссальной по размеру коллекции с гетерогенными форматами, способами доставки, языками, кодировками, массой бессодержательных и дублирующихся текстов. Необходимо поддерживать базу в состоянии максимальной свежести (на самом деле достаточно создавать иллюзию свежести - но это тема отдельного разговора), может быть, учитывать индивидуальные и коллективные предпочтения пользователей. Многие из этих задач никогда прежде не рассматривались в традиционной науке информационного поиска.
Для примера рассмотрим пару таких задач и практических способов их решения в поисковых системах для интернета.
Качество ранжирования
Не все внетекстовые критерии полезны в равной мере. Именно ссылочная популярность и производные от нее оказались решающим фактором, поменявшим в 1999-2000 гг. мир поисковых систем и вернувшим им преданность пользователей. Так как именно с ее помощью поисковые системы научились прилично и самостоятельно (без подпорок из вручную отредактированных результатов) ранжировать ответы на короткие частотные запросы, составляющие значительную часть поискового потока.
Простейшая идея глобального (т.е. статического) учета ссылочной популярности состоит в подсчете числа ссылок, указывающих на страницы. Примерно то, что в традиционном библиотековедении называют индексом цитирования. Этот критерий использовался в поисковых системах еще до 1998 года. Однако он легко подвергается накрутке, кроме того, он не учитывает вес самих источников.
Естественным развитием этой идеи можно считать предложенный Брином и Пейджем в 1998 году алгоритм PageRank - итеративный алгоритм, подобный тому, что используется в задаче определения победителя в шахматном турнире по швейцарской системе. В сочетании с поиском по лексике ссылок, указывающих на страницу (старая, весьма продуктивная идея, которая использовалась в гипертекстовых поисковых системах еще в 80-е годы), эта мера позволила резко повысить качество поиска.
Немного раньше, чем PageRank , был предложен локальный (т.е. динамический, основанный на запросе) алгоритм учета популярности - HITS (Кляйнберг), который не используется на практике в основном из-за вычислительной дороговизны. Примерно по той же причине, что и локальные (т.е. динамические) методы, оперирующие словами.
Оба алгоритма, их формулы, условия сходимости подробно описаны, в том числе и в русскоязычной литературе. Отмечу только, что расчет статической популярности не является самоценной задачей, он используется в многочисленных вспомогательных целях: определение порядка обхода документов, ранжирование поиска по тексту ссылок и т.д. Формулы расчета популярности постоянно улучшают, в них вносят учет дополнительных факторов - тематической близости документов (например, популярная поисковая система www .teoma .com ), их структуры и т.п., позволяющих понизить влияние непотизма. Интересной отдельной темой является эффективная реализация соответствующих структур данных (Бхарат).
Качество индекса
Хотя размер базы в интернете на поверхностный взгляд не кажется критическим фактором, это не так. Недаром рост посещаемости таких машин, как Google и Fast , хорошо коррелирует именно с ростом их баз. Основная причины: «редкие» запросы, то есть те, по которым находится менее 100 документов, составляют в сумме около 30% от всей массы поисков - весьма значительную часть. Этот факт делает размер базы одним из самых критичных параметров системы.
Однако рост базы кроме технических проблем с дисками и серверами ограничивается и логическими: необходимостью адекватно реагировать на мусор, повторы и т.п. Не могу удержаться, чтобы не описать остроумный алгоритм, применяемый в современных поисковых системах для того, чтобы исключить «очень похожие документы».
Происхождение копий документов в интернете может быть различным. Один и тот же документ на одном и том же сервере может отличаться по техническим причинам: быть представлен в разных кодировках и форматах, содержать переменные вставки - рекламу или текущую дату.
Широкий класс документов в вебе активно копируется и редактируется - ленты новостных агентств, документация и юридические документы, прейскуранты магазинов, ответы на часто задаваемые вопросы и т.д. Популярные типы изменений: корректура, реорганизация, ревизия, реферирование, раскрытие темы и т.д. Наконец, публикации могут быть скопированы с нарушением авторских прав и изменены злонамеренно с целью затруднить их обнаружение.
Кроме того, индексация поисковыми машинами страниц, генерируемых из баз данных, порождает еще один распространенный класс внешне мало отличающихся документов: анкеты, форумы, страницы товаров в электронных магазинах.
Очевидно, что с полными повторами проблем особых нет, достаточно сохранять в индексе контрольную сумму текста и игнорировать все остальные тексты с такой же контрольной суммой. Однако этот метод не работает для выявления хотя бы чуть-чуть измененных документов.
Для решения этой задачи Уди Манбер (автор известной программы приближенного прямого поиска agrep ) в 1994 году предложил идею, а Андрей Бродер в 1997-м придумал название и довел до ума алгоритм «шинглов» (от слова shingles - «черепички, чешуйки»). Вот его примерное описание.
Для каждого десятисловия текста рассчитывается контрольная сумма (шингл). Десятисловия идут внахлест, с перекрытием, так, чтобы ни одно не пропало. А затем из всего множества контрольных сумм (очевидно, что их столько же, сколько слов в документе минус 9) отбираются только те, которые делятся на, скажем, 25. Поскольку значения контрольных сумм распределены равномерно, критерий выборки никак не привязан к особенностям текста. Ясно, что повтор даже одного десятисловия - весомый признак дублирования, если же их много, скажем, больше половины, то с определенной (несложно оценить вероятность) уверенностью можно утверждать: копия найдена! Ведь один совпавший шингл в выборке соответствует примерно 25 совпавшим десятисловиям в полном тексте!
Очевидно, что так можно определять процент перекрытия текстов, выявлять все его источники и т.п. Этот изящный алгоритм воплотил давнюю мечту доцентов: отныне мучительный вопрос «у кого студент списывал этот курсовик» можно считать решенным! Легко оценить долю плагиата в любой статье .
Чтобы у читателя не создалось впечатление, что информационный поиск - исключительно западная наука, упомяну про альтернативный алгоритм определения почти-дубликатов, придуманный и воплощенный у нас в Яндексе (Ильинский). В нем используется тот факт, что большинство поисковых систем уже обладают индексом в виде инвертированного файла (или инвертированным индексом), и этот факт удобно использовать в процедуре нахождения почти-дубликатов.
Цена одного процента
Архитектурно современные поисковые системы представляют собой сложные многокомпьютерные комплексы. Начиная с некоторого момента по мере роста системы основная нагрузка ложится вовсе не на робота, а на поиск. Ведь в течение секунды приходят десятки и сотни запросов.
Для того чтобы справиться с этой проблемой, индекс разбивают на части и раскладывают по десяткам, сотням и даже тысячам компьютеров. Сами компьютеры начиная с 1997 года (поисковая система Inktomi ) представляют собой обычные 32-битные машины (Linux , Solaris , FreeBSD , Win 32 ) с соответствующими ограничениями по цене и производительности. Исключением из общего правила осталась лишь AltaVista , которая с самого начала использовала относительно «большие» 64-битные компьютеры Alpha .
Поисковые системы для интернета (и вообще все большие поисковые сиcтемы) могут ускорять свою работу при помощи техник эшелонирования и прюнинга.
Первая техника состоит в разделении индекса на заведомо более релевантную и менее релевантную части. Поиск сначала выполняется в первой части, а затем, если ничего не найдено или найдено мало, поисковая система обращается ко второй части индекса. Прюнинг (от англ. pruning - «отсечение, сокращение») состоит в том, чтобы динамически прекращать обработку запроса после накопления достаточного количества релевантной информации. Бывает еще статический прюнинг, когда на основании некоторых допущений индекс сокращается за счет таких документов, которые заведомо никогда не будут найдены.
Отдельная проблема - организовать бесперебойную работу многокомпьютерных комплексов, бесшовное обновление индекса, устойчивость к сбоям и задержкам с ответами отдельных компонент. Для общения между поисковыми серверами и серверами, собирающими отклики и формирующими страницу выдачи, разрабатываются специальные протоколы.
Заметьте, что один процент производительности (скажем, неудачно написанный оператор в каком-нибудь цикле) для десятитысячнокомпьютерной системы стоит примерно ста компьютеров. Поэтому можно себе представить, как вычищается код, отвечающий за поиск и ранжирование результатов, как оптимизируется использование всех возможных ресурсов: каждого байта памяти, каждого обращения к диску.
Решающее значение приобретает продумывание архитектуры всего комплекса с самого начала, так как любые изменения - например, добавление необычного фактора при ранжировании или сложного источника данных - становятся исключительно болезненной и сложной процедурой. Очевидно, системы, стартующие позже, имеют в этой ситуации преимущество. Но инертность пользователей весьма высока: так, например, требуется два-четыре года, чтобы сформированная многомиллионная аудитория сама, пусть и медленно, перешла на непривычную поисковую систему, даже при наличии у нее неоспоримых преимуществ. В условиях жесткой конкуренции это порой неосуществимо.
Syntactic Clustering of the Web
Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse
WWW6, 1997
The Approximation of One Matrix by Another of Lower Rank
Eckart, G. Young Psychometrika, 1936
Description and Performance Analysis of Signature File Methods
Faloutsos, S. Christodoulakis
ACM TOIS, 1987
Information Retrieval Using a Singular Value Decomposition Model of Latent Semantic Structure
G.W. Furnas, S. Deerwester, S.T. Dumais, T.K. Landauer, R. A. Harshman, L.A. Streeter and K.E. Lochbaum
ACM SIGIR, 1988
Examples of PAT Applied to the Oxford English Dictionary
Gonnet G.
University of Waterloo, 1987
The Thesaurus Approach to Information Retrieval
T. Joyce and R.M. Needham
American Documentation, 1958
An Efficient Method to Detect Duplicates of Web Documents with the Use of Inverted Index
S. Ilyinsky, M. Kuzmin, A. Melkov, I. Segalovich
WWW2002, 2002
Suffix Arrays: A New Method for On-line String Searches
U. Manber, G. Myers
1st ACM-SIAM Symposium on Discrete Algorithms, 1990
Finding Similar Files in a Large File System
U. Manber
USENIX Conference, 1994
On Relevance, Probabilistic Indexing and Information Retrieval
M.E. Maron and J.L. Kuhns
Journal of the ACM, 1960
Relevance Weighting of Search Terms
S.E. Robertson and K. Sparck Jones
JASIS, 1976
Algorithms in C++
Robert Sedgewick
Addison-Wesley, 1992
A Statistical Interpretation of Term Specificity and Its Application in Retrieval
K. Sparck Jones
Journal of Documentation, 1972
Natural Language Information Retrieval
Tomek Strzalkowski (ed.)
Kluwer Academic Publishers, 1999
Симфония, или Словарь-указатель к Священному Писанию Ветхого и Нового Завета
Составители М.А. Бондарев, М.С. Косьян, С.Ю. Косьян
Изд-во Московской патриархии, 1995
Глоссарий
Асессор (assessor , эксперт) - специалист в предметной области, выносящий заключение о релевантности документа, найденного поисковой системой.
Булевская модель (boolean , булева, булевая, двоичная) - модель поиска, опирающаяся на операции пересечения, объединения и вычитания множеств.
Векторная модель - модель информационного поиска, рассматривающая документы и запросы как векторы в пространстве слов, а релевантность - как расстояние между ними.
Вероятностная модель - модель информационного поиска, рассматривающая релевантность как вероятность соответствия данного документа запросу на основании вероятностей соответствия слов данного документа идеальному ответу.
Внетекстовые критерии (off -page , внестраничные) - критерии ранжирования документов в поисковых системах, учитывающие факторы, не содержащиеся в тексте самого документа и не извлекаемые оттуда никаким образом.
Входные страницы (doorways , hallways ) - страницы, созданные для искусственного повышения ранга в поисковых системах (поискового спама). При попадании на них пользователя перенаправляют на целевую страницу.
Дизамбигуация (tagging , part of speech disambiguation , таггинг) - выбор одного из нескольких омонимов c помощью контекста; в английском языке часто сводится к автоматическому назначению грамматической категории «часть речи».
Дубликаты (duplicates ) - разные документы с идентичным, с точки зрения пользователя, содержанием; приблизительные дубликаты (near duplicates , почти-дубликаты), в отличие от точных дубликатов, содержат незначительные отличия.
Иллюзия свежести - эффект кажущейся свежести, достигаемый поисковыми системами в интернете за счет более регулярного обхода тех документов, которые чаще находятся пользователями.
Инвертированный файл (inverted file , инверсный файл, инвертированный индекс, инвертированный список) - индекс поисковой системы, в котором перечислены слова коллекции документов, а для каждого слова перечислены все места, в которых оно встретилось.
Индекс (index , указатель) - см. Индексирование.
Индекс цитирования (citation index ) - число упоминаний (цитирований) научной статьи, в традиционной библиографической науке рассчитывается за промежуток времени, например, за год.
Индексирование (indexing , индексация) - процесс составления или приписывания указателя (индекса) - служебной структуры данных, необходимой для последующего поиска.
Информационный поиск (Information Retrieval , IR ) - поиск неструктурированной информации, единицей представления которой является документ произвольных форматов. Предметом поиска выступает информационная потребность пользователя, неформально выраженная в поисковом запросе. И критерий поиска, и его результаты не детерминированы. Этими признаками информационный поиск отличается от «поиска данных», который оперирует набором формально заданных предикатов, имеет дело со структурированной информацией и чей результат всегда детерминирован. Теория информационного поиска изучает все составляющие процесса поиска, а именно предварительную обработку текста (индексирование), обработку и исполнение запроса, ранжирование, пользовательский интерфейс и обратную связь.
Клоакинг (cloaking ) - техника поискового спама, состоящая в распознании авторами документов робота (индексирующего агента) поисковой системы и генерации для него специального содержания, принципиально отличающегося от содержания, выдаваемого пользователю.
Контрастность термина - см. Различительная сила.
Латентно-семантическое индексирование - запатентованный алгоритм поиска по смыслу, идентичный факторному анализу. Основан на сингулярном разложении матрицы связи слов с документами.
Лемматизация (lemmatization , нормализация) - приведение формы слова к словарному виду, то есть лемме.
Накрутка поисковых систем - см. Спам поисковых систем.
Непотизм - вид спама поисковых систем, установка авторами документов взаимных ссылок с единственной целью поднять свой ранг в результатах поиска.
Обратная встречаемость в документах (inverted document frequency , IDF , обратная частота в документах, обратная документная частота) - показатель поисковой ценности слова (его различительной силы); «обратная» говорят, потому что при вычислении этого показателя в знаменателе дроби обычно стоит число документов, содержащих данное слово.
Обратная связь - отклик пользователей на результат поиска, их суждения о релевантности найденных документов, зафиксированные поисковой системой и использующиеся, например, для итеративной модификации запроса. Следует отличать от псевдообратной связи - техники модификации запроса, в которой несколько первых найденных документов автоматически считаются релевантными.
Омонимия - см. Полисемия.
Основа - часть слова, общая для набора его словообразовательных и словоизменительных (чаще) форм.
Поиск по смыслу - алгоритм информационного поиска, способный находить документы, не содержащие слов запроса.
Поиск похожих документов (similar document search ) - задача информационного поиска, в которой в качестве запроса выступает сам документ и необходимо найти документы, максимально напоминающие данный.
Поисковая система (search engine , SE , информационно-поисковая система, ИПС, поисковая машина, машина поиска, «поисковик», «искалка») - программа, предназначенная для поиска информации, обычно текстовых документов.
Поисковое предписание (query , запрос) - обычно строчка текста.
Полисемия (polysemy , многозначность) - наличие нескольких значений у одного и того же слова.
Полнота (recall , охват) - доля релевантного материала, заключенного в ответе поисковой системы, по отношению ко всему релевантному материалу в коллекции.
Почти-дубликаты (near -duplicates , приблизительные дубликаты) - см. Дубликаты.
Прюнинг (pruning ) - отсечение заведомо нерелевантных документов при поиске с целью ускорения выполнения запроса.
Прямой поиск - поиск непосредственно по тексту документов, без предварительной обработки (без индексирования).
Псевдообратная связь - см. Обратная связь.
Различительная сила слова (term specificity , term discriminating power , контрастность, различительная сила) - степень ширины или узости слова. Слишком широкие термины в поиске приносят слишком много информации, при этом существенная часть ее бесполезна. Слишком узкие термины помогают найти слишком мало документов, хотя и более точных.
Регулярное выражение (regular expression , pattern , «шаблон», реже «трафарет», «маска») - способ записи поискового предписания, позволяющий определять пожелания к искомому слову, его возможные написания, ошибки и т.д. В широком смысле - язык, позволяющий задавать запросы неограниченной сложности.
Релевантность (relevance , relevancy ) - соответствие документа запросу.
Сигнатура (signature , подпись) - множество хеш-значений слов некоторого блока текста. При поиске по методу сигнатур все сигнатуры всех блоков коллекции просматриваются последовательно в поисках совпадений с хеш-значениями слов запроса.
Словоизменение (inflection ) - образование формы определенного грамматического значения, обычно обязательного в данном грамматическом контексте, принадлежащей к фиксированному набору форм (парадигме), характерному для слов данного типа. В отличие от словообразования никогда не приводит к смене типа и порождает предсказуемое значение. Словоизменение имен называют склонением (declension ) , а глаголов - спряжением (conjugation ) .
Словообразование (derivation ) - образование слова или основы из другого слова или основы.
Смыслоразличительный - см. Различительная сила.
Спам поисковых систем (spam , спамдексинг, накрутка поисковых систем) - попытка воздействовать на результат информационного поиска со стороны авторов документов.
Статическая популярность - см. PageRank .
Стемминг - процесс выделения основы слова.
Стоп-слова (stop -words ) - те союзы, предлоги и другие частотные слова, которые данная поисковая система исключила из процесса индексирования и поиска для повышения своей производительности и/или точности поиска.
Суффиксные деревья, суффиксные массивы (suffix trees , suffix arrays , PAT -arrays ) - индекс, основанный на представлении всех значимых суффиксов текста в структуре данных, известной как «бор» (trie ) . Суффиксом в этом индексе называют любую «подстроку», начинающуюся с некоторой позиции текста (текст рассматривается как одна непрерывная строка) и продолжающуюся до его конца. В реальных приложениях длина суффиксов ограничена, а индексируются только значимые позиции - например, начала слов. Этот индекс позволяет выполнять более сложные запросы, чем индекс, построенный на инвертированных файлах.
Токенизация (tokenization , lexical analysis , графематический анализ, лексический анализ) - выделение в тексте слов, чисел и иных токенов, в том числе, например, нахождение границ предложений.
Точность (precision ) - доля релевантного материала в ответе поисковой системы.
Хеш-значение (hash -value ) - значение хеш-функции (hash -function ) , преобразующей данные произвольной длины (обычно строчку) в число фиксированного порядка.
Частота (слова) в документах (document frequency , встречаемость в документах, документная частота) - число документов в коллекции, содержащих данное слово.
Частота термина (term frequency , TF ) - частота употребления слова в документе.
Шингл (shingle ) - хеш-значение непрерывной последовательности слов текста фиксированной длины.
PageRank - алгоритм расчета статической (глобальной) популярности страницы в интернете, назван в честь одного из авторов - Лоуренса Пейджа. Соответствует вероятности попадания пользователя на страницу в модели случайного блуждания.
TF *IDF - численная мера соответствия слова и документа в векторной модели; тем больше, чем относительно чаще слово встретилось в документе и относительно реже - в коллекции.
Поисковая система или просто “поисковик” – это , осуществляющая поиск интернет страниц в соответствии с запросом пользователя. Самая известная поисковая система в мире - это Google, самая популярная в России – Яндекс, а одной из самых старых поисковых систем является Yahoo. В архитектуре поисковой системы можно выделить поисковую машину – ядро системы, представленное набором программных модулей; базу данных или индекс , хранящую информацию обо всех известных поисковой системе интернет ресурсах; и набор сайтов, являющих собой точки входа пользователей в систему (www.google.com, www.yandex.ru, ru.yahoo.com, и т.д.). Все это соответствует классической трехуровневой архитектуре информационных систем: есть пользовательский интерфейс, бизнес логика, которая в данном случае представлена реализацией алгоритмов поиска и база данных.
Специфика поиска в интернете
На первый взгляд поиск в интернете мало чем отличается от обычного информационного поиска, например, от обработки к базе данных или от задачи поиска файла на . Так считали и разработчики первых поисковых систем в интернете, но со временем они осознали, что заблуждались…
Первое отличие поиска в интернете от обычного состоит в том, что алгоритм поиска по той же базе данных предполагает, что ее структура заранее известна поисковой машине и автору запроса. В интернете, по понятным причинам, это не так. Интернет страницы образуют собой не структуру каталога, а сеть, что также влияет на алгоритмы поиска, а формат данных, размещаемых на интернет ресурсах, никем не контролируется.
Второе отличие, как одно из следствий первого – это то, что запрос представляется не в виде набора значений параметров (критериев поиска), а в виде текста, написанного человеком на естественном для него языке. Таким образом, перед тем, как начать поиск нужно еще понять, чего именно хочет автор запроса. Замечу, понять не другому человеку, а вычислительной машине.
Третье отличие уже менее очевидное, но не менее принципиальное: в каталоге или базе данных все элементы равноправны. В интернете имеет место конкуренция, а, следовательно, и разделение на более “благонадежных поставщиков информации” и источников, близких по статусу к “информационному мусору”. Так классифицируют ресурсы люди, и также к ним относятся поисковые машины.
И в заключении следует добавить, что область поиска – это миллиарды страниц, по несколько килобайт и более каждая. Около десятка миллионов страниц добавляется ежедневно и столько же обновляется. Все это представлено различными цифровыми форматами. К сожалению, даже современные технологии и ресурсы, имеющиеся в распоряжении лидеров рынка поисковых услуг в интернете не позволяют им обрабатывать все это многообразие “на лету” и в полной объеме.
Из чего состоит поисковая машина
В первую очередь важно осознать еще одно и, наверное, самое существенное отличие между работой поисковой машины в интернете и работой любой другой информационной системы, осуществляющей поиск в различного рода каталогах и базах данных. Поисковая интернет машина не ищет информацию среди того, что есть в интернете на момент поступления запроса, а пытается сформировать ответ на основании собственного информационного хранилища - базы данных, называемой индексом, где она хранит досье на все известные ей и периодически его обновляет. Другими словами, поисковая машина работает не с оригиналом, а с проекцией области допустимых значений поиска. Все последние изменения в интернете могут отразиться в результатах поиска только после того, как соответствующие страницы будут проиндексированы - добавлены в индекс поисковой системы. Итак, поисковая система в первом приближении состоит из поисковой машины, базы данных или индекса (index) и точек входа в систему.
Теперь кратко о том, из чего состоит поисковая машина:
- Паук или спайдер (spider). Приложение, которое занимается скачиванием страниц интернет ресурсов. Никуда паук не “заползает” – он лишь запрашивает содержимое страниц точно так же, как это делает обычный интернет браузер, отправляя на сервер HTTP запрос и получая от него ответ. После того, как содержимое страницы скачано, оно отправляется индексатору и краулеру, о которых рассказывается далее.
- Индексатор (indexer). Индексатор производит первоначальный анализ содержимого скачанной страницы, выделяет основные части (название страницы, описание, ссылки, заголовки и т.д.) и раскладывает все это по разделам поисковой базы данных – помещает в индекс поисковой системы. Этот процесс называют индексацией интернет ресурсов , отсюда и название самой подсистемы. На основе результатов первоначального анализа индексатор также может принять решение, что страница вообще “недостойна” находиться в индексе. Причины такого решение могут быть разными: страница не имеет названия, является точной копией другой, уже имеющейся в индексе страницы или содержит ссылки на запрещенные законодательством ресурсы.
- Краулер (crawler). Это “животное” призвано “ползать” по ссылкам, имеющимся на скачанной пауком странице. Краулер анализирует пути, ведущие с текущей страницы на другие разделы сайта, или на страницы внешних интернет ресурсов и определяет дальнейший порядок обхода пауком нитей всемирной паутины. Именно краулер находит новые для поисковой машины страницы и передает их пауку. Работа краулера построена на базе алгоритмов поиска на графах в ширину и глубину.
- Подсистема обработки и выдачи результатов (Search Engine and Results Engine).
Самая важная часть любой поисковой машины. Алгоритмы работы этой подсистемы компании разработчики хранят в строгой секретности, поскольку они являют собой коммерческую тайну. Именно эта часть поисковой машины отвечает за адекватность ответа поисковой системы на запрос пользователя. Здесь можно выделить два основных компонента:
- Подсистема ранжирования. Ранжирование – это страниц интернет сайтов в соответствии с их релевантностью определенному запросу. Релевантность страницы – это, в свою очередь, степень соответствия содержания страницы смыслу запроса, и эту величину поисковая машина определяет самостоятельно, исходя из огромного количества параметров. Ранжирование – эта самая загадочная и спорная часть “искусственного интеллекта” поисковой машины. На ранжирование страницы, помимо ее структуры и содержимого (контента) также влияют: количество и качество ссылок, ведущих на данную страницу с других сайтов; возраст домена самого сайта; характер поведения пользователей, просматривающих страницу и многие другие факторы.
- Подсистема выдачи результатов.
В задачи этой подсистемы входит интерпретация пользовательского запроса, его перевод на язык структурированных запросов к индексу и формирование страниц результатов поиска. Помимо разбора самого текста запроса, поисковая машина может также учитывать:
- Контекст запроса , формируемый исходя из смысла ранее осуществленных пользователем запросов . К примеру, если пользователь часто посещает сайты на автомобильные темы, то на запрос со словом “Волга” или “Ока” он, вероятно, хочет получить информацию об автомобилях этих марок, а не о том, откуда начинают свое течение и куда впадают одноименные русские реки. Это называется персонализированным поиском , когда выдача на один и тот же запрос для разных пользователей существенно отличается.
- Пользовательские предпочтения , о которых она (поисковая машина) может “догадываться”, анализируя выбираемые пользователем ссылки на страницах результатов поиска. Это еще один способ скорректировать контекст запроса: пользователь своими действиями как бы подсказывает машине, что именно он хотел найти. Как правило, поисковые машины в результаты поиска стараются добавлять страницы, релевантные запросу, но относящиеся к довольно разным сферам жизни. Допустим, пользователь интересуется кино и поэтому часто выбирает ссылки на страницы с анонсами киноновинок, даже если эти страницы не вполне релевантны исходному запросу. При формировании ответа на его очередной запрос система может отдавать предпочтение страницам с описанием фильмов, в названии которых встречаются слова из текста запроса.
- Регион , что очень важно при обработке коммерческих запросов, связанных с приобретением товаров и услуг у местных поставщиков. Если вы интересуетесь распродажами и скидками и находитесь в Москве, то вам, скорее всего, совсем не интересно, какие акции на эту тему проводятся в Санкт-Петербурге, если вы не указали этого явно в тексте запроса. В первую очередь в результатах поиска должна появиться информация о распродажах в Москве. Таким образом, современные поисковые машины делят запросы на геозависимые и геонезависимые . Скорее всего, если поисковая система решает, что ваш запрос геозависимый, то она автоматически добавляет к нему признак региона, который пытается определить по информации о вашем интернет провайдере.
- Время . Поисковым машинам иногда приходится анализировать, когда имели место события, описываемые на странице. Ведь информация постоянно устаревает, а пользователю нужны в первую очередь ссылки на самые последние новости, актуальные прогнозы и анонсы событий, которые еще не завершились или должны наступить в будущем. Понять, что актуальность страницы зависит от времени, и сопоставить ее с моментом выполнения запроса также требует от поисковой машины изрядной доли интеллекта.
Общие принципы работы поисковой системы
Нужно понимать, что услуги поиска в интернете – это очень и очень выгодный бизнес. В детали, за счет чего живут такие компании, как Google и Яндекс можно не вдаваться, поскольку основная часть их прибыли – это доходы от контекстной рекламы. А раз поиск в интернете является крайне выгодным делом, то и конкуренция среди таких компаний весьма серьезная. Что определяет конкурентоспособность на рынке интернет поиска? Ответ – качество выдачи поисковой системы. Логично, что чем оно выше, тем больше у системы появляется новых пользователей, и тем ценнее размещаемая на страницах этой самой выдачи контекстная реклама. Разработчики поисковых систем затрачивают большие усилия, направленные на то, чтобы “очистить” результаты своей поисковой выдачи от разного рода информационного мусора, называемого в народе спамом (spam). Более подробно о том, как это делается, будет рассказано в отдельной статье, а здесь я приведу общие принципы поведения поисковой системы, сформулированные в виде выводов по всему вышесказанному.
- Поисковая машина в лице своих пауков и краулеров постоянно сканирует интернет на предмет появления новых и обновления существующих страниц, поскольку неактуальная информация ценится ниже.
- Поисковая машина периодически обновляет ранжирование ресурсов по их релевантности ключевым запросам, поскольку в индексе постоянно появляются новые страницы. Этот процесс называют обновлением (update) поисковой выдачи.
- В силу огромных объемов информации, размещенной во всемирной паутине и ограниченности ресурсов самой поисковой системы, поисковая машина всегда старается загружать только самое (по ее мнению) необходимое. В ее арсенале имеются всевозможные фильтры, которые отсекают многое ненужное уже на этапе индексации или выкидывают спам из индекса по результатам обновления поисковой выдачи.
- Современные поисковые системы в ходе анализа запроса стараются учитывать не только текст самого запроса, но и его окружение: контекст и предпочтения пользователя, о которых было сказано ранее, а также время запроса, регион и многое другое.
- На релевантность конкретной страницы влияют не только внутренние ее параметры (структура, содержание), но и внешние параметры, такие как ссылки на страницу с других сайтов и поведение пользователя при ее просмотре.
Работа поисковых систем постоянно совершенствуется. Идеальная работа поисковой машины (для человека) возможна только в том случае, если все решения, касающиеся индексации и ранжирования будет принимать комиссия, состоящая из большого числа специалистов всех областей и направлений человеческой деятельности. Поскольку это нереально, то такую комиссию заменяют экспертные системы, эвристические алгоритмы поиска и прочие элементы искусственного интеллекта. Вероятно, работа всех этих подсистем также могла бы давать более адекватные результаты, если бы была возможность обрабатывать абсолютно все данные, имеющиеся в открытом доступе в интернете, но и это практически невозможно. Несовершенный искусственный интеллект и ограниченность ресурсов – две основные причины того, что результаты поисковой выдачи не всегда радуют пользователей, но все это лечится временем. На сегодня, по моему мнению, работа наиболее известных и крупных поисковых систем вполне соответствует потребностям и ожиданиям их пользователей.
