القطط في مربعات ، أو هياكل البيانات المدمجة

ماذا أفعل إذا نمت شجرة البحث إلى ذاكرة الوصول العشوائي (RAM) بأكملها وكانت على وشك اقتلاع الرفوف المجاورة في غرفة الخادم؟ ماذا تفعل مع مؤشر مقلوب الموارد الجياع؟ هل يجب عليّ الاتصال بتطوير Android إذا تلقى المستخدم "ذاكرة الهاتف ممتلئة" وكان التطبيق نصف حمل حاوية مهمة فقط؟

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

في غضون ذلك ، سيكون هناك بطل على هبر يمكنه إعادة الحديث ثلاث مرات على التوالي
[Səksɪŋkt]؟

الباب إلى عالم الاكتناز

لذلك ، تعتبر بنية البيانات مضغوطة (مختصرة) إذا:

• إنه يحتل عددًا من البتات بالقرب من الحد الأدنى النظري للمعلومات.
• لا يتطلب التفريغ الأولي للاستخدام الكامل.

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

كما أن التطبيقات المألوفة "السائدة" للرسوم البيانية وجداول التجزئة وأشياء أخرى ليست جيدة أيضًا. خذ على الأقل مؤشرات إلى العناصر الفرعية في شجرة البحث. يأكلون أماكن لائقة: $$$O (MN)$ حيث $$$M$ - طول المؤشر ، و $$$N$ - عدد العقد في الشجرة. لكن تنفيذ شجرة مقتضبة يسمح لنا لتحسين السلوك المقارب ل $$$2N + o (N)$ وهو قريب من الحد الأدنى النظري $$$2N - Θ (سجل N)$ للخشب من $$$N$ العقد. مع طول المؤشر $$$M = 8 دولا$ بايت هذا يعني الانتقال من $$$O (8N)$ بترتيب مختلف تمامًا من المقاربات - فقط $$$2N$ ، بالنظر إلى ذلك $$$o (N)$ - قيمة ضئيلة بالنسبة إلى $$$N$ .

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

تعتمد معظم الهياكل المدمجة على مفهوم ما يسمى القاموس القابل للفهرسة المضغوط. هذه حالة خاصة من الصورة النقطية (الصورة النقطية ، bitset). تعتبر الصورة النقطية نفسها مثالية للتحقق مما إذا كانت العناصر موجودة في مجموعة معينة. إذا تم تضمين عنصر في مجموعة ، فسيتم تعيين قيمة البت في فهرس معين على 1 ، وإذا لم يكن الأمر كذلك ، فسيتم إعادة تعيينها إلى 0. مثال حي على ذلك هو extode-bitmap ext4 و UFS وأنظمة ملفات Unix الأخرى. يقوم بتخزين البيانات حول أي إدخالات في جدول inode مشغول وأيها مجانية.

القاموس القابل للفهرسة هو نفس الصورة النقطية ، لكنه يكمله عمليتان: الرتبة والاختيار. هذه العمليات هي الأفيال التي يرتكز عليها العالم المختصر. بمعنى تقريبي ، الترتيب هو عدد العناصر ، والاختيار هو البحث عن عنصر:

• $$$rank_x (i)$ إرجاع عدد البتات يساوي $$$x$ المؤشرات التي تقع على شريحة $$$[0؛ أنا]$ . ل $$$x$ - قيمة البتة ، ثم يمكن أن تساوي حصراً 0 أو 1.
• $$$select_x (j)$ مؤشر العوائد $$$j$ يساوي قليلا ل $$$x$ . يقول الفطرة السليمة أنه لا يوجد أي صفر ، لا يوجد سوى الأول. ول$$ $ inline $ j> 0 $ inline $ : يتم الحساب من واحد. وبالإضافة إلى ذلك، $$$j$ لا يمكن أن يتجاوز إجمالي عدد البتات في القاموس المساوي لـ $$$x$ .

لنفترض أن لدينا قاموسًا يمكن فهرسته حيث تم تعيين 4 من 7 بتات. ثم $$$Rank_1$ و $$$select_1$ سوف تأخذ القيم التالية:

مثال على قاموس يمكن فهرسته وحسابه $$$Rank_1$ . $$$select_1$ .

سوف يلاحظ القارئ اليقظ أن تحديد هو عكس الترتيب. إذا $$$Rank_1 (5) = 4$ ثم $$$select_1 (4) = 5$ .

كان شخص ما ديجا فو على مرأى من $$$rank_1 (i)$ ؟ وكل هذا بسبب تعميم هذه العملية على Hamming Weight - عدد الأحرف غير الصفرية في التسلسل. بالنسبة للتسلسلات الثنائية ، يُطلق على وزن هامينغ أيضًا اسم popcount (عدد السكان).

الرتبة / الاختيار ينطبق أيضًا على البتات المهملة. هنا مثال حساب $$$Rank_0$ و $$$select_0$ بالنسبة للبتات التي تساوي 0:

مثال على قاموس مضغوط قابل للفهرسة وحساب له $$$Rank_0$ . $$$select_0$ .

رأى شجرة في bitiks

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

ثلاث طرق للتمثيل المضغوط للأشجار هي الأكثر شيوعًا:

• BP (أقواس متوازنة) - تسلسلات أقواس متوازنة.
• DFUDS (تسلسل الدرجة الأولى أحادي العمق) - سلسلة من العقد المشفرة بالوحدة مرتبة حسب البحث في العمق.
• LOUDS (متواليات الدرجة أحادية الترتيب مرتبة) - تتابعات العقد المشفرة بالوحدة مرتبة حسب المستوى.

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

تتحد هذه الطرق الثلاثة لتمثيل الأشجار بوجود عمليات سريعة: العثور على أحد الوالدين ؛ العثور على السليل الأول ؛ العثور على آخر سليل. العثور على العقد المجاورة اليمنى واليسرى. يختلف الاحتمال والفعالية الأساسية للعمليات الأخرى من طريقة إلى أخرى.

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

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

تحذير ، شجرة بادئة:

شجرة البادئة جاهزة للضغط باستخدام طريقة LOUDS.

تحضير الشجرة للعرض في شكل ثنائي:

1. نعلق الشجرة على الجذر وهمية. سوف يلعب دوره قريبا جدا.
2. نحن نرقم جميع العقد من الشجرة ، من مستوى إلى مستوى ، من اليسار إلى اليمين ، كما هو الحال في BFS (البحث من أول عرض). يتم تجاهل الجذر وهمية ، وتتم فهرسة الجذر الحقيقي بصفر.
3. تشفير العقد. يتم ترميز عقدة الشجرة من خلال سلسلة من الوحدات المقابلة للأحفاد المباشر ، بالإضافة إلى الصفر. إذا كانت العقدة بها أربعة أطفال ، فسيتم تشفيرها على أنها 11110 ، وإذا لم يكن هناك - 0 ، فسيتم تشفير الجذر المزيف أولاً. لديه سليل واحد ، لذلك الكود هو 10.

شجرة بادئة ذات عقد مرقمة. العقد مشفرة.

في عملية اجتياز شجرة من مستوى إلى مستوى ، يتم إنشاء قاموس مضغوط قابل للفهرسة - سلسلة من البتات من العقد المشفرة الملصقة من أعلى إلى أسفل ومن اليسار إلى اليمين. لدينا تسلسل 21 بت. بالمناسبة ، يطلق عليه LBS (LOUDS Bit String).

القاموس الفهرسة المدمجة لشجرة البادئة.

تم بناء شجرة بادئة LOUDS المدمجة. رطل للخشب مع $$$N$ العقد (وهمية لا تعول) يأخذ $$ الشيء. يبقى الشيء الأكثر إثارة للاهتمام - تحولت صيغ لعبور شجرة إلى صورة نقطية.

البحث عن الطفل الأول . الانتقال من العقدة $$$i$ يتم تنفيذ العقدة الفرعية الأولى وفقًا للمعادلة:

$$

$$firstChild (i) = select_0 (i + 1) - i$$

$$$i$ - هذا هو رقم العقدة في اللوحة السابقة الملصقة باللون الأرجواني.

ابحث عن السليل الأول للعقدة مع الفهرس 3 (الحرف "a"):

$$

$$firsthild (3) = select_0 (3 + 1) - 3 = select_0 (4) - 3 = 9 - 3 = 6$$

العقدة الفرعية الأولى موجودة في الفهرس 6 ، وهذه هي الحرف "k". نحن نطبق صيغة جذر الشجرة:

$$

$$firstChild (0) = select_0 (0 + 1) - 0 = select_0 (1) = 1$$

وجدنا ورقة مع الفهرس 1 ، الحرف "و". CONVERGES! أصبح من الواضح سبب الحاجة إلى جذر مزيف: لسحر فهرسة العقد. لتجنب الأخطاء الغريبة قبل الانتقال إلى أحفاد العقدة $$$i$ سيكون من الجيد معرفة عدد هؤلاء النسل. في الواقع ، بالنسبة لأوراق الشجرة ، وهو أمر غير مفاجئ ، فإن الصيغة تعطي نتيجة غير كافية. للعثور على السليل التالي بعد الأول ، تحتاج إلى إضافة 1. إلى الفهرس الخاص به ، هذا منطقي ، لأن أحفاد إحدى العقدة تكون دائمًا قريبة ، بدون ثغرات. ولكن عند التكرار عليها ، تحتاج إلى التوقف في الوقت المناسب - تحديد من هو السليل الذي يعتبر الأخير.

ابحث عن آخر سليل للعقدة $$$i$ يمر على مرحلتين: تحديد فهرس آخر وحدة في رمز العقدة - وهو الذي يعين السليل المحدد ؛ ثم تحديد مؤشر الطفل نفسه:

$$

$$lastChildPos (i) = select_0 (i + 2) -1$$

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

$$

$$lastChild (i) = rank_1 (lastChildPos (i) -1)$$

العثور على آخر سليل العقدة 2 (الحرف "k").

$$

$$lastChildPos (2) = select_0 (2 + 2) -1 = select_0 (4) -1 = 9-1 = 8 دولارا$$

البتة في الفهرس 8 هي 1 ، وبالتالي ، فإن العقدة 2 ليست ورقة ، ويمكننا إيجاد فهرس آخر طفل لها:

$$

$$lastChild (i) = rank_1 (8-1) = 5$$

عدد المتحدرين. إن أبسط طريقة لتحديد عدد أحفاد هي طرح مؤشر أول نسل له من فهرس آخر نسل العقدة وإضافة 1:

$$

$$childrenCount (i) = lasthild (i) - firsthild (i) + 1$$

لكن لنفترض العقدة $$$i$ هناك عقدة مجاورة $$$i + 1$ تقع في نفس مستوى الشجرة $$$i$ . ثم عدد المتحدرين $$$i$ يمكن تعريفه على أنه الفرق بين مؤشرات أول نسل العقد $$$i + 1$ و $$$i$ :

$$

$$childrenCount (i) = firsthild (i + 1) - firsthild (i)$$

يتم ترقيم أحفاد العقدة أيضًا بالتتابع. إذا كان أول سليل $$$i$ هل هذا $$$j$ ثم الثاني - $$$ي + 1 دولا$ وهكذا نزولاً إلى سليل عقدة مجاورة في هذا المستوى $$$i + 1$ (إن وجدت).

عدد أحفاد الورقة "و" مع الفهرس 1 هو الصفر المتوقع:

$$

$$childrenCount (1) = (select_0 (2 + 1) - 2) - (select_0 (1 + 1) - 1) = 3 - 3 = 0$$

البحث الرئيسي عن عقدة $$$i$ نظمتها الصيغة:

$$

$$parent (i) = rank_0 (select_1 (i + 1) - 1) -1$$

سنستخدمه للبحث عن أصل العقدة 6 (الحرف "k"):

$$

$$parent (6) = rank_0 (select_1 (7) - 1) -1 = rank_0 (9) -1 = 3$$

هذه هي العقدة 3 ، الحرف "أ".

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

زوجان من كوبيل حول أساليب BP و DFUDS. كلتا الطريقتين لها مقاربات مكانية - $$$2N + o (N)$ قليلا للخشب من $$$N$ العقد ، وكلاهما متشابهان في تمثيل عقدة شجرة في شكل فتح وإغلاق الأقواس.

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

من المريح تمثيل تسلسل الأقواس على شكل صورة نقطية ، حيث 1 هي قوس الفتح و 0 هي قوس الإغلاق. يتم توضيح جميع الصيغ للعمل مع BP لإجراء بحث سريع. بخلاف LOUDS ، تسمح لك BP بحساب حجم الشجرة الفرعية وتحديد أقرب سلف مشترك من العقدتين. ولكن العثور عليها $$$i$ -السليل هو أكثر تعقيدا بكثير مما كان عليه في الأحزان.

يشبه DFUDS (تسلسل الدرجة أحادية العمق الأول) كلاً من BP و LOUDS. مع BP ، فهو يجمع بين شجرة في العمق وتمثيل قوس. ومبدأ الأقواس هو نفس مبدأ ترميز العقد في LOUDS. قبل عبور الشجرة ، نضيف قوس فتح واحد إلى تسلسل القوس مقدمًا. بعد ذلك ، عند اجتياز العقد ، نكتب الأقواس المفتوحة وفقًا لعدد الأحفاد ، بالإضافة إلى واحد يغلق واحد. اتضح أن مكان تخزين الأحفاد في DFUDS أعلى من BP. يتم تنفيذ حساب حجم الشجرة الفرعية والبحث عن أقرب سلف مشترك $$$O (1)$ . ولكن تحديد ارتفاع الشجرة الفرعية والعثور على الأصل على $$$j$ المستوى - العمليات الثقيلة ل DFUDS.

من أجل الوضوح ، نقارن طرق LOUDS و BP و DFUDS باستخدام الشجرة الصغيرة كمثال.

يتم ترقيم العقد من الشجرة باللون البرتقالي كما لو كان المشي في العرض (ل LOUDS) ، باللون الأزرق - كما هو الحال عند المشي في العمق (ل BP و DFUDS).

طرق عرض شجرة LOUDS و BP و DFUDS.

لا تتفاجأ إذا رأيت اختلافات في الصيغ في أعمال اللغة الإنجليزية. بين علماء الرياضيات ، هناك عشاق للفهرسة تبدأ من واحد. و بعض المطورين يعتبرون الكلمات مرتبة و متسقة ، لذلك يصنّفون المرتبة نصف الوقت. $$$[0؛ أنا) دولا$ . نظرًا للحاجة إلى الحفاظ على تناسق الرتبة / الاختيار ، يتم حسابها $$ كيف $$ . لكن بعض الصيغ في هذا النموذج تبدو أقصر.

مجموعة متفرقة: يهز ولكن لا تخلط

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

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

دعنا نقول أن لدينا مجموعة متفرقة من السلاسل. إرفاق قاموس فهرسة المدمجة لذلك. ماذا سيعطي؟

مجموعة متفرق مع صورة نقطية.

الآن ، من دون الوصول إلى الصفيف الأصلي مباشرةً ، من السهل التحقق من وجود عنصر فيه في فهرس الاهتمام. لا شيء يمنع تقليص الصفيف الأصلي عن طريق التخلص من جميع العناصر غير المعبئة:

مجموعة بدون عناصر فارغة.

حساب فهرس في صفيف مضغوط. بعد التحقق من وجود عنصر ، سيكون من الجيد الوصول إلى قيمته في المصفوفة الأصلية ، أي تعيين الفهرس $$$i$ في فهرس القاموس المفهرسة $$$j$ في مجموعة مضغوطة. لا عجب أن يتم استخدام هذا الترتيب لهذا:

$$

$$j = rank_1 (i) -1$$

دعونا نتحقق من كيف تسير الأمور مع العنصر الثامن: $$ . لذلك ، في المجموعة الأصلية لا يوجد مثل هذا العنصر. ماذا عن العنصر 7؟ $$ . الحصول على قيمتها: $$$rank_1 (7) - 1 = 3-1 = 2$ . في الفهرس 2 هو "الذهاب".

حساب الفهرس في الصفيف المصدر. بالتأكيد في المجموعة ستحتاج إلى البحث عن العناصر حسب القيمة! إذا لم يتم فرز البيانات ، فسيتم تقليل البحث إلى البحث عنه $$$O (N)$ حيث $$$N$ - عدد العناصر غير الفارغة. للبند وجدت $$$j$ قد تحتاج إلى الحصول على فهرسها $$$i$ كما لو لم تقلصت مجموعة. للقيام بذلك ، استخدم select ، معكوس الرتبة:

$$

$$i = select_1 (j + 1)$$

على سبيل المثال ، ابحث عن السطر "C ++". في صفيف مضغوط ، يوجد في الفهرس 0. وفهرسه في الصفيف الأصلي هو $$$select_1 (0 + 1) = 3 دولا$ .

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

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

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

في الواقع ، يمكن تنفيذ هذه العمليات بكفاءة عالية: الترتيب - من أجل $$$O (1)$ . اختر - ل $$$O (log (log N))$ ، وهو أيضا ثابت تقريبا. وبالطبع ، لا يخلو من بعض الحيل. ولأنه يجب أن يكون هناك أي قدر ضئيل من الأهمية في أي عمل مع مؤامرة معقدة ، سأتوقف هنا.

حقائق مثيرة للاهتمام

ما هو الحد الأدنى النظري للموارد المشغولة من حيث نظرية المعلومات؟ دعنا نقول بنية البيانات بتخزين الكثير من $$$N$ عناصر. لتحديدها دون تصادم ، تحتاج إلى عدد من البتات ، وليس أقل من $$$X = log_2N$ . $$$X$ وهناك الحد الأدنى للغاية الذي تحدده صيغة هارتلي. في بعض الحالات الخاصة ، التي تحتوي على معلومات حول طبيعة البيانات المخزنة ، يمكن ضغط الهيكل بشكل أكثر كفاءة.

هل السلسلة المختصرة هي بنية بيانات؟ أنه يحتوي على $$$N$ الأحرف وينتهي مع حرف ASCII فارغة. لذلك يأخذ $$$N + 1 دولا$ الأماكن ، وبالتالي ... هي مقتضبة ، وبشكل أكثر تحديداً ، ضمنية! مما يقودنا إلى السؤال التالي.

هل جميع الهياكل المختصرة مضغوطة بشكل متساوٍ؟ تعرّف منطقة الأبحاث المختصرة ما يصل إلى ثلاثة أنواع من الهياكل المدمجة التي تختلف في التعقيد المكاني:

• مدمج - $$$O (N)$ . التعقيد الخطي من $$$N$ — . «» . . , : . , . , 0 , . $$$O(2N)$ ( 2 , ) select .
• succinct — $$$N + o(N)$ . — , succinct data structures . : (Pascal string), . $$$N + log(N)$ .
• implicit — $$$N + O(1)$ . , . : (heap) . $$$N + 1$ .

? , , . succinct- . , -, FM-, RMQ (range minimum queries), LCP (longest common prefix), , succinct'. -.

, , . وليس هذا فقط. , , X, .

succinct — , «- ». Succinct — . , , succinct. , . (IME) Google, . MAPS.ME succinct- .

, . ., 97 % -: . 3 %.

ما التالي؟

, succinct:

• rank/select Bitmagic Library.
• , succinct. .
• MIT, succinct.
• , 18 .
• , succinct.
• RRR — .

, :

• مشروع مكتبة هياكل البيانات المختصرة في C ++.
• مشروع BitMagic في C ++.
• حزمة مع تنفيذ موجزة من إلياس فانو في بيثون.
• تنفيذ بعض الهياكل المختصرة في الصدأ.