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

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

تم تقديم مصفوفات اللواحق بواسطة مانبر ومايرز (1990) كبديل بسيط وفعال من حيث المساحة لأشجار اللواحق . وقد اكتشفها جاستون جونيه بشكل مستقل في عام 1987 تحت اسم مصفوفة PAT ( جونيه، بايزا-ياتس وسنايدر 1992 ) .

قدم لي ولي وهوو (2016) أول دراسة في مكانها${\displaystyle {\mathcal {O}}(n)}$خوارزمية بناء مصفوفة لاحقة زمنية مثالية من حيث الوقت والمساحة، حيث تعني كلمة "في المكان" أن الخوارزمية تحتاج فقط إلى${\displaystyle {\mathcal {O}}(1)}$مساحة إضافية تتجاوز سلسلة الإدخال ومصفوفة لاحقة الإخراج.

مصفوفات اللواحق المحسّنة (ESAs) هي مصفوفات لواحق مزودة بجداول إضافية تُعيد إنتاج الوظائف الكاملة لأشجار اللواحق مع الحفاظ على نفس تعقيد الوقت والذاكرة. ^{[ 1 ]} تُسمى المصفوفة المرتبة التي تحتوي على بعض لواحق السلسلة فقط (بدلاً من جميعها) مصفوفة لواحق متفرقة . ^{[ 2 ]}

يترك${\displaystyle S=S[1]S[2]...S[n]}$كن${\textstyle n}$-string و let${\displaystyle S[i,j]}$يشير إلى السلسلة الفرعية من${\displaystyle S}$تتراوح من${\displaystyle i}$ل${\displaystyle j}$شامل.

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

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

انظر إلى النص${\displaystyle S}$= banana$ليتم فهرستها:

أنا	1	2	3	4	5	6	7
${\displaystyle S[i]}$	ب	أ	ن	أ	ن	أ	دولار

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

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

مصفوفة اللواحق${\displaystyle A}$يحتوي على المواضع الأولية لهذه اللواحق المصنفة:

i =	1	2	3	4	5	6	7
${\displaystyle A[i]}$=	7	6	4	2	1	5	3

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

i =	1	2	3	4	5	6	7
${\displaystyle A[i]}$=	7	6	4	2	1	5	3
1	دولار	أ	أ	أ	ب	ن	ن
2		دولار	ن	ن	أ	أ	أ
3			أ	أ	ن	دولار	ن
4			دولار	ن	أ		أ
5				أ	ن		دولار
6				دولار	أ
7					دولار

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

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

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

لقد ثبت أنه يمكن استبدال كل خوارزمية لشجرة اللواحق بشكل منهجي بخوارزمية تستخدم مصفوفة لواحق مُحسَّنة بمعلومات إضافية (مثل مصفوفة LCP ) وتحل نفس المشكلة بنفس التعقيد الزمني. ^{[ 1 ]} تشمل مزايا مصفوفات اللواحق على أشجار اللواحق تحسين متطلبات المساحة، وخوارزميات بناء خطية أبسط (مقارنةً بخوارزمية أوكونين على سبيل المثال )، وتحسين موضعية الذاكرة المؤقتة. ^{[ 3 ]}

تم تقديم مصفوفات اللواحق بواسطة مانبر ومايرز (1990) بهدف تحسين متطلبات المساحة لأشجار اللواحق : تخزن مصفوفات اللواحق${\displaystyle n}$الأعداد الصحيحة. بافتراض أن العدد الصحيح يتطلب${\displaystyle 4}$تتطلب مصفوفة اللاحقة بايتات${\displaystyle 4n}$إجمالي البايتات. وهذا أقل بكثير من${\displaystyle 20n}$البايتات المطلوبة لتنفيذ شجرة اللواحق بعناية. ^{[ 4 ]}

مع ذلك، في بعض التطبيقات، قد تظل متطلبات المساحة لمصفوفات اللواحق باهظة. عند تحليلها بالبتات، تتطلب مصفوفة اللواحق مساحة تخزين تبلغ 10000 بت.${\displaystyle {\mathcal {O}}(n\log n)}$المساحة، بينما النص الأصلي على أبجدية بحجم${\displaystyle \sigma }$لا يتطلب الأمر سوى${\displaystyle {\mathcal {O}}(n\log \sigma )}$بتات. لجينوم بشري مع${\displaystyle \sigma =4}$و${\displaystyle n=3.4\times 10^{9}}$وبالتالي، فإن مصفوفة اللواحق ستشغل مساحة ذاكرة أكبر بحوالي 16 مرة من مساحة الجينوم نفسه.

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

يمكن إنشاء شجرة اللواحق في${\displaystyle {\mathcal {O}}(n)}$ويمكن تحويلها إلى مصفوفة لاحقة عن طريق اجتياز الشجرة بالبحث العميق أولاً، أيضاً في${\displaystyle {\mathcal {O}}(n)}$لذا توجد خوارزميات يمكنها إنشاء مصفوفة لاحقة في${\displaystyle {\mathcal {O}}(n)}$.

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

تستفيد الخوارزميات الأكثر تطوراً من حقيقة أن اللواحق المراد فرزها ليست سلاسل عشوائية، بل هي مترابطة. وتسعى هذه الخوارزميات إلى تحقيق الأهداف التالية: ^{[ 5 ]}

• الحد الأدنى من التعقيد التقاربي${\displaystyle \Theta (n)}$
• خفيف الوزن من حيث المساحة، مما يعني الحاجة إلى ذاكرة عمل قليلة أو معدومة بجانب النص ومصفوفة اللاحقة نفسها.
• سريع في الممارسة

تُعدّ خوارزمية SA-IS التي وضعها نونغ، تشانغ، وتشان (2009) من أوائل الخوارزميات التي حققت جميع الأهداف . تتميز هذه الخوارزمية ببساطتها ( أقل من 100 سطر برمجي ) وإمكانية تطويرها لإنشاء مصفوفة LCP في آنٍ واحد . ^{[ 6 ]} تُعتبر خوارزمية SA-IS من أسرع خوارزميات إنشاء مصفوفات اللواحق المعروفة. وقد تفوّق تطبيقها الدقيق من قِبل يوتا موري ^{[ 7 ]} على معظم طرق الإنشاء الخطية أو شبه الخطية الأخرى.

إلى جانب متطلبات الوقت والمساحة، تختلف خوارزميات إنشاء مصفوفات اللواحق أيضًا حسب الأبجدية المدعومة : أبجديات ثابتة حيث يكون حجم الأبجدية محدودًا بقيمة ثابتة، وأبجديات عددية صحيحة حيث تكون الأحرف أعدادًا صحيحة ضمن نطاق يعتمد على${\displaystyle n}$والأبجديات العامة التي لا يُسمح فيها إلا بمقارنات الأحرف. ^{[ 8 ]}

تعتمد معظم خوارزميات إنشاء مصفوفات اللواحق على أحد الأساليب التالية: ^{[ 5 ]}

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

تُعد خوارزمية DC3 / skew التي وضعها كاركاينن وساندرز (2003) خوارزمية تكرارية معروفة للأبجديات العددية . تعمل هذه الخوارزمية في وقت خطي، وقد استُخدمت بنجاح كأساس لخوارزميات بناء مصفوفات اللواحق المتوازية ^{[ 9 ]} والذاكرة الخارجية ^{[ 10 ] .}

يقترح بحث حديث أجراه سالسون وآخرون (2010) خوارزمية لتحديث مصفوفة اللواحق لنص تم تعديله، بدلاً من إعادة بناء مصفوفة لواحق جديدة من الصفر. حتى لو كان التعقيد الزمني النظري في أسوأ الحالات هو${\displaystyle {\mathcal {O}}(n\log n)}$، ويبدو أنه يعمل بشكل جيد من الناحية العملية: فقد أظهرت النتائج التجريبية التي توصل إليها المؤلفون أن تطبيقهم لمصفوفات اللواحق الديناميكية يكون بشكل عام أكثر كفاءة من إعادة البناء عند النظر في إدراج عدد معقول من الأحرف في النص الأصلي.

في التطبيقات العملية مفتوحة المصدر ، كانت خوارزمية qsufsort، المستندة إلى خوارزمية لارسون-ساداكان لعام 1999، من أكثر الخوارزميات استخدامًا لإنشاء مصفوفات اللواحق. ^{[ 11 ]} وقد حلت محلها خوارزمية DivSufSort التي طورها يوتا موري، والتي تُعتبر "أسرع خوارزمية معروفة لفرز اللواحق في الذاكرة الرئيسية" حتى عام 2017. ويمكن تعديلها أيضًا لحساب مصفوفة LCP. وتستخدم هذه الخوارزمية النسخ المستحث مع خوارزمية إيتوه-تاناكا. ^{[ 12 ] وفي عام 2021، قدم إيليا غريبنوف [ 13 ]} تطبيقًا أسرع للخوارزمية، والذي أظهر في المتوسط ​​تحسنًا في الأداء بنسبة 65% مقارنةً بتطبيق DivSufSort على مجموعة بيانات سيليزيا . ^{[ 14 ]}

يمكن توسيع مفهوم مصفوفة اللواحق ليشمل أكثر من سلسلة نصية واحدة. يُطلق على هذا اسم مصفوفة اللواحق المعممة (أو GSA)، وهي مصفوفة لواحق تحتوي على جميع اللواحق لمجموعة من السلاسل النصية (على سبيل المثال،${\displaystyle S=S_{1},S_{2},S_{3},...,S_{k}}$ويتم ترتيبها معجمياً مع جميع لواحق كل سلسلة. ^{[ 15 ]}

يمكن استخدام مصفوفة اللواحق لسلسلة نصية كمؤشر لتحديد موقع كل ظهور لنمط سلسلة فرعية بسرعة${\displaystyle P}$داخل السلسلة${\displaystyle S}$إن إيجاد كل تكرار للنمط يُعادل إيجاد كل لاحقة تبدأ بالسلسلة الفرعية. وبفضل الترتيب المعجمي، تُجمّع هذه اللواحق معًا في مصفوفة اللواحق، ويمكن إيجادها بكفاءة باستخدام بحثين ثنائيين . يحدد البحث الأول موضع بداية الفاصل، بينما يحدد البحث الثاني موضع نهايته.

n = طول ( S )دالة البحث ( P : سلسلة نصية ) -> مجموعة [ عدد صحيح ، عدد صحيح ]: """  تُرجع الفهارس (s، r) التي تُمثل الفترة A[s:r] (باستثناء  فهرس النهاية) جميع لواحق S التي تبدأ بالنمط P.  """ # إيجاد موضع بداية الفترة l = 0 # في بايثون، يتم فهرسة المصفوفات بدءًا من 0 r = n while l < r : mid = ( l + r ) // 2 # القسمة مع التقريب لأقرب عدد صحيح # suffixAt(A[i]) هي أصغر لاحقة رقم i إذا كان P > suffixAt ( A [ mid ]): l = mid + 1 else : r = mid s = l# إيجاد موضع نهاية الفترة r = n بينما l < r : mid = ( l + r ) // 2 إذا كان suffixAt ( A [ mid ]) . startswith ( P ): l = mid + 1 وإلا : r = mid أرجع ( s , r )

إيجاد نمط السلسلة الفرعية${\displaystyle P}$من الطول${\displaystyle m}$في السلسلة${\displaystyle S}$من الطول${\displaystyle n}$يأخذ${\displaystyle {\mathcal {O}}(m\log n)}$الوقت، بالنظر إلى أن مقارنة لاحقة واحدة تحتاج إلى مقارنة${\displaystyle m}$يصف مانبر ومايرز (1990) كيف يمكن تحسين هذا الحد إلى${\displaystyle {\mathcal {O}}(m+\log n)}$يعتمد وقت البحث على معلومات LCP . الفكرة هي أن مقارنة الأنماط لا تحتاج إلى إعادة مقارنة أحرف معينة، عندما يكون معروفًا مسبقًا أنها جزء من أطول بادئة مشتركة للنمط وفترة البحث الحالية. وقد حسّن أبو الهدى وكورتز وأوليبوش (2004) هذا الحد بشكل أكبر، وحققوا وقت بحث قدره${\displaystyle {\mathcal {O}}(m)}$بالنسبة لحجم الأبجدية الثابت، كما هو معروف من أشجار اللواحق .

يمكن استخدام خوارزميات فرز اللواحق لحساب تحويل بوروز-ويلر (BWT) . يتطلب تحويل بوروز- ويلر فرز جميع التباديل الدورية لسلسلة نصية. إذا انتهت هذه السلسلة بحرف خاص أصغر معجميًا من جميع الأحرف الأخرى (مثل $)، فإن ترتيب مصفوفة تحويل بوروز-ويلر المُرتبة والمُدارة يُطابق ترتيب اللواحق في مصفوفة اللواحق. بالتالي، يمكن حساب تحويل بوروز-ويلر في وقت خطي عن طريق إنشاء مصفوفة لواحق للنص أولًا، ثم استنتاج سلسلة تحويل بوروز-ويلر .${\displaystyle BWT[i]=S[A[i]-1]}$.

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

تتطلب العديد من التطبيقات الإضافية لمصفوفة اللواحق مصفوفة LCP . بعض هذه التطبيقات مُفصّل في قسم التطبيقات من المصفوفة الأخيرة.

تُعدّ أشجار اللواحق هياكل بيانات قوية ذات تطبيقات واسعة في مجالات مطابقة الأنماط والسلاسل النصية، والفهرسة، والإحصاءات النصية. مع ذلك، فهي تشغل مساحة كبيرة، ما يُشكّل عائقًا في العديد من التطبيقات الآنية التي تتطلب معالجة كميات هائلة من البيانات، مثل تحليل الجينوم. وللتغلب على هذا العائق، طُوّرت مصفوفة اللواحق المُحسّنة. وهي هيكل بيانات يتألف من مصفوفة لواحق وجدول إضافي يُسمى جدول الأبناء، يحتوي على معلومات حول علاقة الأصل والفرع بين عُقد شجرة اللواحق. بنية بيانات تفرع العُقد لهذه الشجرة هي قائمة مُرتبطة . تتفوق مصفوفات اللواحق المُحسّنة على أشجار اللواحق من حيث كفاءة استخدام المساحة والتعقيد الزمني، كما أنها سهلة التنفيذ. علاوة على ذلك، يُمكن تطبيقها على أي خوارزمية تستخدم شجرة لواحق باستخدام مفهوم مجرد يُسمى أشجار فترات LCP. التعقيد الزمني للبحث عن نمط بطول${\displaystyle m}$في مصفوفة لاحقة محسّنة${\displaystyle {\mathcal {O}}(m|\Sigma |)}$.

تتكون مصفوفة اللواحق المحسّنة من مصفوفتين:

1. المصفوفة pos[1,...n]: تمثل قائمة مرتبة لجميع اللواحق S. يتم تخزين المواضع الأولية فقط للواحق في المصفوفة لتقليل تعقيد المساحة نظرًا لكبر حجم اللواحق.
2. مصفوفة lcp[1,...n]: هي مصفوفة من n عدد صحيح تحتفظ بأطوال أطول بادئة مشتركة للاحقتين متتاليتين مخزنتين في مصفوفة pos.

• مانبر، أودي ؛ مايرز، جين (1990). مصفوفات اللواحق: طريقة جديدة للبحث عن السلاسل النصية عبر الإنترنت . المؤتمر السنوي الأول لجمعية آلات الحوسبة وجمعية الرياضيات التطبيقية والصناعية حول الخوارزميات المنفصلة. الصفحات 319-327 . 
• مانبر، أودي ؛ مايرز، جين (1993). "مصفوفات اللواحق: طريقة جديدة للبحث عن السلاسل النصية عبر الإنترنت" . مجلة SIAM للحوسبة . 22 (5): 935-948 . doi : 10.1137/0222058 . S2CID 5074629 . 
• لي، تشيزي؛ لي، جيان؛ هو، هونغوي (2016). فرز اللواحق الأمثل في مكانها . وقائع الندوة الدولية الخامسة والعشرين حول معالجة السلاسل واسترجاع المعلومات (SPIRE). سلسلة محاضرات في علوم الحاسوب. المجلد  11147. سبرينغر. الصفحات 268-284 . arXiv : 1610.08305 . doi : 10.1007 /978-3-030-00479-8_22 . ISBN  978-3-030-00478-1.
• شي، فاي (1996). "مصفوفات اللواحق لسلاسل نصية متعددة: طريقة للبحث عن سلاسل نصية متعددة عبر الإنترنت". التزامن والتوازي، البرمجة، الشبكات، والأمن . سلسلة محاضرات في علوم الحاسوب. المجلد  1179. سبرينغر برلين هايدلبرغ. الصفحات 11-22 . doi : 10.1007/BFb0027775 . ISBN  978-3-540-62031-0.
• أبو الهدى، محمد إبراهيم؛ كورتز، ستيفان؛ أوهليبوش، إينو (2002). مصفوفة اللواحق المحسّنة وتطبيقاتها في تحليل الجينوم . خوارزميات في المعلوماتية الحيوية. سلسلة محاضرات في علوم الحاسوب . المجلد  2452. doi : 10.1007/3-540-45784-4_35 . ISBN 978-3-540-44211-0.
• أبو الهدى، محمد إبراهيم؛ كورتز، ستيفان؛ أوهليبوش، إينو (مارس 2004). "استبدال أشجار اللواحق بمصفوفات لواحق محسّنة" . مجلة الخوارزميات المنفصلة . 2 (1): 53-86 . doi : 10.1016/S1570-8667(03)00065-0 . ISSN 1570-8667 . 
• جونيت، جي إتش؛ بايزا-ياتس، آر إيه؛ سنايدر، تي. (1992). "مؤشرات جديدة للنصوص: أشجار PAT ومصفوفات PAT" . استرجاع المعلومات: هياكل البيانات والخوارزميات .
• كورتز، س. (1999). "تقليل متطلبات المساحة لأشجار اللواحق". البرمجيات: الممارسة والخبرة . 29 (13): 1149-1171 . doi : 10.1002/(SICI)1097-024X(199911)29:13 < 1149::AID-SPE274 > 3.0.CO ; 2-O . hdl : 10338.dmlcz/135448 .
• بوغليسي، سيمون جيه؛ سميث، دبليو إف؛ توربين، أندرو إتش (2007). "تصنيف خوارزميات بناء مصفوفات اللواحق" . مجلة ACM Computing Surveys . 39 (2): 4. doi : 10.1145/1242471.1242472 . S2CID 2653529 . 
• نونغ، جي؛ تشانغ، سين؛ تشان، واي هونغ (2009). بناء مصفوفة اللواحق الخطية باستخدام الفرز المستحث شبه النقي . مؤتمر ضغط البيانات 2009. ص  193. doi : 10.1109/DCC.2009.42 . ISBN 978-0-7695-3592-0.
• فيشر، يوهانس (2011). استقراء مصفوفة LCP . الخوارزميات وهياكل البيانات. سلسلة محاضرات في علوم الحاسوب. المجلد  6844. الصفحات 374-385 . arXiv : 1101.3448 . doi : 10.1007/978-3-642-22300-6_32 . ISBN  978-3-642-22299-3.
• سالسون، م.؛ ليكروك، ت.؛ ليونارد، م.؛ موشار، ل. (2010). "مصفوفات اللواحق الموسعة الديناميكية" . مجلة الخوارزميات المنفصلة . 8 (2): 241. doi : 10.1016/j.jda.2009.02.007 .
• بوركهارت، ستيفان؛ كاركاينن، يوها (2003). بناء مصفوفات اللواحق السريعة والخفيفة الوزن والتحقق منها . مطابقة الأنماط التوافقية. سلسلة محاضرات في علوم الحاسوب. المجلد  2676. الصفحات 55-69 . doi : 10.1007/3-540-44888-8_5 . ISBN  978-3-540-40311-1.
• كارب، ريتشارد م.؛ ميلر، ريموند إي.؛ روزنبرغ، أرنولد ل. (1972). التحديد السريع للأنماط المتكررة في السلاسل والأشجار والمصفوفات . وقائع الندوة السنوية الرابعة لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '72. الصفحات 125-136 . doi : 10.1145/800152.804905 . 
• فاراش، م. (1997). بناء شجرة اللواحق الأمثل باستخدام أبجديات كبيرة . وقائع الندوة السنوية الثامنة والثلاثين حول أسس علوم الحاسوب. doi : 10.1109/SFCS.1997.646102 . ISBN 0-8186-8197-7.
• أنا، توموهيرو؛ كاركاينن، جحا؛ كيمبا، دومينيك (2014). أسرع فرز لاحقة متفرقة . إجراءات لايبنيز الدولية في مجال المعلوماتية (LIPIcs). المجلد.  25. شلوس داجشتول – مركز لايبنتز للمعلوماتية. الصفحات من 386 إلى 396. دوى : 10.4230/LIPIcs.STACS.2014.386 . رقم ISBN  978-3-939897-65-1.
• كاركاينن، يوها؛ ساندرز، بيتر (2003). بناء مصفوفة لاحقة العمل الخطي البسيط . الأوتوماتا واللغات والبرمجة. سلسلة محاضرات في علوم الحاسوب. المجلد  2719. doi : 10.1007/3-540-45061-0_73 . ISBN 978-3-540-40493-4.
• ديمنتييف، رومان؛ كاركاينن، جحا؛ مهنيرت، ينس؛ ساندرز، بيتر (2008). "إنشاء مصفوفة لاحقة للذاكرة الخارجية بشكل أفضل" . مجلة الخوارزميات التجريبية . 12 : 1– 24. دوى : 10.1145/1227161.1402296 . S2CID 12296500 . 
• كولا، فابيان؛ ساندرز، بيتر (2007). "بناء مصفوفة لاحقة متوازية قابلة للتوسع". الحوسبة المتوازية . 33 (9): 605-612 . doi : 10.1016/j.parco.2007.06.004 .
• محمد إبراهيم أبو الهدى، ستيفان كورتز، وإينو أوهليبوش. "استبدال أشجار اللواحق بمصفوفات اللواحق المحسنة". مجلة الخوارزميات المنفصلة ، ​​2(1):53-86، 2004.
• دونغ كيو كيم، جيونغ إيون جيون، وهيجين بارك. "بنية بيانات فهرسة فعالة تتمتع بقدرات أشجار اللواحق ومصفوفات اللواحق للأبجديات ذات الحجم غير المهمل." معالجة السلاسل واسترجاع المعلومات، سلسلة محاضرات في علوم الحاسوب ، الصفحات 138-149، 2004.

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