بنية بيانات موجزة

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

لنفترض أن${\displaystyle Z}$يمثل هذا العدد الأمثل من البتات اللازمة لتخزين بعض البيانات من الناحية النظرية للمعلومات. ويُطلق على تمثيل هذه البيانات اسم:

• ضمنيًا إذا كان يأخذ${\displaystyle Z+O(1)}$مساحات صغيرة،
• موجز إذا استغرق الأمر${\displaystyle Z+o(Z)}$مساحات صغيرة، و
• مضغوط إذا استغرق الأمر${\displaystyle O(Z)}$مساحات صغيرة.

على سبيل المثال، بنية بيانات تستخدم${\displaystyle 2Z}$وحدات التخزين صغيرة الحجم،${\displaystyle Z+{\sqrt {Z}}}$كلمة bits مختصرة،${\displaystyle Z+\lg Z}$كلمة "bits" مختصرة أيضاً، و${\displaystyle Z+3}$البتات مفهومة ضمنيًا.

وبالتالي، عادةً ما يتم اختزال الهياكل الضمنية إلى تخزين المعلومات باستخدام بعض التبديلات لبيانات الإدخال؛ والمثال الأكثر شهرة على ذلك هو الكومة .

تشكل القواميس الموجزة القابلة للفهرسة، والتي تسمى أيضًا قواميس الترتيب/الاختيار ، أساسًا لعدد من تقنيات التمثيل الموجزة، بما في ذلك الأشجار الثنائية .${\displaystyle k}$الأشجار من الرتبة n والمجموعات المتعددة ، ^{[ 2 ]} بالإضافة إلى أشجار اللواحق والمصفوفات . ^{[ 3 ]} تكمن المشكلة الأساسية في تخزين مجموعة جزئية${\displaystyle S}$من كون${\displaystyle U=[0\dots n)=\{0,1,\dots ,n-1\}}$، وعادة ما يتم تمثيلها كمصفوفة بت${\displaystyle B[0\dots n)}$أين${\displaystyle B[i]=1}$إذا${\displaystyle i\in S.}$يدعم القاموس القابل للفهرسة الطرق المعتادة في القواميس (الاستعلامات، والإدراجات/الحذف في الحالة الديناميكية) بالإضافة إلى العمليات التالية:

• ${\displaystyle \mathbf {rank} _{q}(x)=|\{k\in [0\dots x]:B[k]=q\}|}$
• ${\displaystyle \mathbf {select} _{q}(x)=\min\{k\in [0\dots n):\mathbf {rank} _{q}(k)=x\}}$

ل${\displaystyle q\in \{0,1\}}$.

بعبارة أخرى،${\displaystyle \mathbf {rank} _{q}(x)}$تُعيد عدد العناصر التي تساوي${\displaystyle q}$حتى الوضع${\displaystyle x}$بينما ${\displaystyle \mathbf {select} _{q}(x)}$يُعيد موضع${\displaystyle x}$الظهور رقم -th من${\displaystyle q}$.

يوجد تمثيل بسيط ^{[ 4 ]} يستخدم${\displaystyle n+o(n)}$وحدات من مساحة التخزين (مصفوفة البتات الأصلية و${\displaystyle o(n)}$( بنية مساعدة) ويدعم الترتيب والاختيار في وقت ثابت. يستخدم فكرة مشابهة لتلك المستخدمة في استعلامات الحد الأدنى للنطاق ؛ حيث يوجد عدد ثابت من التكرارات قبل التوقف عند مشكلة فرعية ذات حجم محدود. مصفوفة البتات${\displaystyle B}$يتم تقسيمها إلى كتل كبيرة الحجم${\displaystyle l=\lg ^{2}n}$أجزاء وكتل صغيرة من الحجم${\displaystyle s=\lg n/2}$البتات. بالنسبة لكل كتلة كبيرة، يتم تخزين رتبة البت الأول فيها في جدول منفصل${\displaystyle R_{l}[0\dots n/l)}$يأخذ كل إدخال من هذا القبيل${\displaystyle \lg n}$بتات بإجمالي${\displaystyle (n/l)\lg n=n/\lg n}$وحدات تخزين. داخل كتلة كبيرة، دليل آخر${\displaystyle R_{s}[0\dots l/s)}$يخزن رتبة كل من${\displaystyle l/s=2\lg n}$يحتوي على كتل صغيرة. والفرق هنا هو أنه يحتاج فقط إلى${\displaystyle \lg l=\lg \lg ^{2}n=2\lg \lg n}$يتم تخزين بتات لكل مدخل، حيث لا يلزم سوى تخزين الفروقات عن رتبة البت الأول في الكتلة الكبيرة الحاوية. وبالتالي، يستغرق هذا الجدول ما مجموعه${\displaystyle (n/s)\lg l=4n\lg \lg n/\lg n}$بتات. جدول بحث${\displaystyle R_{p}}$يمكن بعد ذلك استخدام أداة تخزن الإجابة على كل استعلام ترتيب ممكن على سلسلة بتات بطول${\displaystyle s}$ل${\displaystyle i\in [0,s)}$وهذا يتطلب${\displaystyle 2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)}$أجزاء من مساحة التخزين. وبالتالي، بما أن كل جدول من هذه الجداول المساعدة يأخذ${\displaystyle o(n)}$في هذا الفضاء، يدعم هيكل البيانات هذا استعلامات الترتيب في${\displaystyle O(1)}$الوقت و${\displaystyle n+o(n)}$مساحات صغيرة.

للإجابة على استفسار بخصوص${\displaystyle \mathbf {rank} _{1}(x)}$في زمن ثابت، تقوم خوارزمية الزمن الثابت بحساب ما يلي:

• ${\displaystyle \mathbf {rank} _{1}(x)=R_{l}[\lfloor x/l\rfloor ]+R_{s}[\lfloor x/s\rfloor ]+R_{p}[x\lfloor x/s\rfloor ,x{\text{ mod }}s]}$

عملياً، جدول البحث${\displaystyle R_{p}}$يمكن استبدالها بعمليات على مستوى البت وجداول أصغر تُستخدم لتحديد عدد البتات المُفعّلة في الكتل الصغيرة. غالبًا ما يكون هذا مفيدًا، لأن هياكل البيانات المختصرة تُستخدم في مجموعات البيانات الكبيرة، حيث تزداد حالات عدم العثور على البيانات في ذاكرة التخزين المؤقت، وتزداد احتمالية إخراج جدول البحث من ذاكرة التخزين المؤقت الأقرب لوحدة المعالجة المركزية. ^{[ 5 ]} يمكن دعم استعلامات التحديد بسهولة عن طريق إجراء بحث ثنائي على نفس البنية المساعدة المستخدمة للترتيب ؛ ومع ذلك، فإن هذا يستغرق${\displaystyle O(\lg n)}$الوقت في أسوأ الحالات. بنية أكثر تعقيدًا باستخدام${\displaystyle 3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)}$يمكن استخدام وحدات تخزين إضافية لدعم عملية الاختيار في وقت ثابت. ^{[ 6 ]} عمليًا، تحتوي العديد من هذه الحلول على ثوابت مخفية في${\displaystyle O(\cdot )}$تسود هذه الترميز قبل أن يصبح أي ميزة تقاربية واضحة؛ وغالبًا ما يكون أداء التطبيقات التي تستخدم عمليات الكلمات العريضة والكتل المحاذية للكلمات أفضل في الممارسة العملية. ^{[ 7 ]}

جدول التجزئة الموجز ، المعروف أيضًا باسم القاموس غير المرتب الموجز، هو بنية بيانات تخزن${\displaystyle m}$مفاتيح من الكون${\displaystyle \{0,1,\dots ,n-1\}}$استخدام المساحة${\displaystyle (1+o(1)){\mathcal {B}}(m,n)}$تدعم جداول التجزئة المختصرة عمليات الإدخال والحذف في وقت متوقع ثابت. وإذا كانت تدعم أيضًا عمليات الإدخال والحذف في وقت متوقع ثابت، فإنها تُسمى جداول تجزئة ديناميكية ، وإلا فإنها تُسمى جداول تجزئة ثابتة.

يعود الفضل في أول جدول تجزئة موجز ديناميكي إلى رامان وراو في عام 2003. ^{[ 13 ]} في الحالة التي${\displaystyle n={\text{poly}}(m)}$حلهم يستخدم المساحة${\displaystyle {\mathcal {B}}(m,n)+O(m\log \log m)}$بتات. وفي وقت لاحق، تبين أنه يمكن تحسين هذا الحد المكاني إلى${\displaystyle {\mathcal {B}}(m,n)+O(m\log \log \log \cdots \log m)}$عدد البتات لأي عدد ثابت من اللوغاريتمات ^{[ 14 ]} ، وبعد ذلك بقليل، كان هذا الحد الأمثل أيضًا. ^{[ 15 ] [ 16 ]} يدعم الحل الأخير جميع العمليات في أسوأ الحالات في وقت ثابت باحتمالية عالية .

يعود الفضل في أول جدول تجزئة ثابت ومختصر إلى باج في عام 1999. ^{[ 17 ] [ 18 ]} في الحالة التي${\displaystyle n={\text{poly}}(m)}$حلهم يستخدم المساحة${\displaystyle {\mathcal {B}}(m,n)+O(m(\log \log m)^{2}/\log m)}$يدعم هذا الحد الأقصى للبتات، ويدعم الاستعلامات ذات الوقت الثابت في أسوأ الحالات . وقد تم تحسين هذا الحد لاحقًا إلى${\displaystyle {\mathcal {B}}(m,n)+m/{\text{poly}}\log m}$بتات، ^{[ 9 ]} ثم إلى${\displaystyle {\mathcal {B}}(m,n)+{\text{poly}}\log m}$بتات. ^{[ 19 ]} بينما يدعم الحلان الأولان ^{[ 18 ] [ 9 ]} استعلامات ذات وقت ثابت في أسوأ الحالات، يدعم الحل الأخير استعلامات ذات وقت متوقع ثابت. ^{[ 19 ]} يتطلب الحل الأخير أيضًا الوصول إلى جدول بحث بحجم${\displaystyle n^{\epsilon }}$لكن جدول البحث هذا مستقل عن مجموعة العناصر المخزنة. ^{[ 19 ]} وفي الآونة الأخيرة، ابتكر هو وآخرون ^{[ 20 ]} حلاً يستخدم المساحة${\displaystyle {\mathcal {B}}(m,n)+n^{\epsilon }}$مع دعم الاستعلامات ذات الوقت الثابت في أسوأ الحالات.

تشغل السلسلة ذات الطول العشوائي ( سلسلة باسكال ) مساحة Z + log( Z )، وبالتالي فهي مختصرة. إذا كان هناك حد أقصى للطول - وهو الحال عمليًا، لأن 2^ ³² = 4 جيجابايت من البيانات تُعد سلسلة طويلة جدًا، و2^ ⁶⁴ = 16 إكسابايت من البيانات أكبر من أي سلسلة في الواقع - فإن السلسلة ذات الطول المحدد تكون ضمنية أيضًا، وتشغل مساحة Z + k ، حيث k هو عدد البيانات اللازمة لتمثيل الطول الأقصى (مثلًا، 64 بت).

عند الحاجة إلى ترميز سلسلة من العناصر ذات الأطوال المتغيرة (مثل السلاسل النصية)، تتوفر عدة خيارات. يتمثل أحد الأساليب المباشرة في تخزين الطول والعنصر في كل سجل، ومن ثم يمكن وضع هذه العناصر تباعًا. يتيح هذا الأسلوب الوصول الفعال إلى العنصر التالي، ولكنه لا يتيح العثور على العنصر رقم k . يتمثل بديل آخر في ترتيب العناصر باستخدام فاصل (مثل سلسلة نصية منتهية بـ null ). يستخدم هذا الأسلوب الفاصل بدلًا من الطول، وهو أبطأ بكثير، نظرًا لضرورة فحص السلسلة بأكملها بحثًا عن الفواصل. كلا الأسلوبين يتميزان بكفاءة استخدام المساحة. يتمثل أسلوب آخر في الفصل خارج النطاق: حيث يمكن ببساطة وضع العناصر تباعًا دون فواصل. يمكن بعد ذلك تخزين حدود العناصر كسلسلة من الأطوال، أو الأفضل من ذلك، كإزاحات داخل هذه السلسلة. بدلاً من ذلك، يتم ترميز سلسلة ثنائية منفصلة تتكون من 1 في المواضع التي يبدأ منها العنصر، و0 في أي مكان آخر. وبالنظر إلى هذه السلسلة، فإن${\displaystyle select}$يمكن للدالة تحديد مكان بداية كل عنصر بسرعة، بمعرفة فهرسه. ^{[ 21 ]} هذا مضغوط ولكنه ليس موجزًا، حيث أنه يأخذ مساحة 2Z ، وهو ما يعادل O( Z ).

مثال آخر هو تمثيل الشجرة الثنائية : شجرة ثنائية عشوائية على${\displaystyle n}$يمكن تمثيل العقد في${\displaystyle 2n+o(n)}$يدعم هذا النظام مجموعة متنوعة من العمليات على أي عقدة، بما في ذلك إيجاد العقدة الأب، والعقدة الابنة اليسرى واليمنى، وإرجاع حجم الشجرة الفرعية، كل ذلك في وقت ثابت. عدد الأشجار الثنائية المختلفة على${\displaystyle n}$العقدة هي${\displaystyle {\tbinom {2n}{n}}}$${\displaystyle /(n+1)}$. للأحجام الكبيرة${\displaystyle n}$هذا يتعلق${\displaystyle 4^{n}}$وبالتالي نحتاج على الأقل إلى حوالي${\displaystyle \log _{2}(4^{n})=2n}$عدد البتات اللازمة لترميزها. وبالتالي، فإن الشجرة الثنائية المختصرة ستشغل مساحة لا تتجاوز 10 بتات.${\displaystyle 2}$عدد البتات لكل عقدة.

• دالة التجزئة المثالية الدنيا
• حجج معرفية موجزة غير تفاعلية