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.
Jawaban:
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
varchar
field 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.
sumber
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
sumber
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.
sumber
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.
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).
sumber