مصفوفة اللواحق لسلسلة نصية

في علم الحاسوب ، مصفوفة اللواحق (Suffix Array) هي مصفوفة مرتبة من جميع لواحق السلسلة النصيّة. هو عبارة عن مبنى معطيات يُستخدم في عدة مجالات مثل ألغورتمات ضغط البيانات وغيرها..

تم اقتراح مصفوفة اللواحق بواسطة قالب:Harvard citation text كبديل بسيط وموفر للمساحة لأشجار اللواحق. وقد تم اكتشافها بشكل مستقل من قبل جاستون جونيت في عام 1987 تحت اسم مجموعة PAT قالب:Harvard citation .

قدم قالب:Harvard citation text أول خوارزمية لبناء مصفوفة لاحقات زمنية في تعقيد وقت $𝒪(n)$ وهي الخوارزمية المثالية في كل من الزمان والمكان، حيث تعني في المكان أن الخوارزمية تحتاج فقط إلى مساحة إضافية $𝒪(n)$ تتجاوز سلسلة الإدخال ومصفوفة لاحقات الإخراج.

مصفوفة لواحق مُحسّنة/مُعزّزة (Enhanced suffix arrays - ESA) هي عبارة عن مصفوفة لاواحق تحتوي على جداول إضافية تعيد إنتاج الوظائف الكاملة لأشجار اللاحقة مع الحفاظ على نفس تعقيد الوقت والذاكرة. قالب:Sfn تُسمى مجموعة اللواحق لمجموعة فرعية من جميع لواحق السلسلة بمصفوفة اللواحق المتفرقة . قالب:Sfn تم تطوير خوارزميات احتمالية متعددة لتقليل استخدام الذاكرة الإضافية بما في ذلك خوارزمية الوقت والذاكرة المثلى. قالب:Sfn

تعريف

لتكن $S=S[1]S[2]...S[n]$ وكذلك $n$ -سلسلة و دع $S[i,j]$ تشير إلى السلسلة الفرعية من $S$ تتراوح من $i$ ل $j$ شامل.

مجموعة اللواحق $A$ ل $S$ يتم الآن تعريفه على أنه عبارة عن مجموعة من الأعداد الصحيحة التي توفر مواضع البداية لللاحقات $S$ حسب الترتيب الأبجدي . وهذا يعني دخول $A[i]$ يحتوي على موضع البداية لـ $i$ - أصغر لاحقة في $S$ وهكذا للجميع $1\le i\le n$ : $S[A[i-1],n]<S[A[i],n]$ .

كل لاحقة من $S$ يظهر في $A$ مرة واحدة بالضبط. اللواحق هي سلاسل بسيطة. يتم ترتيب هذه السلاسل النصية، قبل حفظ مواضعها الأولية (مؤشرات الأعداد الصحيحة) في $A$ .

مثال

لنتطلع على النص $S$=banana$ :

وينتهي النص بالرمز الخاص $ الذي يعتبر فريدًا من نوعه وأصغر معجميًا من أي حرف آخر. يحتوي النص على اللواحق التالية:

اللاحقة	i
banana$	1
anana$	2
nana$	3
ana$	4
na$	5
a$	6
$	7

يمكن ترتيب هذه اللواحق بترتيب تصاعدي:

اللاحقة	i
$	7
a$	6
ana$	4
anana$	2
banana$	1
na$	5
nana$	3

مصفوفة اللواحق $A$ يحتوي على مواضع البداية لهذه اللواحق المرتبة:

مصفوفة اللواخق مع اللاحقات المكتوبة عموديًا في الأسفل من أجل الوضوح:

على سبيل المثال، $A[3]$ يحتوي على القيمة 4، وبالتالي يشير إلى اللاحقة التي تبدأ في الموضع 4 داخل $S$ ، وهي اللاحقة ana$ .

علاقة مصفوفة اللواحق بـأشجار اللواحق

ترتبط مصفوفات اللواحق ارتباطًا وثيقًا بأشجار اللواحق :

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

الغوريتمات بناء مبنى المعطيات

يمكن بناء شجرة لاحقة في $𝒪(n)$ ويمكن تحويلها إلى مجموعة لاحقة من خلال عبور عمق الشجرة أولاً أيضًا $𝒪(n)$ لذا، توجد خوارزميات يمكنها بناء مجموعة لاحقة في $𝒪(n)$ .

الطريقة الساذجة لإنشاء مجموعة لاحقة هي استخدام خوارزمية ترتيب تعتمد على المقارنة. تتطلب هذه الخوارزميات $𝒪(n\log n)$ مقارنات اللواحق، ولكن تتم مقارنة اللواحق في $𝒪(n)$ الوقت، لذا فإن وقت التشغيل الإجمالي لهذا النهج هو $𝒪(n^2\log n)$ .

مصفوفة لاحقة معممة

يمكن توسيع مفهوم مجموعة اللواحق إلى أكثر من سلسلة واحدة. يُطلق على هذا اسم مصفوفة لاحقات معممة (أو GSA)، وهي مصفوفة لاحقات تحتوي على جميع اللاحقات لمجموعة من السلاسل (على سبيل المثال، $S=S_1,S_2,S_3,...,S_k$ ويتم ترتيبها معجميًا مع جميع لاحقات كل سلسلة. قالب:Sfn

مراجع

• قالب:استشهاد بمنشورات مؤتمر
• قالب:استشهاد بدورية محكمة
• قالب:استشهاد بدورية محكمة
• قالب:استشهاد بمنشورات مؤتمر
• قالب:استشهاد بمنشورات مؤتمر
• قالب:استشهاد بمنشورات مؤتمر
• قالب:استشهاد بدورية محكمة
• قالب:استشهاد بدورية محكمة
• قالب:استشهاد بدورية محكمة
• قالب:استشهاد بدورية محكمة
• قالب:استشهاد بمنشورات مؤتمر
• قالب:استشهاد بمنشورات مؤتمر
• قالب:استشهاد بدورية محكمة
• قالب:استشهاد بمنشورات مؤتمر
• قالب:استشهاد بمنشورات مؤتمر
• قالب:استشهاد بمنشورات مؤتمر
• قالب:استشهاد بمنشورات مؤتمر
• قالب:استشهاد بمنشورات مؤتمر
• قالب:استشهاد بدورية محكمة
• قالب:استشهاد بدورية محكمة
• Mohamed Ibrahim Abouelhoda, Stefan Kurtz, and Enno Ohlebusch. "Replacing suffix trees with enhanced suffix arrays." Journal of Discrete Algorithms, 2(1):53–86, 2004.
• Dong Kyue Kim, Jeong Eun Jeon, and Heejin Park. "An efficient index data structure with the capabilities of suffix trees and suffix arrays for alphabets of non-negligible size." String Processing and Information Retrieval Lecture Notes in Computer Science, page138–149, 2004.

روابط خارجية

• مصفوفة اللواحق في جافا
• وحدة ترتيب اللاحقات لـ BWT في كود C
• تنفيذ مصفوفة اللواحق في روبي
• مكتبة أدوات مجموعة اللواحق
• مشروع يحتوي على تطبيقات Suffix Array c/c++ المختلفة مع واجهة موحدة
• مكتبة API C سريعة وخفيفة الوزن وقوية لإنشاء مجموعة اللاحقات
• تنفيذ مصفوفة اللواحق في بايثون
• تنفيذ مصفوفة اللاحقات الزمنية الخطية في لغة C باستخدام شجرة اللاحقات