Analisis Kompeksitas Algoritma CYK untuk Aplikasi dalam Pemrosesan Bahasa Indonesia

Rizky Maulana; Armadha Pringgadani; Randi Nova Liza; Restu Adji Winaza; Luthfi A'mal Fadhilah; Ayisa Rahmadani Fitria; Jea Piska; Julio Ricko Rivaldo Ra'u; Muhammad Rafli Risyaputra; Faisal Aristia

doi:10.31004/riggs.v4i4.4568

Authors

Rizky Maulana Universitas Mulawarman
Armadha Pringgadani Universitas Mulawarman
Randi Nova Liza Universitas Mulawarman
Restu Adji Winaza Universitas Mulawarman
Luthfi A'mal Fadhilah Universitas Mulawarman
Ayisa Rahmadani Fitria Universitas Mulawarman
Jea Piska Universitas Mulawarman
Julio Ricko Rivaldo Ra'u Universitas Mulawarman
Muhammad Rafli Risyaputra Universitas Mulawarman
Faisal Aristia Universitas Mulawarman

DOI:

https://doi.org/10.31004/riggs.v4i4.4568

Keywords:

Algoritma CYK, Parsing, NLP, Grammar CNF, Bahasa Indonesia

Abstract

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.

Downloads

Download data is not yet available.

References

Aho, A., & Ullman, J. (1973). The Theory of Parshing, Translation, and Compiling. Prentice-Hall, Inc.Division of Simon and Schuster One Lake Street Upper Saddle River, NJUnited States.

Dall’O’, G. (2013). Speech and Language Processing. Green Energy and Technology, 146, 1–5. https://doi.org/10.1007/978-1-4471-5064-0_1

Earley, J. (1970). An Efficient Context-Free Parsing Algorithm. Communications of the ACM, 13(2), 94–102. https://doi.org/10.1145/362007.362035

Firsov, D., & Uustalu, T. (2014). Certified CYK parsing of context-free languages. Journal of Logical and Algebraic Methods in Programming, 83(5–6), 459–468. https://doi.org/10.1016/j.jlamp.2014.09.002

Huang, L., Chiang, D., & Park, C. (2005). Better k-best Parsing. ACL Anthology, 53–64.

Li, Y., Chen, T., & Liu, D. (2020). Path planning for laser cladding robot on artificial joint surface based on topology reconstruction. Algorithms, 13(4). https://doi.org/10.3390/A13040093

Petrov, S., & Klein, D. (2007). Improved inference for unlexicalized parsing. NAACL HLT 2007 - Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics, Proceedings of the Main Conference, April, 404–411.

Prabowo, B., Rustamadji, H. C., & Fauziah, Y. (2020). Algoritma Cocke Younger Kasami Untuk Deteksi Struktur Kalimat Dan Merekomendasikanya Menggunakan Algoritma Damerau Levenshtein Distance. Telematika, 17(2), 111. https://doi.org/10.31315/telematika.v1i1.3378

Roark, B., Bodenstab, N., & Hollingshead, K. (2012). Finite-state chart constraints for reduced complexity context-free parsing pipelines. Computational Linguistics, 38(4), 719–753. https://doi.org/10.1162/COLI_a_00109

Roark, B. E. (2001). Robust Probabilistic Predictive Syntactic Processing : Motivations, Models, and Applications. May.

Siddharthan, A. (2002). Foundations of Statistical Natural Language Processing. In Nat. Lang. Eng. (Vol. 8, Issue 1). http://dx.doi.org/10.1017/S1351324902212851

Sulianto, T. T., & Herawati, R. (2021). the Implementation of Cyk Algorithm To Separate Sentence-Forming Elements in Indonesian. Proxies : Jurnal Informatika, 2(2), 52. https://doi.org/10.24167/proxies.v2i2.3210

Valiant, L. G. (1975). General context-free recognition in less than cubic time. Journal of Computer and System Sciences, 10(2), 308–315. https://doi.org/10.1016/S0022-0000(75)80046-8

Yi, Y., Lai, C. Y., Petrov, S., & Keutzer, K. (2011). Efficient parallel CKY parsing on GPUs. IWPT 2011 - Proceedings of the 12th International Conference on Parsing Technologies, 175–185.

Zanzotto, F. M., Satta, G., & Cristini, G. (2020). Cyk parsing over distributed representations. Algorithms, 13(10), 1–17. https://doi.org/10.3390/a13100262