Fonctionnement des moteurs de recherche

Nous avons trié les vieilles lettres et sommes tombés sur un article écrit par Ilya Segalovich iseg pour le magazine «World of Internet» en 2002. Il y compare Internet et les moteurs de recherche aux merveilles du monde, réfléchit sur les technologies de recherche et retrace leur histoire. Malgré la charge de travail, Ilya a écrit un article en un temps record et a même fourni un glossaire suffisamment détaillé, ce qui est particulièrement intéressant à lire aujourd'hui. Nous n'avons pas pu trouver une version électronique du magazine avec l'article, alors nous le publions aujourd'hui sur notre blog, dont le premier auteur, soit dit en passant, était Ilya.



Des centaines de moteurs de recherche ont été écrits dans le monde, et si vous comptez les fonctions de recherche mises en œuvre dans une variété de programmes, vous devez en suivre des milliers. Et peu importe la façon dont le processus de recherche est mis en œuvre, quel que soit le modèle mathématique sur lequel il repose, les idées et les programmes qui mettent en œuvre la recherche sont assez simples. Bien que cette simplicité, apparemment, appartient à la catégorie dont ils disent «simple mais fonctionne». D'une manière ou d'une autre, mais ce sont les moteurs de recherche qui sont devenus l'une des deux nouvelles merveilles du monde, donnant à Homo Sapiens un accès illimité et instantané à l'information. Le premier miracle, évidemment, peut être considéré comme Internet en tant que tel, avec ses capacités de communication universelle.

Moteurs de recherche historiques

Il est largement admis que chaque nouvelle génération de programmes est plus parfaite que la précédente. Disons qu'avant tout était imparfait, mais maintenant l' intelligence presque artificielle règne partout. Un autre point de vue extrême est que «tout ce qui est nouveau est bien oublié l'ancien». Je pense qu'en ce qui concerne les moteurs de recherche, la vérité se situe quelque part entre les deux.

Mais qu'est-ce qui a vraiment changé ces dernières années? Pas des algorithmes ou des structures de données, pas des modèles mathématiques. Bien qu'eux aussi. Le paradigme de l'utilisation des systèmes a changé. Autrement dit, une femme au foyer, à la recherche d'un fer à repasser moins cher, et un diplômé d'un pensionnat auxiliaire dans l'espoir de trouver un mécanicien automobile se sont accrochés à l'écran avec la ligne de recherche. En plus de l'apparition d'un facteur impossible dans l'ère pré-Internet - un facteur de la demande totale de moteurs de recherche - quelques changements supplémentaires sont apparus. Premièrement, il est devenu clair que les gens non seulement «pensent avec des mots», mais aussi «recherchent des mots». Dans la réponse du système, ils s'attendent à voir le mot tapé dans la chaîne de requête. Et le second: il est difficile de «recycler un chercheur» à «recycler pour chercher», tout comme il est difficile de se recycler pour parler ou écrire. Les rêves des années 60 et 80 sur le raffinement itératif des requêtes, sur la compréhension du langage naturel, sur la recherche par le sens, sur la génération d'une réponse cohérente à une question peuvent difficilement résister aujourd'hui à l'épreuve cruelle de la réalité.

Algorithme + structure de données = moteur de recherche

Comme tout programme, le moteur de recherche fonctionne avec des structures de données et exécute un algorithme. La variété des algorithmes n'est pas très grande, mais elle l'est. Outre les ordinateurs quantiques, qui nous promettent une percée magique dans la "complexité algorithmique" de la recherche, et dont l'auteur ne sait presque rien, il existe quatre classes d'algorithmes de recherche. Trois algorithmes sur quatre nécessitent une «indexation», traitement préalable des documents, qui crée un fichier auxiliaire, autrement dit «l'index», conçu pour simplifier et accélérer la recherche elle-même. Ce sont des algorithmes de fichiers inversés, des arborescences de suffixes, des signatures . Dans un cas dégénéré, il n'y a pas d'étape d'indexation préliminaire et la recherche est effectuée en visualisant séquentiellement les documents. Une telle recherche est appelée directe .

Recherche directe

Sa version la plus simple est familière à beaucoup, et il n'y a aucun programmeur qui n'écrirait pas un tel code au moins une fois dans sa vie:
Malgré son apparente simplicité, la recherche directe s'est intensifiée au cours des 30 dernières années. Un nombre considérable d'idées ont été avancées qui réduisent parfois le temps de recherche. Ces algorithmes sont décrits en détail dans une variété de littérature, il y a leurs résumés et comparaisons. De bons examens des méthodes de recherche directe peuvent être trouvés dans des manuels tels que Sedgwick ou Cormen . Il convient de garder à l'esprit que les nouveaux algorithmes et leurs options améliorées apparaissent en permanence.

Bien que regarder directement tous les textes soit une tâche assez lente, vous ne devriez pas penser que les algorithmes de recherche directe ne sont pas utilisés sur Internet. Le moteur de recherche norvégien Fast (www.fastsearch.com) a utilisé une puce qui implémente la logique de recherche directe d'expressions régulières simplifiées et a placé 256 de ces puces sur une seule carte. Cela a permis à Fast de traiter un nombre assez important de demandes par unité de temps.

De plus, il existe de nombreux programmes qui combinent la recherche d'index pour trouver un bloc de texte avec une recherche directe supplémentaire à l'intérieur du bloc. Par exemple, l' aperçu est très populaire, y compris sur Runet.

En général, les algorithmes directs ont fondamentalement des caractéristiques distinctives gagnant-gagnant. Par exemple, des possibilités illimitées de recherche approximative et floue. En effet, toute indexation est toujours associée à la simplification et à la normalisation des termes, et, par conséquent, à la perte d'informations. La recherche directe fonctionne directement sur les documents originaux sans aucune distorsion.

Fichier inversé

Cette structure de données simple, malgré son nom étranger mystérieux, est intuitivement familière à toute personne alphabétisée et à tout programmeur de base de données qui n'a même pas traité la recherche en texte intégral. La première catégorie de personnes sait ce que c'est, selon les «concordances» - listes exhaustives classées par ordre alphabétique de mots d'un texte ou appartenant à un auteur (par exemple, «Concordance aux versets par A. S. Pushkin», «Dictionnaire-Concordance du journalisme par F. M. Dostoïevski») ) Ces derniers traitent une forme ou une autre de la liste inversée chaque fois qu'ils construisent ou utilisent «l'index de base de données par champ clé».

Nous illustrerons cette structure à l'aide de la merveilleuse concordance russe - «Symphonie» , publiée par le Patriarcat de Moscou sur le texte de la traduction synodale de la Bible.



Ceci est une liste alphabétique de mots. Pour chaque mot, toutes les «positions» dans lesquelles ce mot apparaît sont répertoriées. L'algorithme de recherche consiste à trouver le bon mot et à charger dans la mémoire une liste de positions déjà élargie.

Pour économiser de l'espace disque et accélérer la recherche, recourez généralement à deux astuces. Tout d'abord, vous pouvez économiser sur les détails de la position elle-même. En effet, plus une telle position est détaillée, par exemple, dans le cas de "Symphony" c'est "livre + chapitre + vers", plus il faudra d'espace pour stocker le fichier inversé.

Dans la version la plus détaillée, dans le fichier inversé, vous pouvez stocker le numéro de mot et le décalage en octets depuis le début du texte, ainsi que la couleur et la taille de la police, et bien plus encore. Le plus souvent, ils indiquent simplement le numéro du document, disons un livre de la Bible, et le nombre d'utilisations de ce mot. C'est une telle structure simplifiée qui est considérée comme fondamentale dans la théorie classique de la recherche d'informations - Information Retrieval (IR).

La deuxième méthode de compression (sans rapport avec la première): pour organiser les positions pour chaque mot dans l'ordre croissant des adresses et pour chaque position pour stocker non pas son adresse complète, mais la différence par rapport à la précédente. Voici à quoi ressemblera cette liste pour notre page en supposant que nous nous souvenons de la position jusqu'au numéro de chapitre:

: [.1],[+11],[0],[+2],[+4],[+2],[+4],..

De plus, une méthode simple de compression est imposée à la méthode de différence de stockage des adresses: pourquoi allouer un nombre fixe "énorme" d'octets à un petit entier, car vous pouvez lui donner presque autant d'octets qu'il le mérite. Ici, il convient de mentionner les codes Golomb ou la fonction intégrée du langage Perl populaire: pack(“w”) .

Dans la littérature, il existe également une artillerie plus lourde d'algorithmes de conditionnement de la plus large gamme: arithmétique, Huffman, LZW, etc. Les progrès dans ce domaine sont continus. En pratique, ils sont rarement utilisés dans les moteurs de recherche: le gain est faible et la puissance du processeur est dépensée de manière inefficace.

En raison de toutes les astuces décrites, la taille du fichier inversé, en règle générale, est de 7 à 30 pour cent de la taille du texte source, en fonction des détails d'adressage.

Inscrite dans le livre rouge

Proposé à plusieurs reprises autres que des algorithmes de recherche inversés et directs et des structures de données. Tout d'abord, ce sont des arbres de suffixes (voir les livres de Manber et Gonnet ), ainsi que des signatures .

Le premier d'entre eux fonctionnait sur Internet, étant un algorithme breveté du système de recherche OpenText . J'ai rencontré des indices de suffixe dans les moteurs de recherche nationaux.

La seconde - la méthode de signature - est une conversion de document en blocs de blocs des valeurs de hachage de ses mots - la "signature" et la visualisation séquentielle des "signatures" pendant la recherche.

Aucune des deux méthodes n'a été largement adoptée et ne méritait donc pas une discussion détaillée dans ce court article.

Modèles mathématiques

Environ 3 moteurs de recherche et modules sur 5 fonctionnent sans aucun modèle mathématique. Plus précisément, leurs développeurs ne se donnent pas pour tâche d'implémenter un modèle abstrait et / ou ignorent son existence. Le principe ici est simple: si seulement le programme trouve quelque chose. Quoi qu'il en soit. Et puis l'utilisateur le découvrira.

Cependant, dès qu'il s'agit d'améliorer la qualité de la recherche, sur une grande quantité d'informations, sur le flux des requêtes des utilisateurs, en plus des coefficients apposés empiriquement, il s'avère utile de fonctionner avec une sorte d'appareil théorique simple. Le modèle de recherche est une certaine simplification de la réalité, sur la base de laquelle une formule est obtenue (qui n'est plus nécessaire à personne), qui permet au programme de prendre une décision: quel document est considéré comme trouvé et comment le classer. Après l'adoption du modèle, les coefficients acquièrent souvent une signification physique et deviennent plus compréhensibles pour le développeur lui-même, et il devient plus intéressant de les sélectionner.

Toute la variété des modèles de recherche d'information traditionnelle (IR) est généralement divisée en trois types: théorie des ensembles (booléen, ensembles flous, booléen étendu), algébrique (vecteur, vecteur généralisé, sémantique latente, réseau neuronal) et probabiliste.

La famille booléenne de modèles, en fait, est la première qui vient à l'esprit d'un programmeur qui implémente la recherche en texte intégral. Il y a un mot - un document est considéré comme trouvé, non - pas trouvé. En fait, le modèle booléen classique est un pont reliant la théorie de la recherche d'informations à la théorie de la recherche et de la manipulation des données.

La critique du modèle booléen, assez juste, consiste en son extrême rigidité et son inadéquation au classement. Par conséquent, en 1957, Joyce et Needham (Joyce et Needham) ont suggéré de prendre en compte les caractéristiques de fréquence des mots afin que "... l'opération de comparaison soit le rapport de la distance entre les vecteurs ...". Le modèle vectoriel a été implémenté avec succès en 1968 par le père fondateur de la science de la recherche d'informations Gerard Salton (Gerard Salton) * dans le moteur de recherche SMART (Salton's Magical Automatic Retriever of Text). Le classement dans ce modèle est basé sur l'observation statistique naturelle que plus la fréquence locale d'un terme dans un document (TF) est élevée et plus «rare» (c'est-à-dire l' occurrence de retour dans les documents ) d'un terme dans une collection (IDF), plus le poids de ce document par rapport au terme est élevé .

---

^{* Gerard Salton (Sahlman) 1927-1995. Il est Selton, il est Zalton et même Zalman, il est Gerard, Gerard, Gerard ou même Gerald, selon le goût du traducteur et les fautes de frappe faites.
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}

La désignation de Tsahal a été introduite par Karen Sparck-Jones (Karen Spark-Jones) en 1972 dans un article sur le terme spécificité . Désormais, la désignation TF * IDF est largement utilisée comme synonyme du modèle vectoriel.

Enfin, en 1977, Robertson et Sparck-Jones ( Robertson et Spark-Jones) ont étayé et mis en œuvre un modèle probabiliste ( proposé en 1960), qui a également jeté les bases d'une famille entière. La pertinence dans ce modèle est considérée comme la probabilité que ce document puisse intéresser l'utilisateur. Cela implique la présence d'un ensemble initial déjà existant de documents pertinents sélectionnés par l'utilisateur ou reçus automatiquement sous une hypothèse simplifiée. La probabilité d'être pertinente pour chaque document subséquent est calculée sur la base du rapport de l'occurrence des termes de l'ensemble pertinent au reste de la partie «non pertinente» de la collection. Bien que les modèles probabilistes aient un certain avantage théorique, car ils classent les documents par ordre décroissant de «probabilité d'être pertinent», dans la pratique, ils n'ont pas reçu beaucoup de distribution.

Je ne vais pas entrer dans les détails et écrire des formules volumineuses pour chaque modèle. Leur résumé, ainsi que la discussion, prend 35 pages sous forme compressée dans le livre «Modern Information Search» . Il est seulement important de noter que dans chacune des familles le modèle le plus simple procède de l'hypothèse d'indépendance des mots et a une condition de filtrage simple: les documents qui ne contiennent pas de mots de requête ne sont jamais trouvés. Les modèles avancés («alternatifs») de chacune des familles ne considèrent pas le mot de requête comme indépendant, mais vous permettent en outre de rechercher des documents qui ne contiennent pas un seul mot de la requête.

Recherchez "par sens"

La capacité à trouver et classer des documents qui ne contiennent pas de mots de la requête est souvent considérée comme un signe d'intelligence artificielle ou une recherche par sens et se rapporte a priori aux avantages du modèle. La question de savoir s'il en est ainsi ou non, nous laisserons en dehors du champ d'application de cet article.

Par exemple, je n'en décrirai qu'un, peut-être le modèle le plus populaire qui fonctionne par sens. Dans la théorie de la recherche d'informations, ce modèle est appelé indexation sémantique latente (en d'autres termes, révélant des significations cachées). Ce modèle algébrique est basé sur la décomposition singulière d'une matrice rectangulaire associant les mots aux documents. L'élément de la matrice est une réponse en fréquence, reflétant le degré de connexion du mot et du document, par exemple, TF * IDF. Au lieu de la matrice d'origine de la millionième dimension, les auteurs de la méthode de Furnas et Deerwester ont suggéré d'utiliser 50 à 150 «significations cachées» correspondant aux premiers composants principaux de sa décomposition singulière .

Une décomposition singulière d'une matrice réelle A de tailles m * n est appelée toute décomposition de la forme A = USV, où U est la matrice orthogonale de tailles m * m, V est la matrice orthogonale de tailles n * n, S est la matrice diagonale de tailles m * n, dont les éléments sont s _ij = 0 si i n'est pas égal à j , et s _ii = s _i > = 0. Les quantités si sont appelées les nombres singuliers de la matrice et sont égales aux valeurs arithmétiques des racines carrées des valeurs propres correspondantes de la matrice AA ^T. Dans la littérature anglaise, la décomposition singulière est communément appelée décomposition SVD .

Il a été prouvé il y a longtemps que si nous laissons les k premiers nombres singuliers en considération (assimilons le reste à zéro), nous obtenons l'approximation la plus proche possible de la matrice initiale de rang k (en un sens, son «interprétation sémantique la plus proche du rang k»). En diminuant le rang, nous filtrons les détails non pertinents; de plus en plus, nous essayons de refléter toutes les nuances de la structure des données réelles.

Les opérations de recherche ou de recherche de documents similaires sont grandement simplifiées, car chaque mot et chaque document est associé à un vecteur relativement court de k significations (lignes et colonnes des matrices correspondantes). Cependant, en raison de la faible signification des «significations», ou pour une autre raison, l'utilisation de LSI dans le front pour la recherche n'est pas encore généralisée. Bien qu'à des fins auxiliaires (filtrage automatique, classification, séparation des collections, abaissement préalable des dimensions pour d'autres modèles), cette méthode semble trouver application.

Évaluation de la qualité

La vérification de la cohérence a montré que le chevauchement des documents pertinents entre deux évaluateurs est de l'ordre de 40% en moyenne ... rappel et précision croisés d'environ 65% ... Cela implique une limite pratique supérieure de 65% pour les performances du système de recherche.
Donna harman
Ce que nous avons appris et non appris de TREC

La traduction

"... un contrôle de stabilité a montré que le chevauchement des documents pertinents entre deux évaluateurs est d'environ 40% en moyenne ... l'exactitude et l'exhaustivité mesurées entre les évaluateurs sont d'environ 65% ... Cela impose une limite pratique supérieure à la qualité de la recherche dans la région de 65% ..."

Quel que soit le modèle, le moteur de recherche a besoin d'un «réglage» - une évaluation de la qualité de la recherche et du réglage des paramètres. L'évaluation de la qualité est une idée fondamentale de la théorie de la recherche. Car c'est grâce à l'évaluation de la qualité que nous pouvons parler de l'applicabilité ou de l'inapplicabilité d'un modèle particulier et même discuter de leurs aspects théoriques.

En particulier, l'une des limites naturelles de la qualité de la recherche est l'observation faite dans l'épigraphe: les opinions de deux «assesseurs» (experts émettant un verdict de pertinence) ne coïncident pas en moyenne très largement entre elles! Cela implique également la limite supérieure naturelle de la qualité de la recherche, car la qualité est mesurée par comparaison avec l’opinion de l’évaluateur.

Habituellement, deux paramètres sont mesurés pour évaluer la qualité d'une recherche:

• précision - la proportion de matériel pertinent dans la réponse d'un moteur de recherche
• exhaustivité (rappel) - la proportion de documents pertinents trouvés dans le nombre total de documents de collecte pertinents

Ces paramètres ont été utilisés et sont utilisés régulièrement pour sélectionner des modèles et leurs paramètres dans le cadre de la conférence d'évaluation de la récupération de texte (TREC) * créée par l'American Institute of Standards (NIST). À partir de 1992, un consortium de 25 groupes, à la fin de l'année 12 de son existence, la conférence a accumulé un matériel important sur lequel les moteurs de recherche sont encore perfectionnés. Pour chaque conférence régulière, de nouveaux documents sont en cours de préparation (ce que l'on appelle la «piste») dans chacun des domaines d'intérêt. La «piste» comprend une collection de documents et de demandes. Je vais donner des exemples:

- Suivi des demandes aléatoires ( ad hoc ) - présent à toutes les conférences
- Recherche multilingue
- Routage et filtrage
- Recherche de haute précision (avec une seule réponse, effectuée à temps)
- Interaction utilisateur
- «Chemin» en langage naturel
- Réponses aux «questions»
- Recherche dans les textes "sales" (juste scannés)
- Recherche vocale
- Recherche dans un très grand boîtier (20 Go, 100 Go, etc.)
- WEB corps (lors des dernières conférences, il est représenté par une sélection pour le domaine .gov)
- Recherche distribuée et fusion des résultats de recherche de différents systèmes

---

^{* Les documents de la conférence sont accessibles au public à trec.nist.gov/pubs.html .}

Pas seulement la recherche

Comme le montrent les «chemins» TREC, un certain nombre de tâches sont étroitement liées à la recherche elle-même, soit partageant une idéologie commune (classification, routage, filtrage, annotation), soit faisant partie intégrante du processus de recherche (regroupement des résultats, expansion et rétrécissement des requêtes, rétroaction, Annotation "dépendante de la requête", interface de recherche et langages de requête). Il n'y a pas un seul moteur de recherche qui n'aurait pas à résoudre en pratique au moins une de ces tâches.

Souvent, la présence de l'une ou l'autre propriété supplémentaire est un argument décisif dans la concurrence des moteurs de recherche. Par exemple, de brèves annotations consistant en des citations informatives d'un document avec lesquelles certains moteurs de recherche accompagnent les résultats de leur travail les aident à garder une longueur d'avance sur la concurrence.

Il est impossible de parler de toutes les tâches et de la façon de les résoudre. Par exemple, considérez l '«extension de requête», qui est généralement effectuée en effectuant la recherche de termes associés. La solution à ce problème est possible sous deux formes - locale (dynamique) et globale (statique). Les techniciens locaux s'appuient sur le texte de la requête et analysent uniquement les documents qui s'y trouvent. Les «extensions» globales peuvent fonctionner avec les thésaurus, à la fois a priori (linguistiques) et construits automatiquement tout au long de la collection de documents. Selon l'opinion généralement acceptée, les modifications globales des requêtes via les thésaurus fonctionnent de manière inefficace, ce qui réduit la précision de la recherche. Une approche globale plus efficace repose sur des classifications statiques construites manuellement, telles que les répertoires WEB. Cette approche est largement utilisée dans les moteurs de recherche Internet dans les opérations de rétrécissement ou d'expansion des requêtes.

Souvent, la mise en œuvre de fonctionnalités supplémentaires est basée sur des principes et des modèles identiques ou très similaires à la recherche elle-même. , , , ( – TF*IDF), . (relevance feedback), () , .

, , «Term Vector Database» , «» ( ).

, . . , (, , ), . , (, ) , . , , :

—
— ( ): ,
— ( - )
— (, ): «», ,
— () (, )
— :
—

, . - (LSI, ), - , .

“Things that work well on TREC often do not produce good results on the web… Some argue that on the web, users should specify more accurately what they want and add more words to their query. We disagree vehemently with this position. If a user issues a query like «Bill Clinton» they should get reasonable results since there is a enormous amount of high quality information available on this topic”
Sergei Brin, Larry Page
The Anatomy of a Large-Scale Hypertextual Web Search Engine

La traduction

«, TREC, … , , , . . « », , ...»

«I was struck when a Google person told me at SIGIR that the most recent Google ranking algorithm completely ignores anything discovered at TREC, because all the good Ad Hoc ranking algorithms developed over the 10 years of TREC get trashed by spam»
Mark Sanderson

La traduction

« , - Google , TREC, , « » ...»

, : ?

, , , - , ( , . .) . (off-page) , ́ , . , , , , – .

C , -. , «» , . , , , « » , , .

, , , , , . ( – ), . .

.

. , 1999-2000 . ( ) , .

( ) , . , . 1998 . , , . 1998 PageRank – , , . , (, , 80- ), .

, PageRank, ( , ) – HITS , - . , (. . ) , .

, , , . , , : , . . , : (, www.teoma.com ), .., . .

, . , Google Fast, . : «» , , 100 , 30% – . .

, , : , .. , , , « ».

. : ; – .

– , , , . . : , , , , . . , .

, , , : , , .

, , . - .

Udi Manber ( ) ( agrep) 1994 , Andrei Broder ( ) 1997- «» ( shingles, «», «»). .



( ). , , , . (, , 9) , , , 25. , . , – , , , , ( ) : ! 25 !

, , .. : « » ! . ( ; , 0%; .)

, , - , . , ( ), -.

. , . .

, , . , 1997 ( Inktomi) 32- (Linux, Solaris, FreeBSD, Win32) . AltaVista, «» 64- Alpha.

(, , c) . . , , , , . Pruning ( . , ) , . pruning, , .

– , , . , .

, (, - ) . , , , , : , .

, , , . , , , . , , , 2-4 , , , , . .

Les références

<sup>Modern Information Retrieval
Baezo-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
http://www7.scu.edu.au/programme/fullpapers/1938/com1938.htm

The Anatomy of a Large-Scale Hypertextual Web Search Engine
S.Brin and L. Page
WWW7, 1998
http://www7.scu.edu.au/programme/fullpapers/1921/com1921.htm

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
http://citeseer.nj.nec.com/deerwester90indexing.html

The approximation of one matrix by another of lower rank
C. Eckart, G. Young
Psychometrika, 1936

Description and performance analysis of signature file methods
C. Faloutsos, S. Christodoulakis
ACM TOIS 1987

FAST PMC — The Pattern Matching Chip
http://www.fast.no/product/fastpmc.html
www.idi.ntnu.no/grupper/KS-grp/microarray/slides/heggebo.pdf ( , web.archive.org – . .)

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…
http://webglimpse.org

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
http://irsg.eu.org/irsg2000online/papers/harman.htm

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
http://citeseer.nj.nec.com/87928.html

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

ME Maron and JL Kuhns
On relevance, probabilistic indexing and information retrieval
Journal of the ACM, 1960

Open Text Corporation
http://www.opentext.com

SE Robertson and Sparck Jones K.
Relevance Weighting of Search Terms
JASIS, 1976

Algorithms in C++, Robert Sedgewick
Addison-Wesley, 1992

A Statistical Interpretation of Term Specificity and Its Application in Retrieval
Karen 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
http://www9.org/w9cdrom/159/159.html

Natural Language Information Retrieval
Tomek Strzalkowski (ed.)
Kluwer Academic Publishers, 1999

: , . , . , .
, 2000
https://www.ozon.ru/context/detail/id/33769775/

- . .. , .., ..
- , 1995</sup>