اگه خیلی با دنیای کامپیوترها سر و کار داشته باشی، احتمالاً میدونی پیدا کردن یه تیکه خاص از متن تو یه عالمه داده، واقعاً میتونه قلق داشته باشه. یعنی مثلاً اگه بخوای تو متنهای عظیم مثل دیتابیس متون خبری یا حتی تو ژنوم انسان دنبال یه الگو بگردی، روشهای معمولی دیگه جوابگو نیستن.
الان چند تا روش سنتی داریم برای جستجوی متن؛ مثلاً Naive Search که خیلی صاف و ساده دونهبهدونه کل متن رو چک میکنه (خیلی کند و بیبازده واسه حجم زیاد)، یا KMP که یکم باهوشتره و الگوها رو سریعتر پیدا میکنه، یا Boyer-Moore که معمولاً تو کتابای الگوریتم حسابی بهش افتخار میکنن! ولی اینا هم وقتی با دادههای امروزی و حجیم طرف میشن حسابی کم میارن.
این تحقیق جدید یه نگاه خیلی جدی انداخته روی این قضیه. اول اومده همین الگوریتمهای کلاسیک رو روی دیتاستهایی مثل مجموعه متون Reuters (یعنی آرشیوی از خبرها که برای آزمایشات NLP استفاده میشه) و حتی دنبالههای ژنومی انسان (ژنوم یعنی کل اطلاعات ژنتیکی بدن یک موجود زنده) امتحان کرده. بعدش سراغ روشی به اسم Suffix Tree رفته؛ این خیلی جالبه چون کلی شاخه و برگ داره برای پیدا کردن همه جور زیررشته یا “الگو” داخل متن. اما ساخت و نگهداری Suffix Treeها خودش داستانیه و میتونه منابع زیادی بخوره.
حالا نکته باحال کلی تحقیق اینجاست: اونا تونستن یه بهینهسازی انجام بدن با ترکیب الگوریتم اوکونن (Ukkonen’s Algorithm یعنی یه روش هوشمندانه برای ساخت سریعتر Suffix Treeها بهجای روشهای کندتر قبلی) و یه روش جستجوی تازه که خودشون طراحی کردن. نتیجه اینه که هم تو زمان و هم تو حافظه (فضا) کاملاً خطی (linear) عمل میکنه. یعنی حجم داده هرچقدر هم زیاد باشه، سرعت و مصرف منابعش از الگوریتمهای سنتی خیلی بهتره و خطی با اندازه رشد میکنه، نه انفجاری!
جالب اینجاست که تو تستهای عملی، همون طور که تئوری پیشبینی کرده بود، این روش تازه واقعاً بهتر از Naive، KMP و Boyer-Moore جواب داده. مخصوصاً وقتی تو ژنوم انسان دنبال یک الگو میگشتن، تونستن با همین تکنیک Suffix Tree بهینهشده، دقت صد درصد بگیرن! یعنی هیچ مورد اشتباهی نبوده.
در آخر نتیجه مهم این مقاله، فقط اثبات یک نظریه آکادمیک نبوده؛ بلکه نشون داده واسه کارهای خیلی واقعی مثل تحلیل زبان طبیعی (NLP یعنی کار با زبانهای انسانی با کمک کامپیوتر) یا شناسایی الگو در بیوانفورماتیک (بیوانفورماتیک یعنی تحلیل دادههای زیستی مثل ژنوم) هم این روش جدید خیلی پربازدهست و منابع کمی مصرف میکنه.
اگه بخوام خلاصه بگم: اگه دنبال یه راه سریع، دقیق و کمهزینه برای پیدا کردن الگو تو دادههای عظیم هستی، این ترکیب الگوریتم اوکونن با روش نوآورانه جدیدشون، حالا حالاها جواب میده و از کلاسیکها خیلی جلوتره!
منبع: +
