خوارزمية CYK

الخوارزمية مكتوبة بلغة شبه رمزية كما يلي:

ليكن المدخل سلسلة نصية I تتكون من n حرفًا: a1 ... an . ولتكن القواعد النحوية تحتوي على r رمزًا غير طرفي R1 ... Rr، حيث R1 هو رمز البداية. ولتكن P[n, n, r ] مصفوفة من القيم المنطقية . قم بتهيئة جميع عناصر P إلى خطأ . ولتكن back [n, n , r ] مصفوفة من قوائم من ثلاثيات تشير إلى الخلف . قم بتهيئة جميع عناصر back إلى قائمة فارغة.لكل قيمة s من 1 إلى n، ولكل وحدة إنتاج R v → a s، اجعل P [ 1 , s , v ] = صحيحًا لكل l = 2 إلى n -- طول المدى لكل s = 1 إلى n - l + 1 -- بداية المدى لكل p = 1 إلى l - 1 تقسيم المدى لكل إنتاج R a → R b R c إذا كان P [ p , s , b ] و P [ l - p , s + p , c ] ، فضع P [ l , s , a ] = صحيح. أضف <p,b,c> إلى الخلف [ l , s , a ] إذا كانت P [n, 1 , 1 ] صحيحة، فإن I ينتمي إلى اللغة، لذا يُعاد تنفيذ الدالة back . من خلال تتبع الخطوات السابقة، يمكن بسهولة إنشاء جميع أشجار التحليل الممكنة للسلسلة. وإلا، تُعاد الدالة "ليس ينتمي إلى اللغة".

ليكن المدخل سلسلة نصية I تتكون من n حرفًا: a1 ... an . ولتكن القواعد النحوية تحتوي على r رمزًا غير طرفي R1 ... Rr، حيث R1 هو رمز البداية. ولتكن P[n, n , r ] مصفوفة من الأعداد الحقيقية . قم بتهيئة جميع عناصر P إلى الصفر . ولتكن back [ n , n , r ] مصفوفة من ثلاثيات الإشارة العكسية . لكل s = 1 إلى n، لكل وحدة إنتاج R v → a s، اجعل P [ 1 , s , v ] = Pr( R v → a s ). لكل l = 2 إلى n ، طول النطاق. لكل s = 1 إلى n - l + 1 ، بداية النطاق. لكل p = 1 إلى l - 1 ، تقسيم النطاق. لكل وحدة إنتاج R a → R b R c ، يكون احتمال التقسيم = Pr( R a → R b R c ) * P [ p , s , b ] * P [ l - p , s + p , c ]. إذا كان احتمال التقسيم > P [ l , s , a ] ، فاجعل P [ l , s , a ] = احتمال التقسيم. اجعل back [ l , s , a ] = <p, b, c>إذا كانت P [n, 1 , 1 ] > 0 ، فابحث عن شجرة التحليل بالرجوع إلى الوراء ، ثم أعد شجرة التحليل، وإلا فأعد "ليس عضوًا في اللغة".

بصورة غير رسمية، تأخذ هذه الخوارزمية في الاعتبار كل سلسلة فرعية ممكنة من سلسلة الإدخال وتحدد${\displaystyle P[l,s,v]}$يكون صحيحًا إذا كانت السلسلة الفرعية ذات الطول${\displaystyle l}$ابتداءً من${\displaystyle s}$يمكن توليدها من الرمز غير الطرفي${\displaystyle R_{v}}$بعد معالجة السلاسل الفرعية ذات الطول 1، ينتقل إلى السلاسل الفرعية ذات الطول 2، وهكذا. بالنسبة للسلاسل الفرعية ذات الطول 2 فأكثر، يُدرس كل تقسيم ممكن للسلسلة الفرعية إلى جزأين، ويتحقق من وجود قاعدة إنتاجية.${\displaystyle A\to B\;C}$بحيث${\displaystyle B}$يتطابق مع الجزء الأول و${\displaystyle C}$يتطابق مع الجزء الثاني. إذا كان الأمر كذلك، فإنه يسجل${\displaystyle A}$بمجرد اكتمال هذه العملية، يتم إنشاء سلسلة الإدخال بواسطة القواعد النحوية إذا تطابقت السلسلة الفرعية التي تحتوي على سلسلة الإدخال بأكملها مع رمز البداية.

الخوارزمية المذكورة أعلاه هي أداة تمييز تحدد فقط ما إذا كانت الجملة تنتمي إلى اللغة. من السهل توسيعها لتصبح محللاً نحوياً يقوم أيضاً بإنشاء شجرة تحليل ، وذلك بتخزين عقد شجرة التحليل كعناصر في المصفوفة، بدلاً من القيمة المنطقية 1. ترتبط العقدة بعناصر المصفوفة التي استُخدمت لإنتاجها، وذلك لبناء بنية الشجرة. يكفي وجود عقدة واحدة فقط في كل عنصر من عناصر المصفوفة إذا كان المطلوب إنتاج شجرة تحليل واحدة فقط. مع ذلك، إذا كان المطلوب الاحتفاظ بجميع أشجار تحليل الجملة الغامضة، فمن الضروري تخزين قائمة في عنصر المصفوفة بجميع الطرق التي يمكن من خلالها الحصول على العقدة المقابلة في عملية التحليل. يتم ذلك أحياناً باستخدام جدول ثانٍ B[n,n,r] لما يُسمى بالمؤشرات الخلفية . والنتيجة النهائية هي غابة مشتركة من أشجار التحليل الممكنة، حيث يتم دمج أجزاء الأشجار المشتركة بين عمليات التحليل المختلفة. يمكن قراءة هذه الغابة المشتركة بسهولة على أنها قواعد نحوية غامضة تولد فقط الجملة التي تم تحليلها، ولكن بنفس الغموض الذي تتسم به القواعد النحوية الأصلية، ونفس أشجار التحليل حتى إعادة تسمية بسيطة للغاية للرموز غير الطرفية، كما هو موضح من قبل لانغ (1994) .

كما أشار لانج وليس (2009) ، فإن عيب جميع التحويلات المعروفة إلى صيغة تشومسكي العادية هو أنها قد تؤدي إلى تضخم غير مرغوب فيه في حجم القواعد النحوية. حجم القواعد النحوية هو مجموع أحجام قواعد الإنتاج الخاصة بها، حيث يكون حجم القاعدة واحدًا زائد طول جانبها الأيمن. باستخدام${\displaystyle g}$للدلالة على حجم القواعد الأصلية، قد يتراوح حجم التضخم في أسوأ الحالات من${\displaystyle g^{2}}$ل${\displaystyle 2^{2g}}$، وذلك بحسب خوارزمية التحويل المستخدمة. وللاستخدام في التدريس، يقترح لانج وليس تعميمًا طفيفًا لخوارزمية CYK، "دون المساس بكفاءة الخوارزمية أو وضوح عرضها أو بساطة البراهين" ( لانج وليس 2009 ) .

من الممكن أيضًا توسيع خوارزمية CYK لتحليل السلاسل النصية باستخدام قواعد نحوية موزونة وعشوائية خالية من السياق . تُخزَّن الأوزان (الاحتمالات) في الجدول P بدلًا من القيم المنطقية، لذا سيحتوي P[i,j,A] على أقل وزن (أعلى احتمال) يمكن من خلاله اشتقاق السلسلة الفرعية من i إلى j من A. تسمح امتدادات أخرى للخوارزمية بترقيم جميع تحليلات السلسلة النصية من أقل وزن إلى أعلى وزن (من أعلى احتمال إلى أقل احتمال).

أسوأ وقت تشغيل لـ CYK هو${\displaystyle \Theta (n^{3}\cdot |G|)}$حيث n هو طول السلسلة المُحللة و| G | هو حجم قواعد اللغة CNF G. وهذا ما يجعلها من أكثر الخوارزميات كفاءةً للتعرف على لغات السياق العام في التطبيق العملي. قدّم فاليانت (1975) امتدادًا لخوارزمية CYK. تحسب خوارزميته نفس جدول التحليل الذي تحسبه خوارزمية CYK؛ ومع ذلك، فقد بيّن أنه يمكن استخدام خوارزميات الضرب الفعال للمصفوفات ذات المدخلات 0-1 لإجراء هذا الحساب.

باستخدام خوارزمية كوبرسميث-وينوغراد لضرب هذه المصفوفات، ينتج عن ذلك وقت تشغيل تقاربي في أسوأ الحالات يبلغ${\displaystyle O(n^{2.38}\cdot |G|)}$مع ذلك، فإن الحد الثابت الذي تخفيه صيغة Big O كبير جدًا لدرجة أن خوارزمية Coppersmith-Winograd لا تُجدي نفعًا إلا مع المصفوفات الكبيرة جدًا التي يصعب على الحواسيب الحالية التعامل معها ( Knuth 1997 ) ، ويتطلب هذا النهج الطرح، لذا فهو مناسب فقط للتعرف. ولا يمكن تجنب الاعتماد على ضرب المصفوفات بكفاءة تمامًا: فقد أثبت Lee (2002) أن أي محلل نحوي لقواعد اللغة الخالية من السياق يعمل في وقت${\displaystyle O(n^{3-\varepsilon }\cdot |G|)}$يمكن تحويلها بشكل فعال إلى خوارزمية لحساب ناتج${\displaystyle (n\times n)}$المصفوفات ذات المدخلات 0-1 في الزمن${\displaystyle O(n^{3-\varepsilon /3})}$وقد تم توسيع هذا بواسطة Abboud et al. ^{[ 4 ]} ليطبق على قواعد نحوية ذات حجم ثابت.