طاولة قطعة
في مجال الحوسبة ، يُعدّ جدول الأجزاء بنية بيانات تُستخدم عادةً لتمثيل مستند نصي أثناء تحريره في محرر نصوص . في البداية، يتم إنشاء مرجع (أو "نطاق") إلى الملف الأصلي بأكمله، والذي يُمثل الملف قبل التغيير. تستبدل عمليات الإدراج والحذف اللاحقة النطاق بمجموعات من مرجع واحد أو مرجعين أو ثلاثة مراجع إلى أقسام إما من المستند الأصلي أو إلى مخزن مؤقت يحتوي على النص المُدرج. [ 1 ]
عادةً ما يُخزَّن نص المستند الأصلي في كتلة واحدة غير قابلة للتغيير ، ويُخزَّن نص كل إضافة لاحقة في كتل جديدة غير قابلة للتغيير. ولأن النص المحذوف يبقى مُضمَّنًا في جدول الأجزاء، فإن هذا يجعل التراجع متعدد المستويات أو غير المحدود أسهل في التنفيذ باستخدام جدول الأجزاء مقارنةً بهياكل البيانات البديلة مثل مخزن الفجوات .
تم ابتكار بنية البيانات هذه بواسطة جيه ستروثر مور . [ 2 ]
وصف
في هذا الوصف، نستخدم المخزن المؤقت ككتلة غير قابلة للتغيير لحفظ المحتويات.
يتكون جدول القطع من ثلاثة أعمدة: [ 1 ]
- أي مخزن مؤقت
- فهرس البداية في المخزن المؤقت
- الطول في المخزن المؤقت
بالإضافة إلى الجدول، يتم استخدام مخزنين مؤقتين للتعامل مع عمليات التحرير:
- " المخزن المؤقت الأصلي ": مخزن مؤقت للمستند النصي الأصلي. هذا المخزن المؤقت للقراءة فقط.
- " إضافة مخزن مؤقت ": مخزن مؤقت لملف مؤقت . هذا المخزن مخصص للإضافة فقط.
العمليات
فِهرِس
التعريف:
Index(i): إرجاع الحرف الموجود في الموضع i في المستند المجمع (PTD).
لاسترداد الحرف رقم i من PTD، تتم قراءة الإدخال المناسب في جدول القطع.
مثال
بالنظر إلى المخازن المؤقتة وجدول القطع التالي:
| المخزن المؤقت | محتوى |
|---|---|
| الملف الأصلي | ipsum sit amet |
| إضافة ملف | Lorem deletedtext dolor |
| أيّ | فهرس البداية | طول | مؤشرات PTD |
|---|---|---|---|
| يضيف | 0 | 6 | 0–5 |
| إبداعي | 0 | 5 | 6-10 |
| يضيف | 17 | 6 | 11-16 |
| إبداعي | 5 | 9 | 17-25 |
لن يتضمن التنفيذ الحقيقي لجدول القطع عمودًا لمؤشرات PTD ("المستند المجمع") نظرًا لاحتواء العمود على معلومات يمكن استنتاجها من فهرس بداية جدول القطع وطوله وموضع الصف، ولكن تم عرضه أعلاه لأغراض تعليمية.
يُحدد ترتيب صفوف جدول الأجزاء ضمنيًا ترتيب الأحرف المستخدمة من المخازن المؤقتة المتاحة. أي أن الصف الأول من جدول الأجزاء (مثل <Add,0,6>) يصف التسلسل الأول من الأحرف في ملف PTD (مثل مؤشرات PTD من 0 إلى 5). ويصف الصف الثاني من جدول الأجزاء (مثل <Original,0,5>) تسلسل الأحرف من مخزن مؤقت مختلف، والذي سيلي مباشرةً الأحرف المختارة من التسلسل الأول (مثل مؤشرات PTD من 6 إلى 10). ويستمر هذا حتى نهاية ملف PTD. في المثال أعلاه، يُشير جدول الأجزاء إلى أن ملف PTD سيحتوي على 6 + 5 + 6 + 9 = 26 حرفًا.
للحصول على قيمة الحرف Index(15)، نبحث أولًا عن المدخل (الصف) في جدول الأجزاء الذي يُطابق فهرس PTD رقم 15. يصف المدخل الأول الأحرف في فهارس PTD من 0 إلى 5، ويصف المدخل الثاني الأحرف في فهارس PTD من 6 إلى 10، ويصف المدخل الثالث الأحرف في فهارس PTD من 11 إلى 16. بما أن المدخل الثالث في جدول الأجزاء يُطابق فهرس PTD رقم 15 (11 ≤ 15 ≤ 16)، يتم استرجاع هذا المدخل. يُوجه المدخل الثالث في جدول الأجزاء البرنامج للبحث عن الأحرف في مخزن " إضافة ملف "، بدءًا من الفهرس 17 في ذلك المخزن. الفهرس النسبي في هذا المدخل هو PTD_SoughtIndex − PTD_StartIndexOfEntry = 15 − 11 = 4، والذي يُضاف إلى موضع بداية المدخل في المخزن المؤقت للحصول على فهرس الحرف: 4 + 17 = 21. قيمة هذا الفهرس Index(15)هي الحرف الحادي والعشرون من مخزن "إضافة ملف"، وهو الحرف "o". بشكل عام، وفي المثال أعلاه،
Buffer_IdxOfSoughtChar = PTD_SoughtIndex − PTD_StartIdxOfEntry + Buffer_StartIdxOfEntry 21 = 15 − 11 + 17 SoughtChar = Entry_NameOfBuffer[Buffer_IdxOfSoughtChar] 'o' = AddFileBuf[21] --------------------------- إذن، 'o' = Index(15)
بالنسبة للمخازن المؤقتة وجدول القطع المذكور أعلاه، يظهر مخطط توزيع الطاقة التالي:
"لوريم" (من مدخل الجدول رقم 1) +"ipsum" (من مدخل الجدول رقم 2) +"ألم" (من مدخل رقم 3 في جدول القطع) +" sit amet" (من مدخل الجدول رقم 4) -------------------------- لوريم إيبسوم دولور سيت أميت
أدخل
تتضمن عملية إدخال الأحرف في النص ما يلي:
- إضافة الأحرف إلى مخزن "إضافة ملف"، و
- تحديث المدخل في جدول القطع (تقسيم المدخل إلى قطعتين أو ثلاث)
يمسح
يمكن أن يكون حذف حرف واحد أحد حالتين محتملتين:
- يتم الحذف في بداية أو نهاية إدخال القطعة، وفي هذه الحالة يتم تعديل الإدخال المناسب في جدول القطع.
- يحدث الحذف في منتصف إدخال قطعة، وفي هذه الحالة يتم تقسيم الإدخال ثم يتم تعديل أحد الإدخالات اللاحقة كما هو مذكور أعلاه.
الاستخدام
تستخدم العديد من محررات النصوص جدول أجزاء داخل ذاكرة الوصول العشوائي (RAM) داخليًا، بما في ذلك Bravo ، [ 1 ] وAbiword ، [ 3 ] [ 4 ] [ 5 ] و Atom ، [ 6 ] و Visual Studio Code . [ 7 ]
تستخدم ميزة "الحفظ السريع" في بعض إصدارات برنامج Microsoft Word جدولًا للأجزاء لتنسيق الملف الموجود على القرص . [ 2 ]
يستخدم نظام Oberon تقنية سلسلة الأجزاء التي تسمح لأجزاء من مستند واحد بالإشارة إلى نص مخزن في مستند آخر، على غرار التضمين . [ 8 ]
انظر أيضاً
- حبل (علوم الحاسوب)
- مخزن الفجوات ، وهو بنية بيانات شائعة الاستخدام في محررات النصوص، تسمح بعمليات إدراج وحذف فعالة مجمعة بالقرب من نفس الموقع.
- إنفيلاد ، موديل تي إنفيلاد عبارة عن طاولة قطع ذات تنفيذ قائم على الشجرة.
مراجع
- 1 2 3 كراولي، تشارلز (10 يونيو 1998). "هياكل البيانات لتسلسلات النصوص. 6.4 طريقة جدول القطع" (ملف PDF) . www.cs.unm.edu . مؤرشف (ملف PDF) من الأصل في 23 فبراير 2018. تم الاطلاع عليه في 26 يوليو 2021 .
- 1 2 ديفيد لو. "ما الذي تم إنجازه باستخدام طاولة القطع؟" ( مناقشة ).
- ↑ "تطوير AbiWord: خلفية جدول القطع" .
- ↑ جيمس براون. "سلاسل القطع: تصميم وتنفيذ محرر نصوص Win32" .
- ↑ خواكين كوينكا أبيلا. "تحسين جدول القطع في برنامج أبي وورد" .
- ↑ ناثان سوبو (12 أكتوبر 2017). "تنفيذ المخزن المؤقت الجديد الملائم للتزامن في Atom" . مدونة Atom . تم الاطلاع عليه بتاريخ 29 أغسطس 2024 .
- ↑ "ملاحظات إصدار VS Code 1.21 ( شفرة المصدر )"
- ↑ نيكلاوس ويرث، يورغ غوتكنيشت. "مشروع أوبرون: تصميم نظام تشغيل ومترجم" مؤرشف في 12 أبريل 2013 على موقع Wayback Machine . 2005. ص 90.
- هياكل بيانات السلاسل