عرض مصدر مصفوفة اللواحق لسلسلة نصية

{{يتيمة|تاريخ =فبراير 2025}}
{{مقالة غير مراجعة|تاريخ =فبراير 2025}}
 {{بطاقة عامة}}

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

تم اقتراح مصفوفة اللواحق بواسطة {{Harvard citation text|Manber|Myers|1990}} كبديل بسيط وموفر للمساحة [[شجرة نهايات السلسلة|لأشجار اللواحق]]. وقد تم اكتشافها بشكل مستقل من قبل جاستون جونيت في عام 1987 تحت اسم ''مجموعة PAT'' {{Harvard citation|Gonnet|Baeza-Yates|Snider|1992}} .

قدم {{Harvard citation text|Li|Li|Huo|2016}} أول خوارزمية لبناء مصفوفة لاحقات زمنية في تعقيد وقت <math>\mathcal{O}(n)</math> وهي الخوارزمية المثالية في كل من الزمان والمكان، حيث تعني في المكان أن الخوارزمية تحتاج فقط إلى مساحة إضافية <math>\mathcal{O}(n)</math> تتجاوز سلسلة الإدخال ومصفوفة لاحقات الإخراج.

مصفوفة لواحق مُحسّنة/مُعزّزة (Enhanced suffix arrays - ESA) هي عبارة عن مصفوفة لاواحق تحتوي على جداول إضافية تعيد إنتاج الوظائف الكاملة لأشجار اللاحقة مع الحفاظ على نفس تعقيد الوقت والذاكرة. {{Sfn|Abouelhoda|Kurtz|Ohlebusch|2004}} تُسمى مجموعة اللواحق لمجموعة فرعية من جميع لواحق السلسلة [[Sparse suffix array|بمصفوفة اللواحق المتفرقة]] . {{Sfn|I|Kärkkäinen|Kempa|2014}} تم تطوير خوارزميات احتمالية متعددة لتقليل استخدام الذاكرة الإضافية بما في ذلك خوارزمية الوقت والذاكرة المثلى. {{Sfn|Gawrychowski|Kociumaka|2017}}

== تعريف ==
لتكن <math>S=S[1]S[2]...S[n]</math> وكذلك <math display="inline">n</math> -سلسلة و دع <math>S[i,j]</math> تشير إلى السلسلة الفرعية من <math>S</math> تتراوح من <math>i</math> ل <math>j</math> شامل.

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

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

== مثال ==
لنتطلع على النص <math>S</math>=<code>banana$</code> :

وينتهي النص بالرمز الخاص <code>$</code> الذي يعتبر فريدًا من نوعه وأصغر معجميًا من أي حرف آخر. يحتوي النص على اللواحق التالية:
{| class="wikitable"
! align="left" |اللاحقة
! align="left" | i
|- class="odd"
| align="left" | banana$
| align="left" | 1
|- class="even"
| align="left" | anana$
| align="left" | 2
|- class="odd"
| align="left" | nana$
| align="left" | 3
|- class="even"
| align="left" | ana$
| align="left" | 4
|- class="odd"
| align="left" | na$
| align="left" | 5
|- class="even"
| align="left" | a$
| align="left" | 6
|- class="odd"
| align="left" | $
| align="left" | 7
|}
يمكن ترتيب هذه اللواحق بترتيب تصاعدي:
{| class="wikitable"
! align="left" |اللاحقة
! align="left" | i
|- class="odd"
| align="left" | $
| align="left" | 7
|- class="even"
| align="left" | a$
| align="left" | 6
|- class="even"
| align="left" | ana$
| align="left" | 4
|- class="even"
| align="left" | anana$
| align="left" | 2
|- class="odd"
| align="left" | banana$
| align="left" | 1
|- class="odd"
| align="left" | na$
| align="left" | 5
|- class="odd"
| align="left" | nana$
| align="left" | 3
|}
مصفوفة اللواحق <math>A</math> يحتوي على مواضع البداية لهذه اللواحق المرتبة:

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

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

== علاقة مصفوفة اللواحق بـ<nowiki/>[[أشجار اللواحق]] ==
ترتبط مصفوفات اللواحق ارتباطًا وثيقًا بأشجار اللواحق :

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

== الغوريتمات بناء [[بنى البيانات|مبنى المعطيات]] ==
يمكن بناء شجرة لاحقة في <math>\mathcal{O}(n)</math> ويمكن تحويلها إلى مجموعة لاحقة من خلال عبور عمق الشجرة أولاً أيضًا <math>\mathcal{O}(n)</math> لذا، توجد خوارزميات يمكنها بناء مجموعة لاحقة في <math>\mathcal{O}(n)</math> .

الطريقة الساذجة لإنشاء مجموعة لاحقة هي استخدام [[الترتيب بالمقارنة|خوارزمية ترتيب تعتمد على المقارنة]]. تتطلب هذه الخوارزميات <math>\mathcal{O}(n \log n)</math> مقارنات اللواحق، ولكن تتم مقارنة اللواحق في <math>\mathcal{O}(n)</math> الوقت، لذا فإن وقت التشغيل الإجمالي لهذا النهج هو <math>\mathcal{O}(n^2 \log n)</math> .

== مصفوفة لاحقة معممة ==
يمكن توسيع مفهوم مجموعة اللواحق إلى أكثر من سلسلة واحدة. يُطلق على هذا اسم مصفوفة لاحقات معممة (أو GSA)، وهي مصفوفة لاحقات تحتوي على جميع اللاحقات لمجموعة من السلاسل (على سبيل المثال، <math>S=S_1,S_2,S_3,...,S_k</math> ويتم ترتيبها معجميًا مع جميع لاحقات كل سلسلة. {{Sfn|Shi|1996}}

== مراجع ==

* {{استشهاد بمنشورات مؤتمر|مؤلف=Manber|الأول=Udi|مؤلف-وصلة=Udi Manber|مؤلف2=Myers|الأول2=Gene|مؤلف2-وصلة=Gene Myers|سنة=1990|عنوان=Suffix arrays: a new method for on-line string searches|مسار=http://dl.acm.org/citation.cfm?id=320176.320218|عنوان المؤتمر=First Annual ACM-SIAM Symposium on Discrete Algorithms|صفحات=319–327|مسار أرشيف=http://web.archive.org/web/20190214154712/https://dl.acm.org/citation.cfm?id=320176.320218|تاريخ أرشيف=2019-02-14}}
* {{استشهاد بدورية محكمة|عنوان=Suffix arrays: a new method for on-line string searches|صحيفة=SIAM Journal on Computing|مسار=http://dl.acm.org/citation.cfm?id=320176.320218|مؤلف=Manber|الأول=Udi|مؤلف-وصلة=Udi Manber|سنة=1993|المجلد=22|العدد=5|صفحات=935–948|مؤلف2=Myers|الأول2=Gene|مؤلف2-وصلة=Gene Myers|s2cid=5074629|دوي=10.1137/0222058|مسار أرشيف=http://web.archive.org/web/20190214154712/https://dl.acm.org/citation.cfm?id=320176.320218|تاريخ أرشيف=2019-02-14}}
* {{استشهاد بدورية محكمة|عنوان=Sparse Suffix Tree Construction in Optimal Time and Space|صحيفة=Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms|مؤلف=Gawrychowski|الأول=Paweł|تاريخ=January 2017|مكان=Philadelphia, PA|ناشر=Society for Industrial and Applied Mathematics|صفحات=425–439|مؤلف2=Kociumaka|الأول2=Tomasz|أرخايف=1608.00865|s2cid=6608776|دوي=10.1137/1.9781611974782.27|isbn=9781611974782}}
* {{استشهاد بمنشورات مؤتمر|مؤلف=Li|الأول=Zhize|مؤلف2=Li|الأول2=Jian|مؤلف3=Huo|الأول3=Hongwei|سنة=2016|عنوان=Optimal In-Place Suffix Sorting|عنوان المؤتمر=Proceedings of the 25th International Symposium on String Processing and Information Retrieval (SPIRE)|سلسلة=Lecture Notes in Computer Science|ناشر=Springer|المجلد=11147|صفحات=268–284|أرخايف=1610.08305|دوي=10.1007/978-3-030-00479-8_22|isbn=978-3-030-00478-1}}
* {{استشهاد بمنشورات مؤتمر|مؤلف=Shi|الأول=Fei|تاريخ=1996|عنوان=Concurrency and Parallelism, Programming, Networking, and Security|سلسلة=Lecture Notes in Computer Science|ناشر=Springer Berlin Heidelberg|المجلد=1179|صفحات=11–22|دوي=10.1007/BFb0027775|isbn=978-3-540-62031-0|الفصل=Suffix arrays for multiple strings: A method for on-line multiple string searches}}
* {{استشهاد بمنشورات مؤتمر|مؤلف=Abouelhoda|الأول=Mohamed Ibrahim|مؤلف2=Kurtz|الأول2=Stefan|مؤلف3=Ohlebusch|الأول3=Enno|سنة=2002|عنوان=The Enhanced Suffix Array and Its Applications to Genome Analysis|عنوان المؤتمر=Algorithms in Bioinformatics|سلسلة={{Ill-WD2|مذكرات محاضرة في علم الحاسوب|id=Q924044}}|المجلد=2452|دوي=10.1007/3-540-45784-4_35|isbn=978-3-540-44211-0}}
* {{استشهاد بدورية محكمة|عنوان=Replacing suffix trees with enhanced suffix arrays|صحيفة=Journal of Discrete Algorithms|مؤلف=Abouelhoda|الأول=Mohamed Ibrahim|تاريخ=March 2004|المجلد=2|العدد=1|صفحات=53–86|مؤلف2=Kurtz|مؤلف3=Ohlebusch|issn=1570-8667|الأول2=Stefan|الأول3=Enno|دوي=10.1016/S1570-8667(03)00065-0|doi-access=free}}
* {{استشهاد بدورية محكمة|عنوان=New indices for text: PAT trees and PAT arrays|صحيفة=Information Retrieval: Data Structures and Algorithms|مسار=http://orion.lcg.ufrj.br/Dr.Dobbs/books/book5/chap05.htm|مؤلف=Gonnet|الأول=G.H.|سنة=1992|مؤلف2=Baeza-Yates|مؤلف3=Snider|الأول2=R.A.|الأول3=T.|مسار أرشيف=http://web.archive.org/web/20211207184603/http://orion.lcg.ufrj.br/Dr.Dobbs/books/book5/chap05.htm|تاريخ أرشيف=2021-12-07}}
* {{استشهاد بدورية محكمة|عنوان=Reducing the space requirement of suffix trees|صحيفة=Software: Practice and Experience|مؤلف=Kurtz|الأول=S|سنة=1999|المجلد=29|العدد=13|صفحات=1149–1171|hdl-access=free|hdl=10338.dmlcz/135448|دوي=10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O}}
* {{استشهاد بدورية محكمة|عنوان=A taxonomy of suffix array construction algorithms|صحيفة=ACM Computing Surveys|مسار=http://researchrepository.murdoch.edu.au/id/eprint/27889/|مؤلف=Puglisi|الأول=Simon J.|سنة=2007|المجلد=39|العدد=2|صفحات=4|مؤلف2=Smyth|مؤلف3=Turpin|الأول2=W. F.|الأول3=Andrew H.|s2cid=2653529|دوي=10.1145/1242471.1242472|مسار أرشيف=http://web.archive.org/web/20220527210626/https://researchrepository.murdoch.edu.au/id/eprint/27889/|تاريخ أرشيف=2022-05-27}}
* {{استشهاد بمنشورات مؤتمر|مؤلف=Nong|الأول=Ge|مؤلف2=Zhang|الأول2=Sen|مؤلف3=Chan|الأول3=Wai Hong|سنة=2009|عنوان=Linear Suffix Array Construction by Almost Pure Induced-Sorting|عنوان المؤتمر=2009 Data Compression Conference|صفحات=193|دوي=10.1109/DCC.2009.42|isbn=978-0-7695-3592-0}}
* {{استشهاد بمنشورات مؤتمر|مؤلف=Fischer|الأول=Johannes|سنة=2011|عنوان=Inducing the LCP-Array|عنوان المؤتمر=Algorithms and Data Structures|سلسلة=Lecture Notes in Computer Science|المجلد=6844|صفحات=374–385|أرخايف=1101.3448|دوي=10.1007/978-3-642-22300-6_32|isbn=978-3-642-22299-3}}
* {{استشهاد بدورية محكمة|عنوان=Dynamic extended suffix arrays|صحيفة=Journal of Discrete Algorithms|مؤلف=Salson|الأول=M.|سنة=2010|المجلد=8|العدد=2|صفحات=241|مؤلف2=Lecroq|مؤلف3=Léonard|مؤلف4=Mouchard|الأول2=T.|الأول3=M.|الأول4=L.|دوي=10.1016/j.jda.2009.02.007|doi-access=free}}
* {{استشهاد بمنشورات مؤتمر|مؤلف=Burkhardt|الأول=Stefan|مؤلف2=Kärkkäinen|الأول2=Juha|سنة=2003|عنوان=Fast Lightweight Suffix Array Construction and Checking|عنوان المؤتمر=Combinatorial Pattern Matching|سلسلة=Lecture Notes in Computer Science|المجلد=2676|صفحات=55–69|دوي=10.1007/3-540-44888-8_5|isbn=978-3-540-40311-1}}
* {{استشهاد بمنشورات مؤتمر|مؤلف=Karp|الأول=Richard M.|مؤلف2=Miller|الأول2=Raymond E.|مؤلف3=Rosenberg|الأول3=Arnold L.|سنة=1972|عنوان=Rapid identification of repeated patterns in strings, trees and arrays|عنوان المؤتمر=Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72|صفحات=125–136|دوي=10.1145/800152.804905}}
* {{استشهاد بمنشورات مؤتمر|مؤلف=Farach|الأول=M.|سنة=1997|عنوان=Optimal suffix tree construction with large alphabets|عنوان المؤتمر=Proceedings 38th Annual Symposium on Foundations of Computer Science|دوي=10.1109/SFCS.1997.646102|isbn=0-8186-8197-7}}
* {{استشهاد بمنشورات مؤتمر|مؤلف=I|الأول=Tomohiro|مؤلف2=Kärkkäinen|الأول2=Juha|مؤلف3=Kempa|الأول3=Dominik|تاريخ=2014|عنوان=Faster Sparse Suffix Sorting|سلسلة=Leibniz International Proceedings in Informatics (LIPIcs)|ناشر=Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik|المجلد=25|صفحات=386–396|دوي=10.4230/LIPIcs.STACS.2014.386|isbn=978-3-939897-65-1|doi-access=free}}
* {{استشهاد بمنشورات مؤتمر|مؤلف=Kärkkäinen|الأول=Juha|مؤلف2=Sanders|الأول2=Peter|مؤلف2-وصلة=Peter Sanders (computer scientist)|سنة=2003|عنوان=Simple Linear Work Suffix Array Construction|عنوان المؤتمر=Automata, Languages and Programming|سلسلة=Lecture Notes in Computer Science|المجلد=2719|دوي=10.1007/3-540-45061-0_73|isbn=978-3-540-40493-4}}
* {{استشهاد بدورية محكمة|عنوان=Better external memory suffix array construction|صحيفة=Journal of Experimental Algorithmics|مسار=https://publikationen.bibliothek.kit.edu/1000009446|مؤلف=Dementiev|الأول=Roman|سنة=2008|المجلد=12|صفحات=1–24|مؤلف2=Kärkkäinen|مؤلف3=Mehnert|مؤلف4=Sanders|الأول2=Juha|الأول3=Jens|الأول4=Peter|مؤلف4-وصلة=Peter Sanders (computer scientist)|s2cid=12296500|دوي=10.1145/1227161.1402296|مسار أرشيف=http://web.archive.org/web/20240829023954/https://publikationen.bibliothek.kit.edu/1000009446|تاريخ أرشيف=2024-08-29}}
* {{استشهاد بدورية محكمة|عنوان=Scalable parallel suffix array construction|صحيفة=Parallel Computing|مؤلف=Kulla|الأول=Fabian|سنة=2007|المجلد=33|العدد=9|صفحات=605–612|مؤلف2=Sanders|الأول2=Peter|مؤلف2-وصلة=Peter Sanders (computer scientist)|دوي=10.1016/j.parco.2007.06.004}}
* 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.

== روابط خارجية ==

* [http://algs4.cs.princeton.edu/63suffix/SuffixArray.java.html مصفوفة اللواحق في جافا]
* [http://code.google.com/p/compression-code/downloads/list وحدة ترتيب اللاحقات لـ BWT في كود C]
* [http://www.codeodor.com/index.cfm/2007/12/24/The-Suffix-Array/1845 تنفيذ مصفوفة اللواحق في روبي]
* [http://sary.sourceforge.net/index.html.en مكتبة أدوات مجموعة اللواحق]
* [http://pizzachili.dcc.uchile.cl/ مشروع يحتوي على تطبيقات Suffix Array c/c++ المختلفة مع واجهة موحدة]
* [https://github.com/y-256/libdivsufsort مكتبة API C سريعة وخفيفة الوزن وقوية لإنشاء مجموعة اللاحقات]
* [http://code.google.com/p/pysuffix/ تنفيذ مصفوفة اللواحق في بايثون]
* [http://www.geeksforgeeks.org/suffix-tree-application-4-build-linear-time-suffix-array/ تنفيذ مصفوفة اللاحقات الزمنية الخطية في لغة C باستخدام شجرة اللاحقات]
{{مقالات بحاجة لشريط بوابات}}
{{روابط شقيقة}}

[[تصنيف:علم الحاسوب النظري]]
[[تصنيف:بنى البيانات]]
[[تصنيف:سلسلة (علم الحاسوب)]]
[[تصنيف:مصفوفات]]