استعلام الحد الأدنى للنطاق
في علوم الحاسوب ، تُستخدم استعلامات الحد الأدنى للنطاق ( RMQ ) لحل مشكلة إيجاد القيمة الدنيا في مصفوفة فرعية من مصفوفة من الكائنات القابلة للمقارنة. وتُستخدم استعلامات الحد الأدنى للنطاق في العديد من تطبيقات علوم الحاسوب، مثل مشكلة السلف المشترك الأدنى ومشكلة البادئة المشتركة الأطول ( LCP).
تعريف
بالنظر إلى مصفوفة A [1 … n ] من n كائنات مأخوذة من مجموعة مرتبة كليًا ، مثل الأعداد الصحيحة، فإن استعلام الحد الأدنى للنطاق RMQ A ( l , r ) =arg min A [ k ] (مع 1 ≤ l ≤ k ≤ r ≤ n ) يُرجع موضع العنصر الأدنى في المصفوفة الفرعية المحددة A [ l … r ] .
على سبيل المثال، عندما تكون A = [0,5,2,5,4,3,1,6,3] ، فإن إجابة استعلام الحد الأدنى للنطاق للمصفوفة الفرعية A [3 … 8] = [2,5,4,3,1,6] هي7 ، حيث A [7] = 1 .
الخوارزميات
حل ساذج
في الوضع النموذجي، تكون المصفوفة A ثابتة، أي لا تُضاف عناصر إليها أو تُحذف منها أثناء تنفيذ سلسلة من الاستعلامات، وتُجاب الاستعلامات فورًا (أي أن مجموعة الاستعلامات الكاملة غير معروفة مسبقًا للخوارزمية). في هذه الحالة، تضمن المعالجة المسبقة المناسبة للمصفوفة وتحويلها إلى بنية بيانات سرعة أكبر في الإجابة على الاستعلامات. يتمثل أحد الحلول البسيطة في حساب جميع الاستعلامات الممكنة مسبقًا، أي إيجاد أصغر قيمة بين جميع المصفوفات الفرعية لـ A ، وتخزينها في مصفوفة B بحيث يكون B [ i , j ] = min( A [ i , j ]) ؛ عندئذٍ يمكن حل استعلام البحث عن أصغر قيمة في نطاق معين في وقت ثابت عن طريق البحث في المصفوفة B. يوجد Θ( n² ) استعلامًا ممكنًا لمصفوفة طولها n ، ويمكن حساب إجابات هذه الاستعلامات في وقت Θ( n² ) باستخدام البرمجة الديناميكية . [ 1 ]
الحل باستخدام زمن ثابت بعد حساب مسبق خطي لوغاريتمي للمساحة والزمن
كما في الحل أعلاه، يُمكن تحقيق الإجابة على الاستعلامات في وقت ثابت من خلال حساب النتائج مسبقًا. مع ذلك، لن يخزن المصفوفة استعلامات الحد الأدنى للنطاق المحسوبة مسبقًا لكل نطاق [ i , j ] ، بل فقط للنطاقات التي يكون حجمها قوة للعدد اثنين . يوجد O(log n ) من هذه الاستعلامات لكل موضع بداية i ، لذا فإن حجم جدول البرمجة الديناميكية B هو O( n log n ) . قيمة B [ i , j ] هي فهرس الحد الأدنى للنطاق A [ i … i + 2j -1] . يستغرق ملء الجدول وقتًا قدره O( n log n ) ، باستخدام فهارس الحد الأدنى وفقًا للعلاقة التكرارية التالية [ 1 ] [ 2 ].
- إذا كان A [ B [ i , j -1]] ≤ A [ B [ i +2 j -1 , j -1]] ، فإن B [ i , j ] = B [ i , j -1] ؛
- وإلا، فإن B [ i , j ] = B [ i +2 j -1 , j -1] .
بعد هذه الخطوة الحسابية المسبقة، يمكن الآن الإجابة على الاستعلام RMQ A ( l , r ) في وقت ثابت بتقسيمه إلى استعلامين منفصلين: الأول هو الاستعلام المحسوب مسبقًا بنطاق من l إلى أكبر قيمة مخزنة أصغر من r . أما الثاني فهو استعلام عن فترة بنفس الطول، وحدودها اليمنى هي r . قد تتداخل هاتان الفترتان، ولكن بما أننا نحاول حساب القيمة الدنيا وليس، على سبيل المثال، مجموع الأرقام في المصفوفة، فإن هذا لا يُؤثر. وبالتالي، يمكن الحصول على النتيجة الإجمالية، بعد الحساب المسبق ذي الوقت الخطي اللوغاريتمي، في وقت ثابت: يمكن الإجابة على الاستعلامين في وقت ثابت، والشيء الوحيد المتبقي هو اختيار النتيجة الأصغر.
| ك | |||||
|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | ||
| ل | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 3 | 3 | 7 | |
| 3 | 3 | 3 | 3 | 7 | |
| 4 | 4 | 5 | 6 | 7 | |
| 5 | 5 | 6 | 7 | 7 | |
| 6 | 6 | 7 | 7 | 7 | |
| 7 | 7 | 7 | 7 | 7 | |
| 8 | 8 | 7 | 7 | 7 | |
| 9 | 9 | 7 | 7 | 7 | |
الحل باستخدام وقت الاستعلام اللوغاريتمي بعد الحساب المسبق الخطي للوقت والمساحة
يُجري هذا الحل الحساب المسبق في زمن قدره O ( n ) . تستخدم هياكل بياناته مساحة قدرها O ( n ) ، ويمكن استخدامها للإجابة على الاستعلامات في زمن لوغاريتمي. [ 2 ] تُقسّم المصفوفة مبدئيًا إلى كتل بحجم s = log n / 4. ثم يُحسب الحد الأدنى لكل كتلة في زمن إجمالي قدره O ( n ) ، وتُخزّن القيم الدنيا في مصفوفة جديدة.
يمكن الآن الإجابة على أسئلة البحث عن الموارد (RMQs) في وقت لوغاريتمي من خلال النظر إلى الكتل التي تحتوي على حدود الاستعلام اليسرى، وحدود الاستعلام اليمنى، وجميع الكتل بينهما:
- يمكن البحث في الكتلتين اللتين تحتويان على الحدود بطريقة بسيطة. لا داعي حتى للنظر في العناصر الموجودة خارج الحدود. ويمكن القيام بذلك في وقت لوغاريتمي.
- يجب مقارنة القيم الدنيا لجميع الكتل الموجودة بالكامل في النطاق، والقيمتين الدنيا المذكورتين أعلاه، للإجابة على الاستعلام.
- لأن المصفوفة تم تقسيمها إلى كتل بحجم log n / 4 ، فهناك على الأكثر 4 n / log n كتل مضمنة بالكامل في الاستعلام.
- باستخدام الحل الخطي اللوغاريتمي، يمكن إيجاد الحد الأدنى الإجمالي بين هذه الكتل. حجم بنية البيانات هذه هو O ( n / log n log ( n / log n ) ) = O ( n ) .
- الآن، لم يتبق سوى مقارنة ثلاث قيم دنيا.
على سبيل المثال، باستخدام المصفوفة A = [0,5,2,5,4,3,1,6,3] وحجم كتلة يبلغ3 (لأغراض التوضيح فقط) ينتج عنه المصفوفة الدنيا A' = [0,3,1] .
الحل باستخدام زمن ثابت ومساحة خطية
باستخدام الحل المذكور أعلاه، لا يزال يتعين الإجابة على الاستعلامات الفرعية داخل الكتل التي لا يشملها الاستعلام بالكامل في وقت ثابت. يوجد على الأكثر كتلتان من هذه الكتل: الكتلة التي تحتوي على l والكتلة التي تحتوي على r . يتم تحقيق الوقت الثابت عن طريق تخزين الأشجار الديكارتية لجميع الكتل في المصفوفة. بعض الملاحظات:
- تعطي الكتل ذات الأشجار الديكارتية المتماثلة نفس النتيجة لجميع الاستعلامات في تلك الكتلة
- عدد الأشجار الديكارتية المختلفة المكونة من s عقدة هو C s ، وهو العدد الكاتالوني رقم s .
- لذلك، يتراوح عدد الأشجار الديكارتية المختلفة للكتل بين 4 و 5
لكل شجرة من هذا النوع ، يجب تخزين النتيجة المحتملة لجميع الاستعلامات. وهذا يعني أن حجم الجدول الإجمالي هو O ( n ) .
للبحث عن النتائج بكفاءة، يجب أن يكون الوصول إلى الشجرة الديكارتية (الصف) المقابلة لكتلة معينة ممكنًا في زمن ثابت. يكمن الحل في تخزين نتائج جميع الأشجار في مصفوفة، ثم إيجاد إسقاط فريد من الأشجار الثنائية إلى أعداد صحيحة للوصول إلى المدخلات. يمكن تحقيق ذلك من خلال إجراء بحث بالعرض أولًا عبر الشجرة، وإضافة عقد ورقية بحيث يكون لكل عقدة موجودة في الشجرة الديكارتية ولدان فقط. بعد ذلك، يتم توليد العدد الصحيح بتمثيل كل عقدة داخلية كبت 0، وكل عقدة ورقية كبت 1 في كلمة بتية (عن طريق اجتياز الشجرة بترتيب المستويات مرة أخرى). يؤدي هذا إلى حجم قدره log n / 4 لكل شجرة . لتمكين الوصول العشوائي في زمن ثابت إلى أي شجرة، يجب تضمين الأشجار غير الموجودة في المصفوفة الأصلية أيضًا. مصفوفة ذات فهارس بطول log n / 4 بت يكون حجمها 2 log n / 4 = O ( n ) .
| فِهرِس | 1 | 2 | 3 | ||||||
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 | |
| 0 | — | ||||||||
| 23 (Bitword 0010111) | 1 | 2 | 3 | — | 2 | 3 | — | — | 3 |
| 39 (Bitword 0100111) | 1 | 1 | 1 | — | 2 | 3 | — | — | 3 |
| 127 | — | ||||||||
التطبيقات
تُستخدم خوارزميات مطابقة السلاسل النصية (RMQs) كأداة للعديد من المهام في مطابقة السلاسل النصية الدقيقة والتقريبية . ويمكن الاطلاع على العديد من التطبيقات في فيشر وهيون (2007). [ 3 ] : 3
حساب السلف المشترك الأدنى في الشجرة
يمكن استخدام استعلامات RMQ لحل مشكلة السلف المشترك الأدنى [ 1 ] [ 2 ] ، وتُستخدم كأداة للعديد من المهام في مطابقة السلاسل النصية الدقيقة والتقريبية . يُعيد استعلام LCA، LCA S ( v , w ) لشجرة جذرية S = ( V , E ) وعقدتين v و w ∈ V ، أعمق عقدة u (والتي قد تكون v أو w ) على المسارات من الجذر إلى كل من w و v . وقد أظهر جابو وبنتلي وتارجان (1984) أنه يمكن اختزال مشكلة LCA في وقت خطي إلى مشكلة RMQ. وبناءً على ذلك، يمكن حل مشكلة LCA، مثل مشكلة RMQ، في وقت ثابت ومساحة خطية. [ 3 ]
حساب أطول بادئة مشتركة في سلسلة نصية
في سياق فهرسة النصوص، يمكن استخدام استعلامات RMQ لإيجاد أطول بادئة مشتركة (LCP)، حيث تحسب الدالة LCP T ( i , j ) أطول بادئة مشتركة لللاحقات التي تبدأ عند الفهرسين i و j في المصفوفة T. وللقيام بذلك، نحسب أولًا مصفوفة اللواحق A ، ومصفوفة اللواحق العكسية A − 1. ثم نحسب مصفوفة LCP، H، التي تعطي أطول بادئة مشتركة لللاحقات المتجاورة في A. بمجرد حساب هياكل البيانات هذه، واستكمال المعالجة المسبقة لاستعلامات RMQ، يمكن حساب طول أطول بادئة مشتركة بشكل عام في وقت ثابت باستخدام الصيغة: LCP( i , j ) = RMQ H ( A - 1 [ i ] + 1, A - 1 [ j ]) ، حيث نفترض، للتبسيط، أن A - 1 [ i ] + 1 ≤ A - 1 [ j ] (وإلا يتم التبديل). [ 4 ]
انظر أيضاً
مراجع
- بيركمان، عمر؛ فيشكين، أوزي (1993). "بنية بيانات متوازية متكررة على شكل شجرة نجمية" . مجلة SIAM للحوسبة . 22 (2): 221-242 . doi : 10.1137/0222017 . مؤرشف من الأصل في 23 سبتمبر 2017.
- يوهانس فيشر (ديسمبر 2009). الإيجاز الأمثل لاستعلامات الحد الأدنى للنطاق (تقرير فني). جامعة توبنغن، مركز المعلوماتية الحيوية. arXiv : 0812.2775 . Bibcode : 2008arXiv0812.2775F .
- [ 2 ]
- بندر، مايكل أ.؛ فاراش-كولتون، مارتن ؛ بيماساني، غيريدهار؛ سكينا، ستيفن ؛ سومازين، بافيل (2005). "أدنى الأسلاف المشتركة في الأشجار والرسوم البيانية الموجهة غير الدورية" (ملف PDF) . مجلة الخوارزميات . 57 ( 2 ) : 75-94 . doi : 10.1016 /j.jalgor.2005.08.001 .
- 1 2 3 4 بندر، مايكل؛ فاراش-كولتون، مارتن (2000). "إعادة النظر في مشكلة تقييم دورة الحياة". LATIN 2000: المعلوماتية النظرية . LNCS. المجلد 1776. سبرينغر. الصفحات 88-94 . doi : 10.1007/10719839_9 . ISBN 978-3-540-67306-4.
- 1 2 فيشر، يوهانس؛ هيون، فولكر (2007). "تمثيل جديد موجز لمعلومات RMQ وتحسينات في مصفوفة اللواحق المحسّنة". التوافقية، والخوارزميات، والمنهجيات الاحتمالية والتجريبية . وقائع الندوة الدولية حول التوافقية، والخوارزميات، والمنهجيات الاحتمالية والتجريبية. سلسلة محاضرات في علوم الحاسوب. المجلد 4614. سبرينغر. الصفحات 459-470 . doi : 10.1007/978-3-540-74450-4_41 . ISBN 978-3-540-74449-8.
- ↑ فيشر، ج. وهيون، ف. (2006). "تحسينات نظرية وعملية على مسألة RMQ، مع تطبيقات على LCA وLCE". مطابقة الأنماط التوافقية . سلسلة محاضرات في علوم الحاسوب. المجلد 4009. الصفحات 36-48 . CiteSeerX 10.1.1.64.5439 . doi : 10.1007/11780441_5 . ISBN 978-3-540-35455-0.
روابط خارجية
- خوارزميات البحث