سرعت بخشیدن به جستجو با الگوریتم Boyer-Moore در C++17

[کامبیز اسدزاده 618]

با نگاهی به الگوی جستجو تحت الگوریتم Boyer-Moore در استاندارد جدید یعنی C++17 می‌توان به کنترل بیشتر و حتی سرعت بسیار بالاتری نسبت به کتابخانهٔ Boost رسید. با استاندارد ۱۷ در سی‌پلاس‌پلاس، اکنون می‌توانید از الگوریتم‌های پیشرفته‌تر و بهتری در عین حال سریعتری برای جستجو استفاده کنید. از این پس، شما می‌توانید کنترل بیشتر و همچنین افزایش کارآیی امیدوار کننده‌ای در بسیاری از موارد داشته باشید که به صورت پیشفرض در استاندارد ۱۷ ارائه شده‌است.

معرفی

روش‌های ساده‌تری برای یافتن الگو در یک رشته O (nm) جایی که n طول تمام رشته است و m طول الگو است وجود دارد. این روش‌ها به عنوان روش‌های دوم و بهتری می‌توان در نظر گرفته شوند.

در C++17 الگوریتم جستجو در استاندارد std::search به دو روش زیر به‌روز رسانی شده است:

• از این پس شما می‌توانید از قانون مجوز استفاده از نسخهٔ پیش‌فرض الگوریتم استفاده کنید، اما به صورت موازی عمل می‌کند.
• شما می‌توانید یک شیء جستجوگر برای مدیریت جستجو فراهم کنید.

بنابراین ما سه نوع جستجوگر خواهیم داشت:

• default_searcher
• boyer_moore_searcher
• boyer_moore_horspool_searcher

 

حالت پیش‌فرض از جستجو به صورت زیر خواهد بود:

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>

int main()
{
    std::string in = "Hello, World from new C++ 17";
    std::string needle = "C++";
    auto it = std::search(in.begin(), in.end(),
    std::default_searcher(needle.begin(), needle.end()));
    if(it != in.end())
      std::cout << "The string " << needle << " found at offset " << it - in.begin() << '\n';
    else
        std::cout << "The string " << needle << " not found\n";
}

پیش‌پردازش

هر دو الگوریتم Boyer Moore و Boyer Moore Horspool از برخی اطلاعات در رابطه با رشته الگو استفاده می‌کنند تا بتوانند مقایسه‌های بی‌نظیری را انجام دهند. به منظور هوشمندانه‌تر شدن هر یک از الگوریتم‌ها یک عمل پیش‌پردازشی را انجام می‌دهند که الگوی ورودی را تحلیل می‌کند. پیچیدگی پیش‌پردازش معمولاً به اندازهٔ الفبای رشته بستگی دارد.

در کتابخانهٔ Boost (بوست)

اگر شما با کتابخانهٔ بوست کار کرده اید، ممکن است شما با الگوریتم‌های جستجو آشنا باشید. در نسخهٔ ۱.۵۰ (در تاریخ ژوئن ۲۰۱۲ میلادی) مجموعهٔ جدیدی از الگوریتم‌ها به کتابخانه اضافه شده است.

در کتابخانه سه شیء جستجوگر وجود دارد:

• الگوریتم جستجوی Boyer-Moore
• الگوریتم جستجوی Boyer-Moore-Horspool
• الگوریتم جستجوی Knuth-Morris-Pratt

نحوهٔ استفاده از این روش‌ها در استاندارد ۱۷ چگونه است؟

در سی‌پلاس‌پلاس ۱۷ سه نوع سربار اضافی بر روی ویژگی‌های std::search اضافه شده است.

template<class ForwardIterator, class Searcher>
ForwardIterator search( ForwardIterator first, ForwardIterator last,
                        const Searcher& searcher );

هر جستجوگر معمولاً دو ورودی تکرار کننده را می‌گیرند. شروع و پایان الگو، و سپس یک پیشفرض باینری که معمولاً آن با عملگر برابر است. آن‌ها ممکن است از پارامتر‌های دیگر نیز استفاده کنند، برای مثال، یک تابع هَش (مخلوط) کننده.

در کل، شما می‌توانید آن را به صورت زیر استفاده کنید:

std::string testString = "Hello Super World";
std::string needle = "Super";
auto it = search(testString.begin(), testString.end(),
                    boyer_moore_searcher(needle.begin(), needle.end()));
if (it == testString.end())
    cout << "The string " << needle << " not found\n";

برخی از آزمون‌های پایه

برای آزمایش مخزنی ارائه شده است که در آن نمونه کُد آن آمده است. در این مثال نمونه‌هایی نوشته شده است که برخی از آن‌ها کارایی و سرعت بسیار خوبی را در الگوریتم‌های جدید با استفاده از MSVC نشان می‌دهد.

آزمایش‌ها چطور کار می‌کنند؟

• برنامه یک فایل را بارگذاری می‌کند، مانند کتابی که شامل متنی با ۵۰۰ کیلوبایت اندازه است.
• تمام محتوای فایل در یک رشتهٔ ورودی ذخیره می‌شود.
• یک الگو انتخاب شده است که N آخرین حرف از رشته ورودی است.
• برنامه از چندین الگوریتم استفاده می‌کند و بارها در جستجو هر یک از ITER ها را اجرا می‌کند.

برای مثال نسخهٔ std::string::find به صورت زیر آمده است:

RunAndMeasure("string::find", [&]() {
    for (size_t i = 0; i < ITERS; ++i)
    {
        std::size_t found = testString.find(needle);
        if (found == std::string::npos)
            std::cout << "The string " << needle << " not found\n";
    }
});

نسخهٔ boyer_moore_horspool به صورت زیر:

RunAndMeasure("boyer_moore_horspool_searcher", [&]() {
    for (size_t i = 0; i < ITERS; ++i)
    {
        auto it = std::search(testString.begin(), testString.end(),
            std::boyer_moore_horspool_searcher(
                needle.begin(), needle.end()));
        if (it == testString.end())
            std::cout << "The string " << needle << " not found\n";
    }
});

در اینحا نتیجه بر روی سخت افزار با پردازندهٔ i7 4720HQ و Win 10 همراه با MSVC 2017 15.8 ریلیز ۶۴ بیت می‌باشد.

الگو از ۱۰۰۰۰ حرف انتهای متن ورودی تشکیل شده است:

.\searchers.exe ..\..\SampleBooks\book-test.txt 1000 10000
string length: 547412
test iterations: 1000
pattern length: 10000
string::find: 693.449 ms
default searcher: 1102.25 ms
boyer_moore_searcher: 133.558 ms
boyer_moore_horspool_searcher: 37.0234 ms

الگو در اینجا اکنون ۱۰۰ حرف آخر از متن ورودی است:

.\searchers.exe ..\..\SampleBooks\book-test.txt 1000 200
string length: 547412
test iterations: 1000
pattern length: 200
string::find: 158.612 ms
default searcher: 467.518 ms
boyer_moore_searcher: 58.8752 ms
boyer_moore_horspool_searcher: 56.7017 ms

البته توجه داشته باشید که، نتایج نمونه نیاز به تحقیق بیشتری دارند. برای مثال در الگو‌های کوتاه، استفاده از روش string::find معمولاً سریعتر است. بنابراین، الگوریتم Horspool سریعتر از الگوریتم boyer_moore در این مورد بوده است.

واقعیت مهم در مورد std::search این است که آن یک الگوریتم عمومی است! بنابراین شما می‌توانید آن را فقط برای رشته‌ها استفاده کنید.

در اینجا مثالی آورده شده است که برای جستجوی یک الگو از شماره‌های موجود در یک بردار از عدد‌های صحیح است.

std::vector<int> testVector(1000000);
std::iota(testVector.begin(), testVector.end(), 0);
std::vector vecNeedle(testVector.end() - 1000, testVector.end());

auto it = std::search(testVector.begin(), testVector.end(),
        std::boyer_moore_horspool_searcher(
                vecNeedle.begin(), vecNeedle.end()));
if (it == testVector.end())
        std::cout << "The pattern " << needle << " not found\n";

خلاصهٔ نتیجه

در این مقاله به صورت مختصر در رابطه با قابلیت‌های جدیدی را که در سی‌پلاس‌پلاس ۱۷ دریافت کرده‌ایم اشاره شده است. مهم این است که بدانید الگوریتم‌های جدید همیشه سریعتر از std::string::find (برای رشته‌ها) نیستند.

ویرایش شده در مهر 99 توسط کامبیز اسدزاده
به‌روز رسانی