خوارزمية CYK
Sign in to saveAlso known as Cocke–Younger–Kasami algorithm, CKY algorithm, CYK parsing, CKY parsing
parsing algorithm for context-free grammars
Article · العربية
خوارزمية كوك-يونغير-كاسامي Cocke-Younger-Kasami (وتسمى أيضاً CKY) هي خوارزمية تحليل نحوي تنتمي للقواعد النحوية الخالية من السياق في علوم الحاسوب، وقد سميت باسم مخترعيها، جون كوك، دانيال يونغير وتاداو كسامي. وهي تستخدم في التحليل من الأسفل إلى الأعلى والبرمجة الديناميكية. يعمل الإصدار القياسي من الخوارزمية فقط على القواعد الخالية من السياق في نموذج تشومسكي الطبيعي (CNF). ومع ذلك، يمكن تحويل أي قواعد نحوية خالية من السياق إلى قواعد CNF معبرة عن نفس اللغة. تنبع أهمية خوارزمية (CYK) من كفاءتها العالية في مواقف معينة. إذا ما قيمنا كفاءة عملها بواسطة مقياس التعقيد الحسابي Big O، فإن اسوء حالة تشغيل يمكن الحصول عليها في خوارزمية CYK هي ، حيث تمثل n طول الجملة المراد تحليلها فيما تمثل G حجم القواعد ضمن نموذج تشومسكي الطبيعي الذي يتم العمل عليه. ويجعلها هذا إحدى أكثر خوارزميات التحليل النحوي فاعلية، من ناحية التعقيد الحسابي.
Abstract from DBpedia / Wikipedia · CC BY-SA