OHL_AutoKey

Task Seleksi Lab IRK 2026 created by Hasri Fayadh Muqaffa

version 31 Juli 2026

Latar Belakang

_{Fig 1. Spellcheck di Google Docs.}

Kalian pasti pernah pakai fitur spell check di Google Docs, garis merah bergelombang muncul di bawah kata yang salah ketik, lengkap dengan beberapa saran koreksi yang paling mendekati. Itu jalan pakai Levenshtein Edit Distance, versi klasik Dynamic Programming yang mungkin sudah kalian dapatkan di kelas Stima dengan menghitung selisih minimal antara kata yang kalian ketik dengan kata-kata valid di kamus.

Ada juga fitur yang lebih sering kalian temui di keyboard HP atau kolom pencarian, yaitu autocomplete, misalnya ketika kalian mengetik "prog", langsung muncul saran "program", "programmer", diurutkan dari yang paling sering dipakai. Ini pakai Trie, struktur pohon yang fondasinya sudah kalian kenal dari materi Pohon di Matdis, di mana tiap cabang mewakili satu huruf sehingga pencarian kata jadi jauh lebih cepat dibanding mengecek satu per satu dari seluruh kamus.

AutoKey adalah teks editor web Bahasa Indonesia yang kalian bangun sendiri dari nol untuk mempraktikkan kedua konsep ini, ditambah satu lagi, yaitu Word Segmentation. Konsep ini adalah varian DP yang membelah string tanpa spasi (contohnya: "programdinamisinicukupsulit") jadi kata-kata valid (contohnya: "program dinamis ini cukup sulit"). Ketiganya akan digabung jadi satu, mulai dari autocomplete yang responsif saat mengetik, spell check yang otomatis menandai kata bermasalah, sampai Auto-Space yang bisa merapikan teks tanpa spasi dalam sekali klik.

_{Fig 2. AutoKey, autocomplete dan spell checker Bahasa Indonesia berbasis Trie dan Dynamic Programming.}

Dataset

Untuk dataset dapat dilihat di data/kamus.json. Dataset ini terdiri dari pasangan {"kata": frekuensi} untuk 78.345 kata bahasa Indonesia.

Dataset tersebut merupakan gabungan dari dua sumber, yaitu daftar katanya diambil dari aryakdaniswara/kbbi-dataset-kbbi-v dan skor frekuensinya diambil dari ardwort/freq-dist-id. Idiom, peribahasa, dan kata satu huruf dari dataset pertama dibuang dan hanya menyisakan 78.345 kata tunggal. Karena hanya 10.000 kata yang punya data frekuensi asli, sebagian besar kata di kamus (sekitar 68 ribu) otomatis diatur skor defaultnya menjadi 1.

Spesifikasi Tugas

Spesifikasi Wajib

Kalian akan membangun sebuah aplikasi web teks editor Bahasa Indonesia dengan autocomplete dan spell checker Bahasa Indonesia dengan cakupan sebagai berikut:

• Tech stack
  • Backend: pilih salah satu dari Python, Go, atau Rust.
  • Frontend: Next.js.
• Data: data/kamus.json yang sudah disediakan (lihat bagian Dataset) di-load oleh backend saat start.

Load Kamus & Build Trie

Build Trie dari from scratch (dilarang library Trie apa pun), lalu load data/kamus.json ke dalamnya. Trie kalian minimal bisa melakukan:

• Insert: masukkan satu kata beserta frekuensinya ke Trie.
• Search: cek apakah satu kata persis ada di Trie (bool).
• Starts with: cek apakah ada kata di Trie yang berawalan prefix tertentu (bool).
• Get suggestions: dari sebuah prefix dan topN, kembalikan daftar kata saran.

Statistik Trie

Begitu aplikasi start, tampilkan di UI:

• Jumlah kata ter-insert
• Jumlah node
• Kedalaman rata-rata
• Estimasi memory usage (jumlah node * ukuran per node dalam byte)

Autocomplete

• Dropdown saran muncul tiap keystroke dengan latency < 100ms yang berisi top-5 suggestion word yang diurutkan berdasarkan frekuensinya.
• Tab/Enter untuk memilih dan complete kata yang sedang diketik.
• Jika tidak terdapat kata dengan prefix yang diketik, maka dropdown tidak perlu dimunculkan.

Levenshtein Edit Distance

Tabel DP berukuran n*m dengan n panjang string s (kata yang diketik/typo) dan m panjang string t (kata pembanding di kamus) dengan basis dan relasi rekurens eksplisit:

• Basis: dp[i][0] = i untuk semua i, dp[0][j] = j untuk semua j.
• Relasi Rekurens: dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost), cost = 0 jika s[i] == t[j], 1 jika berbeda.

Buatkan satu fungsi/method yang menerima satu kata dan mengembalikan seluruh kata di kamus dengan distance ≤ 2 dari kata tersebut, diurutkan jarak ASC lalu frekuensi DESC.

Spell Check di Editor

• Teks editor berbasis contenteditable.
• Tiap kata divalidasi begitu user selesai mengetiknya (trigger: spasi/tanda baca). Kata yang tidak ada di kamus dapat garis bawah merah berlekuk.
• Klik kata bergaris merah, muncul dropdown top-5 saran dari fungsi pencarian jarak ≤2 di atas, dan ditambah opsi "Tambah ke kamus".
• Tombol "Check All" di toolbar untuk scan seluruh teks sekaligus, hasilnya tampil di panel samping lengkap dengan saran koreksinya.

Word Segmentation (Auto-Space)

User paste string tanpa spasi, sistem cari segmentasi optimal jadi kata-kata valid di kamus lewat DP, dimodelkan sebagai Program Dinamis Manu:

• Basis: dp[0] = 0.
• Relasi Rekurens: untuk setiap i, dp[i] = min atas semua j < i di mana s[j..i-1] valid di kamus: dp[j] + cost(s[j..i-1]).
• Cost: cost(w) = log(N / freq(w)), dengan N = total kemunculan seluruh kata di kamus (jumlah seluruh nilai frekuensi, bukan jumlah kata unik) dan freq(w) >= 1 (kata yang tidak ada di kamus dianggap freq = 1).

Tampilkan array dp[] lengkap dan proses trace-back (rekonstruksi mundur) di UI, bukan cuma hasil akhirnya saja.

Dokumentasi

README repository kalian minimal berisi:

• Deskripsi program
• Fitur program
• Tech stack
• Cara menjalankan program
• Penjelasan Trie
• Penjelasan Levenshtein Edit Distance
• Penjelasan Word Segmentation
• Penjelasan fitur bonus
• Screenshot hasil program
• Tautan video demo
• Referensi

Caution

Trie harus dari nol pakai object/dictionary per node, dilarang library Trie apa pun. Levenshtein harus tabel DP n*m from scratch, bukan hanya nilai akhirnya. Word Segmentation juga DP from scratch. Dilarang fuzzywuzzy, rapidfuzz, difflib, python-Levenshtein, natural, string-similarity atau library string similarity/fuzzy-matching apa pun di sisi implementasi inti.

Note

Boleh cross-check hasil Levenshtein dengan library saat development untuk testing, tapi implementasi yang dikumpulkan (submission) harus from scratch.

Spesifikasi Bonus

Di bagian ini kalian dapat mengerjakan (tidak wajib) untuk mendapatkan poin tambahan pada tugas ini:

Smart Trim

Fitur pemendekan otomatis: user dapat menentukan batas karakter (misal buat judul), sistem pilih subset kata dari teks yang sedang ditulis untuk dipertahankan, memaksimalkan total value tanpa melebihi batas karakter. Modelkan sebagai 0/1 Knapsack:

• Basis: dp[0][w] = 0 untuk semua w.
• Relasi Rekurens: untuk kata ke-i dengan weight_i (panjang karakternya) dan value_i, dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight_i] + value_i) jika w >= weight_i, kalau tidak dp[i][w] = dp[i-1][w].
• Value: value_i = log(N / freq(word_i)).

Tampilkan kata-kata mana saja yang dipertahankan (bukan cuma nilai maksimalnya), direkonstruksi mundur dari tabel dp[], mirip trace-back di Word Segmentation.

Bigram Language Model Kontekstual

Autocomplete unigram di atas itu buta konteks, urutannya selalu sama nggak peduli kalimat apa yang lagi ditulis. Intinya bonus ini nambahin konteks, yaitu saran diurutkan ulang berdasarkan kata sebelumnya yang baru selesai diketik.

Bangun bigram count dari teks yang user ketik selama sesi berjalan:

• Hitung pasangan: tiap kali user selesai mengetik satu kata (trigger: spasi/tanda baca, atau lewat Tab/Enter completion), catat pasangan (kata_sebelumnya, kata_yang_baru_selesai). Hanya catat kalau kedua kata sudah tervalidasi (ada di kamus).
• Hitung probabilitas: P(kata_B | kata_A) = count(kata_A, kata_B) / total_pasangan_yang_diawali_kata_A.
• Reranking saat autocomplete: kandidat dari fitur get suggestions Trie di atas diurutkan ulang berdasarkan P(kata_B | kata_A) * freq(kata_B), bukan cuma frekuensi unigram.
• Fallback: kalau kata sebelumnya tidak punya data bigram sama sekali, atau tidak ada satu pun kandidat yang match, kembalikan urutan unigram apa adanya.
• Toggle ON/OFF di UI buat pakai reranking bigram atau tidak.
• Tampilkan counter jumlah pasangan yang sudah tercatat di sesi berjalan.

Video Demo

Setelah menyelesaikan implementasi aplikasi sesuai spesifikasi, peserta wajib membuat video demonstrasi untuk menjelaskan hasil pekerjaan yang telah dibuat.

Struktur Video

Video harus mencakup poin-poin berikut.

1. Arsitektur Program

• Jelaskan singkat arsitektur aplikasi (struktur folder/project, tech stack yang dipilih).
• Jelaskan pembagian modul, misalnya: Trie, Levenshtein DP, Word Segmentation DP, UI/Editor.
• Jelaskan alur data: dari kamus.json di-load, dibangun jadi Trie, sampai dipakai ketiga fitur.

2. Demonstrasi Fitur Wajib

• Load kamus & statistik Trie di UI (tunjukkan angkanya begitu aplikasi start).
• Autocomplete real-time (ketik prefix, dropdown top-5 muncul, uji Tab dan Enter).
• Spell check di editor (ketik typo, garis merah muncul, klik untuk saran, uji "Tambah ke kamus", uji tombol "Check All").
• Word Segmentation / Auto-Space (paste string tanpa spasi, tampilkan array dp[] dan trace-back-nya, bukan cuma hasil akhir).

3. Penjelasan Levenshtein Edit Distance

• Jelaskan basis dan relasi rekurens sambil ditunjukkan di layar.
• Jelaskan mengenai Levenshtein Edit Distance.

4. Penjelasan Word Segmentation

• Jelaskan basis dan relasi rekurens.
• Jelaskan mengenai Word Segmentation.

5. Demonstrasi Fitur Bonus (kalau dikerjakan)

• Smart Trim: jelaskan basis/rekurens Knapsack-nya, demo hasil trim dengan beberapa batas karakter berbeda.
• Bigram: demo perbedaan urutan autocomplete saat toggle ON vs OFF setelah mengetik beberapa pasangan kata berulang.

6. UI/UX Showcase

• Tunjukkan keseluruhan antarmuka aplikasi, navigasi antar panel, dan kemudahan pemakaian secara umum.

Teknis Video

• Durasi maksimum 20 menit.
• Wajib disertai penjelasan suara (voice-over). Subtitle disarankan tapi tidak wajib.
• Fokus penjelasan ke implementasi algoritma dan cara kerja fitur, bukan cuma memperlihatkan hasil akhir.
• Video bisa diunggah ke YouTube (Public/Unlisted) atau Google Drive yang bisa diakses asisten.
• Tautan video wajib dicantumkan di README repository.
• Resolusi video minimal 720p.

Penilaian

Tipe	Aspek	Nilai Maksimum
Spesifikasi Wajib	Trie & Statistik	450
	Autocomplete	300
	Levenshtein Edit Distance & Spell Check Editor	1200
	Word Segmentation	600
	Dokumentasi	350
Spesifikasi Bonus	Smart Trim	450
	Bigram Language Model	600
Demonstrasi	Video Demo	450
Total Maksimum		4400

Pengerjaan dan Pengumpulan

1. Buatlah repositori private pada GitHub masing-masing dan invite Inforable dalam repositori tersebut.
2. Berkas yang dikumpulkan berupa link rilis tag ke repositori GitHub yang telah dibuat dengan ketentuan sebagai berikut.
   • Memberikan tag vn pada commit terakhir setiap kali ingin melakukan submisi, dengan n adalah jumlah submisi yang telah dilakukan. (contoh: v1 untuk submisi pertama).
   • Tidak menggunakan url shortener (bit.ly, shortlink, atau yang lain) saat melakukan pengumpulan task.
   • Panduan rilis bisa dilihat di sini.
3. Lakukan submisi pada website seleksi IRK menggunakan akun std.stei.itb.ac.id, sertakan link video demo (lihat bagian Video Demo), dan lakukan konfirmasi ke LINE @hasrifayadhmuqaffa.
4. Submisi hanya dapat dilakukan sekali saja, tetapi bisa ditarik kembali submisinya sebelum dikunci asisten atau nilai akhir dirilis. Di lain sisi, calon bisa koordinasi lebih dengan LINE @hasrifayadhmuqaffa jika perlu menghapuskan submisi untuk menggantikan submisi yang salah atau semacamnya.
5. Pertanyaan dan hint bisa langsung ke LINE @hasrifayadhmuqaffa.

Referensi

• KBBI V Dataset — aryakdaniswara/kbbi-dataset-kbbi-v
• Frequency Distribution Bahasa Indonesia dari korpus Wikipedia — ardwort/freq-dist-id
• Trie (insert & search) — GeeksforGeeks: Trie | (Insert and Search).
• Levenshtein Edit Distance — GeeksforGeeks: Edit Distance.
• 0/1 Knapsack (dasar Smart Trim) — GeeksforGeeks: 0/1 Knapsack Problem.
• Word Break Problem — GeeksforGeeks: Word Break Problem.
• Inverse Document Frequency / IDF (Spärck Jones, 1972) — Manning, Raghavan & Schütze: Introduction to Information Retrieval — Inverse document frequency.
• N-gram / Bigram Language Model — Jurafsky & Martin: Speech and Language Processing (SLP3), Bab 3 — N-gram Language Models.