Bagaimana cara kerja Lucene

90

Saya ingin mengetahui cara kerja pencarian Lucene begitu cepat. Saya tidak dapat menemukan dokumen yang berguna di web. Jika Anda memiliki sesuatu (singkatnya kode sumber Lucene) untuk dibaca, beri tahu saya.

Permintaan pencarian teks menggunakan pencarian teks mysql5 dengan indeks membutuhkan waktu sekitar 18 menit dalam kasus saya. Pencarian lucene untuk kueri yang sama membutuhkan waktu kurang dari satu detik.

Midhat
sumber
2
Dapatkah saya meminta pertanyaan ini untuk diubah sebagai wiki komunitas? Lucene terdengar seperti platform sekarang.
asyncwait

Jawaban:

75

Lucene adalah indeks teks lengkap terbalik. Artinya, ia mengambil semua dokumen, membaginya menjadi kata-kata, lalu membangun indeks untuk setiap kata . Karena indeks adalah pencocokan string yang tepat, tidak berurutan, ini bisa menjadi sangat cepat. Secara hipotesis, indeks SQL unordered pada sebuah varcharfield bisa sama cepatnya, dan sebenarnya saya pikir Anda akan menemukan database besar dapat melakukan query string-equality sederhana dengan sangat cepat dalam kasus tersebut.

Lucene tidak harus mengoptimalkan pemrosesan transaksi. Saat Anda menambahkan dokumen, itu tidak perlu memastikan bahwa kueri melihatnya secara instan . Dan itu tidak perlu mengoptimalkan pembaruan ke dokumen yang ada.

Namun, pada akhirnya, jika Anda benar-benar ingin tahu, Anda perlu membaca sumbernya. Kedua hal yang Anda rujuk adalah open source.

bmargulies
sumber
Jika saya mengerti dengan benar, hal yang membedakan mesin pencari teks adalah bagaimana mereka menangani pencarian multi-kata dan menggabungkan hasil pencarian ke beberapa indeks secara real time. Saya tidak akan menyarankan berkonsultasi dengan sumber Lucene untuk ini. Mungkin akan lebih baik untuk membaca sedikit tentang teori pencarian teks, jawaban @ alienCoder membantu saya.
Chris Dutrow
1
@bmargulies, Jika pengindeksan adalah "per kata", lalu mengapa pencarian pengguna stackoverflow stackoverflow.com/users mengizinkan pencocokan substring?
Pacerier
2
Ini bukan tempat untuk jawaban seluruh buku. Ada sejumlah elaborasi tentang konsep dasar di sana.
bmargulies
Apa maksudmu "indeks untuk setiap kata" ... jika saya mulai mengetik "abc", bagaimana cara menemukan "abc" dalam dokumen?
Alexander Mills
1
Indeks (B-tree) dari kata ke dokumen dapat mencari dokumen dengan kata-kata dalam dokumen karena tabel indeks tersebut adalah (kata, dokumen) di mana indeks berada pada kolom kata. Pertimbangkan kueri seperti: "Temukan dokumen dengan kata 'polisi', 'kejahatan', 'statistik'" di dalamnya. Dengan mencari indeks kata, Anda dapat melakukan tiga pencarian log (N) untuk mendapatkan dokumen O (N) dengan salah satu kata tersebut di dalamnya. Kemudian Anda dapat melakukan dua loop O (N) untuk membangun satu set yang berisi dokumen yang memiliki ketiga kata tersebut. Meskipun ini secara teoritis adalah operasi O (N), sebagian besar dokumen tidak memiliki ketiga kata jadi O (n) di mana n <N.
Calicoder
34

Lucene membuat indeks besar. Indeks berisi id kata, jumlah dokumen tempat kata tersebut berada, dan posisi kata dalam dokumen tersebut. Jadi ketika Anda memberikan satu kata query itu hanya mencari indeks (O (1) kompleksitas waktu). Kemudian hasilnya diurutkan menggunakan algoritma yang berbeda. Untuk kueri multi-kata, ambil saja perpotongan dari kumpulan file tempat kata-kata tersebut ada. Jadi Lucene sangat cepat.

Untuk info lebih lanjut baca artikel ini oleh pengembang Google- http://infolab.stanford.edu/~backrub/google.html

alienCoder
sumber
8
Membaca sekilas kertas itu, itu cukup membantu. Secara khusus "4.5 Searching" memiliki jawaban yang saya cari. Secara khusus, ini terdengar seperti pencarian hash O (1) digunakan untuk kata-kata individual, tapi kemudian scan O (n) digunakan untuk menggabungkan hasil dengan batas dokumen 40.000. Saya berasumsi algoritma pengurangan peta digunakan untuk membagi pekerjaan ini sehingga pengguna mendapatkan hasil seketika.
Chris Dutrow
Salah satu algoritma yang populer adalah algoritma peringkat merpati. Meskipun saya tidak tahu banyak tentang itu.
alienCoder
3
Makalah itu lucu: "Dalam makalah ini, kami mempersembahkan Google, sebuah prototipe ...". Saya kira Google tidak selalu merupakan perusahaan besar.
Buttons840
tidak tahu Lucene, tapi satu pertanyaan: Peringkat terjadi di setiap pencarian? Atau apakah itu mempertahankan dokumen yang telah diberi peringkat sebelumnya? Jika ia memelihara dokumen sesuai peringkat sebelumnya, bagaimana ia mempertahankan permintaan banyak kata?
Vikas Prasad
Tautannya putus sekarang. @alienCoder
CEGRD
20

Singkatnya: pengindeksan.

Lucene membuat indeks dokumen Anda yang memungkinkannya untuk mencari lebih cepat.

Ini adalah perbedaan yang sama antara struktur data daftar O (N) dan struktur data tabel hash O (1). Daftar tersebut harus menelusuri seluruh koleksi untuk menemukan apa yang Anda inginkan. Tabel hash memiliki indeks yang memungkinkannya mencari tahu persis di mana item yang diinginkan berada dan hanya mengambilnya.

Memperbarui:

Saya tidak yakin apa yang Anda maksud dengan "Pencarian indeks Lucene jauh lebih cepat daripada pencarian indeks mysql."

Dugaan saya adalah Anda menggunakan MySQL "WHERE document LIKE '% phrase%'" untuk mencari dokumen. Jika benar, maka MySQL harus melakukan pemindaian tabel pada setiap baris, yang akan menjadi O (N).

Lucene dapat mengurai dokumen menjadi token, mengelompokkannya menjadi n-gram sesuai petunjuk Anda, dan menghitung indeks untuk masing-masingnya. Ini adalah O (1) untuk menemukan kata dalam dokumen Lucene yang diindeks.

duffymo
sumber
10
Ya, saya mengerti bagian pengindeksan, tetapi sekali lagi, pencarian indeks lucene jauh lebih cepat daripada pencarian indeks mysql. Bagaimana itu bisa terjadi
Midhat
9

Lucene bekerja dengan frekuensi Term dan frekuensi dokumen Invers . Ini menciptakan indeks yang memetakan setiap kata dengan dokumen dan jumlah frekuensinya yang tidak lain adalah indeks terbalik pada dokumen.

Contoh :

File 1: Random Access Memory adalah memori utama.

File 2: Hard disk adalah memori sekunder.

Lucene membuat indeks terbalik seperti

File 1:

Istilah: Acak

Frekuensi: 1

Posisi: 0

Istilah: Memori

Frekuensi: 2

Posisi: 3

Posisi: 6

Sehingga dapat mencari dan mengambil konten yang dicari dengan cepat. Jika ada terlalu banyak kecocokan untuk kueri penelusuran, ia mengeluarkan hasil berdasarkan bobotnya. Pertimbangkan permintaan pencarian "Memori Utama" yang mencari semua 4 kata secara individual dan hasilnya akan seperti,

Utama

File 1: Frekuensi - 1

Penyimpanan

File 1: Frekuensi - 2

File 2: Frekuensi - 1

Hasilnya adalah File1 diikuti oleh File2 . Untuk berhenti terbawa oleh bobot pada kata-kata yang paling umum seperti 'dan', 'atau', 'yang' itu mempertimbangkan frekuensi dokumen terbalik (yaitu 'mengurangi bobot kata yang paling populer di antara kumpulan dokumen).

Tom Taylor
sumber