الشجرة الرقمية
استراتيجيات التنفيذ > شجرات الضغط الرقمية

يمكن أن يؤدي ضغط الشجرة الرقمية ودمج الفروع المشتركة في بعض الأحيان إلى مكاسب كبيرة في الأداء. حيث يعمل هذا بشكل أفضل في ظل الظروف التالية:
الشجرة الرقمية (في الغالب) ثابتة، بحيث لا يلزم إدخال مفتاح أو حذفه (على سبيل المثال، بعد الإنشاء بالجملة للشجرة الرقمية).
هناك حاجة لعمليات البحث فقط.
لا يتم ترميز الشجرة الرقمية بواسطة البيانات الخاصة بالعقدة، أو أن بيانات العقد شائعة.
تكون المجموعة الإجمالية للمفاتيح المخزنة قليلة جدًا ضمن مساحة التمثيل الخاصة بها (لذا فإن الضغط يؤتي ثماره).
وعلى سبيل المثال، يمكن استخدامه لتمثيل مجموعات البت المتفرقة؛ على سبيل المثال، مجموعات فرعية من مجموعة قابلة للعد وثابتة أكبر بكثير. في مثل هذه الحالة، يتم تحديد الشجرة الرقمية بواسطة موضع عنصر البت داخل المجموعة الكاملة. ويتم إنشاء المفتاح من سلسلة البتات اللازمة لتشفير الموضع المتكامل لكل عنصر.و مثل هذه المحاولات لها شكل سيئ للغاية مع العديد من الفروع المفقودة. بعد اكتشاف تكرار الأنماط الشائعة أو ملء الفجوات غير المستخدمة، ويمكن تخزين العقد الورقية الفريدة (سلاسل البت) وضغطها بسهولة، مما يقلل من الحجم الكلي للثلاثي.
ويتم استخدام هذا الضغط أيضًا في تنفيذ جداول البحث السريع المتنوعة لاسترداد خصائص أحرف Unicode. ويمكن أن تشمل هذه الجداول حالة على رسم الخرائط (على سبيل المثال، ل اليوناني إلكتروني بي، من Π لπ)، أو جداول البحث تطبيع الجمع بين القاعدة والجمع بين الحروف (مثل أ- علامة تشكيل في الألمانية، ä، أو دالت - patah - dagesh - أولي في الكتاب المقدس العبرية،דַּ֫ بالنسبة لمثل هذه التطبيقات، يكون التمثيل مشابهًا لتحويل جدول كبير جدًا أحادي البعد ومتفرق (على سبيل المثال، نقاط رمز Unicode) إلى مصفوفة متعددة الأبعاد لمجموعاتها، ثم استخدام الإحداثيات في المصفوفة الفائقة كمفتاح سلسلة لملف غير مضغوط تري لتمثيل الشخصية الناتجة. سيتكون الضغط بعد ذلك من اكتشاف ودمج الأعمدة المشتركة داخل المصفوفة الفائقة لضغط البعد الأخير في المفتاح. على سبيل المثال، لتجنب تخزين نقطة رمز Unicode الكاملة متعددة البايت لكل عنصر يشكل عمود مصفوفة، يمكن استغلال مجموعات نقاط الكود المتشابهة. يخزن كل بُعد من أبعاد المصفوفة الفائقة موضع البداية للبعد التالي، بحيث يتم تخزين الإزاحة فقط (عادةً بايت واحد). المتجه الناتج هو نفسه قابل للضغط عندما يكون متناثرًا أيضًا، لذلك يمكن ضغط كل بُعد (مرتبط بمستوى طبقة في المثلث) بشكل منفصل .
وتدعم بعض التطبيقات ضغط البيانات هذا في المحاولات المتفرقة الديناميكية وتسمح بعمليات الإدراج والحذف في المحاولات المضغوطة. ومع ذلك، فإن هذا عادةً ما يكون له تكلفة كبيرة عند الحاجة إلى تقسيم أو دمج الأجزاء المضغوطة.و يجب إجراء بعض المفاضلة بين ضغط البيانات وسرعة التحديث. تتمثل الإستراتيجية النموذجية في تحديد نطاق عمليات البحث العامة لمقارنة الفروع الشائعة في تجربة متفرقة.
وقد تبدو نتيجة هذا الضغط مشابهة لمحاولة تحويل الشجرة الرقمية إلى رسم بياني لا دوري موجه (DAG)، لأن التحويل العكسي من DAG إلى مثلث يكون واضحًا وممكنًا دائمًا. ومع ذلك، يتم تحديد شكل DAG من خلال شكل المفتاح المختار لفهرسة العقد، مما يؤدي بدوره إلى تقييد الضغط المحتمل .
وهنالك إستراتيجية ضغط أخرى هي «تفكيك» بنية البيانات في مصفوفة بايت واحد. هذا الأسلوب يلغي الحاجة إلى مؤشرات العقدة، مما يقلل بشكل كبير من متطلبات الذاكرة. وهذا بدوره يسمح بتعيين الذاكرة واستخدام الذاكرة الظاهرية لتحميل البيانات بكفاءة من القرص.
وهنالك نهج آخر هو «حزم» الشجرة الرقمية . يصف Liang تنفيذًا فعالًا لمساحة الشجرة الرقمية معبأ متناثر مطبق على الواصلة التلقائية، حيث يمكن تشذير أحفاد كل عقدة في الذاكرة.