مقدمه:
در این مقاله یک تکنیک جدید برای فشرده سازی posting list معرفی می‌شود به طوری که نرخ compression آن تقریبا هم اندازه‌ی روش های قبل است ولی سرعت decoding آن بسیار بیشتر است؛ که بالا بودن سرعت decoding موجب افزایش سرعت query processing می‌شود. ایده‌ی این مقاله استفاده از توزیع آی دی داکیومنت‌ها برای فشرده سازی posting listها می‌باشد.
برای کاهش میزان حافظه برای نگه داری posting listها آنها را به ترتیب شماره‌ی داکیومنت‌ها مرتب کنیم و اختلاف بین مقدار‌های پشت سر هم را بدست می‌آوریم. برای مثال در لیست زیر داکیومنت‌ها مرتب شده اند:
<4, 10, 11, 12, 15, 20, 21, 28, 29, 42, 62, 63, 75, 95>
لیست بالا را به صورت زیر نگه‌داری می‌کنیم و به آن لیستی از d-gapها (gap بین documentها) می‌گوییم:
<4, 6, 1, 1, 3, 5, 1, 7, 1, 13, 20, 1, 12, 20>
با داشتن لیست‌های این چنینی می‌خواهیم 3 روش برای فشرده‌سازی آنها ارائه دهیم که در این روشها ما داده ها را به صورت کلمه به کلمه، که منظور از هر کلمه، ۳۲ بیت می‌باشد، درنظر می‌گیریم. نکته ای که در هر سه روش مشترک می‌باشد، این است که هر کلمه(یا هر ۳۲ بیت) شامل تعداد متغیری از d-gapها می باشد ولی هر d-gap موجود در یک کلمه دارای تعداد بیت برابری با سایر d-gapهای موجود در آن کلمه می‌باشد؛ این هم انداز بودن موجب افزایش سرعت decoding می‌شود. هر کلمه به دو بخش بیت‌هایی برای نگه داری داده و بیت‌هایی برای نگه داری selector(یا انتخابگر) تقسیم می‌شود.
در این روشها جدولی به نام جدول انتخاب(شکل۱) وجود دارد که با استفاده از آن، استراتژی(روش) فشرده‌سازی هر کلمه را، بر اساس اینکه بخش داده‌ی آن به چند بخش برابر تقسیم شود، انتخاب می‌کنیم.
فیلد انتخابگر هر کلمه تعیین می‌کند که از کدام سطر جدول برای فشرده‌سازی بخش داده آن کلمه، استفاده می‌کنیم. فیلد انتخابگر هر کلمه را بر اساس بزرگترین d-gap ای که در هر لیست ما وجود دارد، انتخاب می‌کنیم؛ به این صورت که از بالاترین سطر جدول شروع به پیمایش جدول می‌کنیم و بالاترین سطر مناسب را انتخاب می‌کنیم؛ چون در جدول به ترتیب از بالا به پایین بیشترین نرخ فشرده‌سازی را داریم.(یعنی سطر اول بیشترین نرخ فشرده‌سازی را ایجاد می‌کند.)
Anh و Moffat سه روش را بر اساس این استراتژی ارائه کرده‌اند، که تفاوت اصلی آنها در این است که بیت‌های داخل یک کلمه را چگونه بخش بندی می‌کنیم.
روش اول: simple-9
این روش از ۲۸ بیت برای نگه‌داری بخش داده و از ۴ بیت برای نگه‌داری بخش انتخابگر استفاده می‌کند. از آنجایی که ۹روش برای تقسیم ۲۸ بیت به صورت مساوی وجود دارد، جدول انتخاب simple-9 (شکل۱) دارای ۹ سطر می‌باشد. در هر سطر جدول یک مقدار از a تا i که نمایانگر ۴ بیت selector است، تعداد d-gapهای کدشده، تعداد بیت‌هایی که برای کدکردن هر d-gap استفاده شده و تعداد بیت‌های استفاده نشده‌ی هر کلمه زمانی که از سطر مورد نظر برای کد کردن یک کلمه استفاده می‌کنیم، نشان داده شده است.
به عنوان مثال لیست d-gapهای زیر را در نظر بگیرید، می خواهیم با استفاده از روش simple-9 این لیست را فشرده کنیم:
<4, 6, 1, 1, 3, 5, 1, 7, 1, 13, 20, 1, 12, 20 >
چون d-gap صفر نداریم، بنابراین همه‌ی اعداد را منهای یک می‌کنیم، تا در فشرده‌سازی عملکرد بهتری داشته باشیم:
<۳, 5, 0, 0, 2, 4, 0, 6, 0, 12, 19, 0, 11, 19 >
برای فشرده‌سازی از سطر اول شروع می‌کنیم و هر سطر را امتحان می‌کنیم:
از سطر یک نمی‌توانیم استفاده کنیم، چون در ۲۸ d-gap اول، عددی وجود دارد که برای کد کردن آن به بیش از یک بیت نیاز داریم(مثلا ۴). سطر دوم مناسب نمی‌باشد، چون در ۱۴ d-gap اول، عددی وجود دارد که برای کد کردن آن به بیش از ۲ بیت احتیاج داریم(مثلا ۶). سطر سوم مناسب است چون در ۹ d-gap اول، عددی وجود ندارد که برای کد کردن آن به بیش از سه بیت نیاز داشته باشیم؛ بنابراین این خط را انتخاب می‌کنیم و اولین کلمه‌ی ۳۲بیتی‌مان را به صورت زیر کد می‌کنیم:
c, 011, 101, 000, 000, 010, 100, 000, 110, 000, .,
که در آن C در ۴ بیت کد شده است(۰۰۱۰). کاما فقط برای اینکه به صورت چشمی اعداد را بتوانیم تشخیص دهیم، استفاده شده است وگرنه در خروجی دیده نمی‌شود. نقطه ی اخر نشاندهنده‌ی یک بیت از 28 بیت است که استفاده نشده است.
با این کلمه اعداد ۳ تا قبل از عدد ۱۲ را کد کردیم، حال برای کد کردن بقیه‌ی اعداد موجود در لیستمان به همین منوال عمل می‌کنیم.
e, 01100, 10011, 00000, 01011, 10011, …,
با تمام شدن d-gapها فشرده سازی به اتمام می رسد. در مجموع، دوکلمه ی 32 بیتی قادر به کد کردن 14 تا d-gap موجود در این posting list هستند.
اولین کلمه‌ی ۳۲ بیتی ما که از ۳۱ بیت آن استفاده شده است و یک بیت آن بلا استفاده می‌باشد:
0010011101000000010100000110000
دومین کلمه‌ی ۳۲ بیتی ما که از ۲۹ بیت آن استفاده شده است و ۳ بیت آن بلا استفاده می‌باشد:
01000110010011000000101110011
روش دوم: Relative-10
مشابه روش simple-9 می‌باشد با این تفاوت که فقط از دو بیت برای بخش انتخابگر استفاده می‌کند و از ۳۰ بیت باقی‌مانده برای بخش داده استفاده می‌کند. تفاوت کلیدی در این می‌باشد که با در نظر گرفتن تنها ۲ بیت برای انتخابگر، هر کلمه فقط می‌تواند ۴ سطر از ۱۰ سطر موجود در جدول(جدول این روش دارای ۱۰ سطر می‌باشد) را انتخاب کند، بنابراین در این روش انتخابگر به صورت نسبی نسبت به انتخابگر کلمه‌ی قبلی انتخاب می‌شود. این الگوریتم اندکی بهتر از روش simple-9 عمل می‌کند.
روش سوم: Carryover-12
این روش نوعی از روشRelative-10 می‌باشد که در آن فضای هدر رفته‌ی ناشی از بخش‌بندی با استفاده از بیت‌های استفاده نشده به عنوان انتخابگر کلمه‌ی بعدی احیا شده است، که اجازه می‌دهد هر کلمه از تمام بیت‌هایش برای ذخیره‌سازی داده استفاده کند. در این روش در هر کلمه بخش داده یا ۳۲ بیت می‌باشد یا ۳۰ بیت. این روش بیشترین نرخ فشرده سازی را در بین سه روش معرفی شده ایجاد می‌کند ولی نسبت به دو روش قبلی پیچیده‌تر می‌باشد در نتیجه، به زمان بیشتری برای decoding نیاز دارد.
لینک مقاله:
https://link.springer.com/article/10.1023/B:INRT.0000048490.99518.5c
