الشجرة الرقمية

الشجرة الرقمية
في علوم الكمبيوتر، يُطلق على trie أيضًا اسم الشجرة الرقمية أو شجرة البادئة ، وهو نوع من شجرة البحث، وهي بنية بيانات شجرة تُستخدم لتحديد موقع مفاتيح معينة من داخل مجموعة. وغالبًا ما تكون هذه المفاتيح عبارة عن سلاسل، ومع روابط بين العقد لا يتم تعريفها بواسطة المفتاح بأكمله، ولكن بواسطة الأحرف الفردية. ومن أجل الوصول إلى مفتاح (لاستعادة قيمته أو تغييره أو إزالته)، يتم اجتياز الثلاثي في العمق أولاً، باتباع الروابط بين العقد، والتي تمثل كل حرف في المفتاح.
وعلى عكس شجرة البحث الثنائية، لا تخزن العقد الموجودة في المثلث المفتاح المرتبط بها. بدلاً من ذلك، يحدد موضع العقدة في المثلث المفتاح الذي يرتبط به. يوزع هذا قيمة كل مفتاح عبر بنية البيانات، ويعني أنه ليس بالضرورة أن يكون لكل عقدة مفتاح مرتبط.
وجميع توابع العقدة لديهم بادئة مشتركة للسلسلة المرتبطة بالعقدة الأصلية، والجذر مرتبط بالسلسلة الفارغة. حيث يمكن إنجاز مهمة تخزين البيانات التي يمكن الوصول إليها من خلال بادئتها بطريقة محسّنة للذاكرة من خلال استخدام شجرة الجذر.
وعلى الرغم من إمكانية تحديد المحاولات بسلاسل الأحرف، إلا أنه لا يلزم أن تكون كذلك. ويمكن تكييف نفس الخوارزميات للقوائم المرتبة من أي نوع أساسي، مثل تبديل الأرقام أو الأشكال. وعلى وجه الخصوص، يتم تمييز ثلاثي أحادي البتات على البتات الفردية التي تشكل قطعة من البيانات الثنائية ذات الطول الثابت، مثل رقم صحيح أو عنوان الذاكرة.
التاريخ وأصل الكلمة والنطق
تم وصف فكرة Trie لتمثيل مجموعة من الأوتار لأول مرة بشكل تجريدي بواسطة Axel Thue في عام 1912. وتم وصف المحاولات لأول مرة في سياق الكمبيوتر بواسطة René de la Briandais عام 1959. وقد وصفت هذه الفكرة بشكل مستقل في عام 1960 من قبل ادوارد فريدكين، الذي صاغ مصطلح TRIE، لفظ أنه (باسم «شجرة»)، بعد المقطع الأوسط من استرجاعها. ومع ذلك، مؤلفين آخرين تنطق (بأنها «محاولة»)، وفي محاولة لتمييزه لفظيا من «شجرة».
التطبيقات
تمثيل القاموس
وتتضمن التطبيقات الشائعة للمحاولات تخزين نص تنبؤي أو قاموس إكمال تلقائي وتنفيذ خوارزميات مطابقة تقريبية، مثل تلك المستخدمة في برامج التدقيق الإملائي والواصلة. وتستفيد هذه التطبيقات من قدرة trie على البحث عن الإدخالات وإدراجها وحذفها بسرعة. ومع ذلك، إذا كان تخزين كلمات القاموس هو كل ما هو مطلوب (أي ليست هناك حاجة لتخزين البيانات الوصفية المرتبطة بكل كلمة)، فإن الحد الأدنى من آلية الحالة المحدودة الحتمية (DAFSA) أو شجرة الجذر ستستخدم مساحة تخزين أقل من ثلاثي. وذلك لأن DAFSAs وأشجار الجذر يمكن أن تضغط على فروع متطابقة من trie والتي تتوافق مع نفس اللواحق (أو الأجزاء) من الكلمات المختلفة المخزنة.
استبدال هياكل البيانات الأخرى
استبدال جداول التجزئة
يمكن استعمال trie لاستبدال جدول التجزئة، والذي يتمتع بالمزايا التالية عليه:
ويكون البحث عن البيانات في trie أسرع في أسوأ الحالات، O (m) time (حيث m هو طول سلسلة البحث)، مقارنة بجدول التجزئة غير الكامل. يمكن أن يحتوي جدول التجزئة غير الكامل على تصادمات رئيسية. اصطدام المفاتيح هو تعيين وظيفة التجزئة لمفاتيح مختلفة لنفس الموضع في جدول التجزئة. أسرع سرعة بحث في جدول تجزئة غير كامل هي وقت O (N) ، ولكن عادةً ما تكون O (1)، مع وقت O (m) الذي يقضيه في تقييم التجزئة.
لا توجد اصطدامات بين مفاتيح مختلفة في ثلاثي.
تعتبر الحاويات الموجودة في مثلث، والتي تشبه حاويات جدول التجزئة التي تخزن تصادمات المفاتيح، ضرورية فقط إذا كان مفتاح واحد مرتبطًا بأكثر من قيمة واحدة.
ليست هناك حاجة لتوفير وظيفة تجزئة أو لتغيير وظائف التجزئة حيث تتم إضافة المزيد من المفاتيح إلى ثلاثي.
يمكن أن يوفر Trie ترتيبًا أبجديًا للإدخالات حسب المفتاح.
ومع ذلك، فإن الشجرة الرقمية أيضًا لها بعض العيوب مقارنة بجدول التجزئة:
ويمكن أن يكون البحث Trie أبطأ من البحث في جدول التجزئة، خاصة إذا تم الوصول إلى البيانات مباشرة على محرك الأقراص الثابتة أو بعض أجهزة التخزين الثانوية الأخرى حيث يكون وقت الوصول العشوائي مرتفعًا مقارنة بالذاكرة الرئيسية.
ويمكن أن تؤدي بعض المفاتيح، مثل أرقام الفاصلة العائمة، إلى سلاسل طويلة وبادئات غير ذات معنى بشكل خاص. ومع ذلك، يمكن لثلاثي أحادي الاتجاه التعامل مع أرقام الفاصلة العائمة ذات التنسيق الفردي والمزدوج IEEE القياسي. [ بحاجة لمصدر ]
ويمكن أن تتطلب بعض المحاولات مساحة أكبر من جدول التجزئة، حيث يمكن تخصيص الذاكرة لكل حرف في سلسلة البحث، بدلاً من جزء واحد من الذاكرة للإدخال بأكمله، كما هو الحال في معظم جداول التجزئة.
تمثيل DFSA
ويمكن النظر إلى الشجرة الرقمية على أنها إنسان آلي محدد ومحدود على شكل شجرة. حيث يتم إنشاء كل لغة منتهية من قبل trie automaton ، ويمكن ضغط كل شجرة رقمية في حالة آلية منتهية حتمية غير دورية.
الخوارزميات
الشجرة الرقمية عبارة عن شجرة من العقد التي تدعم عمليات البحث والإدراج. يُرجع البحث قيمة سلسلة المفاتيح، ويقوم «إدراج» بإدراج سلسلة (المفتاح) وقيمة في المثلث. يتم تشغيل كل من Insert and Find في time ، حيث m هو طول المفتاح.
ويمكن استخدام فئة عقدة بسيطة لتمثيل العقد في المثلث:
ولاحظ أن children عبارة عن قاموس من الأحرف لأبناء العقدة؛ ويقال أن العقدة «الطرفية» هي التي تمثل سلسلة كاملة. </br>و يمكن البحث عن قيمة trie على النحو التالي:
ويمكن استخدام تعديلات طفيفة في هذا الروتين
وللتحقق مما إذا كانت هناك أي كلمة في الشجرة الرقمية تبدأ ببادئة معينة (انظر § الإكمال التلقائي)، و
ولإرجاع العقدة الأعمق المقابلة لبادئة معينة لسلسلة معينة.
وتتم عملية الإدراج عن طريق السير في المثلث وفقًا للسلسلة المراد إدخالها، ثم إلحاق عقد جديدة لاحقة السلسلة غير المضمنة في الشجرة الرقمية:
ويمكن أن يتم حذف مفتاح بطريقة بطيئة (عن طريق مسح القيمة الموجودة داخل العقدة المقابلة لمفتاح)، أو بشغف عن طريق تنظيف أي عقد رئيسية لم تعد ضرورية. ويتم وصف الحذف الشديد في الرمز الخاطئ هنا:
الإكمال التلقائي
يمكن استخدام الشجرة الرقمية لإرجاع قائمة مفاتيح ببادئة معينة. يمكن أيضًا تعديل هذا للسماح بأحرف البدل في البحث عن البادئة.
الفرز
ويمكن إجراء الفرز المعجمي لمجموعة من المفاتيح من خلال بناء ثلاثي منها، ومع فرز الأطفال لكل عقدة بطريقة معجمية، واجتيازها بالترتيب المسبق، وطباعة أي قيم في العقد الداخلية أو في العقد الورقية. هذه الخوارزمية هي شكل من أشكال فرز الجذر.
الشجرة الرقمية هي بنية البيانات الأساسية لـ Burstsort ، والتي كانت (في عام 2007) أسرع خوارزمية لفرز السلسلة المعروفة نظرًا لاستخدامها الفعال لذاكرة التخزين المؤقت. الآن هناك أسرع.
البحث عن نص كامل
يمكن استعمال نوع خاص من الشجرة الرقمية، يسمى شجرة اللاحقة، لفهرسة جميع اللواحق في النص من أجل إجراء عمليات بحث سريعة عن النص الكامل.
استراتيجيات التنفيذ
وهناك عدة طرق لتمثيل المحاولات تتوافق مع المقايضات المختلفة بين استخدام الذاكرة وسرعة العمليات.و النموذج الأساسي هو مجموعة متصلة من العقد، حيث تحتوي كل عقدة على مجموعة من المؤشرات الفرعية، واحدة لكل رمز في الأبجدية (لذلك بالنسبة للأبجدية الإنجليزية، يمكن للمرء تخزين 26 مؤشرًا فرعيًا وللحروف الأبجدية من البايت، 256 مؤشرات). هذا بسيط ولكنه مضيعة للذاكرة: باستخدام أبجدية البايت (الحجم 256) ومؤشرات رباعية البايت، تتطلب كل عقدة كيلوبايت من التخزين، وعندما يكون هناك القليل من التداخل في بادئات السلاسل، فإن عدد العقد المطلوبة هو تقريبًا الطول المجمع للسلاسل المخزنة. بعبارة أخرى، العقد الموجودة بالقرب من أسفل الشجرة تميل إلى أن يكون لديها عدد قليل من الأطفال وهناك العديد منهم، لذا فإن الهيكل يهدر مساحة تخزين المؤشرات الفارغة.
ويمكن التخفيف من مشكلة التخزين من خلال تقنية تنفيذ تسمى الاختزال الأبجدي ، حيث يتم إعادة تفسير السلاسل الأصلية على أنها سلاسل أطول على أبجدية أصغر. على سبيل المثال، ويمكن بدلاً من ذلك اعتبار وحدات من أربع بتات وتخزينها في ثلاثي مع ستة عشر مؤشرًا لكل عقدة. وتحتاج عمليات البحث إلى زيارة ضعف عدد العقد في أسوأ الحالات، ولكن متطلبات التخزين تنخفض بمقدار ثمانية أضعاف.
ويمثل التنفيذ البديل العقدة على أنها ثلاثية ويربط أبناء العقدة معًا كقائمة مرتبطة منفردة: إلى الطفل الأول للعقدة، الطفل التالي للعقدة الأصلية. ويمكن أيضًا تمثيل مجموعة الأطفال كشجرة بحث ثنائية؛ أحد الأمثلة على هذه الفكرة هو شجرة البحث الثلاثية التي طورها بنتلي وسيدجويك.
بديل آخر لتجنب استخدام مصفوفة من 256 مؤشر (ASCII)، كما هو مقترح سابقًا، وهو تخزين المصفوفة الأبجدية كصورة نقطية من 256 بت تمثل أبجدية ASCII ، مما يقلل بشكل كبير من حجم العقد.
الشجرة الرقمية Bitwise
تتشابه الشجرة الرقمية Bitwise إلى حد كبير مع الشجرة الرقمية العادية المستند إلى الأحرف فيما عدا أنه يتم استخدام البتات الفردية لاجتياز ما يصبح بشكل فعال شكلاً من أشكال الشجرة الثنائية. وبشكل عام، تستخدم التطبيقات تعليمات خاصة لوحدة المعالجة المركزية للعثور بسرعة كبيرة على أول مجموعة بت في مفتاح طول ثابت (على سبيل المثال، GCC's __builtin_clz() جوهري).و تُستخدم هذه القيمة بعد ذلك لفهرسة جدول 32 أو 64 إدخالًا يشير إلى العنصر الأول في ثلاثي أحادي مع هذا العدد من البتات الصفرية البادئة. يبدأ البحث بعد ذلك باختبار كل بت تالٍ في المفتاح واختيار child[0] أو child[1] مناسب حتى يتم العثور على العنصر.
وعلى الرغم من أن هذه العملية قد تبدو بطيئة، إلا أنها ذات ذاكرة تخزين مؤقت محلية للغاية وقابلة للتوازي بدرجة كبيرة نظرًا لنقص تبعيات التسجيل، وبالتالي فهي تتمتع في الواقع بأداء ممتاز على وحدات المعالجة المركزية الحديثة ذات التنفيذ خارج الترتيب.و تعمل الشجرة ذات اللون الأحمر والأسود على سبيل المثال بشكل أفضل على الورق، ولكنها غير ملائمة بدرجة كبيرة لذاكرة التخزين المؤقت وتتسبب في العديد من خطوط الأنابيب وأكشاك TLB على وحدات المعالجة المركزية الحديثة مما يجعل هذه الخوارزمية مرتبطة بزمن استجابة الذاكرة بدلاً من سرعة وحدة المعالجة المركزية. وبالمقارنة، نادرًا ما يصل ثلاثي أحادي إلى الذاكرة، وعندما يفعل ذلك، فإنه يفعل ذلك للقراءة فقط، وبالتالي يتجنب الحمل الزائد لاتساق ذاكرة التخزين المؤقت SMP. ومن ثم، فقد أصبحت الخوارزمية المختارة بشكل متزايد للكود الذي يؤدي العديد من عمليات الإدراج والحذف السريعة، مثل مخصصات الذاكرة (على سبيل المثال، الإصدارات الحديثة من مُخصص دوج ليا الشهير (dlmalloc) وأحفاده).و أسوأ حالة لخطوات البحث هي نفس وحدات البت المستخدمة لفهرسة الصناديق في الشجرة.
وبدلاً من ذلك، يمكن أن يشير المصطلح «bitwise الشجرة الرقمية» بشكل عام إلى بنية شجرة ثنائية تحمل قيمًا صحيحة، وترتيبها حسب بادئتها الثنائية. مثال على ذلك هو trie سريع x .
شجرات الضغط الرقمية
يمكن أن يؤدي ضغط الشجرة الرقمية ودمج الفروع المشتركة في بعض الأحيان إلى مكاسب كبيرة في الأداء. حيث يعمل هذا بشكل أفضل في ظل الظروف التالية:
الشجرة الرقمية (في الغالب) ثابتة، بحيث لا يلزم إدخال مفتاح أو حذفه (على سبيل المثال، بعد الإنشاء بالجملة للشجرة الرقمية).
هناك حاجة لعمليات البحث فقط.
لا يتم ترميز الشجرة الرقمية بواسطة البيانات الخاصة بالعقدة، أو أن بيانات العقد شائعة.
تكون المجموعة الإجمالية للمفاتيح المخزنة قليلة جدًا ضمن مساحة التمثيل الخاصة بها (لذا فإن الضغط يؤتي ثماره).
وعلى سبيل المثال، يمكن استخدامه لتمثيل مجموعات البت المتفرقة؛ على سبيل المثال، مجموعات فرعية من مجموعة قابلة للعد وثابتة أكبر بكثير. في مثل هذه الحالة، يتم تحديد الشجرة الرقمية بواسطة موضع عنصر البت داخل المجموعة الكاملة. ويتم إنشاء المفتاح من سلسلة البتات اللازمة لتشفير الموضع المتكامل لكل عنصر.و مثل هذه المحاولات لها شكل سيئ للغاية مع العديد من الفروع المفقودة. بعد اكتشاف تكرار الأنماط الشائعة أو ملء الفجوات غير المستخدمة، ويمكن تخزين العقد الورقية الفريدة (سلاسل البت) وضغطها بسهولة، مما يقلل من الحجم الكلي للثلاثي.
ويتم استخدام هذا الضغط أيضًا في تنفيذ جداول البحث السريع المتنوعة لاسترداد خصائص أحرف Unicode. ويمكن أن تشمل هذه الجداول حالة على رسم الخرائط (على سبيل المثال، ل اليوناني إلكتروني بي، من Π لπ)، أو جداول البحث تطبيع الجمع بين القاعدة والجمع بين الحروف (مثل أ- علامة تشكيل في الألمانية، ä، أو دالت - patah - dagesh - أولي في الكتاب المقدس العبرية، بالنسبة لمثل هذه التطبيقات، يكون التمثيل مشابهًا لتحويل جدول كبير جدًا أحادي البعد ومتفرق (على سبيل المثال، نقاط رمز Unicode) إلى مصفوفة متعددة الأبعاد لمجموعاتها، ثم استخدام الإحداثيات في المصفوفة الفائقة كمفتاح سلسلة لملف غير مضغوط تري لتمثيل الشخصية الناتجة. سيتكون الضغط بعد ذلك من اكتشاف ودمج الأعمدة المشتركة داخل المصفوفة الفائقة لضغط البعد الأخير في المفتاح. على سبيل المثال، لتجنب تخزين نقطة رمز Unicode الكاملة متعددة البايت لكل عنصر يشكل عمود مصفوفة، يمكن استغلال مجموعات نقاط الكود المتشابهة. يخزن كل بُعد من أبعاد المصفوفة الفائقة موضع البداية للبعد التالي، بحيث يتم تخزين الإزاحة فقط (عادةً بايت واحد). المتجه الناتج هو نفسه قابل للضغط عندما يكون متناثرًا أيضًا، لذلك يمكن ضغط كل بُعد (مرتبط بمستوى طبقة في المثلث) بشكل منفصل .
وتدعم بعض التطبيقات ضغط البيانات هذا في المحاولات المتفرقة الديناميكية وتسمح بعمليات الإدراج والحذف في المحاولات المضغوطة. ومع ذلك، فإن هذا عادةً ما يكون له تكلفة كبيرة عند الحاجة إلى تقسيم أو دمج الأجزاء المضغوطة.و يجب إجراء بعض المفاضلة بين ضغط البيانات وسرعة التحديث. تتمثل الإستراتيجية النموذجية في تحديد نطاق عمليات البحث العامة لمقارنة الفروع الشائعة في تجربة متفرقة.
وقد تبدو نتيجة هذا الضغط مشابهة لمحاولة تحويل الشجرة الرقمية إلى رسم بياني لا دوري موجه (DAG)، لأن التحويل العكسي من DAG إلى مثلث يكون واضحًا وممكنًا دائمًا. ومع ذلك، يتم تحديد شكل DAG من خلال شكل المفتاح المختار لفهرسة العقد، مما يؤدي بدوره إلى تقييد الضغط المحتمل .
وهنالك إستراتيجية ضغط أخرى هي «تفكيك» بنية البيانات في مصفوفة بايت واحد. هذا الأسلوب يلغي الحاجة إلى مؤشرات العقدة، مما يقلل بشكل كبير من متطلبات الذاكرة. وهذا بدوره يسمح بتعيين الذاكرة واستخدام الذاكرة الظاهرية لتحميل البيانات بكفاءة من القرص.
وهنالك نهج آخر هو «حزم» الشجرة الرقمية . يصف Liang تنفيذًا فعالًا لمساحة الشجرة الرقمية معبأ متناثر مطبق على الواصلة التلقائية، حيث يمكن تشذير أحفاد كل عقدة في الذاكرة.
الذاكرة الخارجية للشجرة الرقمية
العديد من المتغيرات الثلاثية مناسبة للاحتفاظ بمجموعات من السلاسل في الذاكرة الخارجية، بما في ذلك أشجار اللواحق.و قد تم اقتراح توليفة من الشجرة الرقمية وب- الشجرة الرقمية، تسمى ب- الشجرة الرقمية لهذه المهمة؛ مقارنةً بأشجار اللاحقة، فهي محدودة في العمليات المدعومة ولكنها أيضًا أكثر إحكاما، أثناء إجراء عمليات التحديث بشكل أسرع.
انظر أيضًا
بنية بيانات
المراجع
روابط خارجية
قاموس NIST للخوارزميات وهياكل البيانات: Trie
أشجار (بنى معطيات)