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