مصفوفة LCP

لإيجاد عدد مرات ظهور سلسلة معينة${\displaystyle P}$(طول${\displaystyle m}$) في نص${\displaystyle T}$(طول${\displaystyle N}$), ^{[ 3 ]}

• نستخدم البحث الثنائي على مصفوفة اللواحق الخاصة بـ${\displaystyle T}$لإيجاد موضع البداية والنهاية لجميع حالات ظهور${\displaystyle P}$.
• والآن لتسريع عملية البحث، نستخدم مصفوفة LCP، وتحديداً نسخة خاصة من مصفوفة LCP (LCP-LR أدناه).

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

تساعد مصفوفة LCP-LR في تحسين ذلك إلى${\displaystyle O(m+\log N)}$، بالطريقة التالية:

في أي مرحلة من مراحل خوارزمية البحث الثنائي، نأخذ في الاعتبار، كالمعتاد، نطاقًا${\displaystyle (L,\dots ,R)}$من مجموعة اللواحق ونقطتها المركزية${\displaystyle M}$ونقرر ما إذا كنا سنواصل بحثنا في النطاق الفرعي الأيسر${\displaystyle (L,\dots ,M)}$أو في النطاق الفرعي الأيمن${\displaystyle (M,\dots ,R)}$لكي نتخذ القرار، نقوم بالمقارنة${\displaystyle P}$إلى السلسلة في${\displaystyle M}$. لو${\displaystyle P}$هو نفسه${\displaystyle M}$لقد اكتمل بحثنا. ولكن إن لم يكن كذلك، فقد قارنا بالفعل الخيار الأول.${\displaystyle k}$شخصيات${\displaystyle P}$ثم قرر ما إذا${\displaystyle P}$أصغر أو أكبر معجميًا من${\displaystyle M}$لنفترض أن النتيجة هي أن${\displaystyle P}$أكبر من${\displaystyle M}$لذا، في الخطوة التالية، سننظر في${\displaystyle (M,\dots ,R)}$ونقطة مركزية جديدة${\displaystyle M'}$في المنتصف:

 م ...... م' ...... ر | نحن نعلم: lcp(P,M)==k

يكمن السر الآن في أن LCP-LR يتم حسابه مسبقًا بحيث يكون${\displaystyle O(1)}$-lookup يخبرنا بأطول بادئة مشتركة لـ${\displaystyle M}$و${\displaystyle M'}$،${\displaystyle \mathrm {lcp} (M,M')}$.

نعلم بالفعل (من الخطوة السابقة) أن${\displaystyle M}$له بادئة خاصة به${\displaystyle k}$الشخصيات المشتركة مع${\displaystyle P}$:${\displaystyle \mathrm {lcp} (P,M)=k}$والآن توجد ثلاثة احتمالات:

• الحالة 1:${\displaystyle k<\mathrm {lcp} (M,M')}$، أي${\displaystyle P}$تحتوي على عدد أقل من الأحرف البادئة المشتركة مع M مقارنةً بما تشترك فيه M مع M'. هذا يعني أن الحرف (k+1) في M' هو نفسه الحرف (k+1) في M، وبما أن P أكبر معجميًا من M، فلا بد أن تكون أكبر معجميًا من M' أيضًا. لذا نتابع في النصف الأيمن (M',...,R).
• الحالة الثانية:${\displaystyle k>\mathrm {lcp} (M,M')}$، أي${\displaystyle P}$يحتوي على المزيد من الأحرف البادئة المشتركة مع${\displaystyle M}$من${\displaystyle M}$يشترك مع${\displaystyle M'}$وبالتالي، إذا قارنا${\displaystyle P}$ل${\displaystyle M'}$، سيكون البادئة المشتركة أصغر من${\displaystyle k}$، و${\displaystyle M'}$سيكون أكبر معجميًا من${\displaystyle P}$لذا، ودون إجراء المقارنة فعلياً، نواصل في النصف الأيسر${\displaystyle (M,\dots ,M')}$.
• الحالة الثالثة:${\displaystyle k=\mathrm {lcp} (M,M')}$إذن، M و M' متطابقتان مع${\displaystyle P}$في الأول${\displaystyle k}$الشخصيات. لتحديد ما إذا كنا سنستمر في النصف الأيسر أو الأيمن، يكفي مقارنة${\displaystyle P}$ل${\displaystyle M'}$بدءاً من${\displaystyle (k+1)}$الحرف th.
• نستمر بشكل متكرر.

والنتيجة الإجمالية هي أنه لا توجد سمة من سمات${\displaystyle P}$تتم مقارنة الحرف بأي حرف من النص أكثر من مرة (للمزيد من التفاصيل، انظر ^{[ 3 ]} ). ويقتصر العدد الإجمالي لمقارنات الأحرف على${\displaystyle m}$إذن فإن التعقيد الكلي هو بالفعل${\displaystyle O(m+\log N)}$.

ما زلنا بحاجة إلى حساب LCP-LR مسبقًا حتى يتمكن من إخبارنا بذلك في${\displaystyle O(1)}$احسب قيمة LCP بين أي عنصرين في مصفوفة اللواحق. نعلم أن مصفوفة LCP القياسية تعطينا قيمة LCP للعناصر المتتالية فقط، أي${\displaystyle \mathrm {lcp} (i-1,i)}$لأي${\displaystyle i}$. لكن،${\displaystyle M}$و${\displaystyle M'}$لا تُعتبر المدخلات المذكورة في الوصف أعلاه بالضرورة مدخلات متتالية.

يكمن مفتاح ذلك في إدراك أن نطاقات معينة فقط${\displaystyle (L,\dots ,R)}$لن يحدث ذلك أبدًا أثناء البحث الثنائي: يبدأ دائمًا بـ${\displaystyle (0,\dots ,N)}$ويقسمها من المنتصف، ثم يستمر إما إلى اليسار أو اليمين ويقسمها إلى نصفين مرة أخرى وهكذا. ويمكن النظر إلى الأمر بطريقة أخرى  : كل عنصر في مصفوفة اللواحق يمثل نقطة مركزية لنطاق واحد ممكن فقط أثناء البحث الثنائي. لذا، يوجد بالضبط N نطاقًا مختلفًا.${\displaystyle (L\dots M\dots R)}$قد يلعب ذلك دورًا أثناء البحث الثنائي، ويكفي إجراء الحساب المسبق.${\displaystyle \mathrm {lcp} (L,M)}$و${\displaystyle \mathrm {lcp} (M,R)}$لأولئك${\displaystyle N}$النطاقات المحتملة. هذا هو${\displaystyle 2N}$القيم المحسوبة مسبقًا المتميزة، وبالتالي فإن LCP-LR هو${\displaystyle O(N)}$في الحجم.

علاوة على ذلك، توجد خوارزمية تكرارية مباشرة لحساب${\displaystyle 2N}$قيم LCP-LR في${\displaystyle O(N)}$الوقت من مصفوفة LCP القياسية.

لتلخيص:

• من الممكن حساب LCP-LR في${\displaystyle O(N)}$الوقت و${\displaystyle O(2N)=O(N)}$مسافة من LCP.
• يساعد استخدام خوارزمية LCP-LR أثناء البحث الثنائي على تسريع عملية البحث من${\displaystyle O(M\log N)}$ل${\displaystyle O(M+\log N)}$.
• يمكننا استخدام عمليتي بحث ثنائيتين لتحديد الطرف الأيسر والأيمن لنطاق المطابقة لـ${\displaystyle P}$، ويتوافق طول نطاق التطابق مع عدد مرات ظهور P.

بالنظر إلى مصفوفة اللواحق${\displaystyle A}$ومصفوفة LCP${\displaystyle H}$من سلسلة${\displaystyle S=s_{1},s_{2},\ldots s_{n}\$}$من الطول${\displaystyle n+1}$شجرة اللواحق الخاصة بها${\displaystyle ST}$يمكن بناؤها في${\displaystyle O(n)}$يعتمد الوقت على الفكرة التالية: ابدأ بشجرة اللواحق الجزئية لأصغر لاحقة معجميًا وقم بإدخال اللواحق الأخرى بشكل متكرر بالترتيب الذي تحدده مصفوفة اللواحق.

يترك${\displaystyle ST_{i}}$كن شجرة اللواحق الجزئية لـ${\displaystyle 0\leq i\leq n}$. علاوة على ذلك، دع${\displaystyle d(v)}$ليكن طول سلسلة جميع تسميات المسارات من جذر${\displaystyle ST_{i}}$إلى العقدة${\displaystyle v}$.

ابدأ بـ${\displaystyle ST_{0}}$، الشجرة التي تتكون من الجذر فقط. لإدراج${\displaystyle A[i+1]}$داخل${\displaystyle ST_{i}}$اسلك المسار الأيمن بدءًا من الورقة التي تم إدخالها مؤخرًا${\displaystyle A[i]}$إلى الجذر، حتى أعمق عقدة${\displaystyle v}$مع${\displaystyle d(v)\leq H[i+1]}$يتم الوصول إليه.

نحتاج إلى التمييز بين حالتين:

• ${\displaystyle d(v)=H[i+1]}$هذا يعني أن تسلسل التسميات على الجذر إلى${\displaystyle v}$المسار يساوي أطول بادئة مشتركة من اللواحق${\displaystyle A[i]}$و${\displaystyle A[i+1]}$في هذه الحالة ، أدخل${\displaystyle A[i+1]}$كصفحة جديدة${\displaystyle x}$عقدة${\displaystyle v}$وقم بتسمية الحافة${\displaystyle (v,x)}$مع${\displaystyle S[A[i+1]+H[i+1],n]}$وبالتالي، يتكون تصنيف الحافة من الأحرف المتبقية من اللاحقة.${\displaystyle A[i+1]}$التي لا يتم تمثيلها بالفعل من خلال تسلسل تسميات الجذر إلى${\displaystyle v}$المسار. هذا يُنشئ شجرة اللواحق الجزئية${\displaystyle ST_{i+1}}$.

  

• ${\displaystyle d(v)<H[i+1]}$هذا يعني أن تسلسل التسميات على الجذر إلى${\displaystyle v}$يعرض المسار عددًا أقل من الأحرف مقارنةً بأطول بادئة مشتركة من اللواحق.${\displaystyle A[i]}$و${\displaystyle A[i+1]}$والأحرف المفقودة موجودة في تسمية الحافة لـ${\displaystyle v}$الحافة اليمنى لـ 's . لذلك، علينا تقسيم تلك الحافة على النحو التالي: ليكن${\displaystyle w}$أن يكون ابن${\displaystyle v}$على${\displaystyle ST_{i}}$المسار الأيمن.

1. احذف الحافة${\displaystyle (v,w)}$.
2. أضف عقدة داخلية جديدة${\displaystyle y}$وحافة جديدة${\displaystyle (v,y)}$مع ملصق${\displaystyle S[A[i]+d(v),A[i]+H[i+1]-1]}$يتكون الملصق الجديد من الأحرف المفقودة من أطول بادئة مشتركة لـ${\displaystyle A[i]}$و${\displaystyle A[i+1]}$وبالتالي، فإن تسلسل تسميات الجذر إلى${\displaystyle y}$يعرض المسار الآن أطول بادئة مشتركة لـ${\displaystyle A[i]}$و${\displaystyle A[i+1]}$.
3. يتصل${\displaystyle w}$إلى العقدة الداخلية التي تم إنشاؤها حديثًا${\displaystyle y}$من خلال الحافة${\displaystyle (y,w)}$هذا مصنف${\displaystyle S[A[i]+H[i+1],A[i]+d(w)-1]}$يتكون الملصق الجديد من الأحرف المتبقية من الحافة المحذوفة${\displaystyle (v,w)}$التي لم تُستخدم كعلامة للحافة${\displaystyle (v,y)}$.
4. يضيف${\displaystyle A[i+1]}$كصفحة جديدة${\displaystyle x}$وقم بتوصيله بالعقدة الداخلية الجديدة${\displaystyle y}$من خلال الحافة${\displaystyle (y,x)}$هذا مصنف${\displaystyle S[A[i+1]+H[i+1],n]}$وبالتالي، يتكون تصنيف الحافة من الأحرف المتبقية من اللاحقة.${\displaystyle A[i+1]}$التي لا يتم تمثيلها بالفعل من خلال تسلسل تسميات الجذر إلى${\displaystyle v}$طريق.
5. يؤدي هذا إلى إنشاء شجرة اللواحق الجزئية${\displaystyle ST_{i+1}}$.

تُظهر حجة استهلاك بسيطة أن وقت تشغيل هذه الخوارزمية محدود بـ${\displaystyle O(n)}$:

العقد التي يتم اجتيازها في الخطوة${\displaystyle i}$عن طريق السير في المسار الأيمن من${\displaystyle ST_{i}}$(باستثناء العقدة الأخيرة)${\displaystyle v}$تُزال من المسار الأيمن ، عندما${\displaystyle A[i+1]}$تُضاف هذه العقد إلى الشجرة كعقدة جديدة. ولن يتم اجتياز هذه العقد مرة أخرى في جميع الخطوات اللاحقة.${\displaystyle j>i}$لذلك، على الأكثر${\displaystyle 2n}$سيتم اجتياز العقد بالكامل.

مصفوفة LCP${\displaystyle H}$يحتوي فقط على طول أطول بادئة مشتركة لكل زوج من اللواحق المتتالية في مصفوفة اللواحق${\displaystyle A}$ومع ذلك، بمساعدة مصفوفة اللواحق العكسية${\displaystyle A^{-1}}$(${\displaystyle A[i]=j\Leftrightarrow A^{-1}[j]=i}$أي اللاحقة${\displaystyle S[j,n]}$يبدأ ذلك من الموقع${\displaystyle j}$في${\displaystyle S}$يتم تخزينها في الموضع${\displaystyle A^{-1}[j]}$في${\displaystyle A}$) والاستعلامات الدنيا ذات النطاق الزمني الثابت على${\displaystyle H}$من الممكن تحديد طول أطول بادئة مشتركة للواحق العشوائية في${\displaystyle O(1)}$وقت.

بسبب الترتيب المعجمي لمصفوفة اللاحقة، كل بادئة مشتركة للواحق${\displaystyle S[i,n]}$و${\displaystyle S[j,n]}$يجب أن يكون بادئة مشتركة لجميع اللواحق بين${\displaystyle i}$موقع 's في مصفوفة اللواحق${\displaystyle A^{-1}[i]}$و${\displaystyle j}$موقع 's في مصفوفة اللواحق${\displaystyle A^{-1}[j]}$لذلك، فإن طول أطول بادئة مشتركة بين جميع هذه اللواحق هو القيمة الدنيا في الفترة${\displaystyle H[A^{-1}[i]+1,A^{-1}[j]]}$يمكن إيجاد هذه القيمة في زمن ثابت إذا${\displaystyle H}$تتم معالجتها مسبقًا للاستعلامات المتعلقة بالحد الأدنى للنطاق.

وبالتالي، بالنظر إلى سلسلة نصية${\displaystyle S}$من الطول${\displaystyle n}$ وموقعان عشوائيان ${\displaystyle i,j}$في السلسلة${\displaystyle S}$ مع${\displaystyle A^{-1}[i]<A^{-1}[j]}$، طول أطول بادئة مشتركة بين اللواحق${\displaystyle S[i,n]}$و${\displaystyle S[j,n]}$يمكن حسابها على النحو التالي:${\displaystyle \operatorname {LCP} (i,j)=H[\operatorname {RMQ} _{H}(A^{-1}[i]+1,A^{-1}[j])]}$.