تعقيد البحث بالحزمة

الخطوة 1: فهم المدخلات. يتطلب الحساب ثلاثة مدخلات: عرض الحزمة (beamWidth)، طول التسلسل (seqLen)، وحجم المفردات (vocabSize). عرض الحزمة هو عدد الفرضيات (المسارات) التي يتم الاحتفاظ بها في كل خطوة زمنية. طول التسلسل هو عدد الخطوات الزمنية في عملية فك التشفير (طول الجملة الناتجة). حجم المفردات هو عدد الكلمات أو الرموز المحتملة في القاموس. هذه القيم تحدد مدى تعقيد عملية البحث.

الخطوة 2: حساب عدد التوسعات لكل خطوة زمنية. في كل خطوة زمنية، يتم توسيع كل فرضية من الفرضيات الحالية (عددها beamWidth) باستخدام كل رمز من حجم المفردات (vocabSize). وبالتالي، عدد التوسعات لكل خطوة = beamWidth × vocabSize. على سبيل المثال، إذا كان عرض الحزمة 5 وحجم المفردات 50000، فسيتم تقييم 250000 مرشح جديد في كل خطوة.

الخطوة 3: حساب التعقيد الكلي. يتم ضرب التوسعات لكل خطوة بعدد الخطوات الزمنية (seqLen). لذا فإن التعقيد الإجمالي = beamWidth × seqLen × vocabSize. هذا الرقم يمثل العدد الإجمالي للمرشحين الذين يتم تقييم درجاتهم خلال عملية فك التشفير بأكملها. ملاحظة: هذا لا يشمل تعقيد عملية الاختيار (اختيار أفضل B مرشح من بين B×V مرشح)، ولكن العامل المهيمن هو هذا الضرب. التعقيد الفعلي قد يتضمن عاملاً لوغاريتمياً إضافياً إذا تم استخدام الفرز أو الكومة لاختيار أفضل الفرضيات.