Bagian 3: Inverted Index

Dengan tokenize dari Bagian 2, kita sekarang mengubah korpus menjadi inverted index. Struktur ini adalah inti dari setiap search engine: alih-alih menyimpan dokumen dan mencari di dalamnya saat query datang, kita menyimpan pemetaan dari setiap kata ke daftar dokumen yang memuatnya. Query “data” cukup melakukan satu lookup ke index — tidak perlu membaca ulang seluruh korpus.

Struktur Posting #

Untuk setiap (term, dokumen), kita simpan Posting berisi docId dan termFreq (frekuensi term dalam dokumen tersebut). Frekuensi diperlukan untuk perhitungan TF-IDF pada Bagian 4.

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

Struktur ini disebut inverted karena membalik arah: dari dokumen → kata menjadi kata → dokumen. Trade-offnya: index membutuhkan memori tambahan, tetapi query sangat cepat — O(1) lookup + O(k) untuk iterasi posting (k = jumlah dokumen yang memuat term).

Algoritma Build Index #

Untuk setiap dokumen:

Tokenisasi teks.
Hitung frekuensi tiap token di dokumen tersebut.
Untuk setiap token unik, tambahkan Posting{docId, freq} ke index[token].

cpp
#include <unordered_map>

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;
}

Program Verifikasi #

Berikut program lengkap yang membangun index untuk korpus contoh dan mencetak seluruh index untuk verifikasi.

cpp
#include <cctype>
#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;
}

void printIndex(const InvertedIndex& index) {
    std::cout << "Inverted index (sorted by term):\n";
    std::vector<std::string> terms;
    for (const auto& [t, _] : index) terms.push_back(t);
    std::sort(terms.begin(), terms.end());
    for (const auto& term : terms) {
        std::cout << "  " << term << " -> ";
        for (const auto& p : index.at(term)) {
            std::cout << "(doc " << p.docId << ", freq " << p.termFreq << ") ";
        }
        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);
    printIndex(index);
    std::cout << "\nTotal term unik: " << index.size() << "\n";
    return 0;
}

Output yang Dihasilkan:

text
Inverted index (sorted by term):
  adalah -> (doc 2, freq 1) 
  algoritma -> (doc 2, freq 1) (doc 3, freq 1) 
  belajar -> (doc 0, freq 1) 
  butuh -> (doc 1, freq 1) 
  c++ -> (doc 0, freq 1) (doc 4, freq 1) 
  dan -> (doc 3, freq 1) 
  data -> (doc 0, freq 1) (doc 2, freq 1) (doc 4, freq 1) 
  dengan -> (doc 0, freq 1) 
  disiplin -> (doc 1, freq 1) 
  fondasi -> (doc 2, freq 1) 
  kaya -> (doc 4, freq 1) 
  mendukung -> (doc 4, freq 1) 
  modern -> (doc 1, freq 1) 
  pemrograman -> (doc 1, freq 1) 
  penting -> (doc 3, freq 1) 
  searching -> (doc 3, freq 1) 
  sorting -> (doc 3, freq 1) 
  stl -> (doc 4, freq 1) 
  struktur -> (doc 0, freq 1) (doc 2, freq 1) (doc 4, freq 1) 
  yang -> (doc 4, freq 1) 

Total term unik: 20

Bedah Baris Penting #

std::unordered_map<std::string, int> freq: map lokal untuk menghitung frekuensi term dalam satu dokumen. Kunci adalah term, value adalah jumlah kemunculan. Karena unordered, lookup O(1) rata-rata.
for (const auto& [term, count] : freq): structured binding C++17 membongkar pair key-value menjadi dua variabel. const auto& menghindari salinan string — frekuensi map bisa besar pada dokumen panjang.
index[term].push_back(Posting{docId, count}): operator[] pada unordered_map akan menyisipkan entri kosong bila key belum ada, lalu kita push posting ke vector. Efek samping: entri hantu tidak muncul karena push selalu terjadi setelah [].
std::sort(terms.begin(), terms.end()) di printIndex: kita sortir term menurut abjad hanya untuk output yang konsisten. Urutan iterasi unordered_map tidak deterministik — tanpa sort, output berubah-ubah antar run.
index.at(term): pakai .at() alih-alih [] saat membaca karena [] mode write akan menyisipkan entri kosong. Bila ada bug, .at() melempar std::out_of_range segera — lebih aman daripada entri hantu.

Analisis Kompleksitas #

Tahap	Kompleksitas	Penjelasan
Tokenisasi	O(T)	T = total token di korpus
Hitung freq per dokumen	O(T_d)	T_d = token per dokumen
Insert ke index	O(T) rata-rata	hash lookup O(1)
Total build	O(T) rata-rata	linear terhadap total token
Memory	O(T)	setiap token disimpan sekali + posting

Kompilasi dan Pengujian #

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

Verifikasi bahwa term seperti “data” muncul di tiga dokumen (0, 2, 4) — informasi ini yang akan dipakai pada Bagian 4 untuk ranking.