شجرة بوادئ

الشجرة الرقمية في سياق علوم الحاسب هي هيكل بيانات شجري تحتوي عقده غالبا على تسلسل من الحروف، ترتبط فيما بينها بحسب ترتيب الحروف ابتداءا من الحرف الأول، حيث أن كل عقدة فرعية ترث حروف العقدة الأصلية لها وبنفس الترتيب، لِتُكون حروف مشتركة بينهم تسمي المفتاح (انظر الصورة المقابلة)، ومن ثَم فإن موقع عُقدها الفرعية بالنسبة للعقدة الأصلية هو الذي يحدد قيمتها، بعبارة أخرى فإنه يمكن التنبؤ بالعقدة الفرعية إذا ما عرفت العقدة الأصلية لها، وهو الأمر الذي يُمَكن الشجرة الرقمية من أن تعمل كشجرة بحث عن عقدة تحتوي على تسلسل معين من الحروف (تسمى المفتاح) باستخدام خوارزمية بحث العمق أولاً.

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

 التاريخ وأصل الكلمة والنطق 
وصف أكسل تو فكرة الشجرة الرقمية كطريقة لتمثيل تسلسل من الحروف بشكل مجرد لأول مرة عام 1912،
 Cited by Knuth.
ثم وصفها René de la Briandais في سياق الحاسب لأول مرة عام 1959،

كما وصفها ادوارد فريدكين بشكل مستقل عام 1960، 
وهو الذي صاغ لها مصطلح trie

 التطبيقات 

 تمثيل القاموس 
يشيع استخدام الشجرة الرقمية في النص التنبؤي وقواميس لإكمال التلقائي، وخوارزميات المطابقة التقريبية للسلاسل، 
ومواءمة أطول بادئة والتدقيق الإملائي نظرا لسرعتها في البحث وصغر حجم الذاكرة المطلوبة.
Franklin Mark Liang (1983). Word Hy-phen-a-tion By Com-put-er (PDF) (Doctor of Philosophy thesis). Stanford University. Archived (PDF) from the original on 2005-11-11. Retrieved 2010-03-28.

وتستفيد هذه التطبيقات من قدرة trie على البحث عن الإدخالات وإدراجها وحذفها بسرعة. ومع ذلك، إذا كان تخزين كلمات القاموس هو كل ما هو مطلوب (أي ليست هناك حاجة لتخزين البيانات الوصفية المرتبطة بكل كلمة)، فإن الحد الأدنى من آلية الحالة المحدودة الحتمية (DAFSA) أو شجرة الجذر ستستخدم مساحة تخزين أقل من ثلاثي. وذلك لأن DAFSAs وأشجار الجذر يمكن أن تضغط على فروع متطابقة من trie والتي تتوافق مع نفس اللواحق (أو الأجزاء) من الكلمات المختلفة المخزنة.

 استبدال هياكل البيانات الأخرى 

 استبدال جداول التجزئة 
يمكن استبدال جدول التجزئة بالشجرة الرقمية لتحقيق المزايا التالية:
 ويكون البحث عن البيانات في trie أسرع في أسوأ الحالات، O (m) time (حيث m هو طول سلسلة البحث)، مقارنة بجدول التجزئة غير الكامل. يمكن أن يحتوي جدول التجزئة غير الكامل على تصادمات رئيسية. اصطدام المفاتيح هو تعيين وظيفة التجزئة لمفاتيح مختلفة لنفس الموضع في جدول التجزئة. أسرع سرعة بحث في جدول تجزئة غير كامل هي وقت O (N) ، ولكن عادةً ما تكون O (1)، مع وقت O (m) الذي يقضيه في تقييم التجزئة.
 لا توجد اصطدامات بين مفاتيح مختلفة في ثلاثي.
 تعتبر الحاويات الموجودة في مثلث، والتي تشبه حاويات جدول التجزئة التي تخزن تصادمات المفاتيح، ضرورية فقط إذا كان مفتاح واحد مرتبطًا بأكثر من قيمة واحدة.
 ليست هناك حاجة لتوفير وظيفة تجزئة أو لتغيير وظائف التجزئة حيث تتم إضافة المزيد من المفاتيح إلى ثلاثي.
 يمكن أن يوفر Trie ترتيبًا أبجديًا للإدخالات حسب المفتاح.

ومع ذلك، فإن الشجرة الرقمية أيضًا لها بعض العيوب مقارنة بجدول التجزئة:

 ويمكن أن يكون البحث Trie أبطأ من البحث في جدول التجزئة، خاصة إذا تم الوصول إلى البيانات مباشرة على محرك الأقراص الثابتة أو بعض أجهزة التخزين الثانوية الأخرى حيث يكون وقت الوصول العشوائي مرتفعًا مقارنة بالذاكرة الرئيسية.Edward Fredkin (1960). "Trie Memory". Communications of the ACM. 3 (9): 490–499. doi:10.1145/367390.367400.
 ويمكن أن تؤدي بعض المفاتيح، مثل أرقام الفاصلة العائمة، إلى سلاسل طويلة وبادئات غير ذات معنى بشكل خاص. ومع ذلك، يمكن لثلاثي أحادي الاتجاه التعامل مع أرقام الفاصلة العائمة ذات التنسيق الفردي والمزدوج IEEE القياسي. [ بحاجة لمصدر ]
 ويمكن أن تتطلب بعض المحاولات مساحة أكبر من جدول التجزئة، حيث يمكن تخصيص الذاكرة لكل حرف في سلسلة البحث، بدلاً من جزء واحد من الذاكرة للإدخال بأكمله، كما هو الحال في معظم جداول التجزئة.

 تمثيل DFSA 
ويمكن النظر إلى الشجرة الرقمية على أنها إنسان آلي محدد ومحدود على شكل شجرة. حيث يتم إنشاء كل لغة منتهية من قبل trie automaton ، ويمكن ضغط كل شجرة رقمية في حالة آلية منتهية حتمية غير دورية.

 الخوارزميات 
الشجرة الرقمية عبارة عن شجرة من العقد التي تدعم عمليات البحث والإدراج. يُرجع البحث قيمة سلسلة المفاتيح، ويقوم «إدراج» بإدراج سلسلة (المفتاح) وقيمة في المثلث. يتم تشغيل كل من Insert and Find في  time ، حيث m هو طول المفتاح.

ويمكن استخدام فئة عقدة بسيطة لتمثيل العقد في المثلث:

ولاحظ أن children عبارة عن قاموس من الأحرف لأبناء العقدة؛ ويقال أن العقدة «الطرفية» هي التي تمثل سلسلة كاملة. </br>و يمكن البحث عن قيمة trie على النحو التالي:

ويمكن استخدام تعديلات طفيفة في هذا الروتين

 وللتحقق مما إذا كانت هناك أي كلمة في الشجرة الرقمية تبدأ ببادئة معينة (انظر § الإكمال التلقائي)، و
 ولإرجاع العقدة الأعمق المقابلة لبادئة معينة لسلسلة معينة.

وتتم عملية الإدراج عن طريق السير في المثلث وفقًا للسلسلة المراد إدخالها، ثم إلحاق عقد جديدة لاحقة السلسلة غير المضمنة في الشجرة الرقمية:

ويمكن أن يتم حذف مفتاح بطريقة بطيئة (عن طريق مسح القيمة الموجودة داخل العقدة المقابلة لمفتاح)، أو بشغف عن طريق تنظيف أي عقد رئيسية لم تعد ضرورية. ويتم وصف الحذف الشديد في الرمز الخاطئ هنا:

 الإكمال التلقائي 
يمكن استخدام الشجرة الرقمية لإرجاع قائمة مفاتيح ببادئة معينة. يمكن أيضًا تعديل هذا للسماح بأحرف البدل في البحث عن البادئة.Sedgewick, Robert; Wayne, Kevin (June 12, 2020). "Tries". algs4.cs.princeton.edu. Retrieved 2020-08-11.

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

الشجرة الرقمية هي بنية البيانات الأساسية لـ Burstsort ، والتي كانت (في عام 2007) أسرع خوارزمية لفرز السلسلة المعروفة نظرًا لاستخدامها الفعال لذاكرة التخزين المؤقت.  الآن هناك أسرع.

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

 استراتيجيات التنفيذ 
تصغير|تم تنفيذ Trie كشجرة ثنائية شقيق يمين-طفلة : الأسهم الرأسية هي ، الأسهم الأفقية المتقطعة هيالمؤشرات مجموعة السلاسل المخزنة في هذا المثلث هي }. يتم فرز القوائم للسماح بالمسح بترتيب معجمي.
وهناك عدة طرق لتمثيل المحاولات تتوافق مع المقايضات المختلفة بين استخدام الذاكرة وسرعة العمليات.و النموذج الأساسي هو مجموعة متصلة من العقد، حيث تحتوي كل عقدة على مجموعة من المؤشرات الفرعية، واحدة لكل رمز في الأبجدية (لذلك بالنسبة للأبجدية الإنجليزية، يمكن للمرء تخزين 26 مؤشرًا فرعيًا وللحروف الأبجدية من البايت، 256 مؤشرات). هذا بسيط ولكنه مضيعة للذاكرة: باستخدام أبجدية البايت (الحجم 256) ومؤشرات رباعية البايت، تتطلب كل عقدة كيلوبايت من التخزين، وعندما يكون هناك القليل من التداخل في بادئات السلاسل، فإن عدد العقد المطلوبة هو تقريبًا الطول المجمع للسلاسل المخزنة.   بعبارة أخرى، العقد الموجودة بالقرب من أسفل الشجرة تميل إلى أن يكون لديها عدد قليل من الأطفال وهناك العديد منهم، لذا فإن الهيكل يهدر مساحة تخزين المؤشرات الفارغة.

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

ويمثل التنفيذ البديل العقدة على أنها ثلاثية ويربط أبناء العقدة معًا كقائمة مرتبطة منفردة: إلى الطفل الأول للعقدة، الطفل التالي للعقدة الأصلية.Allison, Lloyd. "Tries". Retrieved 18 February 2014. ويمكن أيضًا تمثيل مجموعة الأطفال كشجرة بحث ثنائية؛ أحد الأمثلة على هذه الفكرة هو شجرة البحث الثلاثية التي طورها بنتلي وسيدجويك.  

بديل آخر لتجنب استخدام مصفوفة من 256 مؤشر (ASCII)، كما هو مقترح سابقًا، وهو تخزين المصفوفة الأبجدية كصورة نقطية من 256 بت تمثل أبجدية ASCII ، مما يقلل بشكل كبير من حجم العقد.

 الشجرة الرقمية Bitwise 
تتشابه الشجرة الرقمية Bitwise إلى حد كبير مع الشجرة الرقمية العادية المستند إلى الأحرف فيما عدا أنه يتم استخدام البتات الفردية لاجتياز ما يصبح بشكل فعال شكلاً من أشكال الشجرة الثنائية. وبشكل عام، تستخدم التطبيقات تعليمات خاصة لوحدة المعالجة المركزية للعثور بسرعة كبيرة على أول مجموعة بت في مفتاح طول ثابت (على سبيل المثال، GCC's __builtin_clz() جوهري).و تُستخدم هذه القيمة بعد ذلك لفهرسة جدول 32 أو 64 إدخالًا يشير إلى العنصر الأول في ثلاثي أحادي مع هذا العدد من البتات الصفرية البادئة. يبدأ البحث بعد ذلك باختبار كل بت تالٍ في المفتاح واختيار child[0] أو child[1] مناسب حتى يتم العثور على العنصر.

وعلى الرغم من أن هذه العملية قد تبدو بطيئة، إلا أنها ذات ذاكرة تخزين مؤقت محلية للغاية وقابلة للتوازي بدرجة كبيرة نظرًا لنقص تبعيات التسجيل، وبالتالي فهي تتمتع في الواقع بأداء ممتاز على وحدات المعالجة المركزية الحديثة ذات التنفيذ خارج الترتيب.و تعمل الشجرة ذات اللون الأحمر والأسود على سبيل المثال بشكل أفضل على الورق، ولكنها غير ملائمة بدرجة كبيرة لذاكرة التخزين المؤقت وتتسبب في العديد من خطوط الأنابيب وأكشاك TLB على وحدات المعالجة المركزية الحديثة مما يجعل هذه الخوارزمية مرتبطة بزمن استجابة الذاكرة بدلاً من سرعة وحدة المعالجة المركزية. وبالمقارنة، نادرًا ما يصل ثلاثي أحادي إلى الذاكرة، وعندما يفعل ذلك، فإنه يفعل ذلك للقراءة فقط، وبالتالي يتجنب الحمل الزائد لاتساق ذاكرة التخزين المؤقت SMP. ومن ثم، فقد أصبحت الخوارزمية المختارة بشكل متزايد للكود الذي يؤدي العديد من عمليات الإدراج والحذف السريعة، مثل مخصصات الذاكرة (على سبيل المثال، الإصدارات الحديثة من مُخصص دوج ليا الشهير (dlmalloc) وأحفاده).و أسوأ حالة لخطوات البحث هي نفس وحدات البت المستخدمة لفهرسة الصناديق في الشجرة. HTTP for Source Code. Binary Trie is described in Version 2.8.6, Section "Overlaid data structures", Structure "malloc_tree_chunk".

وبدلاً من ذلك، يمكن أن يشير المصطلح «bitwise الشجرة الرقمية» بشكل عام إلى بنية شجرة ثنائية تحمل قيمًا صحيحة، وترتيبها حسب بادئتها الثنائية. مثال على ذلك هو trie سريع x .

 شجرات الضغط الرقمية 
يمكن أن يؤدي ضغط الشجرة الرقمية ودمج الفروع المشتركة في بعض الأحيان إلى مكاسب كبيرة في الأداء. حيث يعمل هذا بشكل أفضل في ظل الظروف التالية:

 الشجرة الرقمية (في الغالب) ثابتة، بحيث لا يلزم إدخال مفتاح أو حذفه (على سبيل المثال، بعد الإنشاء بالجملة للشجرة الرقمية).
 هناك حاجة لعمليات البحث فقط.
 لا يتم ترميز الشجرة الرقمية بواسطة البيانات الخاصة بالعقدة، أو أن بيانات العقد شائعة. Alt URL
 تكون المجموعة الإجمالية للمفاتيح المخزنة قليلة جدًا ضمن مساحة التمثيل الخاصة بها (لذا فإن الضغط يؤتي ثماره).

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

ويتم استخدام هذا الضغط أيضًا في تنفيذ جداول البحث السريع المتنوعة لاسترداد خصائص أحرف Unicode. ويمكن أن تشمل هذه الجداول حالة على رسم الخرائط (على سبيل المثال، ل اليوناني إلكتروني بي، من Π لπ)، أو جداول البحث تطبيع الجمع بين القاعدة والجمع بين الحروف (مثل أ- علامة تشكيل في الألمانية، ä، أو دالت - patah - dagesh - أولي في الكتاب المقدس العبرية، بالنسبة لمثل هذه التطبيقات، يكون التمثيل مشابهًا لتحويل جدول كبير جدًا أحادي البعد ومتفرق (على سبيل المثال، نقاط رمز Unicode) إلى مصفوفة متعددة الأبعاد لمجموعاتها، ثم استخدام الإحداثيات في المصفوفة الفائقة كمفتاح سلسلة لملف غير مضغوط تري لتمثيل الشخصية الناتجة. سيتكون الضغط بعد ذلك من اكتشاف ودمج الأعمدة المشتركة داخل المصفوفة الفائقة لضغط البعد الأخير في المفتاح. على سبيل المثال، لتجنب تخزين نقطة رمز Unicode الكاملة متعددة البايت لكل عنصر يشكل عمود مصفوفة، يمكن استغلال مجموعات نقاط الكود المتشابهة. يخزن كل بُعد من أبعاد المصفوفة الفائقة موضع البداية للبعد التالي، بحيث يتم تخزين الإزاحة فقط (عادةً بايت واحد). المتجه الناتج هو نفسه قابل للضغط عندما يكون متناثرًا أيضًا، لذلك يمكن ضغط كل بُعد (مرتبط بمستوى طبقة في المثلث) بشكل منفصل .

وتدعم بعض التطبيقات ضغط البيانات هذا في المحاولات المتفرقة الديناميكية وتسمح بعمليات الإدراج والحذف في المحاولات المضغوطة. ومع ذلك، فإن هذا عادةً ما يكون له تكلفة كبيرة عند الحاجة إلى تقسيم أو دمج الأجزاء المضغوطة.و يجب إجراء بعض المفاضلة بين ضغط البيانات وسرعة التحديث. تتمثل الإستراتيجية النموذجية في تحديد نطاق عمليات البحث العامة لمقارنة الفروع الشائعة في تجربة متفرقة.

وقد تبدو نتيجة هذا الضغط مشابهة لمحاولة تحويل الشجرة الرقمية إلى رسم بياني لا دوري موجه (DAG)، لأن التحويل العكسي من DAG إلى مثلث يكون واضحًا وممكنًا دائمًا. ومع ذلك، يتم تحديد شكل DAG من خلال شكل المفتاح المختار لفهرسة العقد، مما يؤدي بدوره إلى تقييد الضغط المحتمل .

وهنالك إستراتيجية ضغط أخرى هي «تفكيك» بنية البيانات في مصفوفة بايت واحد. هذا الأسلوب يلغي الحاجة إلى مؤشرات العقدة، مما يقلل بشكل كبير من متطلبات الذاكرة. وهذا بدوره يسمح بتعيين الذاكرة واستخدام الذاكرة الظاهرية لتحميل البيانات بكفاءة من القرص.

وهنالك نهج آخر هو «حزم» الشجرة الرقمية . يصف Liang تنفيذًا فعالًا لمساحة الشجرة الرقمية معبأ متناثر مطبق على الواصلة التلقائية، حيث يمكن تشذير أحفاد كل عقدة في الذاكرة.

 الذاكرة الخارجية للشجرة الرقمية 
العديد من المتغيرات الثلاثية مناسبة للاحتفاظ بمجموعات من السلاسل في الذاكرة الخارجية، بما في ذلك أشجار اللواحق.و قد تم اقتراح توليفة من الشجرة الرقمية وب- الشجرة الرقمية، تسمى ب- الشجرة الرقمية لهذه المهمة؛ مقارنةً بأشجار اللاحقة، فهي محدودة في العمليات المدعومة ولكنها أيضًا أكثر إحكاما، أثناء إجراء عمليات التحديث بشكل أسرع.

 انظر أيضًا 
 بنية بيانات

 المراجع 


 روابط خارجية 
 قاموس NIST للخوارزميات وهياكل البيانات: Trie

تصنيف:أشجار (بنى معطيات)