Inverted Index

Indeks Bangunan

Data pengujian berasal dari ClueWeb09B Dataset, sampelnya disimpan di direktori ./test_data untuk tujuan pengujian. Saat mulai membuat indeks, program membaca indeks maju yang dikompresi, mendekompresinya, dan menghasilkan posting posisi. Postingan posisi dihitung untuk menghasilkan postingan non-posisi.

Postingan posisi dan postingan non-posisi disimpan dalam dua vektor STL secara terpisah. Ketika vektor mencapai ukuran tertentu, misalnya 500, kedua vektor tersebut dikompresi dan dikosongkan. Dua file dibuat pada disk di bawah direktori disk_index untuk menyimpan array biner terkompresi. Proses ini diulangi hingga tersisa kurang dari 500 postingan. Postingan yang tersisa disimpan dalam memori sebagai indeks dinamis.

Pengkodean Byte Variabel

Saat ini, hanya satu bentuk metode pengkodean yang diterapkan. Ketika metode sama dengan 1, postingan dikompresi menggunakan pengkodean byte variabel. Aturan byte variabel yang digunakan dalam indeks saya adalah sebagai berikut:

• jika <128, gunakan satu byte (bit tertinggi disetel ke 0)
• jika < 128*128 = 16384, gunakan dua byte (pertama memiliki bit tertinggi 0, yang lain 1)
• jika < 128^3, maka gunakan tiga byte, dan seterusnya... Misal: 34 = 00100010 144 = 00000001 10010000 16385 = 00000001 10000001 10000001

Penggabungan Logaritmik

Nama setiap file berisi dua bagian, awalan dan nomor. Indeks posisi disimpan dalam file "Z0", "Z1", ... "Zn", "I0", "I1", ... "In". Setelah mengompresi, pengindeks memeriksa apakah "Z0" ada di disk. Jika "Z0" tidak keluar maka "Z0" dibuat dan tulis indeks ke "Z0". Jika "Z0" ada, indeksnya ditulis ke "I0". Untuk indeks non-posisi, "X0" dicentang dan ditulis jika tidak ada. Jika tidak, indeks non-posisi ditulis ke "L0". Istilah ID disimpan dalam file meta data dari file yang sesuai. Meta data dari istilah tersebut menyimpan nama file dan posisi awal dan akhir.

Dua file yang memiliki nomor indeks yang sama tidak akan pernah bisa hidup berdampingan di disk secara permanen. Setiap kali 500 postingan selesai ditulis ke disk, pengindeks memeriksa apakah ada dua file yang memiliki nomor indeks yang sama. Jika ada, dua file digabungkan menjadi satu file baru dengan nomor indeks bertambah 1. Proses ini disebut penggabungan logaritmik. Misalnya, jika "Z0" dan "I0" ada, keduanya digabungkan dan ditulis menjadi "Z1", atau "I1" jika "Z1" sudah ada di disk. Proses ini diulangi hingga tidak ada file "I" di disk. Meta data diperbarui sesuai dengan itu.

Memperbarui Indeks

Postingan baru diterima dan disimpan dalam indeks dinamis. Postingan yang dihasilkan oleh penganalisis dokumen disebut postingan eksternal dan postingan yang akan disimpan dalam memori disebut postingan internal. Ketika ada 500 posting di memori, itu dikompresi menggunakan metode yang sama seperti membangun indeks.

---

Apa yang Harus Dilakukan Selanjutnya

• Menerapkan pemroses kueri
• Dua kesalahan di indexer.cpp yang perlu diperbaiki, dan dua fungsi dapat dioptimalkan dalam file yang sama
• Buat tabel halaman untuk menyimpan semua halaman, sehingga kita bisa menampilkan cuplikan teks saat melakukan kueri

---

Cara Membangun proyek

./initialize.sh untuk membuat direktori tempat indeks disk disimpan dan pastikan direktori tersebut kosong, lakukan panggilan make ./INDEX mulai membuat indeks