Wie Suchmaschinen funktionieren

Wir haben die alten Briefe aussortiert und sind auf einen Artikel gestoßen, den Ilya Segalovich iseg bereits 2002 für die Zeitschrift „World of Internet“ geschrieben hat. Darin vergleicht er das Internet und Suchmaschinen mit den Wundern der Welt, reflektiert Suchtechnologien und erinnert sich an deren Geschichte. Trotz der Arbeitsbelastung schrieb Ilya in Rekordzeit einen Artikel und lieferte sogar ein ausreichend detailliertes Glossar mit Begriffen, das heute besonders interessant zu lesen ist. Wir konnten keine elektronische Version des Magazins mit dem Artikel finden, deshalb veröffentlichen wir ihn heute in unserem Blog, dessen erster Autor übrigens Ilya war.



Hunderte von Suchmaschinen wurden auf der Welt geschrieben. Wenn Sie die Suchfunktionen zählen, die in einer Vielzahl von Programmen implementiert sind, müssen Sie Tausende im Auge behalten. Unabhängig davon, wie der Suchprozess implementiert ist und auf welchem ​​mathematischen Modell er basiert, sind die Ideen und Programme, die die Suche implementieren, recht einfach. Obwohl diese Einfachheit anscheinend zu der Kategorie gehört, von der sie sagen "einfach, aber funktioniert". Auf die eine oder andere Weise, aber es waren Suchmaschinen, die zu einem von zwei neuen Weltwundern wurden und Homo Sapiens uneingeschränkten und sofortigen Zugang zu Informationen ermöglichten. Das erste Wunder kann natürlich als das Internet als solches mit seinen Fähigkeiten zur universellen Kommunikation betrachtet werden.

Historische Suchmaschinen

Es ist weit verbreitet, dass jede neue Generation von Programmen perfekter ist als die vorherige. Sagen wir, bevor alles unvollkommen war, herrscht jetzt überall fast künstliche Intelligenz . Ein weiterer extremer Gesichtspunkt ist, dass "alles Neue gut vergessen ist, alt". Ich denke, dass in Bezug auf Suchmaschinen die Wahrheit irgendwo dazwischen liegt.

Aber was hat sich in den letzten Jahren wirklich geändert? Keine Algorithmen oder Datenstrukturen, keine mathematischen Modelle. Obwohl sie auch. Das Paradigma der Verwendung von Systemen hat sich geändert. Einfach ausgedrückt, eine Hausfrau, die nach einem günstigeren Bügeleisen suchte, und ein Absolvent eines Hilfsinternats in der Hoffnung, einen Automechaniker zu finden, waren mit der Suchzeile auf dem Bildschirm süchtig. Neben dem Auftreten eines Faktors, der in der Zeit vor dem Internet unmöglich war - ein Faktor für die Gesamtnachfrage nach Suchmaschinen - wurden einige weitere Änderungen sichtbar. Zunächst wurde klar, dass Menschen nicht nur „mit Worten denken“, sondern auch „nach Worten suchen“. In der Antwort des Systems erwarten sie, dass das in die Abfragezeichenfolge eingegebene Wort angezeigt wird. Und zweitens: Es ist schwierig, einen Suchenden neu zu schulen, um zu suchen, genauso wie es schwierig ist, zu sprechen oder zu schreiben. Die Träume der 60er und 80er Jahre über die iterative Verfeinerung von Abfragen, über das Verstehen der natürlichen Sprache, über das Suchen nach Bedeutungen, über das Generieren einer kohärenten Antwort auf eine Frage können den grausamen Test der Realität derzeit kaum bestehen.

Algorithmus + Datenstruktur = Suchmaschine

Wie jedes Programm arbeitet die Suchmaschine mit Datenstrukturen und führt einen Algorithmus aus. Die Vielfalt der Algorithmen ist nicht sehr groß, aber es ist. Abgesehen von Quantencomputern, die uns einen magischen Durchbruch in der "algorithmischen Komplexität" der Suche versprechen und von denen der Autor fast nichts weiß, gibt es vier Klassen von Suchalgorithmen. Drei von vier Algorithmen erfordern eine "Indizierung", eine vorläufige Verarbeitung von Dokumenten, wodurch eine Hilfsdatei erstellt wird, dh der "Index", der die Suche selbst vereinfachen und beschleunigen soll. Dies sind Algorithmen für invertierte Dateien, Suffixbäume und Signaturen . In einem entarteten Fall gibt es keinen vorläufigen Indizierungsschritt, und die Suche wird durch sequentielles Anzeigen von Dokumenten durchgeführt. Eine solche Suche nennt man direkt .

Direkte Suche

Die einfachste Version ist vielen bekannt, und es gibt keinen Programmierer, der solchen Code nicht mindestens einmal in seinem Leben schreiben würde:
Trotz ihrer offensichtlichen Einfachheit hat sich die direkte Suche in den letzten 30 Jahren intensiv entwickelt. Es wurde eine beträchtliche Anzahl von Ideen vorgebracht, die die Suchzeit zeitweise verkürzen. Diese Algorithmen werden in einer Vielzahl von Literaturstellen ausführlich beschrieben, es gibt ihre Zusammenfassungen und Vergleiche. Gute Bewertungen direkter Suchmethoden finden sich in Lehrbüchern wie Sedgwick oder Cormen . Es sollte berücksichtigt werden, dass ständig neue Algorithmen und ihre verbesserten Optionen erscheinen.

Obwohl das direkte Betrachten aller Texte eine eher langsame Aufgabe ist, sollten Sie nicht glauben, dass im Internet keine direkten Suchalgorithmen verwendet werden. Die norwegische Suchmaschine Fast (www.fastsearch.com) verwendete einen Chip , der die direkte Suchlogik vereinfachter regulärer Ausdrücke implementiert, und platzierte 256 dieser Chips auf einer Karte. Dies ermöglichte es Fast, eine ziemlich große Anzahl von Anfragen pro Zeiteinheit zu bedienen.

Darüber hinaus gibt es viele Programme, die die Indexsuche kombinieren, um einen Textblock mit einer weiteren direkten Suche innerhalb des Blocks zu finden. Zum Beispiel ist ein Blick sehr beliebt, auch bei Runet.

Im Allgemeinen weisen direkte Algorithmen grundsätzlich Win-Win-Besonderheiten auf. Zum Beispiel unbegrenzte Möglichkeiten für die ungefähre und unscharfe Suche. In der Tat ist jede Indizierung immer mit der Vereinfachung und Normalisierung von Begriffen und folglich mit dem Verlust von Informationen verbunden. Die direkte Suche funktioniert direkt auf den Originaldokumenten ohne Verzerrung.

Invertierte Datei

Diese einfache Datenstruktur ist trotz ihres mysteriösen Fremdnamens jeder gebildeten Person und jedem Datenbankprogrammierer, der sich noch nicht einmal mit der Volltextsuche befasst hat, intuitiv vertraut. Die erste Kategorie von Menschen weiß, was es ist, nach "Konkordanzen" - alphabetisch geordnete erschöpfende Listen von Wörtern aus einem Text oder von einem Autor (zum Beispiel "Konkordanz zu Versen von A. S. Puschkin", "Wörterbuch-Konkordanz des Journalismus von F. M. Dostoevsky"). ) Letztere behandeln die eine oder andere Form der invertierten Liste, wenn sie den "Datenbankindex nach Schlüsselfeld" erstellen oder verwenden.

Wir werden diese Struktur mit Hilfe der wunderbaren russischen Konkordanz „Symphonie“ veranschaulichen, die vom Moskauer Patriarchat zum Text der synodalen Übersetzung der Bibel herausgegeben wurde.



Dies ist eine alphabetische Liste von Wörtern. Für jedes Wort werden alle „Positionen“ aufgelistet, an denen dieses Wort vorkommt. Der Suchalgorithmus besteht darin, das richtige Wort zu finden und eine bereits erweiterte Liste von Positionen in den Speicher zu laden.

Um Speicherplatz zu sparen und die Suche zu beschleunigen, greifen Sie normalerweise auf zwei Tricks zurück. Erstens können Sie die Details der Position selbst speichern. Je detaillierter eine solche Position festgelegt ist, z. B. bei „Symphony“ (Buch + Kapitel + Vers), desto mehr Speicherplatz wird zum Speichern der invertierten Datei benötigt.

In der detailliertesten Version können Sie in der invertierten Datei die Wortnummer und den Versatz in Bytes vom Anfang des Textes sowie die Farbe und Größe der Schriftart und vieles mehr speichern. Häufiger geben sie einfach nur die Nummer des Dokuments an, beispielsweise ein Buch der Bibel, und die Anzahl der Verwendungen dieses Wortes darin. Es ist eine solche vereinfachte Struktur, die in der klassischen Theorie des Information Retrieval - Information Retrieval (IR) als grundlegend angesehen wird.

Die zweite (nicht mit der ersten verwandte) Komprimierungsmethode: Ordnen Sie die Positionen für jedes Wort in aufsteigender Reihenfolge der Adressen an und speichern Sie für jede Position nicht ihre vollständige Adresse, sondern den Unterschied zur vorherigen. So sieht diese Liste für unsere Seite unter der Annahme aus, dass wir uns an die Position bis zur Kapitelnummer erinnern:

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

Darüber hinaus wird der Differenzmethode zum Speichern von Adressen eine einfache Art des Packens auferlegt: Warum sollte einer kleinen Ganzzahl eine feste "große" Anzahl von Bytes zugewiesen werden, da Sie ihr fast so viele Bytes geben können, wie sie verdient? Hier ist es angebracht, die Golomb-Codes oder die eingebaute Funktion der beliebten Perl-Sprache zu erwähnen: pack(“w”) .

In der Literatur gibt es auch eine schwerere Artillerie von Verpackungsalgorithmen des breitesten Bereichs: Arithmetik, Huffman, LZW usw. Die Fortschritte in diesem Bereich sind kontinuierlich. In der Praxis werden sie in Suchmaschinen selten verwendet: Der Gewinn ist gering und die Prozessorleistung wird ineffizient verbraucht.

Aufgrund aller beschriebenen Tricks beträgt die Größe der invertierten Datei in der Regel 7 bis 30 Prozent der Größe des Quelltextes, abhängig von den Adressierungsdetails.

Im Roten Buch aufgeführt

Wiederholt andere als invertierte und direkte Suchalgorithmen und Datenstrukturen vorgeschlagen. Dies sind zunächst Suffixbäume (siehe Bücher von Manber und Gonnet ) sowie Unterschriften .

Der erste von ihnen funktionierte im Internet und war ein patentierter Algorithmus des Suchsystems OpenText . Ich bin auf Suffix-Indizes in inländischen Suchmaschinen gestoßen.

Die zweite - die Signaturmethode - ist eine Dokumentkonvertierung in Blocktabellen der Hashwerte ihrer Wörter - die "Signatur" und die sequentielle Anzeige der "Signaturen" während der Suche.

Keine der beiden Methoden war weit verbreitet und verdiente daher keine ausführliche Diskussion in diesem kurzen Artikel.

Mathematische Modelle

Etwa 3 von 5 Suchmaschinen und Modulen arbeiten ohne mathematische Modelle. Genauer gesagt, ihre Entwickler stellen sich nicht die Aufgabe, ein abstraktes Modell zu implementieren, und / oder sind sich seiner Existenz nicht bewusst. Das Prinzip hier ist einfach: Wenn nur das Programm etwas findet. Jedenfalls. Und dann wird der Benutzer es herausfinden.

Sobald es jedoch darum geht, die Qualität der Suche zu verbessern, über eine große Menge an Informationen, über den Fluss von Benutzeranfragen, zusätzlich zu empirisch festgelegten Koeffizienten, erweist es sich als nützlich, mit einer Art einfacher theoretischer Vorrichtung zu arbeiten. Das Suchmodell ist eine gewisse Vereinfachung der Realität, auf deren Grundlage eine Formel erhalten wird (die von niemandem mehr benötigt wird), die es dem Programm ermöglicht, eine Entscheidung zu treffen: Welches Dokument sollte als gefunden betrachtet werden und wie es zu bewerten ist. Nach der Übernahme des Modells erhalten die Koeffizienten häufig eine physikalische Bedeutung und werden für den Entwickler selbst verständlicher, und es wird interessanter, sie auszuwählen.

Die gesamte Vielfalt der Modelle des traditionellen Information Retrieval (IR) wird normalerweise in drei Typen unterteilt: satztheoretisch (Boolesche, Fuzzy-Mengen, erweiterte Boolesche Werte), algebraisch (Vektor, generalisierter Vektor, latent-semantisches, neuronales Netzwerk) und probabilistisch.

Die boolesche Modellfamilie ist in der Tat die erste, die einem Programmierer in den Sinn kommt, der die Volltextsuche implementiert. Es gibt ein Wort - ein Dokument gilt als gefunden, nein - nicht gefunden. Tatsächlich ist das klassische Boolesche Modell eine Brücke, die die Theorie des Informationsabrufs mit der Theorie der Suche und Datenmanipulation verbindet.

Die Kritik am ziemlich fairen Booleschen Modell besteht in seiner extremen Starrheit und Ungeeignetheit für das Ranking. Daher schlugen Joyce und Needham (Joyce und Needham) 1957 vor, die Frequenzcharakteristika von Wörtern zu berücksichtigen, damit "... die Vergleichsoperation das Verhältnis des Abstands zwischen den Vektoren ist ...". Das Vektormodell wurde 1968 vom Gründungsvater der Wissenschaft des Informationsabrufs Gerard Salton (Gerard Salton) * in der Suchmaschine SMART (Saltons Magical Automatic Retriever of Text) erfolgreich implementiert. Die Rangfolge in diesem Modell basiert auf einer natürlichen statistischen Beobachtung, dass das Gewicht dieses Dokuments in Bezug auf den Begriff umso höher ist, je größer die lokale Häufigkeit eines Begriffs in einem Dokument (TF) und je „seltener“ (dh das Auftreten von Rückgaben in Dokumenten ) eines Begriffs in einer Sammlung (IDF) ist .

---

^{* Gerard Salton (Sahlman) 1927-1995. Er ist Selton, er ist Zalton und sogar Zalman, er ist Gerard, Gerard, Gerard oder sogar Gerald, je nach Geschmack des Übersetzers und den gemachten Tippfehlern.
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}

Die IDF-Bezeichnung wurde 1972 von Karen Sparck-Jones (Karen Spark-Jones) in einem Artikel über den Begriff Spezifität eingeführt . Von nun an wird die Bezeichnung TF * IDF häufig als Synonym für das Vektormodell verwendet.

Schließlich begründeten und implementierten Robertson und Sparck-Jones ( Robertson und Spark-Jones) 1977 ein probabilistisches Modell (bereits 1960 vorgeschlagen ), das auch den Grundstein für eine ganze Familie legte. Die Relevanz in diesem Modell wird als die Wahrscheinlichkeit angesehen, dass dieses Dokument für den Benutzer von Interesse ist. Dies impliziert das Vorhandensein eines bereits vorhandenen anfänglichen Satzes relevanter Dokumente, die vom Benutzer ausgewählt oder unter einer vereinfachten Annahme automatisch empfangen wurden. Die Wahrscheinlichkeit, für jedes nachfolgende Dokument relevant zu sein, wird basierend auf dem Verhältnis des Auftretens von Begriffen in der relevanten Menge zum Rest des „irrelevanten“ Teils der Sammlung berechnet. Obwohl probabilistische Modelle einen gewissen theoretischen Vorteil haben, weil sie Dokumente in absteigender Reihenfolge der „Wahrscheinlichkeit, relevant zu sein“ anordnen, haben sie in der Praxis nicht viel Verbreitung erhalten.

Ich werde nicht auf Details eingehen und sperrige Formeln für jedes Modell schreiben. Ihre Zusammenfassung umfasst zusammen mit der Diskussion 35 Seiten in komprimierter Form im Buch „Modern Information Search“ . Es ist nur wichtig zu beachten, dass in jeder der Familien das einfachste Modell von der Annahme der Wortunabhängigkeit ausgeht und eine einfache Filterbedingung aufweist: Dokumente, die keine Abfragewörter enthalten, werden nie gefunden. Erweiterte ("alternative") Modelle jeder Familie betrachten das Abfragewort nicht als unabhängig, sondern ermöglichen es Ihnen außerdem, Dokumente zu finden, die kein einziges Wort aus der Abfrage enthalten.

Suche "nach Sinn"

Die Fähigkeit, Dokumente zu finden und zu bewerten, die keine Wörter aus der Abfrage enthalten, wird häufig als Zeichen künstlicher Intelligenz oder als Suche nach Bedeutung angesehen, und a priori beziehen sie sich auf die Vorteile des Modells. Die Frage, ob dies so ist oder nicht, werden wir außerhalb des Geltungsbereichs dieses Artikels belassen.

Zum Beispiel werde ich nur ein, vielleicht das beliebteste Modell beschreiben, das nach Bedeutung funktioniert. In der Theorie des Informationsabrufs wird dieses Modell als latent-semantische Indizierung bezeichnet (mit anderen Worten, um verborgene Bedeutungen aufzudecken). Dieses algebraische Modell basiert auf der singulären Zerlegung einer rechteckigen Matrix, die Wörter mit Dokumenten verknüpft. Das Element der Matrix ist ein Frequenzgang, der den Grad der Verbindung des Wortes und des Dokuments widerspiegelt, beispielsweise TF * IDF. Anstelle der ursprünglichen millionstel-dimensionalen Matrix schlugen die Autoren der Furnas- und Deerwester-Methode vor, 50-150 „versteckte Bedeutungen“ zu verwenden, die den ersten Hauptkomponenten ihrer singulären Zerlegung entsprechen .

Eine singuläre Zerlegung einer reellen Matrix A der Größen m * n heißt jede Zerlegung der Form A = USV, wobei U die orthogonale Matrix der Größen m * m ist, V die orthogonale Matrix der Größen n * n ist, S die diagonale Matrix der Größen m * n ist, deren Elemente s _{ij sind} = 0, wenn i nicht gleich j ist und s _ii = s _i > = 0. Die Größen si heißen Singularzahlen der Matrix und sind gleich den arithmetischen Werten der Quadratwurzeln der entsprechenden Eigenwerte der Matrix AA ^T. In der englischen Literatur wird die singuläre Zerlegung üblicherweise als SVD-Zerlegung bezeichnet .

Es wurde vor langer Zeit bewiesen , dass wir, wenn wir die ersten k Singularzahlen in Betracht ziehen (den Rest mit Null gleichsetzen), die bestmögliche Annäherung an die anfängliche Matrix von Rang k erhalten (in gewissem Sinne ihre „engste semantische Interpretation von Rang k“). Indem wir den Rang verringern, filtern wir irrelevante Details heraus. Zunehmend versuchen wir, alle Nuancen der Struktur realer Daten widerzuspiegeln.

Das Suchen oder Finden ähnlicher Dokumente wird erheblich vereinfacht, da jedem Wort und jedem Dokument ein relativ kurzer Vektor von k Bedeutungen (Zeilen und Spalten der entsprechenden Matrizen) zugeordnet ist. Aufgrund der geringen Aussagekraft der „Bedeutungen“ oder aus einem anderen Grund ist die Verwendung von LSI in der Stirn für die Suche jedoch noch nicht weit verbreitet. Obwohl diese Methode für Hilfszwecke (automatische Filterung, Klassifizierung, Trennung von Sammlungen, vorläufige Absenkung der Abmessungen für andere Modelle) Anwendung zu finden scheint.

Qualitätsbewertung

Die Konsistenzprüfung hat gezeigt, dass die Überlappung relevanter Dokumente zwischen zwei beliebigen Assesoren im Durchschnitt in der Größenordnung von 40% liegt ... Cross-Assesor-Rückruf und Genauigkeit von etwa 65% ... Dies impliziert eine praktische Obergrenze für die Leistung des Abrufsystems von 65% ...
Donna Harman
Was wir von TREC gelernt und nicht gelernt haben

Übersetzung

"... eine Stabilitätsprüfung ergab, dass die Überlappung relevanter Dokumente zwischen zwei beliebigen Bewertern durchschnittlich etwa 40% beträgt ... die zwischen den Bewertern gemessene Genauigkeit und Vollständigkeit beträgt etwa 65% ... Dies legt eine praktische Obergrenze für die Qualität der Suche in der Region von 65% fest ..."

Unabhängig vom Modell muss die Suchmaschine „optimiert“ werden - eine Bewertung der Qualität der Suche und der Optimierung der Parameter. Die Qualitätsbewertung ist eine grundlegende Idee für die Suchtheorie. Dank der Qualitätsbewertung können wir über die Anwendbarkeit oder Nichtanwendbarkeit eines bestimmten Modells sprechen und sogar deren theoretische Aspekte diskutieren.

Eine der natürlichen Einschränkungen der Suchqualität ist insbesondere die im Epigraph gemachte Beobachtung: Die Meinungen von zwei „Gutachtern“ (Experten, die ein Urteil über die Relevanz abgeben) stimmen im Durchschnitt nicht sehr stark überein! Dies impliziert auch die natürliche Obergrenze der Suchqualität, da die Qualität durch Vergleich mit der Meinung des Bewerters gemessen wird.

Normalerweise werden zwei Parameter gemessen, um die Qualität einer Suche zu beurteilen:

• Präzision - der Anteil des relevanten Materials in einer Suchmaschinenantwort
• Vollständigkeit (Rückruf) - Der Anteil der relevanten Dokumente an der Gesamtzahl der relevanten Sammlungsdokumente

Diese Parameter wurden verwendet und werden regelmäßig verwendet, um Modelle und ihre Parameter im Rahmen der vom American Institute of Standards (NIST) erstellten Text Retrieval Evaluation Conference (TREC) * auszuwählen. Ab 1992, einem Konsortium aus 25 Gruppen, hat die Konferenz bis zum 12. Jahr ihres Bestehens bedeutendes Material gesammelt, an dem Suchmaschinen noch immer weiterentwickelt werden. Für jede reguläre Konferenz wird in jedem der interessierenden Bereiche neues Material vorbereitet (der sogenannte „Track“). Der „Track“ enthält eine Sammlung von Dokumenten und Anfragen. Ich werde Beispiele geben:

- Verfolgen Sie zufällige Anfragen ( ad hoc ) - bei allen Konferenzen vorhanden
- Mehrsprachige Suche
- Routing und Filterung
- Hochpräzise Suche (mit einer einzigen Antwort, pünktlich durchgeführt)
- Benutzerinteraktion
- Pfad in natürlicher Sprache
- Antworten auf Fragen"
- Suchen Sie in "schmutzigen" (gerade gescannten) Texten
- Sprachsuche
- Suchen Sie in einem sehr großen Fall (20 GB, 100 GB usw.)
- WEB Corps (auf den letzten Konferenzen wird es durch eine Auswahl für die .gov-Domain vertreten)
- Verteilte Suche und Zusammenführen von Suchergebnissen aus verschiedenen Systemen

---

^{* Konferenzmaterialien sind unter trec.nist.gov/pubs.html öffentlich verfügbar.}

Nicht nur suchen

Wie aus den TREC- „Pfaden“ ersichtlich ist, sind eine Reihe von Aufgaben eng mit der Suche selbst verbunden, entweder mit einer gemeinsamen Ideologie (Klassifizierung, Routing, Filterung, Annotation) oder als integraler Bestandteil des Suchprozesses (Clustering von Ergebnissen, Erweitern und Eingrenzen von Abfragen, Feedback, "Abfrageabhängige" Annotation, Suchoberfläche und Abfragesprachen). Es gibt keine einzige Suchmaschine, die in der Praxis mindestens eine dieser Aufgaben nicht lösen müsste.

Oft ist das Vorhandensein der einen oder anderen zusätzlichen Eigenschaft ein entscheidendes Argument im Wettbewerb der Suchmaschinen. Beispielsweise helfen kurze Anmerkungen, die aus informativen Zitaten eines Dokuments bestehen, mit denen einige Suchmaschinen die Ergebnisse ihrer Arbeit begleiten, ihnen, der Konkurrenz einen halben Schritt voraus zu sein.

Es ist unmöglich, über alle Aufgaben zu erzählen und wie man sie löst. Betrachten Sie beispielsweise die "Abfrageerweiterung", die normalerweise durch die Suche nach zugehörigen Begriffen durchgeführt wird. Die Lösung für dieses Problem ist in zwei Formen möglich - lokal (dynamisch) und global (statisch). Lokale Techniker verlassen sich auf den Abfragetext und analysieren nur die darauf gefundenen Dokumente. Globale „Erweiterungen“ können mit Thesauri betrieben werden, sowohl a priori (sprachlich) als auch automatisch in der gesamten Dokumentensammlung erstellt. Nach allgemeiner Meinung funktionieren globale Abfragemodifikationen durch Thesauri ineffizient und verringern die Genauigkeit der Suche. Ein erfolgreicher globaler Ansatz basiert auf manuell erstellten statischen Klassifizierungen wie WEB-Verzeichnissen. Dieser Ansatz wird in Internet-Suchmaschinen häufig bei Eingrenzungs- oder Abfrageerweiterungen verwendet.

Häufig basiert die Implementierung zusätzlicher Funktionen auf denselben oder sehr ähnlichen Prinzipien und Modellen wie die Suche selbst. , , , ( – TF*IDF), . (relevance feedback), () , .

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

Sprachwissenschaft

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

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

, . - (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

Übersetzung

«, 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

Übersetzung

« , - 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 , , , , . .

Referenzliste

<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>