Разработка поисковика

алгоритм, применяемый в современных поисковых системах для того, чтобы исключить «очень похожие документы».

Происхождение копий документов в Интернете может быть различным. Один и тот же документ на одном и том же сервере может отличаться по техническим причинам: быть представлен в разных кодировках и форматах; может содержать переменные вставки – рекламу или текущую дату.

Широкий класс документов в вебе активно копируется и редактируется – ленты новостных агентств, документация и юридические документы, прейскуранты магазинов, ответы на часто задаваемые вопросы и т.д. Популярные типы изменений: корректура, реорганизация, ревизия, реферирование, раскрытие темы и т.д. Наконец, публикации могут быть скопированы с нарушением авторских прав и изменены злонамеренно с целью затруднить их обнаружение.

Кроме того, индексация поисковыми машинами страниц, генерируемых из баз данных, порождает еще один распространенных класс внешне мало отличающихся документов: анкеты, форумы, страницы товаров в электронных магазинах

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

Для решения этой задачи Udi Manber (Уди Манбер) (автор известной программы приближенного прямого поиска agrep) в 1994 году предложил идею [manber1994], а Andrei Broder (Андрей Бродер) в 1997 [broder] придумал название и довел до ума алгоритм «шинглов» (от слова shingles, «черепички, чешуйки»). Вот его примерное описание.

Рис.2

Для каждого десятисловия текста рассчитывается контрольная сумма (шингл). Десятисловия идут внахлест, с перекрытием, так, чтобы ни одно не пропало. А затем из всего множества контрольных сумм (очевидно, что их столько же, сколько слов в документе минус 9) отбираются только те, которые делятся на, скажем, 25. Поскольку значения контрольных сумм распределены равномерно, критерий выборки никак не привязан к особенностям текста. Ясно, что повтор даже одного десятисловия – весомый признак дублирования, если же их много, скажем, больше половины, то с определенной (несложно оценить вероятность) уверенностью можно утверждать: копия найдена! Ведь один совпавший шингл в выборке соответствует примерно 25 совпавшим десятисловиям в полном тексте!

Источник: http://old.company.yandex.ru/articles/article10.html

Шинглы

Наиболее известным способом обработки почти-дубликатов в веб-поиске, изящно представленным Андреем Бродером в 1997 году, является метод "шинглов". Очевидно, чтобы повысить вероятность того , чтобы в результате небольших изменения текста контрольная сумма не изменилась, можно попытаться выбрать из текста несколько подстрок. Шингл (от английского shingle - чешуйка, черепичка) это и есть подстрока текста, по которой происходит вычислений контрольной суммы.

Выбирать такие подстроки можно по-разному. Во-первых, можно брать разный шаг, например: символ, слово, предложение. Во-вторых, решить, как они должны идти - внахлест (как раз так и получаются именно "шинглы"), или встык. В-третьих, следует понять, какого размера должны быть подстроки (выбранный размер должен свести к минимуму случайные повторы, то есть должен быть достаточно большим, но при этом оставаться достаточно малым, чтобы типичные изменения текста не разрушили все сигнатуры, конкретные цифры я здесь не привожу, по понятным причинам они не должны афишироваться), и делать ли их фиксированного размера. И, в-четвертых, поскольку возможных подстрочек в тексте чересчур много, надо решить - какие запоминать, а какие выбрасывать.

Встык

Если запоминать контрольные суммы для строчек фиксированной длины, идущих встык, то вставка и удаление одного символа (особенно в начале текста) разрушит их все, как их ни выбирай. Это - безусловно, самый неудачный вариант.

Однако, если отменить фиксацию длины и считать подстрочки от одной характерной точки в тексте до другой (например, от буквы "ю" до буквы "ю", или от двухбуквия, сумма численных значений символов (букв) которого кратна 50, до следующего такого же), вставка (или удаление) с большой вероятностью разрушит только тот шингл, где она случилась.

Когда заведомо известно, что документ изменяется, пусть и сильно, но в малом количестве мест, этот тип сигнатур успешно применяют. Например: передача HTML-файлов или синхронизация репозитория исходных текстов программ и т.п.

К сожалению, в этом варианте сигнатур остается слишком много, если, конечно, не выбирать характерные точки, отстоящие друг от друга в среднем далеко. Но тогда строчки становятся слишком большого размера и алгоритм слишком неустойчив к небольшим изменениям в тексте. Для вероятностного сравнения двух документов все равно необходимо как-то сокращать выборку, и об этом позже.

Внахлест

Поначалу кажется, что считать контрольные суммы по всем строчкам внахлест - странная идея. Нам же нужно сократить объем данных для сравнения, а в таком варианте он страшно возрастает? Однако именно так мы гарантируем, что не пропускаем ни одной подстроки текста (заданной длины) и, при условии, что удастся придумать устойчивый способ отбирать шинглы, нам удастся очень точно отождествлять документы, имеющие совпадающие части.

Выборка. Какие шинглы запоминать?

Классический алгоритм Бродера предлагает отбирать либо фиксированное количество минимальных по значению шинглов, либо все шинглы, значение которых делятся на какое-нибудь небольшое число (10-30). В первом случае мы получаем фиксированную по размеру выборку (что иногда удобно) и приличный по размеру набор шинглов даже для относительно коротких документов, но нельзя будет судить о вложенности документов. Во втором случае число шинглов пропорционально размеру документа, то есть оно переменное, зато можно по набору шинглов оценивать такие интересные вещи, как вложение документов друг в друга или процент их пересечения. Наконец, последний самый "модный" алгоритм формирует фиксированную выборку, размер которой определяется заданным числом (например, 85 для веб-документов) разных независимых случайных функций, для каждой из которых запоминается ровно один шингл, минимальный по значению контрольной суммы. Этот подход комбинирует преимущества двух предыдущих.

Короткие документы. Что можно сделать?

Что делать с совсем короткими документами, для которых алгоритм отбора шинглов (например, второй) может вообще не выбрать ни одного подходящего? Или выбрать слишком мало? Я знаю два альтернативных решения: одно из них: закольцевать текст документа, то есть виртуально продолжить его начало после окончания, чтобы добиться получения необходимого количества шинглов даже в таких условиях. Второй подход, применяемый в Яндекс-Почте, состоит в использовании выборки, размер которой имеет логарифмическую зависимость от размера документа.

Супершингл

Если для каждого письма отбирать более одного шингла, мы столкнемся с задачей отождествления документов, имеющих только несколько совпавших шинглов. Как бы мы не сокращали число шинглов, все равно остается нетривиальный объем работы: данных очень много, даже если отбрасывать слишком редкие и слишком частые шинглы; не существует мгновенно работающего запроса по отождествлению документа и т.д.

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

Замена супершингла: лексические сигнатуры

Совсем необязательно искать очень похожие документы по контрольным суммам и хитрым подстрочкам. Вполне успешно (по крайней мере в задачах веб-поиске) работают и лексические (основанные на словах) методы. Все разнообразие этих методов сейчас разбивают на два класса, локальные и глобальные лексические сигнатуры. Если локальные сигнатуры рассматривают документ изолированно от коллекции и пытаются извлечь несколько характерных слов, основываясь только на их статистике в самом документе - TF (характерный пример: взять 5 самых частотных слов в документе длиннее пяти букв и упорядочить их по убыванию частоты), то глобальные либо пытаются при анализе документа учитывать информацию о глобальной статистике слова - IDF, либо, вообще выбирают опорные слова, опираясь исключительно на уже существующий инвертированный индекс (см. метод Яндекса). Для работы глобальных методов необходимо как-то считать глобальную статистику слов, что в интенсивной антиспамовой системе вполне возможно, например в рамках байесовского подхода.

Источник: http://www.spamtest.ru/document.html?context=15932&pubid=32

Способность находить и ранжировать документы, не содержащие слов из запроса, часто считают признаком искусственного интеллекта или поиска по смыслу и относят априори к преимуществам модели. Вопроса, о том, так ли это или нет мы оставим за рамками данной статьи.

Для примера опишу лишь одну, пожалуй, самую популярную модель, работающую по смыслу. В теории информационного поиска данную модель принято называть латентно-семантическим индексированием (иными словами, выявлением скрытых смыслов). Эта алгебраическая модель основана на сингулярном разложении прямоугольной матрицы, ассоциирующей слова с документами. Элементом матрицы является частотная характеристика, отражающая степень связи слова и документа, например, TF*IDF. Вместо исходной миллионно-размерной матрицы авторы метода [furnas], [deerwester] предложили использовать 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-разложением.

Давным-давно доказано [eckart], что если оставить в рассмотрении первые k сингулярных чисел (остальные приравнять нулю), мы получим ближайшую из всех возможных аппроксимацию исходной матрицы ранга k (в некотором смысле ее «ближайшую семантическую интерпретацию ранга k»). Уменьшая ранг, мы отфильтровываем нерелевантные детали; увеличивая, пытаемся отразить все нюансы структуры реальных данных.

Операции поиска или нахождения похожих документов резко упрощаются, так как каждому слову и каждому документу сопоставляется относительно короткий вектор из k смыслов (строки и столбцы соответствующих матриц). Однако по причине малой ли осмысленности «смыслов», или по какой иной , но использование LSI в лоб для поиска так и не получило распространения. Хотя во вспомогательных целях (автоматическая фильтрация, классификация, разделение коллекций, предварительное понижение размерности для других моделей) этот метод, по-видимому, находит применение.

Источник: http://old.company.yandex.ru/articles/article10.html

Немного в стороне от статистических моделей и структур данных стоит класс алгоритмов, традиционно относимых к лингвистическим. Точно границы между статистическим и лингвистическими методами провести трудно. Условно можно считать лингвистическими методы, опирающиеся на словари (морфологические, синтаксические, семантические), созданные человеком. Хотя считается доказанным, что для некоторых языков лингвистические алгоритмы не вносят существенного прироста точности и полноты (например, английский) [strzalkowski], все же основная масса языков требует хотя бы минимального уровня лингвистической обработки. Не вдаваясь в подробности, приведу только список задач, решаемый лингвистическими или окололингвистическими приемами:

• автоматическое определение языка документа
• токенизация (графематический анализ): выделение слов, границ предложений
• исключение неинформативных слов (стоп-слов)
• лемматизация (нормализация, стемминг): приведение словоизменительных форм к «словарной». В том числе и для слов, не входящих в словарь системы
• разделение сложных слов (компаундов) для некоторых языков (например, немецкого)
• амбигуация: полное или частичное снятие нимии
• выделение нных групп

Еще реже в исследованиях и на практике можно встретить алгоритмы вообразовательного, таксического и даже антического анализа. При этом под семантическим анализом чаще подразумевают какой-нибудь статистический алгоритм (LSI, нейронные сети), а если толково-комбинаторные или семантические словари и используются, то в крайне узких предметных областях.

Источник: http://old.company.yandex.ru/articles/article10.html

PageRank performs an objective measurement of the importance of web pages by solving an equation of more than 500 million variables and 2 billion terms. Instead of counting direct links, PageRank interprets a link from Page A to Page B as a vote for Page B by Page A. PageRank then assesses a page's importance by the number of votes it receives.

PageRank also considers the importance of each page that casts a vote, as votes from some pages are considered to have greater value, thus giving the linked page greater value. Important pages receive a higher PageRank and appear at the top of the search results. Google's technology uses the collective intelligence of the web to determine a page's importance. There is no human involvement or manipulation of results, which is why users have come to trust Google as a source of objective information untainted by paid placement.

Общая формула: PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))

Источники:

http://www.google.ru/corporate/tech.html

/ru/articles/344

RFC 2616 - Hypertext Transfer Protocol -- HTTP/1.1

RFC 1945 - Hypertext Transfer Protocol -- HTTP/1.0

RFC 2279 - UTF-8, a transformation format of ISO 10646.

RFC 2396 - Uniform Resource Identifiers (URI):
RFC 1738 - Uniform Resource Locators (URL)
RFC 1345 - Character Mnemonics & Character Sets
RFC 2854 - The 'text/html' Media Type

W.Ed., я заранее глубоко извиняюсь...

Но смысл того, что Вы сейчас делаете мне не понятен.

Вы решили разработать свой собственный поисковик?

Или решили на техническом уровне документации разобраться (и продемонстрировать читателям сего форума) как работаю SE?

P.S. Если мой пост оффтоп - скажите и я его удалю...

SLASH, да, я разрабатываю свой собственный поисковик.

И тут дело не в том, чтобы разобраться или продемонстрировать как работают SE, а в том, чтобы найти и собрать воедино различные медоты поиска и обработки информации; работы различных частей поисковых машин.

А также используемые при этом документы, стандарты и ссылки на сопутствующую литературу.

W.Ed., на мой взгляд для создания собственного успешного поисковика нужно изобрести что-то новое (не исключая изучения уже изобретенного).

В любом другом случае при создании клона поисковик заранее обречён на неудачу и намного проще соорудить МЕТА-поисковик.

Можно устроить здесь что-то типа brainstrom и, возможно, мы все будем присутсвовать при рождении новых Пейджа и Брина

Народ, лучше скажите, где создателю поисковика брать бесплатный трафик (входящий) и железо. :)

А что, ведь реально есть наверное, хостинги крупные, у которых исходящего трафика избыток, и они могут входящим поделиться? :)

SLASH, я не исключаю вариента изобретения чего-то нового.

Но, цитирую: "не исключая изучения уже изобретенного".

В данной теме не рассматривается создание клонов и это не тема для дисскуссий о создании поисковиков. Это тема только для рассмотрения технологий.

МЕТА-поисковик, конечно, проще, но именно он и будет обречен на неудачу.