Cara kerja mesin pencari

Kami memilah-milah surat-surat lama dan menemukan sebuah artikel yang ditulis oleh Ilya Segalovich iseg untuk majalah "World of Internet" pada tahun 2002. Di dalamnya, ia membandingkan Internet dan mesin pencari dengan keajaiban dunia, merefleksikan teknologi pencarian dan mengingat sejarah mereka. Terlepas dari beban kerja, Ilya menulis sebuah artikel dalam waktu singkat dan bahkan memberikan glosarium istilah yang cukup rinci, yang sangat menarik untuk dibaca hari ini. Kami tidak dapat menemukan versi elektronik majalah dengan artikel tersebut, jadi hari ini kami menerbitkannya di blog kami, penulis pertama yang, omong-omong, adalah Ilya.



Ratusan mesin pencari telah ditulis di dunia, dan jika Anda menghitung fungsi pencarian diimplementasikan dalam berbagai program, maka Anda perlu melacak ribuan. Dan tidak peduli bagaimana proses pencarian diimplementasikan, tidak peduli apa model matematika itu didasarkan pada, ide-ide dan program-program yang mengimplementasikan pencarian cukup sederhana. Meskipun kesederhanaan ini, tampaknya, termasuk dalam kategori yang mereka katakan "sederhana tetapi berhasil." Bagaimanapun juga, tetapi mesin pencarilah yang menjadi salah satu dari dua keajaiban baru dunia, memberi Homo Sapiens akses tak terbatas dan instan ke informasi. Mukjizat pertama, jelas, dapat dianggap sebagai Internet, dengan kemampuan komunikasi universal.

Mesin Pencari Sejarah

Ada kepercayaan yang tersebar luas bahwa setiap generasi program baru lebih sempurna dari yang sebelumnya. Katakanlah, sebelum semuanya tidak sempurna, tetapi sekarang kecerdasan buatan hampir berkuasa di mana-mana. Pandangan ekstrem lain adalah bahwa "segala sesuatu yang baru sudah lama terlupakan." Saya pikir sehubungan dengan mesin pencari, kebenaran ada di antara keduanya.

Tetapi apa yang benar-benar berubah dalam beberapa tahun terakhir? Bukan algoritma atau struktur data, bukan model matematika. Meskipun mereka juga. Paradigma menggunakan sistem telah berubah. Sederhananya, seorang ibu rumah tangga, mencari besi yang lebih murah, dan lulusan sekolah asrama tambahan dengan harapan menemukan seorang mekanik mobil terpikat di layar dengan garis pencarian. Selain munculnya faktor yang tidak mungkin di era pra-Internet - faktor dari total permintaan mesin pencari - beberapa perubahan lagi menjadi jelas. Pertama, menjadi jelas bahwa orang tidak hanya "berpikir dengan kata-kata", tetapi juga "mencari kata-kata." Dalam respons sistem, mereka berharap melihat kata yang diketik dalam string kueri. Dan yang kedua: sulit untuk "melatih kembali seorang pencari" untuk "melatih kembali untuk mencari," seperti halnya sulit untuk melatih kembali untuk berbicara atau menulis. Mimpi-mimpi tahun 60-an dan 80-an tentang perbaikan berulang pertanyaan, tentang memahami bahasa alami, tentang mencari dengan makna, tentang menghasilkan jawaban yang koheren untuk pertanyaan hampir tidak tahan dengan ujian kejam kenyataan sekarang.

Algoritma + Struktur Data = Mesin Pencari

Seperti program apa pun, mesin pencari beroperasi dengan struktur data dan mengeksekusi algoritma. Variasi algoritme tidak terlalu besar, tetapi begitu. Terlepas dari komputer kuantum, yang menjanjikan kita terobosan ajaib dalam "kompleksitas algoritme" pencarian, dan yang hampir tidak diketahui penulisnya, ada empat kelas algoritma pencarian. Tiga dari empat algoritma memerlukan "pengindeksan", pra-pemrosesan dokumen, yang membuat file tambahan, dengan kata lain, "indeks", yang dirancang untuk menyederhanakan dan mempercepat pencarian itu sendiri. Ini adalah algoritma file terbalik, pohon sufiks, tanda tangan . Dalam kasus degenerasi, tidak ada langkah pengindeksan awal, dan pencarian dilakukan dengan melihat dokumen secara berurutan. Pencarian semacam itu disebut langsung .

Pencarian langsung

Versi yang paling sederhana sudah tidak asing lagi bagi banyak orang, dan tidak ada programmer yang tidak akan menulis kode seperti itu setidaknya satu kali dalam hidupnya:
Meskipun terlihat sederhana, pencarian langsung telah berkembang secara intensif selama 30 tahun terakhir. Sejumlah besar gagasan telah diajukan yang mengurangi waktu pencarian pada waktu-waktu tertentu. Algoritma ini dijelaskan secara rinci dalam berbagai literatur, ada ringkasan dan perbandingannya. Ulasan bagus tentang metode pencarian langsung dapat ditemukan di buku pelajaran seperti Sedgwick atau Cormen . Harus diingat bahwa algoritma baru dan opsi yang ditingkatkan muncul terus-menerus.

Meskipun melihat semua teks secara langsung adalah tugas yang agak lambat, Anda seharusnya tidak berpikir bahwa algoritma pencarian langsung tidak digunakan di Internet. Mesin pencari Norwegia Fast (www.fastsearch.com) menggunakan sebuah chip yang mengimplementasikan logika pencarian langsung dari ekspresi reguler yang disederhanakan, dan menempatkan 256 chip ini di satu papan. Ini memungkinkan Fast untuk melayani sejumlah besar permintaan per unit waktu.

Selain itu, ada banyak program yang menggabungkan pencarian indeks untuk menemukan blok teks dengan pencarian langsung lebih lanjut di dalam blok. Sebagai contoh, glimpse sangat populer, termasuk di Runet.

Secara umum, algoritma langsung memiliki fitur khas win-win yang unik. Misalnya, kemungkinan tak terbatas untuk perkiraan dan pencarian fuzzy. Memang, setiap pengindeksan selalu dikaitkan dengan penyederhanaan dan normalisasi istilah, dan, akibatnya, dengan hilangnya informasi. Pencarian langsung bekerja langsung pada dokumen asli tanpa distorsi.

File terbalik

Struktur data yang sederhana ini, meskipun memiliki nama asing yang misterius, secara intuitif akrab bagi setiap orang yang melek huruf dan pemrogram basis data apa pun yang bahkan belum berurusan dengan pencarian teks lengkap. Kategori pertama orang tahu apa itu, menurut "konkordansi" - secara abjad memesan daftar kata lengkap dari satu teks atau milik satu penulis (misalnya, "Konkordansi ke ayat oleh A. S. Pushkin", "Kamus-Konkordansi Jurnalisme oleh F. M. Dostoevsky" ) Kesepakatan yang terakhir dengan satu bentuk atau yang lain dari daftar terbalik kapan pun mereka membangun atau menggunakan "indeks basis data menurut bidang kunci".

Kami akan mengilustrasikan struktur ini dengan bantuan konkordansi Rusia yang luar biasa - “Simfoni” , yang dikeluarkan oleh Patriarkat Moskwa tentang teks terjemahan Alkitab secara sinode.



Ini adalah daftar kata berdasarkan abjad. Untuk setiap kata, semua "posisi" di mana kata ini muncul tercantum. Algoritme pencarian terdiri dalam menemukan kata yang tepat dan memuat ke dalam daftar posisi yang sudah diperluas.

Untuk menghemat ruang disk dan mempercepat pencarian, biasanya gunakan dua trik. Pertama, Anda dapat menghemat detail posisi itu sendiri. Memang, semakin rinci posisi seperti itu diatur, misalnya, dalam kasus "Simfoni" itu adalah "buku + bab + ayat", semakin banyak ruang yang diperlukan untuk menyimpan file yang terbalik.

Dalam versi yang paling terperinci, dalam file terbalik Anda dapat menyimpan nomor kata, dan offset dalam byte dari awal teks, dan warna dan ukuran font, dan banyak lagi. Lebih sering, mereka hanya menunjukkan jumlah dokumen, katakanlah, buku Alkitab, dan jumlah penggunaan kata ini di dalamnya. Ini adalah struktur yang disederhanakan yang dianggap mendasar dalam teori klasik pengambilan informasi - Information Retrieval (IR).

Metode kompresi kedua (tidak terkait dengan yang pertama): untuk mengatur posisi untuk setiap kata dalam urutan alamat yang naik dan untuk setiap posisi untuk menyimpan bukan alamat lengkapnya, tetapi perbedaan dari yang sebelumnya. Berikut adalah tampilan daftar ini untuk halaman kami dengan asumsi bahwa kami mengingat posisi hingga nomor bab:

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

Selain itu, beberapa cara pengemasan sederhana diberlakukan pada metode perbedaan menyimpan alamat: mengapa mengalokasikan jumlah byte "besar" yang tetap ke integer kecil, karena Anda dapat memberikannya byte sebanyak yang layak. Di sini tepat untuk menyebutkan kode Golomb atau fungsi built-in dari bahasa Perl yang populer: pack(“w”) .

Dalam literatur, ada juga artileri algoritma pengemasan dengan jangkauan terluas: aritmatika, Huffman, LZW, dll. Kemajuan di bidang ini kontinu. Dalam praktiknya, mereka jarang digunakan di mesin pencari: perolehannya kecil, dan daya prosesor dihabiskan secara tidak efisien.

Sebagai hasil dari semua trik yang dijelaskan, ukuran file terbalik, sebagai aturan, adalah 7 hingga 30 persen dari ukuran teks sumber, tergantung pada detail pengalamatan.

Tercantum dalam Buku Merah

Diusulkan berulang kali selain algoritma penelusuran dan struktur data terbalik dan langsung. Pertama-tama, ini adalah pohon sufiks (lihat buku karya Manber dan Gonnet ), serta tanda tangan .

Yang pertama dari mereka berfungsi di Internet, menjadi algoritma yang dipatenkan dari sistem pencarian OpenText . Saya telah menemukan indeks sufiks di mesin pencari domestik.

Yang kedua - metode tanda tangan - adalah konversi dokumen untuk memblokir tabel nilai hash dari kata-katanya - "tanda tangan" dan tampilan berurutan dari "tanda tangan" selama pencarian.

Tidak ada metode yang diadopsi secara luas, dan oleh karena itu tidak pantas diskusi rinci dalam artikel singkat ini.

Model matematika

Sekitar 3 dari 5 mesin pencari dan modul beroperasi tanpa model matematika. Lebih tepatnya, pengembang mereka tidak mengatur sendiri tugas menerapkan model abstrak dan / atau tidak menyadari keberadaannya. Prinsipnya di sini sederhana: jika saja program menemukan sesuatu. Bagaimanapun. Dan kemudian pengguna akan mencari tahu.

Namun, segera setelah itu untuk meningkatkan kualitas pencarian, tentang sejumlah besar informasi, tentang aliran permintaan pengguna, di samping koefisien yang secara empiris ditempelkan, ternyata bermanfaat untuk beroperasi dengan beberapa jenis peralatan teoretis sederhana. Model pencarian adalah penyederhanaan realitas tertentu, berdasarkan formula yang diperoleh (yang tidak lagi dibutuhkan oleh siapa pun), yang memungkinkan program untuk membuat keputusan: dokumen mana yang dianggap ditemukan dan bagaimana cara memeringkatnya. Setelah adopsi model, koefisien sering memperoleh makna fisik dan menjadi lebih dimengerti oleh pengembang sendiri, dan menjadi lebih menarik untuk memilihnya.

Seluruh variasi model pengambilan informasi tradisional (IR) biasanya dibagi menjadi tiga jenis: set-theoretik (Boolean, fuzzy set, extended Boolean), aljabar (vektor, vektor umum, laten-semantik, jaringan saraf) dan probabilistik.

Keluarga model Boolean, pada kenyataannya, adalah yang pertama kali muncul di benak seorang programmer yang mengimplementasikan pencarian teks lengkap. Ada kata - dokumen dianggap ditemukan, tidak - tidak ditemukan. Sebenarnya, model Boolean klasik adalah jembatan yang menghubungkan teori pencarian informasi dengan teori pencarian dan manipulasi data.

Kritik terhadap model Boolean, cukup adil, terdiri atas kekakuan yang ekstrem dan ketidakcocokan untuk peringkat. Oleh karena itu, pada tahun 1957, Joyce dan Needham (Joyce dan Needham) menyarankan untuk mempertimbangkan karakteristik frekuensi kata sehingga "... operasi perbandingan akan menjadi rasio jarak antara vektor ...". Model vektor berhasil diimplementasikan pada tahun 1968 oleh bapak pendiri ilmu pengambilan informasi Gerard Salton (Gerard Salton) * di mesin pencari SMART (Salton's Magical Automatic Retriever of Text). Pemeringkatan dalam model ini didasarkan pada pengamatan statistik alami bahwa semakin besar frekuensi lokal suatu istilah dalam dokumen (TF) dan semakin "langka" (yaitu, kembalinya kejadian dalam dokumen ) dari suatu istilah dalam koleksi (IDF), semakin tinggi bobot dokumen ini dalam kaitannya dengan istilah tersebut. .

---

^{* Gerard Salton (Sahlman) 1927-1995. Dia adalah Selton, dia adalah Zalton dan bahkan Zalman, dia adalah Gerard, Gerard, Gerard atau bahkan Gerald, tergantung pada selera penerjemah dan kesalahan ketik yang dibuat.
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}

Penunjukan IDF diperkenalkan oleh Karen Sparck-Jones (Karen Spark-Jones) pada tahun 1972 dalam sebuah artikel tentang istilah kekhususan . Mulai sekarang, penunjukan TF * IDF banyak digunakan sebagai sinonim untuk model vektor.

Akhirnya, pada tahun 1977, Robertson dan Sparck-Jones ( Robertson dan Spark-Jones) mendukung dan menerapkan model probabilistik ( diusulkan pada tahun 1960), yang juga meletakkan dasar bagi seluruh keluarga. Relevansi dalam model ini dianggap sebagai kemungkinan bahwa dokumen ini mungkin menarik bagi pengguna. Ini menyiratkan adanya set awal dokumen relevan yang sudah ada yang dipilih oleh pengguna atau diterima secara otomatis dengan asumsi sederhana. Peluang untuk menjadi relevan untuk setiap dokumen selanjutnya dihitung berdasarkan rasio kemunculan istilah dalam set yang relevan dengan sisa bagian "tidak relevan" dari koleksi. Meskipun model probabilistik memiliki beberapa keunggulan teoretis, karena mereka mengatur dokumen dalam urutan "kemungkinan relevan," dalam praktiknya mereka belum menerima banyak distribusi.

Saya tidak akan masuk ke detail dan menulis formula besar untuk setiap model. Ringkasan mereka, bersama dengan diskusi, mengambil 35 halaman dalam bentuk terkompresi dalam buku "Pencarian Informasi Modern" . Penting untuk dicatat bahwa di setiap keluarga, model paling sederhana dihasilkan dari asumsi kata independensi dan memiliki kondisi penyaringan sederhana: dokumen yang tidak mengandung kata-kata permintaan tidak pernah ditemukan. Model lanjutan ("alternatif") dari masing-masing keluarga tidak menganggap kata permintaan sebagai independen, tetapi, di samping itu, memungkinkan Anda menemukan dokumen yang tidak mengandung satu kata pun dari permintaan.

Cari "dengan akal"

Kemampuan untuk menemukan dan membuat peringkat dokumen yang tidak mengandung kata-kata dari permintaan sering dianggap sebagai tanda kecerdasan buatan atau pencarian dengan makna dan apriori berhubungan dengan keunggulan model. Pertanyaan apakah ini benar atau tidak, kami akan meninggalkan ruang lingkup artikel ini.

Sebagai contoh, saya hanya akan menjelaskan satu, mungkin model paling populer yang bekerja berdasarkan makna. Dalam teori pencarian informasi, model ini disebut pengindeksan laten-semantik (dengan kata lain, mengungkapkan makna tersembunyi). Model aljabar ini didasarkan pada dekomposisi singular dari matriks segi empat yang menghubungkan kata-kata dengan dokumen. Unsur matriks adalah respons frekuensi, yang mencerminkan tingkat koneksi kata dan dokumen, misalnya, TF * IDF. Alih-alih matriks dimensi juta asli, penulis metode Furnas dan Deerwester menyarankan menggunakan 50-150 "makna tersembunyi" yang sesuai dengan komponen utama pertama dari dekomposisi singularnya .

Dekomposisi singular dari matriks nyata A ukuran m * n disebut dekomposisi bentuk A = USV, di mana U adalah matriks ortogonal dengan ukuran m * m, V adalah matriks ortogonal dengan ukuran n * n, S adalah matriks diagonal ukuran m * n, elemen-elemennya yang mana _ij = 0 jika i tidak sama dengan j , dan s _ii = s _i > = 0. Kuantitas si disebut bilangan singular dari matriks dan sama dengan nilai aritmatika dari akar kuadrat dari nilai eigen yang sesuai dari matriks AA ^T. Dalam sastra Inggris, dekomposisi singular biasa disebut dekomposisi SVD .

Sudah lama terbukti bahwa jika kita membiarkan angka singular k pertama dalam pertimbangan (menyamakan sisanya dengan nol), kita mendapatkan perkiraan terdekat dari matriks awal peringkat k (dalam arti, "interpretasi semantik terdekat dari peringkat k"). Dengan mengurangi peringkat, kami memfilter detail yang tidak relevan; meningkat, kami mencoba untuk mencerminkan semua nuansa struktur data nyata.

Operasi mencari atau menemukan dokumen yang serupa sangat disederhanakan, karena setiap kata dan setiap dokumen dikaitkan dengan vektor makna k yang relatif pendek (baris dan kolom dari matriks yang sesuai). Namun, karena kebermaknaan yang rendah dari "makna," atau karena alasan lain , penggunaan LSI di dahi untuk pencarian belum mendapatkan distribusi. Meskipun untuk tujuan tambahan (penyaringan otomatis, klasifikasi, pemisahan koleksi, penurunan dimensi awal untuk model lain), metode ini tampaknya menemukan aplikasi.

Penilaian kualitas

Pengecekan konsistensi telah menunjukkan bahwa tumpang tindih dokumen yang relevan antara dua assesor berada di urutan rata-rata 40% ... cross-assesor recall dan presisi sekitar 65% ... Ini menyiratkan batas atas praktis pada kinerja sistem pengambilan 65% ...
Donna harman
Apa yang telah kita pelajari, dan tidak pelajari, dari TREC

Terjemahan

"... pemeriksaan stabilitas menunjukkan bahwa tumpang tindih dokumen yang relevan antara dua penilai rata-rata sekitar 40% ... akurasi dan kelengkapan yang diukur antara penilai adalah sekitar 65% ... Ini memaksakan batas atas praktis pada kualitas pencarian di wilayah 65% ..."

Apa pun modelnya, mesin pencari membutuhkan "penyetelan" - penilaian kualitas pencarian dan penyetelan parameter. Penilaian kualitas adalah ide dasar untuk mencari teori. Untuk itu berkat penilaian kualitas bahwa kita dapat berbicara tentang penerapan atau tidak dapat diterapkannya model tertentu dan bahkan mendiskusikan aspek teoretis mereka.

Secara khusus, salah satu batasan alami dari kualitas pencarian adalah pengamatan yang dibuat dalam epigraf: pendapat dua "penilai" (para ahli mengeluarkan vonis pada relevansi) rata-rata tidak bertepatan satu sama lain dalam tingkat yang sangat besar! Ini juga menyiratkan batas atas alami kualitas pencarian, karena kualitas diukur dengan perbandingan dengan pendapat penilai.

Biasanya, dua parameter diukur untuk menilai kualitas pencarian:

• presisi - proporsi materi yang relevan dalam respons mesin pencari
• kelengkapan (recall) - proporsi dokumen yang relevan ditemukan dalam jumlah total dokumen pengumpulan yang relevan

Parameter ini digunakan dan digunakan secara teratur untuk memilih model dan parameternya dalam kerangka konferensi evaluasi pengambilan teks (TREC) * yang dibuat oleh American Institute of Standards (NIST). Mulai tahun 1992, sebuah konsorsium yang terdiri dari 25 kelompok, pada tahun ke 12 keberadaannya, konferensi tersebut telah mengumpulkan materi penting yang masih mengasah mesin pencari. Untuk setiap konferensi reguler, materi baru sedang dipersiapkan (yang disebut "jalur") di masing-masing bidang yang diminati. "Track" termasuk koleksi dokumen dan permintaan. Saya akan memberikan contoh:

- Lacak permintaan acak ( ad hoc ) - hadir di semua konferensi
- Pencarian multibahasa
- Routing dan filtering
- Pencarian presisi tinggi (dengan satu jawaban, dilakukan tepat waktu)
- Interaksi pengguna
- "Jalur" bahasa alami
- Jawaban untuk "pertanyaan"
- Cari dalam teks "kotor" (hanya dipindai)
- Pencarian Suara
- Cari dalam wadah yang sangat besar (20GB, 100GB, dll.)
- WEB corps (di konferensi baru-baru ini, diwakili oleh pemilihan untuk domain .gov)
- Pencarian terdistribusi dan menggabungkan hasil pencarian dari sistem yang berbeda

---

^{* Materi konferensi tersedia untuk umum di trec.nist.gov/pubs.html .}

Bukan hanya mencari

Seperti dapat dilihat dari "jalur" TREC, sejumlah tugas terkait erat dengan pencarian itu sendiri, baik berbagi ideologi umum (klasifikasi, perutean, penyaringan, anotasi), atau menjadi bagian integral dari proses pencarian (hasil pengelompokan, perluasan dan penyempitan kueri, umpan balik, Anotasi "ketergantungan-kueri", antarmuka pencarian, dan bahasa permintaan). Tidak ada mesin pencari tunggal yang tidak harus menyelesaikan dalam praktek setidaknya satu dari tugas-tugas ini.

Seringkali kehadiran satu atau beberapa properti tambahan adalah argumen yang menentukan dalam persaingan mesin pencari. Misalnya, anotasi singkat yang terdiri dari kutipan informatif dari dokumen, dengan mana beberapa mesin pencari menemani hasil pekerjaan mereka, membantu mereka untuk tetap setengah langkah di depan kompetisi.

Tidak mungkin menceritakan semua tugas dan cara menyelesaikannya. Misalnya, pertimbangkan "ekstensi kueri", yang biasanya dilakukan dengan melakukan pencarian untuk istilah terkait. Solusi untuk masalah ini dimungkinkan dalam dua bentuk - lokal (dinamis) dan global (statis). Teknisi lokal mengandalkan teks kueri dan hanya menganalisis dokumen yang ditemukan di sana. "Ekstensi" global dapat beroperasi dengan thesauri, baik a priori (linguistik) dan dibangun secara otomatis di seluruh kumpulan dokumen. Menurut pendapat yang diterima secara umum, modifikasi permintaan global melalui thesauri bekerja secara tidak efisien, mengurangi akurasi pencarian. Pendekatan global yang lebih sukses didasarkan pada klasifikasi statis yang dibangun secara manual, seperti direktori WEB. Pendekatan ini banyak digunakan di mesin pencari Internet dalam operasi penyempitan atau perluasan permintaan.

Seringkali, penerapan fitur tambahan didasarkan pada prinsip dan model yang sama atau sangat mirip dengan pencarian itu sendiri. , , , ( – 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

Terjemahan

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

Terjemahan

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

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