‏زیر پوست جست‌وجوی فازی در SereneDB

تیم SereneDB مقالهٔ شش سال پیشش دربارهٔ جست‌وجوی فازی رو دوباره نوشته، این بار بر اساس جایی که کد امروز توش زندگی می‌کنه. موتور جست‌وجو IResearch حالا هستهٔ سرچ SereneDB هست و به‌جای یه زبان کوئری اختصاصی، از SQL بهش می‌رسی. به گفتهٔ نویسنده تئوری پشتش یه ذره هم کهنه نشده. خود fuzzy search یه چتره برای خانواده‌ای از الگوریتم‌های تطبیق تقریبی — یعنی روش‌هایی که می‌سنجن یه کلمه چقدر به کلمهٔ دیگه نزدیکه، تا موتور تصمیم بگیره چی رو نشون بده و با چه ترتیبی.

معیار اول فاصلهٔ Levenshtein هست — یعنی کمترین تعداد درج، حذف یا جایگزینی حرف که یه کلمه رو به کلمهٔ دیگه تبدیل می‌کنه. الگوریتم کلاسیک Wagner–Fischer اینو با برنامه‌ریزی پویا حساب می‌کنه که برای مقایسهٔ دو کلمه عالیه، ولی وقتی دیکشنری صدها هزار واژه داره باید روی تک‌تک اون‌ها اجراش کنی و همین‌جا کم میاره.

ترفند اصلی مال Schulz و Mihov (۲۰۰۲) هست: برای هر کلمهٔ ورودی یه اتوماتون قطعی می‌سازن که هر رشتهٔ با فاصلهٔ حداکثر n رو قبول می‌کنه، و ساختش خطی نسبت به طول کلمه‌ست. بعد اتوماتون رو با trie دیکشنری تقاطع می‌دن و هر زیردرختی که دیگه نمی‌تونه به جواب برسه همون‌جا هرس می‌شه؛ مثلاً موقع جست‌وجوی kargo با فاصلهٔ ۱، کل شاخهٔ av- اصلاً باز نمی‌شه. سه قدم — locality، subsumption و parametrization — پیچیدگی رو از نمایی به خطی رسوندن، و برای فاصلهٔ ۱ فقط پنج «حالت پارامتری» باقی می‌مونه.

نویسنده هزینه‌ها رو هم پنهون نمی‌کنه: جدول انتقال با n منفجر می‌شه — ۴۰ انتقال برای فاصلهٔ ۱، ۹۶۰ برای ۲، ۲۵٬۰۸۸ برای ۳ و ۶۹۲٬۷۳۶ برای ۴. برای همین SereneDB سقف فاصله رو ۴ برای Levenshtein و ۳ برای Damerau–Levenshtein گذاشته، یعنی نسخه‌ای که جابه‌جایی دو حرف کنار هم رو هم یک ویرایش حساب می‌کنه. یه ترفند قشنگ هم هست: با دو دیکشنری، یکی مستقیم و یکی معکوس (FB-trie)، می‌شه جواب فاصلهٔ n+۱ رو با دوتا اتوماتون فاصلهٔ n داد.

توی SereneDB همهٔ اینا پشت تابع ts_levenshtein جمع شده و کوئری فازی فقط عملگر @@ در برابر اونه. اگه آرگومان فاصله رو ننویسی حالت auto فعال می‌شه و فاصله از روی طول کوئری انتخاب می‌شه: ۰ تا دو کاراکتر، ۱ برای سه تا پنج و ۲ از شش به بالا — همون چیزی که پشت یه سرچ‌باکس لازم داری. جابه‌جایی حروف هم پیش‌فرض روشنه، پس act هم جزو نتایج cat میاد:

SELECT id, name FROM idx_products
WHERE name @@ ts_levenshtein('cat', 1)
ORDER BY id;
--  1 cat | 2 bat | 3 car | 5 cats | 6 act

نکات کلیدی:

• IResearch حالا هستهٔ جست‌وجوی SereneDB هست و از راه SQL بهش دسترسی داری، نه یه زبان کوئری جدا.
• روش Schulz–Mihov اتوماتون فاصلهٔ ویرایشی رو در زمان خطی نسبت به طول کلمه می‌سازه.
• فاصلهٔ ۱ فقط ۵ حالت پارامتری و ۴۰ انتقال لازم داره؛ فاصلهٔ ۴ به ۶۹۲٬۷۳۶ انتقال می‌رسه.
• سقف فاصله در SereneDB: ۴ برای Levenshtein و ۳ برای Damerau–Levenshtein.
• امتیاز هر ترم پذیرفته‌شده از رابطهٔ ۱ منهای d تقسیم بر طول کوتاه‌تر درمیاد، پس تطبیق دقیق بالاتر می‌شینه.
• حالت auto فاصله رو از طول کوئری برمی‌داره: ۰ تا دو کاراکتر، ۱ برای سه تا پنج، ۲ از شش به بالا.