Sistem Pencarian

Setiap kali kita mengetik kata kunci di Google, jutaan dokumen dipindai dalam hitungan milidetik. Kunci kecepatan ini bukan pemindaian linear, melainkan struktur data bernama inverted index yang memetakan setiap kata ke daftar dokumen yang memuatnya. Pada Chapter ini kita akan membangun tiny search engine yang menyerupai prinsip kerja mesin pencari nyata: tokenisasi teks, pembangunan inverted index dengan hash map, dan ranking hasil menggunakan skor TF-IDF. Tujuan akhirnya adalah memahami bagaimana konsep DSA yang sudah kita pelajari — hash map, vector, dan string processing — bersatu menjadi sistem yang melayani miliaran query per hari.

Arsitektur Search Engine Mini #

Search engine modern terdiri dari tiga komponen utama: crawler yang mengumpulkan dokumen, indexer yang membangun inverted index, dan ranker yang mengurutkan hasil berdasarkan relevansi. Pada Chapter ini kita fokus pada dua komponen terakhir dengan asumsi dokumen sudah tersedia di memori.

Tabel berikut merangkum peran setiap komponen:

Inverted Index: Aturan dan Mekanisme #

Aturan #

Inverted index adalah struktur data yang memetakan setiap term unik ke daftar posting — pasangan (doc_id, term_freq) yang menyatakan pada dokumen mana term muncul dan berapa kali. Struktur ini disebut “inverted” karena kebalikan dari forward index (yang memetakan doc_id → list_of_terms). Pencarian menjadi O(1) lookup per term, bukan O(n) pemindaian seluruh dokumen.

Mekanisme di Balik Layar #

Saat sebuah dokumen ditambahkan ke index, tokenizer memecah teks menjadi token-token kecil (lowercase, alfanumerik). Setiap token dihitung frekuensinya dalam dokumen tersebut menggunakan hash map lokal. Setelah agregasi, setiap term yang ditemukan ditambahkan ke inverted_index_[term] sebagai satu objek Posting. Variabel doc_freq_[term] diinkrementasi setiap kali term muncul di dokumen baru — nilai ini nantinya dipakai untuk menghitung IDF.

Skor TF-IDF #

Skor relevansi dokumen d terhadap query q dihitung sebagai jumlah skor setiap term di query:

• TF (Term Frequency) = freq(term, d) / |d| — seberapa sering term muncul relatif terhadap panjang dokumen.
• IDF (Inverse Document Frequency) = log(N / df(term)) — term yang muncul di sedikit dokumen lebih informatif.
• Skor total = Σ TF × IDF untuk setiap term pada query.

Kode: Tiny Search Engine #

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

struct Posting {
    int doc_id;
    int term_freq;          // frekuensi term pada dokumen
};

class TinySearchEngine {
public:
    void addDocument(int doc_id, const string& text) {
        // Tokenisasi sederhana: lowercase + split non-alpha
        vector<string> tokens = tokenize(text);
        unordered_map<string, int> freq;
        for (const auto& t : tokens) freq[t]++;

        // Catat panjang dokumen untuk normalisasi TF
        doc_len_[doc_id] = (int)tokens.size();
        total_len_ += (int)tokens.size();

        // Tambahkan ke inverted index
        for (const auto& kv : freq) {
            inverted_index_[kv.first].push_back({doc_id, kv.second});
            doc_freq_[kv.first]++;     // jumlah dokumen yang memuat term
        }
        num_docs_++;
    }

    // Skor TF-IDF: tf * log(N / df)
    vector<pair<int, double>> search(const string& query, int top_k = 3) {
        vector<string> q_tokens = tokenize(query);
        unordered_map<int, double> scores;

        for (const auto& term : q_tokens) {
            auto it = inverted_index_.find(term);
            if (it == inverted_index_.end()) continue;

            int df = doc_freq_[term];
            double idf = log((double)num_docs_ / df);

            for (const auto& post : it->second) {
                double tf = (double)post.term_freq / doc_len_[post.doc_id];
                scores[post.doc_id] += tf * idf;
            }
        }

        vector<pair<int, double>> result(scores.begin(), scores.end());
        sort(result.begin(), result.end(),
             [](const auto& a, const auto& b) { return a.second > b.second; });

        if ((int)result.size() > top_k) result.resize(top_k);
        return result;
    }

private:
    unordered_map<string, vector<Posting>> inverted_index_;
    unordered_map<string, int> doc_freq_;
    unordered_map<int, int> doc_len_;
    int num_docs_ = 0;
    int total_len_ = 0;

    static vector<string> tokenize(const string& s) {
        vector<string> out;
        string cur;
        for (char c : s) {
            if (isalnum((unsigned char)c)) cur += (char)tolower((unsigned char)c);
            else if (!cur.empty()) { out.push_back(cur); cur.clear(); }
        }
        if (!cur.empty()) out.push_back(cur);
        return out;
    }
};

int main() {
    TinySearchEngine engine;

    engine.addDocument(1, "belajar struktur data dan algoritma");
    engine.addDocument(2, "algoritma pencarian biner pada array terurut");
    engine.addDocument(3, "struktur data hash map untuk pencarian cepat");
    engine.addDocument(4, "graf algoritma shortest path dijkstra");
    engine.addDocument(5, "pencarian jalur terpendek dengan bfs pada grid");

    cout << "=== Tiny Search Engine ===\n";
    cout << "Dokumen terindeks: 5\n\n";

    string query = "pencarian algoritma";
    cout << "Query: \"" << query << "\"\n\n";

    auto results = engine.search(query, 3);
    cout << "Top-3 hasil (TF-IDF):\n";
    cout << left << setw(10) << "Doc ID" << setw(12) << "Skor" << "\n";
    cout << "----------|-----------\n";
    for (const auto& kv : results) {
        cout << left << setw(10) << kv.first
             << fixed << setprecision(4) << kv.second << "\n";
    }
    return 0;
}

Output yang Dihasilkan:

=== Tiny Search Engine ===
Dokumen terindeks: 5

Query: "pencarian algoritma"

Top-3 hasil (TF-IDF):
Doc ID    Skor
----------|-----------
2         0.1703
4         0.1022
1         0.1022

Bedah Kode Baris-per-Baris #

1. struct Posting { int doc_id; int term_freq; }: posting adalah unit terkecil inverted index. Setiap term di index memiliki vektor posting yang menyatakan di dokumen mana term muncul dan berapa kali.
2. vector<string> tokens = tokenize(text);: pemanggilan tokenizer. Teks “Belajar Struktur Data!” menjadi ["belajar", "struktur", "data"]. Lowercase menggabungkan variasi kapital; split non-alfanumerik memisahkan tanda baca.
3. unordered_map<string, int> freq; for (const auto& t : tokens) freq[t]++;: hitung frekuensi setiap term pada dokumen saat ini. Hash map memberi agregasi O(rata-rata O(1) per token).
4. inverted_index_[kv.first].push_back({doc_id, kv.second});: untuk setiap term unik di dokumen, tambahkan posting ke vektor yang dimiliki term tersebut. Lookup inverted_index_[term] adalah O(1) rata-rata.
5. doc_freq_[kv.first]++;: inkrementasi document frequency. Nilai ini dipakai pada perhitungan IDF saat query.
6. double idf = log((double)num_docs_ / df);: rumus IDF klasik. Term yang muncul di semua dokumen memiliki df = N, sehingga idf = log(1) = 0 — tidak menambah skor. Term unik di satu dokumen memiliki idf = log(N) yang besar.
7. double tf = (double)post.term_freq / doc_len_[post.doc_id];: normalisasi TF agar dokumen panjang tidak mendominasi. Tanpa normalisasi, dokumen panjang dengan term banyak akan selalu menang.
8. scores[post.doc_id] += tf * idf;: akumulasi skor TF-IDF per dokumen. Query multi-term menjumlahkan kontribusi setiap term.
9. sort(result.begin(), result.end(), [](...) { return a.second > b.second; });: urut descending berdasarkan skor. Hasil terbesar di paling atas.

Kompleksitas #

Lookup inverted_index_[term] rata-rata O(1) membuat pencarian jauh lebih cepat daripada pemindaian linear O(N × L) yang akan diperlukan tanpa index.

Kapan TF-IDF Tidak Cukup #

TF-IDF bekerja baik untuk query keyword pendek, tetapi lemah pada kasus berikut:

Ringkasan #

• Inverted index memetakan term → daftar posting (doc_id, freq), mengubah pencarian dari O(N) pemindaian menjadi O(1) lookup per term.
• TF-IDF menggabungkan frekuensi term pada dokumen (TF) dengan keunikan term di seluruh koleksi (IDF).
• Tokenizer melakukan lowercase + split non-alfanumerik untuk normalisasi teks.
• Untuk skala besar, tambahkan kompresi posting, sharding per term, dan lapisan scoring berbasis ML.
• Struktur ini menjadi dasar semua mesin pencari — dari Elasticsearch hingga Google Search.