Key points are not available for this paper at this time.
يُقال إن السلسلة w هي كلمة غائبة بالحد الأدنى (MAW) لسلسلة S إذا لم تحدث w في S وأي جزء صحيح من w يحدث في S. نحن نركز على MAWs غير التافهة التي تكون بطول لا يقل عن 2. إن العثور على مثل هذه MAWs غير التافهة لسلسلة معينة يُحفّز للتطبيقات في المعلومات الحيوية وضغط البيانات. اقترح Fujishige وزملاؤه في TCS 2023 هيكل بيانات بحجم (n) يمكنه إخراج مجموعة MAW (S) لجميع MAWs لسلسلة معينة S من الطول n في وقت O (n + |MAW (S) |) ، بناءً على رسم بياني للكلمات الموجهة بدون دوائر (DAWG). في هذه الورقة، نقدم هيكل بيانات أكثر كفاءة في استخدام الفضاء استنادًا إلى CDAWG المضغوط ، والذي يمكنه إخراج MAW (S) في وقت O (|MAW (S) |) مع مساحة O (e) ، حيث e يدل على الحد الأدنى من أحجام CDAWGs لـ S ولعكسها SR. بالنسبة لأي سلاسل بطول n، فإن e < 2n، وللسلاسل المتكررة بشكل كبير يمكن أن تكون e أقل من خطية (حتى لوغاريتمية) في n. نظهر أيضًا أن MAWs وتعميمها الكلمات النادرة بالحد الأدنى لها علاقات وثيقة مع العوامل الثنائية الخاصة الممتدة، من خلال CDAWG.
درس Inenaga وزملاؤه (الأربعاء) هذا السؤال.