شجرة متناظرة

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

وصف

مثال على شجرة الكلمات المتناظرة لـ TACOCAT، حيث تمثل الخطوط المتصلة حواف الأحرف والخطوط المتقطعة حواف اللواحق.

كغيرها من الأشجار، تتكون شجرة الكلمات المتناظرة من رؤوس وحواف موجهة . يمثل كل رأس في الشجرة كلمة متناظرة (مثل 'tacocat')، ولكنه يخزن طولها فقط، بينما تمثل كل حافة إما حرفًا أو لاحقة . تشير حواف الأحرف إلى أنه عند إضافة حرف إلى طرفي الكلمة المتناظرة التي يمثلها رأس المصدر، تتكون الكلمة المتناظرة في رأس الوجهة (على سبيل المثال، حافة تحمل الحرف 't' تربط رأس المصدر 'acoca' برأس الوجهة 'tacocat'). تربط حافة اللاحقة كل كلمة متناظرة بأكبر لاحقة متناظرة تمتلكها (في المثال السابق، ترتبط لاحقة 'tacocat' بالحرف 't'، بينما ترتبط لاحقة 'atacocata' بالحرف 'ata'). ما يميز أشجار الكلمات المتناظرة عن الأشجار العادية هو وجود جذرين لها (فهي في الواقع شجرتان منفصلتان). يمثل الجذران متناظرين بطول -1 و0. أي أنه إذا أُضيف الحرف 'a' إلى كلا الجذرين، فستُنتج الشجرة 'a' و'aa' على التوالي. وبما أن كل حافة تُضيف (أو تُزيل) عددًا زوجيًا من الأحرف، فإن الشجرتين متصلتان فقط بحواف اللواحق.

العمليات

يضيف

بما أن شجرة المتناظرات تُبنى بشكل متسلسل، فإنها تحتفظ بمؤشر إلى آخر متناظر أُضيف إليها. لإضافة الحرف التالي إلى شجرة المتناظرات، add(x)يُتحقق أولًا مما إذا كان الحرف الأول قبل المتناظر يُطابق الحرف المُضاف، فإذا لم يُطابقه، تُتبع روابط اللواحق حتى يُمكن إضافة متناظر إلى الشجرة. بمجرد العثور على متناظر، إذا كان موجودًا بالفعل في الشجرة، فلا حاجة لأي إجراء. وإلا، يُضاف رأس جديد مع رابط من اللاحقة إلى هذا الرأس، ويُضاف رابط لاحقة للرأس الجديد. إذا كان طول المتناظر الجديد يساوي 1، فإن رابط اللاحقة يُشير إلى جذر شجرة المتناظرات الذي يُمثل طولًا يساوي -1.

# S -> سلسلة الإدخال # x -> موضع الحرف المراد إضافته في السلسلة def add ( x : int ) -> bool : """إضافة حرف إلى شجرة الكلمات المتناظرة.""" while True : if x - 1 - current . length >= 0 and S [ x - 1 - current . length ] == S [ x ]: break current = current . suffixإذا لم تكن قيمة `current.add [ S [ x ] ] ` تساوي `None` ، فسيتم إرجاع القيمة `False`.اللاحقة = الحالي ، الحالي = رأس متناظر ( ) ، الحالي.الطول = اللاحقة.الطول + 2 ، اللاحقة.إضافة [ S [ x ] ] = الحاليإذا كان طول العنصر الحالي يساوي 1 ، فإن لاحقة العنصر الحالي تساوي الجذر ، ثم يتم إرجاع القيمة True.بينما صحيح : اللاحقة = اللاحقة.اللاحقة إذا كان طول x - 1 - اللاحقة أكبر من أو يساوي 0 و S [ x - 1 - اللاحقة.الطول ] يساوي S [ x ] : اللاحقة الحالية = اللاحقة.أضف [ S [ x ] ] أرجع صحيح

الأشجار المشتركة

يمكن إيجاد المتواليات المتناظرة المشتركة بين عدة سلاسل نصية أو الفريدة لسلسلة نصية واحدة باستخدام $O(n*i)$ مساحة إضافية حيث $i$ يمثل عدد السلاسل النصية التي تتم مقارنتها. ويتم ذلك عن طريق إضافة مصفوفة بطول $i$ لكل رأس، وتعيين العلامة إلى 1 عند الفهرس $i$ إذا تم الوصول إلى تلك الرأس عند إضافة السلسلة $i$ التعديل الوحيد الآخر المطلوب هو إعادة ضبط المؤشر الحالي إلى الجذر في نهاية كل سلسلة نصية. من خلال ربط الأشجار بهذه الطريقة، يمكن حل المشكلات التالية:

عدد الكلمات المتناظرة المشتركة بين جميع السلاسل
عدد الكلمات المتناظرة الفريدة في سلسلة نصية
أطول سلسلة متناظرة مشتركة بين جميع السلاسل
عدد المتواليات المتناظرة التي تظهر بشكل متكرر في سلسلة واحدة أكثر من غيرها

تعقيد

وقت

يستغرق بناء شجرة الكلمات المتناظرة $O(n\log {\sigma })$ الوقت، أين $n$ هو طول الخيط و $\sigma$ حجمه بحجم الأبجدية. مع $n$ المكالمات إلى add(x)، كل مكالمة تستغرق $O(\log {\sigma })$ الوقت المستهلك . هذا نتيجة لكل استدعاء add(x)يزيد عمق الرأس الحالي (آخر كلمة متناظرة في الشجرة) بمقدار واحد على الأكثر، ويستغرق البحث في جميع حواف الأحرف الممكنة للرأس $O(\log {\sigma })$ الوقت. من خلال تخصيص تكلفة الانتقال لأعلى ولأسفل الشجرة لكل استدعاء لـ add(x)، يتم "دفع" تكلفة الانتقال لأعلى الشجرة أكثر من مرة من خلال عدد متساوٍ من الاستدعاءات لـ add(x)عندما لم يحدث الانتقال لأعلى الشجرة.

فضاء

شجرة متناظرة تأخذ $O(n)$ المساحة: على الأكثر $n+2$ رؤوس لتخزين التتابعات الفرعية المتناظرة وجذرين، $n$ الحواف التي تربط الرؤوس و $n+2$ حواف لاحقة.

المفاضلة بين الزمكان والمكان

إذا قمنا بدلاً من تخزين حواف الجمع الموجودة لكل كلمة متناظرة فقط، بمصفوفة طولها $\sigma$ يتم تخزين الحواف، ويمكن إيجاد الحافة الصحيحة في وقت ثابت مما يقلل وقت الإنشاء إلى $O(n+p*\sigma )$ مع زيادة المساحة لـ $O(p*\sigma )$ ، أين $p$ هو عدد الكلمات المتناظرة.

مراجع

↑ روبينتشيك، ميخائيل؛ شور، أرسيني م. (2015). "Eertree: بنية بيانات فعالة لمعالجة المتناظرات في السلاسل النصية". المجلة الأوروبية للتوافقية . arXiv : 1506.04862v1 .
↑ جاليل، زفي؛ سيفراس، جويل (1978). "خوارزمية التعرف الخطي الفوري لـ Palstar " . مجلة ACM . 25 (1): 102-111 . doi : 10.1145/322047.322056 . S2CID 41095273 .
^ فيسي، غابرييل. جاجي، ترافيس؛ كاركاينن، جحا؛ كيمبا، دومينيك (2014). "خوارزمية شبه تربيعية للحد الأدنى من التحليل المتناوب" . مجلة الخوارزميات المنفصلة . 28 : 41 – 48. أرخايف : 1403.2431 . دوى : 10.1016/j.jda.2014.08.001 . S2CID 14871164 .

[MR&AS-1] روبينتشيك، ميخائيل؛ شور، أرسيني م. (2015). "Eertree: بنية بيانات فعالة لمعالجة المتناظرات في السلاسل النصية". المجلة الأوروبية للتوافقية . arXiv : 1506.04862v1 .

[kfactor-2] جاليل، زفي؛ سيفراس، جويل (1978). "خوارزمية التعرف الخطي الفوري لـ Palstar " . مجلة ACM . 25 (1): 102-111 . doi : 10.1145/322047.322056 . S2CID 41095273 .

[plength-3] فيسي، غابرييل. جاجي، ترافيس؛ كاركاينن، جحا؛ كيمبا، دومينيك (2014). "خوارزمية شبه تربيعية للحد الأدنى من التحليل المتناوب" . مجلة الخوارزميات المنفصلة . 28 : 41 – 48. أرخايف : 1403.2431 . دوى : 10.1016/j.jda.2014.08.001 . S2CID 14871164 .

[ 1 ]

[ 2 ]

[ 3 ]

اللغة	العربية (RTL)
روابط موسوعية	16 رابطاً
المصدر الأصلي	ويكيبيديا ↗