Translated material
How search engines work
In July last year, Ilya Segalovich , the founder and director of Yandex technologies, the creator of the first version of the search engine and the author of his name, did not become. In memory of this outstanding person and public figure, who helped many, including COLTA . Ru , we will recover his popular science article on information search and mathematical models that are based on it. Ilya Segalovich called the search engines one of the two new wonders of the world. In any case, without them, including without the main brainchild of Segalovich - “Yandex” our life would be completely different.
Hundreds of search engines are written in the world, and if we consider the search functions implemented in a variety of programs, then the account must be kept for thousands. And no matter how the search process is implemented, no matter what mathematical model it is based, ideas and programs implementing the search are quite simple. Although this simplicity applies, apparently, to the category that they say "simply, but it works." One way or another, but it was the search engines that became one of the two new wonders of the world, providing Homo sapiens unlimited and instant access to information. The first miracle, obviously, can be considered the Internet as such with its capabilities of universal communication.
Search systems in the historical perspective
There is a widespread belief that each new generation of programs is more perfect than the previous one. Say, before everything was imperfect, but now almost artificial intelligence reigns everywhere. Another extreme point of view is that "everything new is well -forgotten old." I think that in relation to search engines, truth lies somewhere in the middle.
But what has actually changed in recent years? Not algorithms and non -data structure, not mathematical models. Although they too. The paradigm of use of systems has changed. Simply put, a housewife, looking for an iron cheaper, and a graduate of the auxiliary boarding school in the hope of finding the work of a car mechanic, got to the screen with a search line. In addition to the emergence of a factor, impossible in the pre -Internet era, a couple of changes became obvious to a couple of changes. Firstly, it became clear that people not only “think in words”, but also “look for words”. In the response of the system, they expect to see the word typed in the line line. And the second: “a person seek” is difficult to “re -teach to search”, as well as it is difficult to retrain to speak or write. Dreams of the 60-80s about iterative clarification of requests, about understanding the natural language, about the search for meaning, about the generation of a coherent answer to the question hardly withstand a cruel test of reality.
Algorithm + data structure = search engine
Like any program, the search engine operates with data structures and performs the algorithm. The variety of algorithms is not very large, but it is. Apart from the quantum computers who promise us a magical breakthrough in the “algorithmic complexity” of the search and about which the author is almost known, there are four classes of search algorithms. Three out of four algorithms require “indexing”, preliminary processing of documents in which an auxiliary file is created, the “index” is designed to simplify and accelerate the search itself. These are algorithms of inverted files, suffix trees, signatures. In the degenerated case, the preliminary stage of indexing is absent, and the search takes place using sequential viewing of documents. Such a search is called direct.
Direct search
His simplest version is familiar to many, and there is no programmer who would not write such a code at least once in his life:
Despite the apparent simplicity, the last 30 years a direct search has been developing intensively. A considerable number of ideas were put forward that reducing the time of search at times. These algorithms are described in detail in a variety of literature, there are their reports and comparisons. Good reviews of direct search methods can be found in textbooks, for example, Sedzhvik or Corn. At the same time, it must be taken into account that new algorithms and their improved options appear constantly.
Although direct viewing of all texts is a rather slow activity, one should not think that direct search algorithms are not used on the Internet. The Norwegian search engine Fast used a chip that implements the logic of direct search for simplified regular expressions ( FASTPMC ) , and placed 256 of these chips on one board. This allowed Fast to serve a fairly large number of requests per unit time.
In addition, there are a lot of programs that combine an index search for finding a text block with a further direct search inside the block. For example, very popular, including in Runet, Glimpse .
In general, direct algorithms have fundamentally win -win distinctive features. For example, unlimited possibilities for approximate and fuzzy search. After all, any indexing is always fired with simplification and normalization of terms, and therefore with the loss of information. The direct search works directly according to original documents without any distortion.
Inverted file
This simplest data structure, despite its mysterious foreign name, is intuitively familiar to any competent person and any database programmer who did not even deal with full -text search. The first category of people knows what it is, according to “concordans”-alphabetically streamlined exhaustive lists of words from one text or belonging to one author (for example, “Concordance to the poems of A.S. Pushkin”, “Dictionary of the journalism of F.M. Dostoevsky”). The second are dealing with one or another form of inverted list whenever they build or use the "database index according to the key field."
We illustrate this structure with the help of a wonderful Russian concordance - “symphony” released by the Moscow Patriarchate in the text of the synodal translation of the Bible.
Before us is a list of words streamlined in alphabet. For each word, all the "positions" in which this word met. The search algorithm consists in finding the right word and loading in the memory of an already detailed list of positions.
To save on the disk space and speed up the search, they usually resort to two tricks. Firstly, you can save on the details of the position itself. After all, the more this position is set (for example, in the case of a “symphony” this is a “book+chapter+verse”), the more space will be required to store an inverted file.
In the most inverted version, in an inverted file, you can store the word number and offset in bytes from the beginning of the text, and the color and size of the font, and much more. More often, they simply indicate the number of the document (say, the book of the Bible) and the number of use of this word in it. It is such a simplified structure that is considered the main in the classical theory of information search - Information Retrieval (IR ) .
The second (in no way related to the first) method of compression: to streamline the position for each word by increasing addresses and for each position to store it not a complete address, but the difference from the previous one. This is what such a list for our page will look like in the assumption that we remember the position up to the number of the chapter:
Additionally, a simple way of packaging is imposed on the different way of storing addresses: why divert a fixed “huge” number of bytes, because you can take it almost as much bytes as it deserves. It is appropriate to mention the codes of Golomb or the built -in function of the popular Perl : Pack (“W ”) .
In the literature there is a heavier artillery of packaging algorithms of the widest spectrum: arithmetic, Hafman, LZW , etc. Progress in this area is continuous. In practice, they are rarely used in search engines: the winnings are small, and the processor power is consumed ineffectively.
As a result of all described tricks, the size of the inverted file, as a rule, is from 7 to 30 percent of the size of the source text, depending on the details of the addressing.
Listed in the Red Book
Other algorithms and data structure were repeatedly offered other than inverted and direct search. These are, first of all, suffix trees (manber, gonnet), as well as signatures (Falutzos).
The first of them also functioned on the Internet, being a patented algorithm for the Opentext search engine. I had to meet suffix indices in domestic search engines. The second-the signature method-represents the transformation of the document to the pounding tables of the hash-meanings of its words-the “signature” and the sequential viewing of the “signatures” during the search.
Neither one nor the other method received widespread, and therefore, they did not deserve detailed discussions in this small article.
Mathematical models
About three of the five search engines and modules function without any mathematical models. More precisely, their developers do not set themselves the task of implementing an abstract model and/or do not suspect the existence of it. The principle here is simple: if only to find the program at least something. Abeas like. And then the user himself will figure it out.
However, as soon as it comes to improving the quality of the search, about a large amount of information, about the flow of user requests, except for empirically affixed coefficients, it is useful to operate with some, albeit a simple, theoretical apparatus. The search model is some simplification of reality, on the basis of which the formula is obtained (by itself, no one needs), which allows the program to make a decision: which document is considered to be found and how to rank it. After the adoption of the model, the coefficients often acquire physical meaning and become more understandable to the developer itself, and it becomes more interesting to choose them.
The whole variety of models of traditional information search ( IR ) is customary to divide into three types: theoretical-nominal (Bulevskaya, fuzzy sets, expanded Bulevskaya), algebraic [1] (vector, generalized vector, latent-semantic, neural network) and probabilistic.
Bulevsky family of models is essentially the first to come to the mind to a programmer that implements a full -text search. There is a word - the document is considered to be found, no - not found. Actually, the classic Bulevskaya model is a bridge that connects the theory of information search with the theory of search and manipulation of data.
Criticism of the Bulevsky model, quite fair, consists in its extreme stiffness and unsuitability for ranking. Therefore, back in 1957, Joyce and Nidham proposed taking into account the frequency characteristics of the words so that “... the operation of comparison would be the ratio of the distance between the vectors ...” (Joyce, 1957). The vector model was successfully implemented in 1968 by the Founder of the Science of the Information Search by Gerard Salton [2] in the Smart (Salton 'S Magical Automatic Retriever of Text ) .
The ranking in this model is based on natural statistical observation that the larger the local frequency of the term in the document ( TF ) and more “rarity” (i.e. reverse encounter in the documents) of the term in the collection ( IDF ) , the higher the weight of this document in relation to the term. The IDF designation introduced Karen Spark-Jones in 1972 in an article about distinguishing force ( Term Specificity ) . From this moment, the TF *IDF designation is widely used as a synonym for the vector model.
Finally, in 1977, Robertson and Spark-Jones substantiated and implemented a probabilistic model (proposed back in 1960 (Maron)), which also laid the foundation for the whole family. Relevance in this model is considered as the likelihood that this document may be an interesting user. This implies the existence of an existing initial set of relevant documents selected by the user or received automatically with any simplified assumption. The probability of being relevant for each of the next document is calculated on the basis of the ratio of the occurrence of terms in a relevant set and in the rest of the “irrelevant” part of the collection. Although probabilistic models have some theoretical advantage - after all, they have documents in decreasing order of “the probability of being relevant” - in practice they have not received much widespread.
I am not going to go into details and write out bulky formulas for each model. Their summary, together with the discussion, occupies a compressed 35 pages in the book Modern Information Search (Basa-Qitees). It is only important to notice that in each of the families the simplest model proceeds from the assumption of the mutual dependence of words and has a simple filtration condition: documents that do not contain words are never found. The advanced (“alternative”) models of each of the families do not consider the words of the request to be mutually dependent, and in addition, they allow you to find documents that do not contain a single word from the request.
Search "in meaning"
The ability to find and rank documents that do not contain words from a request is often considered a sign of artificial intelligence or a search for meaning and attribute a priori to the advantages of the model. The question of whether it is or not, we will leave beyond the scope of this article.
For example, I will describe only one, perhaps the most popular model that works in meaning. In the theory of information search, this model is called Latative-semantic indexing (in other words, the identification of hidden meanings). This algebraic model is based on the singular decomposition of a rectangular matrix associating words with documents. An element of the matrix is a frequency characteristic that reflects the degree of connection of the word and document, for example, TF *IDF . Instead of the initial million -sized matrix, the authors of the Furnas and Dirvester method proposed using 50-150 “hidden meanings” [3] , corresponding to the first main components of its singular decomposition.
Singular decomposition of the actual matrix a size m *n is called all its decomposition of the type A = USV , where U is the orthogonal size of the size M *M , v - orthogonal size matrix n *n , s is the diagonal matrix of sizes m *n , the elements of which sij = 0 , if I is not equal to J , and SII = Si > = 0 . SI values are called the singular numbers of the matrix and are equal to the arithmetic values of square roots from the corresponding values of the AAT matrix. In the English literature, the singular decomposition is commonly called SVD -laying.
It has long been proven (Ekart) that if we leave the first K singular numbers (the rest to equate to zero), we will get the nearest of all possible approximation of the original ranking matrix K (in a sense, its “nearest semantic interpretation of the rank K ”). Reducing the rank, we filter the irrelevant details; By increasing, we are trying to reflect all the nuances of the structure of real data.
Searching or finding similar documents are sharply simplified, since each word and each document compare a relatively short vector from K of meanings (lines and columns of the corresponding matrices). However, due to the low meaningfulness of "meanings" or by what other [4] , but the use of LSI in the forehead for the search has not become widespread. Although for auxiliary purposes (automatic filtering, classification, separation of collections, preliminary decrease in the dimension for other models), this method, apparently, finds application.
Quality assessment
“... The stability test showed that the overlapping of relevant documents between any two assessors is approximately 40% on average <...> the accuracy and completeness between the assessors, about 65% <...> This imposes a practical upper boundary on the quality of the search in the region of 65% ...”
("What We have learned, and not learned, from Trec", Donna Harman)
Whatever the model, the search engine needs “tuning” - assessing the quality of the search and setting up parameters. Quality assessment is an idea fundamental for the theory of search. For it is precisely thanks to the assessment of quality that we can talk about the applicability or inconsistency of a particular model and even discuss their theoretical aspects.
In particular, one of the natural restrictions on the quality of the search is the observation made to the epigraph: the opinions of two “assessors” (specialists who take the verdict of relevance) on average do not coincide with each other to a very large extent! This also follows the natural upper limit of the quality of the search, because the quality is measured according to the results of comparison with the opinion of the assessor.
Usually [5] To assess the quality of the search, they measure two parameters:
1) accuracy ( Precision ) - the share of relevant material in the response of the search engine;
2) completeness ( recall ) - the share of the found relevant documents in the total number of relevant documents of the collection.
It is these parameters that were used and are used on a regular basis for choosing models and their parameters within the framework of the Standards ( NIST ) conference on evaluating text search systems ( TREC - Text Retrival Evaldition Conference ) [6] . The consortium of 25 groups that began in 1992, by the 12th year of its existence, the conference has accumulated significant material on which search engines are still honed. К каждой очередной конференции готовится новый материал (т.н. дорожка) по каждому из интересующих направлений. «Дорожка» включает коллекцию документов и запросов. Приведу примеры.
Дорожка произвольных запросов ( ad hoc ) — присутствует на всех конференциях.
Многоязычный поиск.
Маршрутизация и фильтрации.
Высокоточный поиск (с единственным ответом, выполняемый на время).
Взаимодействие с пользователем.
Естественно-языковая дорожка.
Ответы на «вопросы».
Поиск в «грязных» (только что отсканированных) текстах.
Voice Search.
Поиск в очень большом корпусе (20 GB , 100 GB и т.д.).
WEB -корпус (на последних конференциях он представлен выборкой по домену . gov ).
Распределенный поиск и слияние результатов поиска из разных систем.
Не только поиск
Как видно из «дорожек» TREC , к самому поиску тесно примыкает ряд задач, либо разделяющих с ним общую идеологию (классификация, маршрутизация, фильтрация, аннотирование), либо являющихся неотъемлемой частью поискового процесса (кластеризация результатов, расширение и сужение запросов, обратная связь, «запросозависимое» аннотирование, поисковый интерфейс и языки запросов). Нет ни одной поисковой системы, которой бы не приходилось решать на практике хотя бы одну из этих задач.
Зачастую наличие того или иного дополнительного свойства является решающим доводом в конкурентной борьбе поисковых систем. Например, краткие аннотации, состоящие из информативных цитат из документа, которыми некоторые поисковые системы сопровождают результаты соей работы, помогают им оставаться на полшага впереди конкурентов.
Обо всех задачах и способах их решения рассказать невозможно. Для примера рассмотрим «расширение запроса», которое обычно производится через привлечение к поиску ассоциированных терминов. Решение этой задачи возможно в двух видах — локальном (динамическом) и глобальном (статическом). Локальные техники опираются на текст запроса и анализируют только документы, найденные по нему. Глобальные же «расширения» могут оперировать тезаурусами, как априорными (лингвистическими), так и построенными автоматически по всей коллекции документов. По общепринятому мнению, глобальные модификации запросов через тезаурусы работают неэффективно, понижая точность поиска. Более успешный глобальный подход основан на построенных вручную статических классификациях, например, веб-директориях. Этот подход широко используется в интернет-поисковиках в операциях сужения или расширения запроса.
Нередко реализация дополнительных возможностей основана на тех же самых или очень похожих принципах и моделях, что и сам поиск. Сравните, например, нейросетевую поисковую модель, в которой используется идея передачи затухающих колебаний от слов к документам и обратно к словам (амплитуда первого колебания — все тот же TF *IDF ), с техникой локального расширения запроса. Последняя основана на обратной связи ( relevance feedback ) , в которой берутся наиболее смыслоразличительные (контрастные) слова из документов, принадлежащих верхушке списка найденного.
К сожалению, локальные методы расширения запроса, несмотря на эффектные технические идеи типа Term Vector Database (Стата) и очевидную пользу, все еще остаются крайне «дорогим» [7] удовольствием.
Linguistics
Немного в стороне от статистических моделей и структур данных стоит класс алгоритмов, традиционно относимых к лингвистическим. Точно границы между статистическими и лингвистическими методами провести трудно. Условно можно считать лингвистическими методы, опирающиеся на словари (морфологические, синтаксические, семантические), созданные человеком. Хотя считается доказанным, что для некоторых языков лингвистические алгоритмы не вносят существенного прироста точности и полноты — например, английского (Стржалковски), — все же основная масса языков требует хотя бы минимального уровня лингвистической обработки. Не вдаваясь в подробности, приведу только список задач, решаемых лингвистическими или окололингвистическими приемами:
— автоматическое определение языка документа;
— токенизация (графематический анализ): выделение слов, границ предложений;
— исключение неинформативных слов (стоп-слов);
— лемматизация (нормализация, стемминг): приведение словоизменительных форм к «словарной» (в том числе и для слов, не входящих в словарь системы);
— разделение сложных слов (компаундов) для некоторых языков (например, немецкого);
— дизамбигуация: полное или частичное снятие омонимии;
— выделение именных групп.
Еще реже в исследованиях и на практике можно встретить алгоритмы словообразовательного, синтаксического и даже семантического анализа. При этом под семантическим анализом чаще подразумевают какой-нибудь статистический алгоритм ( LSI , нейронные сети), а если толково-комбинаторные или семантические словари и используются, то в крайне узких предметных областях.
Поиск в вебе
«То, что хорошо работает в TREC , часто не срабатывает в вебе <...> некоторые утверждают, что в вебе пользователи обязаны более точно специфицировать то, что им нужно, писать побольше слов в запросах. Мы категорически не согласны с такой точкой зрения. Если люди спрашивают “Билл Клинтон”, они должны получать осмысленные результаты, так как в вебе полным-полно качественной информации на эту тему...»
Сергей Брин, Ларри Пейдж. «The Anatomy of a Large-Scale Hypertextual Web Search Engine»
«...Я был потрясен, когда кто-то из Google сказал мне, что они вообще не используют ничего наработанного в TREC , потому что все алгоритмы, заточенные на дорожке “произвольных запросов”, спам расшибает вдребезги...»
Пора вернуться к теме, с которой началась эта статья: что же изменилось в поисковых системах за последнее время?
Прежде всего, стало очевидно, что поиск в вебе не может быть сколько-нибудь корректно выполнен, будучи основан на анализе (пусть даже сколь угодно глубоком, семантическом и т.п.) одного лишь текста документа. Ведь внетекстовые ( off -page ) факторы играют не меньшую, а порой и бо́льшую роль, чем текст самой страницы. Положение на сайте, посещаемость, авторитетность источника, частота обновления, цитируемость страницы и ее авторов — все эти факторы невозможно сбрасывать со счета.
Cтав основным источником получения справочной информации для человеческого вида, поисковые системы стали основным источником трафика для интернет-сайтов. Как следствие, они немедленно подверглись «атакам» недобросовестных авторов, желающих любой ценой оказаться в первых страницах результатов поиска. Искусственная генерация входных страниц, насыщенных популярными словами, техника клоакинга, «слепого текста» и многие другие приемы, предназначенные для обмана поисковых систем, мгновенно заполонили интернет.
Кроме проблемы корректного ранжирования создателям поисковых систем в интернете пришлось решать задачу обновления и синхронизации колоссальной по размеру коллекции с гетерогенными форматами, способами доставки, языками, кодировками, массой бессодержательных и дублирующихся текстов. Необходимо поддерживать базу в состоянии максимальной свежести (на самом деле достаточно создавать иллюзию свежести — но это тема отдельного разговора), может быть, учитывать индивидуальные и коллективные предпочтения пользователей. Многие из этих задач никогда прежде не рассматривались в традиционной науке информационного поиска.
Для примера рассмотрим пару таких задач и практических способов их решения в поисковых системах для интернета.
Качество ранжирования
Не все внетекстовые критерии полезны в равной мере. Именно ссылочная популярность и производные от нее оказались решающим фактором, поменявшим в 1999—2000 гг. мир поисковых систем и вернувшим им преданность пользователей. Так как именно с ее помощью поисковые системы научились прилично и самостоятельно (без подпорок из вручную отредактированных результатов) ранжировать ответы на короткие частотные запросы, составляющие значительную часть поискового потока.
Простейшая идея глобального (т.е. статического) учета ссылочной популярности состоит в подсчете числа ссылок, указывающих на страницы. Примерно то, что в традиционном библиотековедении называют индексом цитирования. Этот критерий использовался в поисковых системах еще до 1998 года. Однако он легко подвергается накрутке, кроме того, он не учитывает вес самих источников.
Естественным развитием этой идеи можно считать предложенный Брином и Пейджем в 1998 году алгоритм PageRank — итеративный алгоритм, подобный тому, что используется в задаче определения победителя в шахматном турнире по швейцарской системе. В сочетании с поиском по лексике ссылок, указывающих на страницу (старая, весьма продуктивная идея, которая использовалась в гипертекстовых поисковых системах еще в 80-е годы), эта мера позволила резко повысить качество поиска.
Немного раньше, чем PageRank , был предложен локальный (т.е. динамический, основанный на запросе) алгоритм учета популярности — HITS (Кляйнберг), который [8] не используется на практике в основном из-за вычислительной дороговизны. Примерно по той же причине, что и локальные (т.е. динамические) методы, оперирующие словами.
Оба алгоритма, их формулы, условия сходимости подробно описаны, в том числе и в русскоязычной литературе. Отмечу только, что расчет статической популярности не является самоценной задачей, он используется в многочисленных вспомогательных целях: определение порядка обхода документов, ранжирование поиска по тексту ссылок и т.д. Формулы расчета популярности постоянно улучшают, в них вносят учет дополнительных факторов — тематической близости документов (например, популярная поисковая система www .teoma .com ), их структуры и т.п., позволяющих понизить влияние непотизма. Интересной отдельной темой является эффективная реализация соответствующих структур данных (Бхарат).
Качество индекса
Хотя размер базы в интернете на поверхностный взгляд не кажется критическим фактором, это не так. Недаром рост посещаемости таких машин, как Google и Fast , хорошо коррелирует именно с ростом их баз. Основная причины: «редкие» запросы, то есть те, по которым находится менее 100 документов, составляют в сумме около 30% от всей массы поисков — весьма значительную часть. Этот факт делает размер базы одним из самых критичных параметров системы.
Однако рост базы кроме технических проблем с дисками и серверами ограничивается и логическими: необходимостью адекватно реагировать на мусор, повторы и т.п. Не могу удержаться, чтобы не описать остроумный алгоритм, применяемый в современных поисковых системах для того, чтобы исключить «очень похожие документы».
Происхождение копий документов в интернете может быть различным. Один и тот же документ на одном и том же сервере может отличаться по техническим причинам: быть представлен в разных кодировках и форматах, содержать переменные вставки — рекламу или текущую дату.
Широкий класс документов в вебе активно копируется и редактируется — ленты новостных агентств, документация и юридические документы, прейскуранты магазинов, ответы на часто задаваемые вопросы и т.д. Популярные типы изменений: корректура, реорганизация, ревизия, реферирование, раскрытие темы и т.д. Наконец, публикации могут быть скопированы с нарушением авторских прав и изменены злонамеренно с целью затруднить их обнаружение.
Кроме того, индексация поисковыми машинами страниц, генерируемых из баз данных, порождает еще один распространенный класс внешне мало отличающихся документов: анкеты, форумы, страницы товаров в электронных магазинах.
Очевидно, что с полными повторами проблем особых нет, достаточно сохранять в индексе контрольную сумму текста и игнорировать все остальные тексты с такой же контрольной суммой. Однако этот метод не работает для выявления хотя бы чуть-чуть измененных документов.
Для решения этой задачи Уди Манбер (автор известной программы приближенного прямого поиска agrep ) в 1994 году предложил идею, а Андрей Бродер в 1997-м придумал название и довел до ума алгоритм «шинглов» (от слова shingles — «черепички, чешуйки»). Вот его примерное описание.
Для каждого десятисловия текста рассчитывается контрольная сумма (шингл). Десятисловия идут внахлест, с перекрытием, так, чтобы ни одно не пропало. А затем из всего множества контрольных сумм (очевидно, что их столько же, сколько слов в документе минус 9) отбираются только те, которые делятся на, скажем, 25. Поскольку значения контрольных сумм распределены равномерно, критерий выборки никак не привязан к особенностям текста. Ясно, что повтор даже одного десятисловия — весомый признак дублирования, если же их много, скажем, больше половины, то с определенной (несложно оценить вероятность) уверенностью можно утверждать: копия найдена! Ведь один совпавший шингл в выборке соответствует примерно 25 совпавшим десятисловиям в полном тексте!
Очевидно, что так можно определять процент перекрытия текстов, выявлять все его источники и т.п. Этот изящный алгоритм воплотил давнюю мечту доцентов: отныне мучительный вопрос «у кого студент списывал этот курсовик» можно считать решенным! Легко оценить долю плагиата в любой статье [9] .
Чтобы у читателя не создалось впечатление, что информационный поиск — исключительно западная наука, упомяну про альтернативный алгоритм определения почти-дубликатов, придуманный и воплощенный у нас в Яндексе (Ильинский). В нем используется тот факт, что большинство поисковых систем уже обладают индексом в виде инвертированного файла (или инвертированным индексом), и этот факт удобно использовать в процедуре нахождения почти-дубликатов.
Цена одного процента
Архитектурно современные поисковые системы представляют собой сложные многокомпьютерные комплексы. Начиная с некоторого момента по мере роста системы основная нагрузка ложится вовсе не на робота, а на поиск. Ведь в течение секунды приходят десятки и сотни запросов.
Для того чтобы справиться с этой проблемой, индекс разбивают на части и раскладывают по десяткам, сотням и даже тысячам компьютеров. Сами компьютеры начиная с 1997 года (поисковая система Inktomi ) представляют собой обычные 32-битные машины ( Linux , Solaris , FreeBSD , Win 32 ) с соответствующими ограничениями по цене и производительности. Исключением из общего правила осталась лишь AltaVista , которая с самого начала использовала относительно «большие» 64-битные компьютеры Alpha .
Поисковые системы для интернета (и вообще все большие поисковые сиcтемы) могут ускорять свою работу при помощи техник эшелонирования и прюнинга.
Первая техника состоит в разделении индекса на заведомо более релевантную и менее релевантную части. Поиск сначала выполняется в первой части, а затем, если ничего не найдено или найдено мало, поисковая система обращается ко второй части индекса. Прюнинг (от англ. pruning — «отсечение, сокращение») состоит в том, чтобы динамически прекращать обработку запроса после накопления достаточного количества релевантной информации. Бывает еще статический прюнинг, когда на основании некоторых допущений индекс сокращается за счет таких документов, которые заведомо никогда не будут найдены.
Отдельная проблема — организовать бесперебойную работу многокомпьютерных комплексов, бесшовное обновление индекса, устойчивость к сбоям и задержкам с ответами отдельных компонент. Для общения между поисковыми серверами и серверами, собирающими отклики и формирующими страницу выдачи, разрабатываются специальные протоколы.
Заметьте, что один процент производительности (скажем, неудачно написанный оператор в каком-нибудь цикле) для десятитысячнокомпьютерной [10] системы стоит примерно ста компьютеров. Поэтому можно себе представить, как вычищается код, отвечающий за поиск и ранжирование результатов, как оптимизируется использование всех возможных ресурсов: каждого байта памяти, каждого обращения к диску.
Решающее значение приобретает продумывание архитектуры всего комплекса с самого начала, так как любые изменения — например, добавление необычного фактора при ранжировании или сложного источника данных — становятся исключительно болезненной и сложной процедурой. Очевидно, системы, стартующие позже, имеют в этой ситуации преимущество. Но инертность пользователей весьма высока: так, например, требуется два-четыре года, чтобы сформированная многомиллионная аудитория сама, пусть и медленно, перешла на непривычную поисковую систему, даже при наличии у нее неоспоримых преимуществ. В условиях жесткой конкуренции это порой неосуществимо.
[1] В отечественной литературе алгебраические модели часто называют линейными.
[2] Gerard Salton ( Sahlman ) , 1927—1995. Он же Селтон, он же Залтон и даже Залман, он же Жерар, Герард, Жерард или даже Джеральд в зависимости от вкуса переводчика и допущенных опечаток.
http://www.cs.cornell.edu/Info/Department/Annual95/Faculty/Salton.html
http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/s/Salton:Gerald.html
http://www.cs.virginia.edu/~clv2m/salton.txt
[3] Для больших коллекций число «смыслов» увеличивают до 300.
[4] После наших экспериментов с LSI получилось, что «смысл номер 1» в рунете — все англоязычные документы, «смысл номер 3» — все форумы и т.п.
[5] Но не обязательно — есть и «альтернативные» метрики!
[6] Материалы конференции публично доступны по адресу trec .nist .gov /pubs .html .
[7] В смысле вычислительных ресурсов.
[8] Точнее, производные от него, так как сам алгоритм оказался не очень устойчив.
[9] В том числе и в данной; надеюсь, что 0%; можете проверить.
[10] Размер кластера Google в конце 2001-го — начале 2002 года.
Список литературы
Modern Information Retrieval
Baeza-Yates R. and Ribeiro-Neto B.
ACM Press Addison Wesley, 1999
The Connectivity Server: Fast Access to Linkage Information on the Web
K. Bharat, A. Broder, M. Henzinger, P. Kumara and S. Venkatasubramanian
WWW7, 1998
The Anatomy of a Large-Scale Hypertextual Web Search Engine
S. Brin and L. Page
WWW7, 1998
Syntactic Clustering of the Web
Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse
WWW6, 1997
Indexing by Latent Semantic Analysis
S. Deerwester, ST Dumais, GW Furnas, TK Landauer, R. Harshman
JASIS, 1990
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
FAST PMC — The Pattern Matching Chip
http://www.idi.ntnu.no/grupper/KS-grp/microarray/slides/heggebo.pdf
Information Retrieval Using a Singular Value Decomposition Model of Latent Semantic Structure
GW Furnas, S. Deerwester, ST Dumais, TK Landauer, RA Harshman, LA Streeter and KE Lochbaum
ACM SIGIR, 1988
Glimpse, Webglimpse, Unix-Based Search Software…
Examples of PAT Applied to the Oxford English Dictionary
Gonnet G.
University of Waterloo, 1987
What We Have Learned, and Not Learned, from TREC
Donna Harman
The Thesaurus Approach to Information Retrieval
T. Joyce and RM Needham
American Documentation, 1958
Authoritative Sources in a Hyperlinked Environment
Jon M. Kleinberg
JACM, 1998
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
ME Maron and JL Kuhns
Journal of the ACM, 1960
Relevance Weighting of Search Terms
SE 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
The Term Vector Database: Fast Access to Indexing Terms for Web Pages
R. Stata, K. Bharat, F. Maghoul
WWW9, 2000
Natural Language Information Retrieval
Tomek Strzalkowski (ed.)
Kluwer Academic Publishers, 1999
Алгоритмы: построение и анализ
Т. Кормен, Ч. Лейзерсон, Р. Ривест
МЦНМО, 2000
Симфония, или Словарь-указатель к Священному Писанию Ветхого и Нового Завета
Составители М.А. Бондарев, М.С. Косьян, С.Ю. Косьян
Изд-во Московской патриархии, 1995
Glossary
Асессор ( 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 — численная мера соответствия слова и документа в векторной модели; тем больше, чем относительно чаще слово встретилось в документе и относительно реже — в коллекции.
Текст статьи на «Яндексе»