تقطيع سلسلة بقاموس محدد: حدود الوصول وشاهد يغطي النص كله

تغطية السلسلة من قاموس معلن

لدينا سلسلة رموز وقاموس يحتوي عناصر غير فارغة، ونريد معرفة هل يمكن تقسيم السلسلة كلها إلى هذه العناصر بالترتيب. كل جزء يجب أن يكون مقطعًا متصلًا مطابقًا لعنصر في القاموس، والأجزاء تتجاور دون فراغ غير مغطى أو تداخل. لا يكفي العثور على كلمة واحدة داخل السلسلة أو تغطية بدايتها ثم ترك الباقي؛ السؤال عن النص كاملًا.

تعرض مسألة CSES المسماة Word Combinations إنشاء سلسلة من كلمات قاموس، ويعرف تمرين Stanford CS221 تجزئة السلسلة إلى عناصر قاموس مع أهداف اختيار مختلفة. سنستعمل هذا التعريف في مثال مؤلف، لكن مخرجنا إمكانية التقطيع وشاهد واحد. لا نحسب هنا كل الطرق أو درجة طلاقة لغوية أو أقل عدد كلمات، ولا ننقل أمثلة المصادر أو حلولها.

الكلمة في هذا المقال تعني مدخلًا معلنًا في القاموس، وقد تكون رمزًا مؤلفًا لا كلمة لغوية مستقلة. نختار رموزًا لاتينية صغيرة ليسهل مراجعة المواضع، ونعامل المساواة حرفيًا. الهدف أن نفهم حدود الأجزاء وسبب نجاح شاهد أو فشله، دون تحويل قبول السلسلة بالقاموس إلى حكم عن صحة اللغة أو معنى عبارة لم نفحصها.

مسألة الإنشاء بالقاموس، تعريف التقطيع وأهدافه.

مثال redbluered وثلاثة مداخل

نختار السلسلة redbluered، والقاموس الذي يحتوي red و blue و redblue. طول السلسلة عشرة رموز: ثلاثة للأولى red، ثم أربعة لـ blue، ثم ثلاثة لـ red الأخيرة. يمكن أن نقسمها إلى red ثم blue ثم red، ويمكن أيضًا إلى redblue ثم red. كلا الشاهدين يستخدم مداخل القاموس ويعيد السلسلة نفسها عند ضم أجزائه بالترتيب.

لا نحتاج استعمال جميع مداخل القاموس في الشاهد، ولا نعد redblue كلمة جديدة صنعناها بجمع red و blue ثم أضفناها سرًا؛ هي مدخل موجود منذ البداية. هذه المعلومة هي التي تسمح بالتقطيع الثاني ذي الجزأين. إذا حذفنا ذلك المدخل من القاموس، يبقى الشاهد ذو الثلاثة أجزاء صالحًا، لكن لا يبقى redblue جزءًا مسموحًا وحده.

نرقم حدود السلسلة من صفر إلى عشرة. الجزء red الأول بين صفر وثلاثة، و blue بين ثلاثة وسبعة، و red الأخير بين سبعة وعشرة. الحدود تصف ما قبل الرموز وبعدها؛ ليست كل حدود الوصول رموزًا يمكن قراءتها. الحد عشرة بعد آخر رمز، بينما الموضع تسعة يحمل آخر d. نثبت هذه الطريقة قبل تسجيل الأجزاء أو الرجوع في الشاهد.

حدود الوصول بدل أسماء الحروف

نحفظ عند كل حد جوابًا: هل يمكن تقسيم البادئة التي تنتهي قبله بالكامل من القاموس؟ عند الحد صفر تكون البادئة فارغة، وهي قابلة للتقسيم إلى قائمة أجزاء فارغة. لذلك نبدأ بنعم عند صفر. بقية الحدود تبدأ بلا وصول مثبت، ثم نراجع إن كان مدخل قاموس كامل يصل إليها من حد سابق قابل للوصول.

في مثالنا لا يصل القاموس إلى الحد واحد أو اثنين، لأنه لا يحتوي r أو re. ومع ذلك يصل إلى ثلاثة بمدخل red من الحد صفر. عدم الوصول إلى حد داخلي في الكلمة لا يمنع استعمال الكلمة كلها؛ لا نشترط أن يكون كل حرف منفرد مدخل قاموس. نراجع القفزة من بداية الجزء إلى نهايته كوحدة مطابقة.

الحد القابل للوصول يثبت بادئة فقط، ولا يثبت أن بقية السلسلة يمكن استكمالها. لذلك لا نتوقف بالنجاح عند ثلاثة أو سبعة في سلسلة طولها عشرة. النجاح النهائي يتطلب الوصول إلى حد الطول نفسه. ونحتفظ بالحدود السابقة لأن بعضها قد يفتح استمرارًا صحيحًا بينما يعجز استمرار من حد آخر، كما سيظهر في المثال الذي يفشل فيه الاختيار الجشع.

كلمة أخيرة من حد سابق

لمراجعة حد توقف j، نجرب حد بداية i أصغر منه. إذا كانت البادئة حتى i قابلة للتقسيم، وكان المقطع من i إلى ما قبل j داخل القاموس، فإن إضافة هذا المقطع تعطي تقسيمًا كاملًا للبادئة حتى j. يكفي وجود بداية واحدة تحقق الشرطين للإجابة بنعم عن هذا الحد. لا نجمع أسماء الكلمات أو أطوالها دون فحص المقطع الذي يقع بينها.

نمر على حدود التوقف من الأصغر إلى الأكبر، حتى نكون قد عرفنا إمكان البداية التي نقرأها. الكلمات غير فارغة تجعل i أصغر من j دائمًا، فتتقدم الانتقالات نحو نهاية السلسلة. إذا سمحنا بجزء فارغ يعيد الحد إلى نفسه، نحتاج عقدًا آخر لعدد الطرق وأثر الرجوع؛ تنفيذنا يرفض هذا المدخل ضمن الشروط المعلنة.

وعندما يصل حد لأول مرة، نحفظ بداية الجزء الذي أثبت وصوله. في تنفيذنا نجرب البدايات بالترتيب الصاعد ونحتفظ بأول نجاح عند الحد، لكن هذه سياسة لشاهد ممكن، وليست تقليلًا لعدد الأجزاء. حالة نعم لا تخبرنا عدد التقسيمات أو جودتها اللغوية. سنراجع الشاهد نفسه كي نرى ما الذي اختارته السياسة بالفعل.

الوصول إلى ثلاثة وسبعة وعشرة

عند الحد ثلاثة نجد المقطع من صفر إلى ثلاثة هو red، وهو في القاموس، والبداية صفر قابلة للوصول. نحفظ السابق صفرًا ونثبت الوصول إلى ثلاثة. الحدود التي تقع داخل blue لا تعطي مداخل إضافية في قاموسنا، لكن الحد سبعة يصل إليه مدخل redblue من صفر. يوجد كذلك طريق إليه من ثلاثة بكلمة blue.

تجريب البدايات من الصفر يجعل الشاهد المحفوظ عند سبعة هو الجزء redblue، مع السابق صفرًا. لا يعني هذا حذف إمكان red ثم blue؛ الشاهد الثاني ما زال تقسيمًا صحيحًا للبادئة نفسها، لكن خانة نعم والسابق الواحد لا يحتفظان به كاملًا. هذه نقطة نفصل فيها الإمكانية من تعداد جميع الطرق أو عرض كل تفسير للبادئة.

عند الحد عشرة لا تكون السلسلة كلها مدخلًا في القاموس، لكن red بين سبعة وعشرة مدخل صالح، وسبعة قابل للوصول. لذلك نثبت الوصول إلى عشرة ونسجل سابقه سبعة. حدود الوصول النهائية هي صفر وثلاثة وسبعة وعشرة. نجاح الحد الأخير يجيب عن السلسلة كلها، مع بقاء الحدود الأخرى معلومات تساعد على تفسير كيفية الوصول.

رجوع يغطي النص دون فجوات

نبدأ من عشرة ونقرأ السابق سبعة، فنحفظ الجزء بينهما red. ثم نرجع إلى سبعة ونقرأ السابق صفرًا، فنحفظ redblue. وصلنا إلى حد البداية، فانتهى الرجوع. الأجزاء التي جمعناها من النهاية هي red ثم redblue، ونعكسها للعرض الأمامي إلى redblue ثم red. ضمها يعيد redbluered تمامًا.

حدود الشاهد المعروض هي من صفر إلى سبعة، ثم من سبعة إلى عشرة، ببداية مشمولة وتوقف غير مشمول لكل مقطع. نهاية الجزء الأول هي بداية الثاني، فلا يوجد رمز متروك أو جزء محسوب مرتين. نراجع كل مقطع حرفيًا في القاموس، ونراجع أول بداية صفرًا وآخر توقف مساويًا طول النص، بدل الاكتفاء بأن مجموع الطولين يساوي عشرة.

يمكن حفظ الأجزاء نفسها والحدود معًا. الأجزاء تساعد على القراءة، والحدود تبين مواقعها في النسخة الأصلية. لا نستعمل فهارس نص أضفنا إليه فراغات العرض كأنها فهارس السلسلة غير المفصولة. إذا عرضنا redblue ثم red مع فاصل توضيحي، يبقى الحد سبعة متعلقًا بالنص الأصلي، لا بمكانه بعد إدخال الفاصل على الشاشة.

إعادة مدخل القاموس ليست إعادة عنصر مخزون

القاموس هنا مجموعة أنواع نصية مسموحة، وليس قائمة قطع تنفد بعد استخدامها. لذلك التقطيع red ثم blue ثم red يستطيع استعمال المدخل red في موضعين مختلفين من السلسلة، رغم أنه مسجل مرة واحدة في القاموس. كل استعمال يطابق مقطعًا جديدًا في موقعه، ولا يكرر استهلاك رموز الجزء السابق نفسه.

إذا أردنا منع إعادة استخدام كلمة أكثر من عدد معين، نحتاج حالة تحفظ الكمية المتبقية أو شروطًا أخرى. مجرد حد الوصول لا يكفي ليعرف كم مرة استعملنا كل مدخل في الشاهد السابق. لذلك لا ننقل خوارزمية القاموس القابل لإعادة الاستخدام إلى سؤال مخزون محدود ثم نفسر كل جواب نعم بأنه احترم حدود الكميات التي لم نحفظها.

كذلك لا يكفي حل سؤال أطوال العناصر. قاموس يحتوي xyz و abcd يملك طولين ثلاثة وأربعة، ويمكن ترتيب هذه الأطوال لتجمع إلى عشرة، لكن أيًا من هذين النصين لا يطابق الأجزاء اللازمة في redbluered. فحص الحروف المتصلة جزء أساسي من المهمة، ولا تتحول مساواة مجموع الأطوال إلى شهادة تغطية للسلسلة المعطاة.

بادئة صحيحة ونهاية لا تصل

نغير السلسلة إلى redbluerex ونبقي القاموس نفسه. تصل البادئة red إلى ثلاثة، ويصل redblue إلى سبعة، لكن المقطع الأخير rex ليس في القاموس. لا نجد بداية قابلة للوصول يطابق منها مدخل إلى نهاية النص، فيبقى الحد عشرة غير قابل للوصول. حدود الوصول الموجودة صفر وثلاثة وسبعة لا تكفي لإعلان النجاح الكامل.

نفرق في المخرج بين غياب تقسيم كامل وبين شاهد فارغ صالح للنص الفارغ. في هذه السلسلة غير الفارغة الفاشلة لا نعيد قائمة كلمات نعرف أنها غطت جزءًا فقط ثم نسميها شاهدًا للنص كله. قد يكون عرض البادئة مفيدًا للتشخيص، لكن ينبغي تسمية ما تغطيه والجزء الذي بقي خارج أي شاهد مكتمل.

لا يثبت الفشل أن rex ليست كلمة في لغة ما أو أن النص خطأ إملائي. ما أثبتناه أنها لم تُغطّ من القاموس الذي أعطيناه لهذا السؤال. إذا أضفنا rex إلى القاموس، فقد يتغير جواب النسخة الجديدة. لذلك نحفظ محتويات القاموس مع النص والنتيجة، ونقرأ لا بوصفها حكمًا نسبيًا إلى تلك البيانات المحددة.

أطول كلمة أولًا قد تسد الاستمرار

نختار السلسلة blueberry وقاموسًا يحتوي blueb و blue و berry. أطول مدخل يطابق البداية هو blueb بطول خمسة. إذا التزمنا به فورًا، بقي erry الذي لا يغطّيه القاموس، فيفشل هذا الفرع. لكن blue بطول أربعة يترك berry، وهو مدخل صالح، لذلك يوجد تقسيم كامل من blue ثم berry.

حدا أربعة وخمسة كلاهما قابل للوصول؛ الأول من blue والثاني من blueb. لا نرمي الأربعة لأننا وجدنا قفزة أطول إلى خمسة. عند النهاية تسعة، نجد استمرارًا من أربعة إلى تسعة بكلمة berry، ونحفظ هذا الطريق. الصورة الثانية تعرض الفرع الذي توقف والبداية الأقصر التي اكتمل منها النص، مع الكلمات وحدودها المعلنة.

هذا مثال مؤلف يبين أن اختيار أطول مطابقة محلية لا يثبت تغطية الباقي. لا يعني أن كل سياسة جشعة تفشل في كل بيانات، ولا أننا شغلنا محلل لغة على الكلمة. وجود مدخل blueb في القاموس التعليمي جزء من تعريف التجربة، حتى إن لم نعطه تفسيرًا لغويًا طبيعيًا. معيار القبول هنا العضوية الحرفية في مجموعة معلنة.

عرض الرسم بالحجم الكامل

شاهد محفوظ ليس كل الطرق أو أقلها

في redbluered يوجد تقسيمان كاملان في قاموسنا: redblue ثم red، أو red ثم blue ثم red. تنفيذ الإمكانية يعرض أحدهما، ولا يحفظ في قيمة نعم أن العدد اثنان. مسألة CSES المرجعية تسأل عن عدد التركيبات بباقي قسمة، وهذا مخرج مختلف. لا نستعمل السابق الواحد الذي حفظناه دليلًا أن التقسيم المعروض هو الوحيد.

وقد لا يكون أول شاهد أقل عدد أجزاء. نختار مثالًا مستقلًا abcde مع القاموس a و b و cde و abc و de. يجرب تنفيذنا بدايات الكلمة الأخيرة صعودًا، فيجد cde من الحد اثنين، وكان هذا الحد مغطى بـ a ثم b. فيعيد a ثم b ثم cde، رغم أن abc ثم de تقسيم آخر من جزأين فقط.

إذا كان الهدف تقليل عدد الكلمات أو زيادة الطلاقة بين الكلمات المتجاورة، نحتاج معنى حالة وقاعدة مفاضلة يخصان هذا الهدف. يعرض تمرين Stanford هذه الأهداف المختلفة، ولا نختزلها إلى إمكانية التغطية. في المقال نتأكد من أن الشاهد يحقق العقد البسيط، ونذكر سياسة اختيار أول سابق دون أن ننسب إليها تحسينًا لم تحسبه.

القاموس الفارغ والتكرار والمدخل المخالف

مع قاموس فارغ، لا يمكن تغطية نص غير فارغ، لكن النص الفارغ له تقسيم فارغ صالح. هذا متسق مع حالة الوصول إلى الحد صفر. وإذا كررنا المدخل red في قائمة القاموس، فإن مجموعة النصوص المسموحة لا تتغير، فيبقى جواب الإمكانية والشاهد كما كانا. نعامل المداخل مجموعة، لا تذاكر متعددة تعد طرقًا جديدة لمجرد تكرار السطر.

يرفض تنفيذنا المدخل القاموسي الفارغ، ويرفض عنصرًا غير نصي داخل القاموس، وكذلك يرفض تمرير كلمة واحدة بوصفها مجموعة الكلمات. المثال الأخير مهم لأن قراءة red حرفًا حرفًا قد تنشئ قاموسًا مختلفًا من r و e و d بدل مدخل red واحد. نريد أن تكون بنية المدخل محددة، لا أن يتغير السؤال بسبب طريقة تفكيك قيمة نصية.

الترتيب الذي ترد به الكلمات في القاموس لا يغير العضوية التي نستعملها. سياسة الشاهد هنا مرتبطة بترتيب حدود البداية في السلسلة، وقد تحققنا من ثبات الشاهد عند عكس ترتيب قائمة الكلمات. أما إذا اختار تنفيذ آخر قاعدة تعرض الكلمات بترتيب مختلف أثناء البحث، فنراجع أثرها في الشاهد دون أن نفترض أنها تغير إمكانية وجود تقسيم كامل.

المساواة ووحدة النص ونسخة البيانات

الأمثلة تستعمل رموزًا صغيرة ومساواة حرفية؛ النص RED لا يطابق مدخل red في عقدنا. ولا نحذف الفراغ أو علامة من السلسلة قبل البحث دون تصريح. إذا كانت علامة جزءًا من المدخل، يحتاج المقطع المختار إلى تغطيتها كما وردت، أو يحتاج صاحب المهمة إلى تعريف تحويل سابق وربط حدوده بالنص الأصلي عند عرض النتيجة.

وفي نصوص طبيعية قد تعني الوحدة حرفًا برمجيًا أو وحدة كتابة مرئية أو كلمة مركبة بحسب المهمة. لا تقدم أمثلة red و blue معيارًا لتقطيع العربية أو تقييم نموذج لغوي. نثبت وحدة المقطع وسياسة المساواة والتحويلات قبل تفسير الحدود، ونميز قاموسًا مصطنعًا كامل المعرفة في التجربة من قاموس ناقص قد يحتاج بيانات وقاعدة للتعامل مع المجهول.

والنتيجة تخص نسخة نص وقاموس. إلحاق رمز بالسلسلة قد يبقي بعض حدود البداية كما كانت ويغير النهاية، وحذف مدخل أو إضافته قد يغير الوصول إلى أكثر من حد. لذلك لا نحفظ قائمة كلمات وحدها ثم نرسلها شاهدًا لأي نسخة لاحقة. نربط النص الأصلي والمداخل والحدود والاختيار المحفوظ، ونراجع التغطية من جديد عندما تتغير البيانات.

عدد الحدود لا يقيس زمن التنفيذ وحده

لسلسلة طولها n توجد حدود من صفر إلى n، ونحفظ لكل منها الوصول وسابقًا إن ظهر. في الطريقة البسيطة نجرب بدايات أصغر من كل توقف. إذا استكملنا جميع الأزواج، فعدد المرشحين من مجموع الواحد إلى n، أي n مضروبًا في مجموع n وواحد، ثم مقسومًا على اثنين. قد يتوقف فحص حد مبكرًا عند أول نجاح في تنفيذنا.

لكن عد الأزواج لا يجعل زمن كل فحص ثابتًا في كل بيئة. إنشاء المقطع النصي ومقارنته بمداخل القاموس وحفظ الشاهد أعمال إضافية. لم نقس زمنًا أو نعلن أن الطريقة هي الأفضل لكل نص طويل وقاموس ضخم؛ هدفها أن تظهر علاقة البداية والتوقف والمطابقة والرجوع بوضوح، وأن نستطيع مقارنة نتائجها بمرجع مباشر في الأمثلة الصغيرة.

يمكن لتطبيقات أخرى استعمال بنى أو طرق مطابقة تقلل فحص المقاطع، لكن ذلك يحتاج تنفيذًا ومراجعة لعقده. لم ننفذ هنا شجرة كلمات أو تجزئة احتمالية أو تحديثًا جزئيًا للقاموس. نحفظ نتيجة الإمكانية وشاهدها وحدودها، ولا نضيف إليها ادعاء أن البنية الصغيرة التي عرضناها استوفت متطلبات أداء أو لغة لم تختبرها التجربة.

مرجع جميع مواضع القطع الصغيرة

راجعنا 8128 زوجًا من سلسلة وقاموس في تجربة محدودة. السلاسل من رمزي a و b بأطوال من صفر إلى ستة، والقواميس جميع المجموعات الممكنة من a و b و aa و ab و ba و bb. لكل سلسلة عددنا مواضع القطع الممكنة مباشرة، ثم قبلنا التقسيم إذا كانت أجزاؤه كلها في القاموس، دون استعمال علاقة حدود الوصول التي يطبقها التنفيذ المختبر.

قارنّا كل بادئة كذلك بنتيجة هذا المرجع، فراجعنا 49216 حالة حد. وفي الشاهد الصالح تحققنا من عضوية كل جزء، وضم الأجزاء إلى النص نفسه، وتجاور الحدود، والبداية صفرًا والنهاية عند طول السلسلة. راجعنا أمثلة النهاية الفاشلة والجشع وأول شاهد غير الأقل، وحالات الفراغ وتكرار القاموس وترتيبه ورفض المدخل المخالف. هذه فحوص محدودة وليست قياس جودة لغوية أو أداء.

قبل اعتماد نتيجة جديدة، حدد هل تريد الإمكانية أم العدد أم أفضل تقسيم بمعيار معين، وثبت النص والقاموس ووحدة المقطع. ثم راجع الوصول إلى الحد الأخير واستعد شاهدًا وافحص التغطية حرفيًا. ستعرف بذلك لماذا لا يكفي نجاح بادئة أو تطابق أطوال، وكيف يحفظ السابق انتقالًا محددًا، وما الذي يحتاج قاعدة أخرى عندما يتغير هدف الاختيار أو معنى الكلمة.