بازیابی سند - قسمت دوم

اندیس گذاری

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

انتخاب روش اندیس گذاری به ساختار سیستم اطلاعاتی  بستگی دارد. برای مثال روشهای اندیس گذاری در یک پایگاه داده، یک موتور جست و جو یا یک فرهنگ لغت متفاوت است.

•  در یک پایگاه داده بین اهمیت ذخیره سازی و بازیابی موازنه بر قرار است و باید در عین افزایش سرعت برخی عملیات ها به کمک اندیس گذاری، اثرات سوء آن را در سایر اعمال در نظر داشت.
• در موتور جست و جو، سرعت جست و جو بسیار مهمتر است و عملیات جمع آوری اطلاعات و اندیس گذاری می تواند با سرعت کمتری صورت گیرد.
• در فرهنگ لغت با اطلاعات پابداری رو به رو هستیم که پس از ارائه تغییرات ناچیزی ( اگر نگوییم هیچ! ) خواهد داشت و می توانید به روش اندیس گذاری پیچیده تر و زمان برتری فکر کنیم.

ابتدا به بررسی اندیس گذاری در پایگاه های داده رابطه ای می پردازیم:

اندیس گذاری در پایگاه های داده رابطه ای

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

برای مثال :

به تصویر زیر نگاه کنید.

در ابتدا یک جدول حاوی هشت رکورد با فیلدهای شناسه، نام و نمره در اختیار داریم و می خواهیم آنها را اندیس گذاری کنیم. برای اندیس گذاری از این روش استفاده میکنیم:

از فیلد نام برای اندیس گذاری استفاده میکنیم. رکورد ها را به صورت الفبایی بر اساس فیلد نام مرتب میکنیم و هر سه تای آنها را در یک گروه قرار میدهیم. در هر گروه فیلد نام و شناسه ذخیره می شوند. سپس شماره هر گروه و مقدارآخرین فیلد نام آن گروه را در یک لیست ذخیره میکنیم.

حالا فرض کنیم به دنبال رکوردی می گردیم که فیلد نام در آن برابر Reza باشد. ابتدا به لیست گروها نگاه میکنیم و می بینیم که این رکورد باید در گروه دو باشد، چون Reza از نظر الفبایی از آخرین فیلد نام در گروه 1 بزرگتر است. پس به سراغ اعضای گروه دو می رویم و با جست و جو باینری ( به خاطر مرتب بودن عناصر امکان پذیر است ) رکورد مورد نظر خود را پیدا می کنیم و به کمک شناسه رکورد، رکورد مرتبط با آن در جدول مشخص میشود.

اگر از اندیس گزاری استفاده نمی کردیم باید هر هشت رکورد را بررسی میکردیم. می توانید فایده این عملیات را برای جدولی به چند میلیون رکورد تصور کنید!

اما همیشه یک اندیس کافی نیست.به دو دلیل نیاز به چند اندیس برای یک جدول وجود دارد:

1- مقادیر تکرار: اگر فیلد نام تکراری باشد، یعنی مثلا دوتا رکورد با فیلد نام Reza داشته باشیم. در این صورت اندیس دوم برای مقادیر تکراری استفاده میشود. مثلا فیلد ها بر اساس نام اندیس گذاری میشوند و برای نام های یکسان، از فیلد نمره برای اندیس گذاری آنها استفاده میشود.

2- پرس و جو و مرتب سازی تنها بر اساس فیلد نام بهبود یافته است. که باز هم با چند فیلد اندیس گذاری شده، این بهبود ها را در مورد آنها نیز شاهد خواهیم بود.

اما اندیس گذاری همیشه مفید نیست و اگر در انتخاب فیلد برای اندیس دقت نکنیم با نتیجه عکس روبه رو خواهیم شد. 

در قسمت بعد به این مطلب می پردازیم.

بازیابی سند - قسمت اول

مقدمه ای بر بازیابی سند

بازیابی سند ترجمه تحت الفظی برای Document retrieval به حساب می آید. پروسه ای که طی آن در قبال یک پرس و جو توسط کاربر، نتایجی استخراج شده از اسناد به کاربر ارائه می شود. تفاوت مهمی که این نوع پرس و جو با سایر پرس و جوها مانند پرس و جو از بانک ها اطلاعاتی دارد در این است که در این نوع منابع اطلاعاتی بی ساختار ( unstructured  ) هستند. این منابع اطلاعاتی که مجموعه ای از اسناد می باشند ممکن است مبتنی بر زبان های طبیعی باشند یا نه که این ویژگی می تواند در انتخاب روش استخراج نتایج تاثیر داشته باشد.

یافتن نتایج پرس و جو حاصل یک جست و جو است. این جست و جو می تواند با پیمایش تمام محتویات اسناد صورت گیرد. روشی که grep از آن استفاده می کند. اما روش های موثرتری هم وجود دارد. دراین روشها معمولا ابتدا به روشی اسناد اندیس گذاری ( indexing ) می شوند وسپس پرس و جو برروی اندیس ها اعمال میشود. روش های زیادی برای اندیس گزاری وجود دارد. اندیس گزاری را می توان به صورت خلاصه استخراج عناصر مهم هر سند تعریف کرد. به این ترتیب نه تنها سرعت جست و جو افزایش می یابد بلکه کیفیت نتایج را بهبود و منابع مورد نیاز سیستم را کاهش میدهد.

در شکل بالا، رنگ سبز عملیات پرس و جو و رنگ قرمز عملیات اندیس گذاری را نشان میدهد. این دو عملیات می تواند مسقل از هم باشند و موازی یکدیگر انجام شوند. همانطور که Google Desktop به موازات اندیس گذاری فایل های کاربر، امکان جست و جو درآنها را فراهم می کند، هر چند اندیس گذاری به پایان نرسیده باشد.

اگرچه همان طور که گفته شد، عملیات های پرس و جو و اندیس گذاری میتواند مستقلا انجام شود، ولی موثر کردن بازخورد نتایج جست و جو در اندیس گذاری می تواند در بهبود سیستم کمک کننده باشد.

به ازای هر پرس و جو نیز، دو عمل باید انجام شود: اول استخراج نتایح مرتبط و دوم ارزش دهی نتایج و ارائه اولویت بندی  شده ی آنها بر اساس همین ارزش گذاری به کاربر.

استراتژی بازیابی میتواند بر پایه یکی از اصول زیر بنا نهاده شود:

1- بر پایه ظاهر سند: که اسناد را با توجه به معنای نحوی بررسی میکند. اسنادی که به صورت یک موجودیت معنای خاصی ندارند را بر این اساس میتوان پردازش کرد. مثلا اسناد حاوی لیستی از نام ها، آدرسها، کلمات کلیدی و ... .

2- بر پایه ی محتوای سند: اسناد بر پایه معنا و ارتباط بین بخش های مختلفش بررسی میشود.اسنادی را که به زبان طبیعی هستند و اجزای تشکیل دهنده آنها ( کلمات ) در کنار هم، معنا دارند را بر این اساس پردازش میکنیم. به این وسیله علاوه بر هر کلمه، به معنایی که در ورای آنهاست، دست پیدا میکنیم. توانایی در استخراج این معناست که می تواند در برتری یک سیستم جست و جو را بر دیگری موثر باشد.