Analisis Kompeksitas Algoritma CYK untuk Aplikasi dalam Pemrosesan Bahasa Indonesia - Maulana, Rizky; Pringgadani, Armadha; Liza, Randi Nova; Winaza, Restu Adji; Fadhilah, Luthfi A'mal; Fitria, Ayisa Rahmadani; Piska, Jea; Ra'u, Julio Ricko Rivaldo; Risyaputra, Muhammad Rafli; Aristia, Faisal (RIGGS: Journal of Artificial Intelligence and Digital Business, 2026)
Pemrosesan Bahasa Alami (Natural Language Processing/NLP) memerlukan parser sintaksis yang mampu menganalisis struktur kalimat secara akurat dan transparan. Salah satu algoritma klasik yang masih banyak digunakan dalam parsing berbasis Context-Free Grammar (CFG) adalah algoritma Cocke–Younger–Kasami (CYK). Meskipun bersifat deterministik dan menjamin validitas struktur sintaksis, algoritma CYK memiliki kompleksitas komputasi yang tinggi, terutama ketika panjang kalimat dan ukuran grammar meningkat. Penelitian ini bertujuan untuk menganalisis kompleksitas algoritma CYK secara teoretis dan empiris dalam proses parsing kalimat Bahasa Indonesia, serta mengevaluasi pengaruh panjang kalimat dan ukuran grammar terhadap performa algoritma. Metode penelitian yang digunakan adalah pendekatan kuantitatif-eksperimental dengan mengimplementasikan parser CYK berbasis Chomsky Normal Form (CNF) menggunakan bahasa pemrograman Python. Data uji terdiri atas kalimat Bahasa Indonesia dengan variasi struktur sintaksis, meliputi kalimat dasar, majemuk setara, majemuk bertingkat, inversi, dan konstruksi pasif. Variabel eksperimen mencakup panjang kalimat, ukuran grammar, waktu eksekusi, dan akurasi parsing. Hasil penelitian menunjukkan bahwa waktu eksekusi meningkat secara signifikan seiring bertambahnya panjang kalimat, sejalan dengan kompleksitas teoretis O(n³·|G|) algoritma CYK. Selain itu, grammar berukuran besar menghasilkan akurasi parsing yang lebih tinggi, namun diiringi peningkatan beban komputasi. Dari sisi struktur sintaksis, algoritma CYK bekerja paling optimal pada kalimat berpola dasar dan mengalami penurunan akurasi pada struktur yang lebih kompleks. Temuan ini menegaskan adanya trade-off antara efisiensi dan akurasi dalam penggunaan algoritma CYK. Secara keseluruhan, penelitian ini menyimpulkan bahwa algoritma CYK masih relevan dan layak digunakan dalam aplikasi NLP Bahasa Indonesia, khususnya pada sistem yang menuntut keterjelasan proses analisis sintaksis, dengan catatan didukung oleh strategi optimasi yang sesuai.