خانه --> پایگاه داده های مبتنی بر متن --> ایندکس معکوس (inverted index) چیست؟

ایندکس معکوس (inverted index) چیست؟

در قسمت های قبل روشهای شاخص گذاری بر روی داده ها را بررسی نمودیم. اکنون در بخش ایندکس معکوس (inverted index) مورد مطالعه قرار میدهیم. شاخص­ گذاری معکوس، یک مکانیزم مبتنی بر کلمه است که برای جستجوی سریع اسناد شامل یک کلمه­ خاص به کار می­رود. در اینجا منظور از سند، دنباله محدودی از کاراکترها است و یک کلمه، زیردنباله‍ای از یک سند است.

شاخص ­گذاری معکوس دارای دو مولفه اصلی است:

  • کلمه
  •  لیستی از کلمه­ ها

یک “لیست پست” (Posting list) که در ارتباط با یک کلمه­ ی خاص است، اطلاعاتی را درباره رخدادهای کلمه نگهداری می­کند و شامل شناسه سند (کلمه و لیست مکان­های کلمه در آن سند) است. در شکل های زیر فرایند و مراحل نمایه گذاری معکوس نمایش داده شده است.

ایندکس معکوس
مراحل ایندکس معکوس

 

ایندکس معکوس
مراحل ایندکس معکوس

 

ایندکس معکوس
Inverted Index

برای هر کلمه ، لیست پست شامل پست­های <d,[o1,…,of]> است که در آن d شناسه سند، [o1,…,of] لیست مکان­ ها و f تعداد تکرارهای کلمه در سند d است. گذشته از این­ها، شاخص‍گذاری+  B-tree نیز بر روی کلمه­ ها اعمال می­شود تا به سرعت یک لیست پست را مکان­یابی کند. ‏شکل زیر  ساختار شاخص معکوس را نشان می­دهد‎.

شاخص‍گذاری + B-tree
شاخص‍گذاری + B-tree

ساختار ایندکس معکوس (شاخص معکوس)

با توجه به روش استخراج کلمه­ ها، شاخص­گذاری معکوس به دو قسمت طبقه ­بندی می­شود:

۱) شاخص‍ گذاری معکوس بر مبنای انتخاب کلمه که خود بر دو نوع بوده و در ادامه توضیح داده می­شود

۲) شاخص­گذاری چند-‍وزنی، که بیشتر روی شاخص ­گذاری چند-­وزنی تمرکز می‍شود.

انواع شاخص گداری یا ایندکس معکوس بر مبنای انتخاب کلمه عبارتند از‏:

شاخص‌گذاری مبتنی بر کلمه

روش شاخص‌گذاری مبتنی بر کلمه (Word-Based Indexing) در زبان‌های زیادی همانند انگلیسی و اسپانیایی استفاده می‌شود تا اسناد و پرس و جوها را نمایش دهد. شاخص‌گذاری مبتنی بر کلمه، کلمات را با بعضی نشانه‌ها همانند فضاهای خالی و ویرگول  از هم تفکیک می‌کند. همچنین شامل فرآیند ریشه‌یابی می باشد. در فرآیند ریشه‏یابی اضافات انتهای کلمات را عموماً حذف می‌کند تا کلاس‌های مشابه برای شکل‌های مختلف کلمات یافت شود. برای مثال، ریشه‌یاب، برای واژه‌های «مهندسی کردن»، «مهندسی» و «مهندس» واژه شاخص «مهندس» را تولید می‌کند. این روش شاخص‌گذاری، ریشه‌یابی را انجام داده و واژه‌های شاخص را با استفاده از تغییر شکل متن به صورت زیر تولید می‌کند:

  1. شناسایی کلمات مجزا در متن
  2. تولید ریشه‌های کلمات با استفاده از حذف پسوندها
  3. حذف ریشه‌های کلماتی که متعلق به لیست توقف هستند.

این روش، یک اسم ترکیبی را به اسامی ساده‌تر تجزیه نمی‌کند و زمانی­که متن شامل تعداد زیادی اسم ترکیبی باشد، کارایی بازیابی اطلاعات به طور جدی کاهش می­یابد.

شاخص‌گذاری مبتنی بر کوچک‌ترین واحد زبان

روش شاخص‌گذاری مبتنی بر کوچک‌ترین واحد زبان (Morpheme-Based Indexing) مشکل شاخص‌گذاری مبتنی بر کلمه (عدم تجزیه­ی اسامی مرکب به اسامی ساده­تر) را ندارد، زیرا اسناد و پرس و جوها را تنها با اسامی ساده نشان می‌دهد. معمولاً روش شاخص‌گذاری مبتنی بر کوچک‌ترین واحد زبان شامل ۵ گام است:

  1. شناسایی کلمات مجزا در متن
  2. جداسازی یک کلمه به شکل تمامی دنباله‌های ممکن از اجزای زبان
  3. انتخاب محتمل‌ترین دنباله از اجزای زبان
  4. استخراج اسامی ساده از دنباله
  5. حذف اسامی ساده متعلق به لیست توقف

در این روش از شاخص‌گذاری، سطوحی از پردازش زبان طبیعی که شامل تحلیل لغوی یا تحلیل معنایی هستند، پوشش داده می‌شوند و یک کلمه به شکل یک مجموعه از کوچک‌ترین واحدهای معنی‌دار زبان که اغلب واژک نامیده می‌شود، تجزیه می‌شود و شاخه‌های لغوی آن را که شامل اسامی ساده، فعل‌ها، صفت‌ها و واژه‌های ناشناخته هستند، تولید می‌کند. بنابراین تنها اسامی ساده را به عنوان کلمات کلیدی بازیابی و استخراج می‌کند.

شاخص‌گذاری چند‌-وزنی

کاربرد چند‌‌-وزنی‌ها برای بازیابی اطلاعات از تمایل برای کاهش اندازه مجموعه لغات (Dictionary) ناشی می‌شود ‏. تعداد کلماتی که ممکن است در یک مجموعه یافت شوند، محدود به n (تعداد حروف الفبا) است. برای مثال، زمانی که زبان انگلیسی مدنظر باشد و n=3 در نظر گرفته شود، با توجه به اینکه تعداد حروف انگلیسی ۲۶ است، در نتیجه حداکثر ۱۹۶۸۳ عدد ۳-وزنی ممکن است یافت شود. بر این اساس، مطالعات بی‏شماری روی تاثیر چند‌-وزنی‌ها انجام شده است. در سال ۱۹۷۴،de hear استفاده از چند‌-وزنی‌ها را به عنوان جایگزینی برای کلمات، کشف کرد‏. او مجموعه‌ای از چند‌-وزنی‌هایی که از یک کلمه مشتق می‌شوند، دنباله­ نحوی (syntactic trace) آن کلمه نامید. کارهای بعدی به تدریج طول چند‌-وزنی را افزایش دادند که طول چند‌-وزنی‌ها با تغییر بسامد واژه و افزایش اندازه مجموعه آزمایشی تغییر می‌کند. در سال ۱۹۹۰ میلادی، تغییراتی در چگونگی ایجاد چند‌-وزنی‌ها هنگام بازیابی اطلاعات رخ داد. این تغییرات شامل افزایش n و جابجایی چند‌-وزنی‌ها بود. از لحاظ کیفی، این تغییرات، دیدگاه جدیدی از چند‌-وزنی‌ها را با عنوان کلمه‌های شاخص‌گذاری منعکس کرد که از به کارگیری نمایش نادرستی از کلمات اجتناب می‏کرد. علاوه بر تاثیر چند‌-وزنی‌ها بر روی کلمه­های شاخص‌گذاری (کاهش مصرف حافظه)، اهمیت متمایز و ممتاز دیگر آن، شباهت‌یابی اسناد است (صحت بازیابی). کاربردهای چند‌-وزنی علاوه بر بازیابی اسناد، شناسایی زبان، تشخیص خطای املایی و برجسته‌سازی کلمات کلیدی است. همچنین بزرگ‌ترین کاربرد چند‌-وزنی‌ها، در بازیابی اطلاعات زبان‌های آسیایی است. این روش، واژه‌های شاخص را با استفاده از تبدیل متن، به صورت زیر تولید می‌کند‏:

  1. شناسایی کلمات مجزای متن
  2. تولید ریشه‌های کلمات با استفاده از حذف پسوندها
  3. حذف ریشه‌های کلمات متعلق به لیست توقف
  4. شکستن ریشه‌های کلمات باقی‌مانده به شکل چند‌-وزنی

چند­-وزنی­ها را می‍توان به دو شاخه تقسیم کرد:

۱) چند-وزنی بر اساس حرف

۲) چند-وزنی بر اساس کلمه

منبع:

https://developer.apple.com/library/content/documentation/UserExperience/Conceptual/SearchKitConcepts/searchKit_basics/searchKit_basics.html

م. دانش، “یک سامانه شاخص گذاری چند-وزنی توزیع شده برای بهبود بازیابی اطلاعات در زبان فارسی”، پایان­نامه کارشناسی ارشد، کتابخانه دانشگاه علم و صنعت، ۱۳۹۰

کانال تلگرام ما:

http://t.me/bigdata_channel

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *