بنية البيانات الضمنية

في علوم الحاسوب ، تُعرف بنية البيانات الضمنية أو بنية البيانات الموفرة للمساحة بأنها بنية بيانات تخزن معلومات قليلة جدًا بخلاف البيانات الأساسية أو المطلوبة، أي أنها تتطلب موارد إضافية قليلة . ويُطلق عليها اسم "ضمنية" لأن موقع العناصر يحمل دلالة وعلاقة بينها، وهذا يختلف عن استخدام المؤشرات لإعطاء علاقة صريحة بين العناصر. تختلف تعريفات "الموارد الإضافية القليلة"، ولكنها تعني عمومًا موارد إضافية ثابتة؛ في ترميز Big O ، تكون الموارد الإضافية O (1). وهناك تعريف أقل تقييدًا لبنية البيانات المختصرة ، والتي تسمح بموارد إضافية أكبر.

بنية البيانات الضمنية هي بنية ذات مساحة ثابتة O (1) (أعلى من الحد الأدنى النظري للمعلومات ).

عرّف مونرو وسواندا (1980) تاريخيًا بنية البيانات الضمنية (والخوارزميات التي تعمل عليها) بأنها "بنية تكون فيها المعلومات الهيكلية ضمنية في طريقة تخزين البيانات، وليست صريحة في المؤشرات". كان تعريفهم غامضًا إلى حد ما، حيث عرّفوها بدقة على أنها مصفوفة واحدة، مع الاحتفاظ بالحجم فقط (قيمة واحدة للحمل الزائد)، ^{[ 1 ]} أو بشكل أكثر مرونة على أنها بنية بيانات ذات حمل زائد ثابت ( O (1) ). ^{[ 2 ]} يُعد هذا التعريف الأخير هو الأكثر شيوعًا اليوم، أما المفهوم الأكثر مرونة لبنية البيانات ذات الحمل الزائد غير الثابت ولكنه صغير (o ( n )) فيُعرف اليوم باسم بنية البيانات المختصرة ، كما عرّفها جاكوبسون (1988) ؛ وقد أشار إليها مونرو وسواندا (1980) باسم شبه ضمنية . ^{[ 3 ]}

يتمثل أحد الفروق الأساسية بين هياكل البيانات الثابتة (للقراءة فقط) وهياكل البيانات الديناميكية (التي يمكن تعديلها). قد تكون هياكل البيانات الضمنية البسيطة، مثل تمثيل قائمة مرتبة كمصفوفة، فعالة للغاية كهيكل بيانات ثابت، ولكنها غير فعالة كهيكل بيانات ديناميكي، وذلك بسبب عدم كفاءة عمليات التعديل (مثل الإضافة في حالة القائمة المرتبة).

من الأمثلة البسيطة على هياكل البيانات الضمنية مصفوفة البيانات ، وهي بنية بيانات ضمنية للقوائم ، ولا تتطلب سوى قيمة ثابتة لطول القائمة؛ على عكس القائمة المتصلة ، التي تحتوي على مؤشر مرتبط بكل عنصر من عناصر البيانات، مما يوضح العلاقة بين كل عنصر وآخر بشكل صريح . وبالمثل، تُعد السلسلة النصية المنتهية بـ null بنية بيانات ضمنية للسلاسل النصية (قائمة من الأحرف). وتُعتبر هذه الهياكل بسيطة للغاية لأنها هياكل بيانات ثابتة (للقراءة فقط)، ولا تسمح إلا بعملية التكرار البسيطة على عناصرها.

وبالمثل، من السهل تمثيل مصفوفة متعددة الأبعاد كمصفوفة أحادية البعد، مع أبعادها. على سبيل المثال، يمكن تمثيل مصفوفة m × n كقائمة واحدة بطول m·n ، مع العددين m و n (بدلاً من تمثيلها كمصفوفة أحادية البعد من المؤشرات إلى كل مصفوفة فرعية أحادية البعد). لا يشترط أن تكون العناصر من النوع نفسه، ويمكن تمثيل جدول البيانات (قائمة السجلات ) ضمنيًا كقائمة مسطحة (أحادية البعد)، مع طول كل حقل ، بشرط أن يكون لكل حقل حجم موحد (بحيث يمكن استخدام حجم واحد لكل حقل، وليس لكل سجل).

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

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

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

تتضمن هياكل البيانات الضمنية الأكثر تطوراً الكومة (الكومة ثنائية الأبوين).

تعود الأمثلة البسيطة للقوائم أو جداول القيم إلى عصور ما قبل التاريخ، بينما يعود تاريخ هياكل البيانات الضمنية غير البسيطة تاريخيًا على الأقل إلى جدول الأنساب (Ahnentafel)، الذي قدمه مايكل إيتزينجر عام 1590 لاستخدامه في علم الأنساب. في علوم الحاسوب الرسمية، تُعتبر القائمة المرتبة، المستخدمة في البحث الثنائي، أول هيكل بيانات ضمني، وقد قدمها جون موشلي عام 1946 في محاضرات مدرسة مور ، وهي أول سلسلة محاضرات على الإطلاق تتناول أي موضوع متعلق بالحاسوب. ^{[ 4 ] [ 5 ]} تم تقديم الكومة الثنائية في ويليامز (1964) لتنفيذ فرز الكومة . ^{[ 5 ]} تم صياغة مفهوم هيكل البيانات الضمني رسميًا في مونرو وسواندا (1980) ، كجزء من تقديم وتحليل الكومة الثنائية . ^{[ 5 ]}

انظر منشورات هيرفيه برونيمان ، وجيه إيان مونرو ، وجريج فريدريكسون .