Bagian 4: Pemrosesan Query

Inverted index telah berdiri; sekarang kita menggunakannya untuk menjawab query. Pada bagian ini, satu kata query dipreprocess dengan pipeline yang sama (lowercase, tanpa tanda baca), dilihat di index untuk mendapatkan daftar posting, lalu skor TF-IDF dihitung untuk setiap posting. Hasil diurutkan menurun berdasarkan skor dan dicetak dengan ringkasan dokumen.

Rumus TF-IDF #

Kita pakai varian sederhana:

TF(t, d) = frekuensi term t dalam dokumen d (raw count, tanpa normalisasi).
IDF(t) = log(N / df(t)) di mana N = total dokumen, df(t) = jumlah dokumen yang memuat t.
Skor(d, t) = TF × IDF.

Konsekuensi penting: term yang muncul di semua dokumen mendapat IDF = log(N/N) = 0, sehingga skornya nol meskipun TF tinggi. Ini otomatis menurunkan ranking stop word seperti “dan” atau “adalah”.

Implementasi `search` #

cpp
#include <algorithm>
#include <cmath>

struct SearchResult {
    int docId;
    double score;
};

std::vector<SearchResult> search(
        const InvertedIndex& index,
        const std::vector<std::string>& corpus,
        const std::string& word) {
    // Preprocess query sama dengan dokumen: lowercase + strip punctuation.
    std::vector<std::string> qTokens = tokenize(word);
    if (qTokens.empty()) return {};
    std::string term = qTokens[0];

    auto it = index.find(term);
    if (it == index.end()) return {};   // term tidak ada di korpus

    int N = (int)corpus.size();
    int df = (int)it->second.size();
    double idf = std::log((double)N / (double)df);

    std::vector<SearchResult> results;
    for (const auto& p : it->second) {
        double tf = (double)p.termFreq;
        results.push_back({p.docId, tf * idf});
    }
    std::sort(results.begin(), results.end(),
        [](const SearchResult& a, const SearchResult& b) {
            if (a.score != b.score) return a.score > b.score;
            return a.docId < b.docId;
        });
    return results;
}

Program Lengkap Bagian 4 #

Berikut program lengkap yang membangun index dan menjalankan beberapa query uji.

cpp
#include <algorithm>
#include <cctype>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

bool isTokenChar(char c) {
    return std::isalnum(static_cast<unsigned char>(c)) || c == '_' || c == '+' || c == '-';
}

std::vector<std::string> tokenize(const std::string& text) {
    std::vector<std::string> tokens;
    std::string current;
    for (char c : text) {
        if (isTokenChar(c)) {
            current += static_cast<char>(
                std::tolower(static_cast<unsigned char>(c)));
        } else if (!current.empty()) {
            tokens.push_back(current);
            current.clear();
        }
    }
    if (!current.empty()) tokens.push_back(current);
    return tokens;
}

struct Posting {
    int docId;
    int termFreq;
};
using InvertedIndex = std::unordered_map<std::string, std::vector<Posting>>;

InvertedIndex buildIndex(const std::vector<std::string>& corpus) {
    InvertedIndex index;
    for (int docId = 0; docId < (int)corpus.size(); ++docId) {
        std::vector<std::string> tokens = tokenize(corpus[docId]);
        std::unordered_map<std::string, int> freq;
        for (const auto& tok : tokens) freq[tok]++;
        for (const auto& [term, count] : freq) {
            index[term].push_back(Posting{docId, count});
        }
    }
    return index;
}

struct SearchResult {
    int docId;
    double score;
};

std::vector<SearchResult> search(
        const InvertedIndex& index,
        const std::vector<std::string>& corpus,
        const std::string& word) {
    std::vector<std::string> qTokens = tokenize(word);
    if (qTokens.empty()) return {};
    std::string term = qTokens[0];
    auto it = index.find(term);
    if (it == index.end()) return {};

    int N = (int)corpus.size();
    int df = (int)it->second.size();
    double idf = std::log((double)N / (double)df);

    std::vector<SearchResult> results;
    for (const auto& p : it->second) {
        double tf = (double)p.termFreq;
        results.push_back({p.docId, tf * idf});
    }
    std::sort(results.begin(), results.end(),
        [](const SearchResult& a, const SearchResult& b) {
            if (a.score != b.score) return a.score > b.score;
            return a.docId < b.docId;
        });
    return results;
}

void runQuery(const InvertedIndex& index,
        const std::vector<std::string>& corpus,
        const std::string& word) {
    std::cout << "Query: \"" << word << "\"\n";
    auto results = search(index, corpus, word);
    if (results.empty()) {
        std::cout << "  (tidak ada hasil)\n\n";
        return;
    }
    for (const auto& r : results) {
        std::cout << "  [doc " << r.docId << "] skor="
                  << std::fixed << std::setprecision(3) << r.score
                  << "  \"" << corpus[r.docId] << "\"\n";
    }
    std::cout << "\n";
}

int main() {
    std::vector<std::string> corpus = {
        "Belajar struktur data dengan C++.",
        "Pemrograman modern butuh disiplin.",
        "Struktur data adalah fondasi algoritma.",
        "Algoritma sorting dan searching penting.",
        "C++ mendukung STL yang kaya struktur data."
    };
    InvertedIndex index = buildIndex(corpus);
    std::cout << "Korpus: " << corpus.size() << " dokumen\n\n";

    runQuery(index, corpus, "data");
    runQuery(index, corpus, "algoritma");
    runQuery(index, corpus, "c++");
    runQuery(index, corpus, "missing");
    return 0;
}

Output yang Dihasilkan:

text
Korpus: 5 dokumen

Query: "data"
  [doc 0] skor=0.511  "Belajar struktur data dengan C++."
  [doc 2] skor=0.511  "Struktur data adalah fondasi algoritma."
  [doc 4] skor=0.511  "C++ mendukung STL yang kaya struktur data."

Query: "algoritma"
  [doc 2] skor=0.916  "Struktur data adalah fondasi algoritma."
  [doc 3] skor=0.916  "Algoritma sorting dan searching penting."

Query: "c++"
  [doc 0] skor=0.916  "Belajar struktur data dengan C++."
  [doc 4] skor=0.916  "C++ mendukung STL yang kaya struktur data."

Query: "missing"
  (tidak ada hasil)

Bedah Baris Penting #

std::vector<std::string> qTokens = tokenize(word): query dipreprocess dengan pipeline yang sama dengan dokumen. Tanpa ini, query “Data” (huruf besar) tidak akan cocok dengan token “data” di index.
qTokens[0]: kita hanya pakai token pertama dari query. Bila user mengetik “data structure”, hanya “data” yang dicari — sesuai cakupan single-word yang ditetapkan pada Bagian 1.
auto it = index.find(term): lookup O(1) rata-rata berkat unordered_map. Bila term tidak ada, kembalikan vector kosong.
std::log((double)N / (double)df): rumus IDF klasik. Cast ke double eksplisit karena N dan df bertipe int — tanpa cast, pembagian integer menghasilkan 0 atau 1 yang merusak perhitungan.
if (a.score != b.score) return a.score > b.score: sort menurun berdasarkan skor. Tie-breaker pada docId menjamin urutan deterministik untuk dokumen dengan skor sama.
std::fixed << std::setprecision(3): format output 3 desimal agar mudah dibaca. Tanpa ini, double mencetak 6+ desimal yang menyulitkan perbandingan visual.

Analisis Hasil #

Pada query "data":

3 dokumen memuat “data” (df = 3), N = 5, sehingga IDF = log(5/3) ≈ 0.511.
Setiap dokumen memiliki TF = 1, sehingga skor = 1 × 0.511 = 0.511.
Ketiga dokumen mendapat skor sama; urutan akhirnya berdasarkan docId.

Pada query "algoritma":

2 dokumen memuat “algoritma” (df = 2), IDF = log(5/2) ≈ 0.916.
Skor lebih tinggi karena term lebih langka. Inilah esensi TF-IDF: kata langka di korpus mendapat bobot lebih besar.

Pada query "missing":

Term tidak ada di index, hasil kosong. Tanpa inverted index, kita harus memindai semua dokumen untuk menyimpulkan ketiadaan — index membuat “tidak ditemukan” menjadi O(1).

Ringkasan Proyek #

Search engine mini telah lengkap: preprocessing (Bagian 2), inverted index (Bagian 3), dan query + ranking TF-IDF (Bagian 4). Arsitektur inverted index yang kita bangun sama prinsipnya dengan Elasticsearch dan Lucene — perbedaan utama adalah skala dan optimasi yang tidak kita terapkan di sini. Konsep kunci yang harus diingat: tokenisasi yang konsisten antara dokumen dan query, IDF yang menurunkan ranking stop word secara alami, dan sort hasil berdasarkan skor untuk memberi jawaban terbaik di puncak.

Kompilasi dan Pengujian #

bash
g++ -std=c++17 -O2 -Wall -Wextra -o search.bin search.cpp
./search.bin

Coba ubah korpus atau tambah query sendiri untuk menguji perilaku pada term langka vs umum.

Rumus TF-IDF #

Implementasi search #

Program Lengkap Bagian 4 #

Bedah Baris Penting #

Analisis Hasil #

Ringkasan Proyek #

Kompilasi dan Pengujian #

Implementasi `search` #