فهرس مقلوب

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

يكمن الغرض من الفهرس المقلوب في السماح بعمليات بحث سريع وشامل باستخدام النصوص (Full-text search)، على حساب زيادة في المعالجة عند إضافة وثيقة إلى قاعدة البيانات. قد يكون الملف المقلوب هو ملف قاعدة البيانات نفسه، وليس فهرسها. يُعد الفهرس المقلوب أكثر هياكل البيانات شيوعًا والمُستخدمة في أنظمة استرجاع الوثائق، ويُستخدم على نطاق واسع في محركات البحث على سبيل المثال. بالإضافة إلى ذلك، استخدمت العديد من أنظمة إدارة قواعد البيانات العامة المهمة القائمة على الحواسيب المركزية (Mainframe) معماريات القائمة المقلوبة، ومنها ADABAS و DATACOM/DB و Model 204.

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

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

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

في عصور ما قبل الحاسوب كانت المسارد الأبجدية للكتب تُجمع يدويًا. كانت هذه الفهارس في الواقع فهارس مقلوبة مع قدر صغير من التعليقات المصاحبة، وتطلبت قدرًا هائلاً من الجهد لإنتاجها.

تُعد الفهارس المقلوبة في المعلوماتية الحيوية مهمة جدًا في تجميع متواليات الأجزاء القصيرة من الحمض النووي (DNA) الذي تم تحديد تسلسله. تتمثل إحدى طرق العثور على مصدر لجزء ما في البحث عنه مقابل متوالية مرجعية للحمض النووي. يمكن حساب عدد صغير من عدم التطابقات (بسبب الاختلافات بين الحمض النووي المُحدد تسلسله والحمض النووي المرجعي، أو الأخطاء) عن طريق تقسيم الجزء إلى أجزاء أصغر - ومن المحتمل أن يتطابق جزء فرعي واحد على الأقل مع متوالية الحمض النووي المرجعية. يتطلب التطابق بناء فهرس مقلوب لجميع المتواليات الفرعية (Substrings) ذات طول معين من متوالية الحمض النووي المرجعية. نظرًا لأن الحمض النووي البشري يحتوي على أكثر من 3 مليارات زوج قاعدي، ونحتاج إلى تخزين متوالية فرعية للحمض النووي لكل فهرس وعدد صحيح 32 بت للفهرس نفسه، فمن المحتمل أن تكون متطلبات التخزين لمثل هذا الفهرس المقلوب في عشرات الجيجابايت.

 الضغط 
لأسباب تاريخية، تم تطوير ضغط القائمة المقلوبة و ضغط الصور النقطية (Bitmap compression) كمسارين بحثيين منفصلين، ولم يتم الاعتراف بهما إلا لاحقًا على أنهما يحلان نفس المشكلة بشكل أساسي.

 مراجع 

 مراجع 

تصنيف:إدارة البيانات
تصنيف:خوارزميات بحث