Bagaimana dokumen indeks Lucene?

Saya membaca beberapa dokumen tentang Lucene; Saya juga membaca dokumen di tautan ini ( http://lucene.sourceforge.net/talks/pisa ).

Saya tidak begitu mengerti bagaimana Lucene mengindeks dokumen dan tidak mengerti algoritma mana yang digunakan Lucene untuk mengindeks?

Di tautan di atas, dikatakan Lucene menggunakan algoritme ini untuk mengindeks:

• algoritma inkremental:
  • memelihara tumpukan indeks segmen
  • buat indeks untuk setiap dokumen yang masuk
  • mendorong indeks baru ke dalam tumpukan
  • misalkan b = 10 menjadi faktor penggabungan; M = 8

for (size = 1; size < M; size *= b) {
    if (there are b indexes with size docs on top of the stack) {
        pop them off the stack;
        merge them into a single index;
        push the merged index onto the stack;
    } else {
        break;
    }
}

Bagaimana algoritme ini memberikan pengindeksan yang dioptimalkan?

Apakah Lucene menggunakan algoritma B-tree atau algoritma lain seperti itu untuk pengindeksan - atau apakah ia memiliki algoritma tertentu?

Ada artikel yang cukup bagus di sini: https://web.archive.org/web/20130904073403/http://www.ibm.com/developerworks/library/wa-lucene/

Sunting 12/2014: Diperbarui ke versi yang diarsipkan karena yang asli telah dihapus, mungkin alternatif terbaru yang terbaik adalah http://lucene.apache.org/core/3_6_2/fileformats.html

Ada versi yang lebih baru di http://lucene.apache.org/core/4_10_2/core/org/apache/lucene/codecs/lucene410/package-summary.html#package_description , tetapi tampaknya memiliki lebih sedikit informasi di dalamnya dari yang lebih tua.

Singkatnya, ketika lucene mengindeks sebuah dokumen, ia memecahnya menjadi beberapa istilah. Ini kemudian menyimpan istilah dalam file indeks di mana setiap istilah dikaitkan dengan dokumen yang berisi itu. Anda bisa menganggapnya sebagai hashtable.

Istilah-istilah dihasilkan menggunakan alat analisis yang menempatkan setiap kata pada bentuk akarnya. Algoritma stemming yang paling populer untuk bahasa Inggris adalah algoritma stemming Porter: http://tartarus.org/~martin/PorterStemmer/

Saat kueri dikeluarkan, kueri diproses melalui penganalisis yang sama yang digunakan untuk membuat indeks dan kemudian digunakan untuk mencari istilah yang cocok di indeks. Itu memberikan daftar dokumen yang cocok dengan kueri.

Singkatnya, Lucene membuat indeks terbalik menggunakan Skip-List pada disk , lalu memuat pemetaan untuk istilah yang diindeks ke dalam memori menggunakan Finite State Transducer (FST). Namun, perhatikan bahwa Lucene tidak (harus) memuat semua istilah yang diindeks ke RAM , seperti yang dijelaskan oleh Michael McCandless, penulis sistem pengindeksan Lucene sendiri. Perhatikan bahwa dengan menggunakan Skip-List, indeks dapat ditelusuri dari satu klik ke hit lainnya, membuat hal-hal seperti set dan, khususnya, query range menjadi mungkin (seperti B-Trees). Dan entri Wikipedia tentang mengindeks Skip-List juga menjelaskan mengapa implementasi Skip-List Lucene disebut a multi-levelSkip-List - pada dasarnya, untuk membuat O(log n)look-up menjadi mungkin (sekali lagi, seperti B-Trees).

Jadi, setelah indeks (istilah) terbalik - yang didasarkan pada struktur data Lewati Daftar - dibuat dari dokumen, indeks disimpan di disk. Lucene kemudian memuat (seperti yang telah dikatakan: mungkin, hanya beberapa dari) istilah-istilah tersebut ke dalam Transduser Keadaan Hingga , dalam implementasi FST yang terinspirasi oleh Morfologick .

Michael McCandless (juga) melakukan pekerjaan yang cukup baik dan singkat dalam menjelaskan bagaimana dan mengapa Lucene menggunakan FST (asiklik minimal) untuk mengindeks istilah yang disimpan Lucene dalam memori, pada dasarnya sebagai SortedMap<ByteSequence,SomeOutput>, dan memberikan ide dasar tentang bagaimana FST bekerja (yaitu, bagaimana FST memadatkan urutan byte [yaitu, istilah yang diindeks] untuk membuat penggunaan memori dari pemetaan ini tumbuh sub-linier). Dan dia menunjuk ke makalah yang menjelaskan algoritma FST tertentu yang digunakan Lucene juga.

Bagi mereka yang ingin tahu mengapa Lucene menggunakan Lewati-Lists, sementara sebagian besar database menggunakan (B +) - dan / atau (B) -Trees, lihatlah yang tepat jawaban SO tentang pertanyaan ini (Lewati-Lists vs B-Pohon). Jawaban tersebut memberikan penjelasan yang cukup bagus dan dalam - pada dasarnya, tidak begitu banyak membuat pembaruan indeks secara bersamaan "lebih bisa diterima" (karena Anda dapat memutuskan untuk tidak segera menyeimbangkan kembali B-Tree, sehingga mendapatkan kinerja bersamaan yang sama seperti Lewati-Daftar), melainkan, Lewati-Daftar menyelamatkan Anda dari keharusan bekerja pada operasi penyeimbangan (tertunda atau tidak) (pada akhirnya) dibutuhkan oleh Pohon-B (Faktanya, seperti yang ditunjukkan oleh jawaban / referensi, mungkin ada perbedaan kinerja yang sangat kecil antara Daftar-B dan Daftar Lewati [multi-level], jika salah satunya "dilakukan dengan benar.")

Tampaknya pertanyaan Anda lebih banyak tentang penggabungan indeks daripada tentang pengindeksan itu sendiri.

Proses pengindeksan cukup sederhana jika Anda mengabaikan detail tingkat rendah. Lucene membentuk apa yang disebut "indeks terbalik" dari dokumen. Jadi jika dokumen dengan teks "To be or not to be" dan id = 1 masuk, indeks terbalik akan terlihat seperti:

[to] → 1
[be] → 1
[or] → 1
[not] → 1

Ini pada dasarnya - indeks dari kata ke daftar dokumen yang berisi kata yang diberikan. Setiap baris indeks (kata) ini disebut daftar posting. Indeks ini bertahan pada penyimpanan jangka panjang.

Kenyataannya tentu saja hal-hal lebih rumit:

• Lucene mungkin melewatkan beberapa kata berdasarkan Analyzer khusus yang diberikan;
• kata-kata dapat diproses sebelumnya menggunakan algoritma stemming untuk mengurangi flexia bahasa;
• daftar posting tidak hanya berisi pengidentifikasi dokumen, tetapi juga offset dari kata yang diberikan di dalam dokumen (kemungkinan beberapa contoh) dan beberapa informasi tambahan lainnya.

Masih banyak lagi komplikasi yang tidak begitu penting untuk pemahaman dasar.

Namun penting untuk dipahami, bahwa indeks Lucene hanya ditambahkan . Di beberapa titik waktu aplikasi memutuskan untuk melakukan (mempublikasikan) semua perubahan dalam indeks. Lucene menyelesaikan semua operasi layanan dengan indeks dan menutupnya, sehingga tersedia untuk pencarian. Setelah komit, indeks pada dasarnya tidak dapat diubah. Indeks ini (atau bagian indeks) disebut segmen . Ketika Lucene menjalankan pencarian untuk sebuah query, ia mencari di semua segmen yang tersedia.

Jadi pertanyaannya muncul - bagaimana kita bisa mengubah dokumen yang sudah diindeks ?

Dokumen baru atau versi baru dari dokumen yang sudah diindeks diindeks di segmen baru dan versi lama tidak valid di segmen sebelumnya menggunakan apa yang disebut kill list . Kill list adalah satu-satunya bagian dari indeks yang berkomitmen yang dapat berubah. Seperti yang Anda duga, efisiensi indeks turun seiring waktu, karena indeks lama mungkin berisi sebagian besar dokumen yang dihapus.

Di sinilah masuknya penggabungan. Penggabungan - adalah proses menggabungkan beberapa indeks untuk membuat keseluruhan indeks lebih efisien. Apa yang pada dasarnya terjadi selama penggabungan adalah dokumen langsung disalin ke segmen baru dan segmen lama dihapus seluruhnya.

Dengan menggunakan proses sederhana ini Lucene mampu menjaga indeks dalam kondisi yang baik dalam hal kinerja pencarian.

Semoga bisa membantu.

Ini adalah indeks terbalik , tetapi itu tidak menentukan struktur mana yang digunakannya. Format indeks dalam Lucene memiliki informasi yang lengkap.
Mulailah dengan 'Ringkasan Ekstensi File'.

Anda pertama kali akan melihat bahwa itu berbicara tentang berbagai indeks yang berbeda. Sejauh yang saya bisa perhatikan tidak ada yang menggunakan secara tegas pohon-B , tetapi ada kesamaan - struktur di atas memang menyerupai pohon.