Proyek: Mesin Pencarian Kata

Setiap kali kita mengetik kata di Google, mesin pencari tidak membaca semua halaman web satu per satu. Sebaliknya, ia mengakses inverted index — struktur data yang memetakan setiap kata ke daftar dokumen yang memuatnya. Pada proyek ini kita membangun search engine mini dengan arsitektur yang sama: korpus dokumen teks di-preprocess menjadi inverted index, lalu query satu kata dicocokkan ke index untuk mengembalikan dokumen yang paling relevan.

Tool yang akan kita bangun memiliki cakupan berikut:

• menerima korpus berupa std::vector<std::string> dokumen teks,
• melakukan preprocessing: tokenisasi, lowercasing, penghapusan tanda baca,
• membangun inverted index std::unordered_map<string, vector<Posting>> dengan frekuensi kata per dokumen,
• menerima query satu kata, mencari di index, dan mengembalikan dokumen yang diranking dengan skor TF-IDF.

Tampilan Akhir Tool #

Berikut contoh sesi pencarian pada korpus kecil:

Korpus: 5 dokumen
Query: "data"
Hasil (ranking TF-IDF):
  [doc 3] skor=0.693  "Struktur data adalah fondasi algoritma."
  [doc 0] skor=0.000  "Belajar struktur data dengan C++."
  [doc 1] skor=0.000  "Pemrograman modern butuh disiplin."

Dokumen 3 menempati peringkat atas karena mengandung kata “data” dan relatif pendek (TF tinggi, IDF tinggi). Dokumen 0 dan 1 tidak mengandung kata “data” sehingga skor TF-IDF-nya nol, tetapi tetap dicantumkan untuk perbandingan kosong.

Tujuan Pembelajaran #

Setelah menyelesaikan proyek ini, kita mampu:

• merancang format dokumen dan tipe query yang realistis untuk search engine mini,
• menulis pipeline preprocessing teks (tokenisasi, normalisasi, penghapusan stop word opsional),
• membangun inverted index dengan std::unordered_map dan struktur Posting per dokumen,
• mengimplementasikan ranking TF-IDF dan mengurutkan hasil berdasarkan skor,
• memvalidasi pencarian dengan beberapa query uji.

Prasyarat #

Proyek ini memanfaatkan materi yang sudah dibahas pada Section sebelumnya:

• Hash Table — std::unordered_map sebagai backbone inverted index,
• String Processing — tokenisasi, manipulasi karakter,
• Sorting Algorithms — mengurutkan hasil pencarian berdasarkan skor,
• Standard Library Algorithms — std::transform, std::sort, std::stable_sort.

Tahapan Pengerjaan #

Proyek dikerjakan dalam empat bagian berurutan:

1. Bagian 1: Perancangan Search Engine — menentukan format dokumen, tipe query (single word), dan skema ranking TF-IDF.
2. Bagian 2: Preprocessing Teks — tokenisasi, lowercasing, dan penghapusan tanda baca.
3. Bagian 3: Inverted Index — membangun std::unordered_map<std::string, std::vector<Posting>> dari korpus.
4. Bagian 4: Pemrosesan Query — mencari kata di index, menghitung skor TF-IDF, dan mengembalikan hasil terurut.

Mulailah dari Bagian 1 dan kerjakan secara berurutan. Setiap bagian membangun di atas berkas bagian sebelumnya.