پیاده سازی Boolean OR Search در meilisearch

Summarize this content to 400 words in Persian Lang
Meilisearch یک موتور جستجوی رعد و برق سریع است که در rust پیاده سازی شده است، راه اندازی مستقیم و API های آسان آن را در بین توسعه دهندگان بسیار جذاب می کند. علاوه بر این، پشتیبانی شخص اول توسط لاراول با پکیج Sout به آن کمک می کند تا در سراسر جامعه لاراول گسترش یابد. در این مقاله به شما نشان خواهم داد که چگونه OR search در meilisearch پیاده سازی می شود.

بیان مشکل:

ما می خواهیم یک جستجوی متن کامل در میان ویژگی های انتخاب شده با شرایط OR انجام دهیم، به عنوان مثال: جستجوی “PHP” یا “Engineer” باید تمام اسنادی را که حاوی “PHP” یا “Engineer” یا هر دو “PHP” هستند را برگرداند. & “مهندس”. این یک ایده اساسی از شرط OR است که ما در جبر بولی مطالعه کردیم. با این حال، هیچ راه حل مستقیمی برای این مشکل در وجود ندارد [Meilisearch][1]. نزدیک‌ترین چیزی که می‌توانید به آن برسید استفاده از «آخرین» یا «فرکانس» برای گزینه MatchingStrategy است، اما دقیقاً OR نیست، در عوض، این الگوریتم‌ها یک کلمه (آخرین یا بیشتر) را در یک زمان حذف می‌کنند و در صورت وجود، جستجو را انجام می‌دهند. نتایج کافی نیست

راه حل

ایده اصلی برای حل این مشکل استفاده از فرمول AUB فرمول SET ریاضی است، فرمول اتحادیه را می توان به صورت زیر نوشت:

n(A∪B)=n(A)+n(B)−n(A∩B)

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

کجا،

n(A U B) نشان دهنده A OR B است، به این معنی که باید تمام اسناد حاوی عبارات A یا B، یا هر دو A و B را برگرداند.

n(A) تعداد اسنادی است که شامل عبارت A است،

n(B) تعداد اسنادی است که شامل عبارت B است

n(A∩B) تعداد اسنادی است که هر دو عبارت A و B را در بر می گیرد

با استفاده از فرمول بالا، جستجوی عبارت “PHP” یا “Engineer” به نظر می رسد،

n(PHP ∪ Engineer) = n(PHP) + n(Engineer) – n(PHP ∩ Engineer)

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

به طور مشابه، فرمول برای سه عبارت جستجو به نظر می رسد،

n(A∪B∪C)=n(A)+n(B)+n(C)−n(A∩B)−n(B∩C)−n(A∩C)+n(A∩B∩C)

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

از آنجایی که n(A) نه تنها نشان دهنده اصلی بودن اسناد حاوی عبارات A است، بلکه اسنادی را که شامل A و مجموعه های دیگر هستند نیز نشان می دهد. برای سادگی محاسبه، مایلیم از فرمولی استفاده کنیم که به طور صریح فقط با A یا فقط آن قسمت سروکار دارد. به عنوان مثال،

n(A∩B) = n0(A∩B) + n(A∩B∩C)

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

اینجا، n0(A∩B) مجموعه ای است که فقط شامل تقاطع بین A و B است.

که در ادامه می توان به صورت زیر نوشت

n(A∪B∪C)=n0(A)+n0(B)+n0(C)+n0(A∩B)+n0(B∩C)+n0(A∩C)+n(A∩B∩C)

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

کجا،

n0(A) نشان دهنده فقط A است، به استثنای B و C به طور کامل. در جستجو، n0(PHP) به اسنادی اطلاق می شود که شامل PHP هستند اما هرگونه ذکر مهندس یا مدیر را حذف نمی کنند.در Meilisearch، حذف را می توان با استفاده از نشان داد – علامت، مانند ‘PHP’ -‘Engineer’ -‘Manager’.

بنابراین، جستجوی ما می شود:

n0(A) = PHP -Engineer -Manager
n0(B) = Engineer -PHP -Manager
n0(C) = Manager -Engineer -PHP
n0(A∩B) = PHP Engineer -Manager
n0(B∩C) = Engineer Manager -PHP
n0(A∩C) = PHP Manager -Engineer
n(A∩B∩C) = PHP Engineer Manager

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

این بدان معناست که ما باید 7 فراخوان API برای 3 عبارت جستجو انجام دهیم. با افزایش تعداد عبارات جستجو، بر اساس فرمول، تعداد تماس‌های API مورد نیاز نیز افزایش می‌یابد 2^n−1. بنابراین، تعداد تماس های API مورد نیاز به شرح زیر است:

تعداد عبارات جستجو (n)
تعداد تماس های API

1
1

2
3

3
7

4
15

5
31

برای جستجو با استفاده از شرایط OR با 5 عبارت، باید 31 تماس API برقرار کنیم. از آنجایی که هیچ جایگزینی برای اجرای مستقیم این ویژگی وجود ندارد، می‌توانیم تعداد عبارات جستجو را به 4 یا 5 محدود کنیم. با این حال، یک ویژگی به نام جستجوی چندگانه وجود دارد که به ما امکان می‌دهد چندین جستجو را به طور همزمان انجام دهیم و با اجرای همه تماس‌های API در آن، عملکرد را افزایش دهیم. یک بار

ما می توانیم این اصطلاحات را با استفاده از یک رویکرد بازگشتی ایجاد کنیم:

function generateTerm(array $ans, $data, array $current)
{
$last = end($current);

if ($last == count($data) – 1) {
return $ans;
}

$nextCurrent = $current;
$nextCurrent[] = $last + 1;

array_pop($current);
$current[] = $last + 1;

$ans[formatTerm($data, $nextCurrent)] = count($nextCurrent);
$ans[formatTerm($data, $current)] = count($current);

$ans = generateTerm($ans, $data, $nextCurrent);
$ans = generateTerm($ans, $data, $current);

return $ans;
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

درک الگوریتم بالا ممکن است کمی مشکل باشد. اگر توضیح مفصلی خواستید به من بگویید. این روش را می توان به صورت زیر نامید:

$data = [‘php’, ‘engineer’, ‘manager’];
$ans[formatTerm($data, [0])] = 1;

$ans = generateTerm($ans, $data, [0]);
arsort($ans);

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

را formatTerm تابع برای قالب بندی عبارات جستجو به طور خاص برای Meilisearch استفاده می شود. خروجی الگوریتم بالا بسته به داده های ورودی چیزی شبیه به این خواهد بود:

ما تمام اجزای جستجوی لازم برای انجام عملیات OR را آماده کرده ایم. در این ساختار، کلید نشان دهنده عبارات جستجو شده است، در حالی که مقدار نشان دهنده امتیاز است. این امتیاز تعداد عبارات منطبق در هر سند را نشان می دهد، با این ایده که اسنادی با تعداد عبارات تطبیق بیشتری در ابتدا در نتایج جستجو ظاهر می شوند.

برای شمارش کل اسناد برای هر عبارت جستجو

$searches = [];
foreach ($terms as $term => $index) {
$searches[] = (new SearchQuery())
->setQuery($term)
->setAttributesToRetrieve([‘id’])
->setIndexUid(‘jobins_data’)
->setPage(1)
->setHitsPerPage(1)
->setMatchingStrategy(‘all’);
}

$client = new \Meilisearch\Client(‘http://localhost:7700’, ‘masterKey’);
$response = $client->multiSearch($searches);

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

برای یافتن اصطلاحات چه هستند، باید برای یک صفحه خاص پرس و جو کنیم

$page = 1;
$per_page = 10;
$offset = ($page – 1) * $per_page;

$possibleSearchTerms = [];
$count = 0;
$termKeys = array_keys($terms);
$next = $offset + $per_page;
$hasOffset = false;
while (count($termKeys) > 0) {
$term = array_pop($termKeys);
$neededForOffset = $offset – $count;
$neededForLimit = $offset + $per_page – $count;
$count = $count + $metadata[$term];

if ($count > $offset && $count $offset + $per_page) {
$possibleSearchTerms[] = [
‘q’ => $term,
‘offset’ => $hasOffset ? 0 : $neededForOffset,
];
$hasOffset = true;
}

if ($count >= $offset + $per_page) {
$possibleSearchTerms[] = [
‘offset’ => $hasOffset ? 0 : $neededForOffset,
‘q’ => $term,
‘limit’ => min($neededForLimit, $per_page),
];
break;
}
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

را $possibleSearchTerms عبارات جستجوی احتمالی را برای جستجوی نتایج ارائه می دهد. در نهایت انجام جستجوی عبارات جستجوی احتمالی نتایج لازم را می دهد.

$searches = [];
foreach ($possibleSearchTerms as $term) {
$searches[] = (new SearchQuery())
->setQuery($term[‘q’])
->setAttributesToRetrieve([‘id’])
->setIndexUid(‘jobins_data’)
->setOffset($term[‘offset’] ?? 0)
->setLimit($term[‘limit’] ?? $per_page)
->setSort([‘id:desc’])
->setMatchingStrategy(‘all’);
}

$response = $client->multiSearch($searches);
$results[‘hits’] = collect($response[‘results’])->pluck(‘hits’)->flatten(1);

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

مثال کامل در tinker در زیر آورده شده است،

const BASE_PATH = ‘/Users/ellite/code/office/api.jobins.test’;

require_once BASE_PATH.’/vendor/autoload.php’;
use Illuminate\Foundation\Console\Kernel;
use Meilisearch\Contracts\SearchQuery;

$app = require BASE_PATH.’/bootstrap/app.php’;
$app->make(Kernel::class)->bootstrap();

/** Data preparation */
config()->set(‘scout.queue’, false);
config()->set(‘scout.after_commit’, false);

class Post extends \Illuminate\Database\Eloquent\Model
{
use \Laravel\Scout\Searchable;

protected $table = ‘posts’;

protected $fillable = [
‘title’,
‘body’,
];

public function searchableAs(): string
{
return ‘posts’;
}

public function toSearchableArray()
{
return $this->toArray();
}
}

config()->set(‘scout.meilisearch.index-settings’, [
Post::class => [

],
]);

\Illuminate\Support\Facades\Artisan::call(‘scout:sync-index-settings’);

\Illuminate\Support\Facades\Schema::dropIfExists(‘posts’);
\Illuminate\Support\Facades\Schema::create(‘posts’, function (\Illuminate\Database\Schema\Blueprint $table) {
$table->id();
$table->string(‘title’);
$table->text(‘body’)->nullable();
$table->timestamps();
});

$data = [
[‘title’ => ‘PHP’],
[‘title’ => ‘Engineer’],
[‘title’ => ‘Manager’],
[‘title’ => ‘PHP Engineer’],
[‘title’ => ‘PHP Manager’],
[‘title’ => ‘Engineer Manager’],
[‘title’ => ‘PHP Engineer Manager’],

[‘title’ => ‘Engineering’],
];

foreach ($data as $row) {
$post = Post::query()->create($row);
}

/** End of Data Preparation*/

function formatTerm($data, array $current): string
{
$data = array_map(fn($item) => “‘$item'”, $data);
$current = array_map(fn($item) => $data[$item], $current);

$exclude = array_diff($data, $current);

$current = implode(‘ ‘, $current);
$exclude = implode(‘ -‘, $exclude);

return trim(implode(‘ -‘, [$current, $exclude]), ‘ -‘);
}

function generateTerm(array $ans, $data, array $current)
{
$last = end($current);

if ($last == count($data) – 1) {
return $ans;
}

$nextCurrent = $current;
$nextCurrent[] = $last + 1;

array_pop($current);
$current[] = $last + 1;

$ans[formatTerm($data, $nextCurrent)] = count($nextCurrent);
$ans[formatTerm($data, $current)] = count($current);

$ans = generateTerm($ans, $data, $nextCurrent);
$ans = generateTerm($ans, $data, $current);

return $ans;
}

$data = [‘PHP’, ‘Engineer’, ‘manager’];

$ans[formatTerm($data, [0])] = 1;

$terms = generateTerm($ans, $data, [0]);
arsort($terms);

$searches = [];
foreach ($terms as $term => $index) {
$searches[] = (new SearchQuery())
->setQuery($term)
->setAttributesToRetrieve([‘id’])
->setIndexUid(‘posts’)
->setPage(1)
->setHitsPerPage(1)
->setMatchingStrategy(‘all’);
}

$client = new \Meilisearch\Client(‘http://localhost:7700’, ‘masterKey’);
$response = $client->multiSearch($searches);
$metadata = collect($response[‘results’])->pluck(‘totalHits’, ‘query’);

$page = 1;
$per_page = 10;
$offset = ($page – 1) * $per_page;

$count = 0;
$possibleSearchTerms = [];
$termKeys = array_keys($terms);
$next = $offset + $per_page;
$hasOffset = false;
while (count($termKeys) > 0) {
$term = array_pop($termKeys);
$neededForOffset = $offset – $count;
$neededForLimit = $offset + $per_page – $count;
$count = $count + $metadata[$term];

if ($count > $offset && $count $offset + $per_page) {
$possibleSearchTerms[] = [
‘q’ => $term,
‘offset’ => $hasOffset ? 0 : $neededForOffset,
];
$hasOffset = true;
}

if ($count >= $offset + $per_page) {
$possibleSearchTerms[] = [
‘offset’ => $hasOffset ? 0 : $neededForOffset,
‘q’ => $term,
‘limit’ => min($neededForLimit, $per_page),
];
break;
}
}

$searches = [];
foreach ($possibleSearchTerms as $term) {
$searches[] = (new SearchQuery())
->setQuery($term[‘q’])
->setAttributesToRetrieve([‘id’])
->setIndexUid(‘jobins_data’)
->setOffset($term[‘offset’] ?? 0)
->setLimit($term[‘limit’] ?? $per_page)
->setSort([‘id:desc’])
->setMatchingStrategy(‘all’);
}

$response = $client->multiSearch($searches);
$results[‘hits’] = collect($response[‘results’])->pluck(‘hits’)->flatten(1);

dd($results[‘hits’]);

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

نتیجه گیری

در نتیجه، اجرای جستجوی OR در Meilisearch به دلیل عدم وجود یک عملیات OR بومی، به یک راه حل استراتژیک نیاز دارد. با استفاده از اصول تئوری مجموعه‌ها، می‌توانیم راه‌حلی بسازیم که شامل انجام پرس و جوهای جستجوی متعدد و ترکیب نتایج است. این رویکرد، در حالی که از نظر محاسباتی با افزایش تصاعدی تعداد فراخوان‌های API با تعداد عبارات جستجو، فشرده می‌شود، تضمین می‌کند که اسنادی را که با هر ترکیبی از عبارت‌های مشخص شده مطابقت دارند، به‌طور دقیق بازیابی کنیم. استفاده از قابلیت جستجوی چندگانه در Meilisearch به کاهش برخی نگرانی‌های مربوط به عملکرد کمک می‌کند و امکان اجرای همزمان کوئری‌ها را فراهم می‌کند. این روش یک راه حل عملی برای سناریوهای جستجوی پیچیده که در آن شرایط OR ضروری هستند، ارائه می دهد.

مراجع

n(A∪B)=n(A)+n(B)−n(A∩B)

n(PHP ∪ Engineer) = n(PHP) + n(Engineer) - n(PHP ∩ Engineer)

n(A∪B∪C)=n(A)+n(B)+n(C)−n(A∩B)−n(B∩C)−n(A∩C)+n(A∩B∩C)

n(A∩B) = n0(A∩B) + n(A∩B∩C)  

n(A∪B∪C)=n0(A)+n0(B)+n0(C)+n0(A∩B)+n0(B∩C)+n0(A∩C)+n(A∩B∩C)

n0(A) = PHP -Engineer -Manager
n0(B) = Engineer -PHP -Manager
n0(C) = Manager -Engineer -PHP
n0(A∩B) = PHP Engineer -Manager
n0(B∩C) = Engineer Manager -PHP
n0(A∩C) = PHP Manager -Engineer
n(A∩B∩C) = PHP Engineer Manager

function generateTerm(array $ans, $data, array $current)
{
    $last = end($current);

    if ($last == count($data) - 1) {
        return $ans;
    }

    $nextCurrent   = $current;
    $nextCurrent[] = $last + 1;

    array_pop($current);
    $current[] = $last + 1;

    $ans[formatTerm($data, $nextCurrent)] = count($nextCurrent);
    $ans[formatTerm($data, $current)]     = count($current);

    $ans = generateTerm($ans, $data, $nextCurrent);
    $ans = generateTerm($ans, $data, $current);

    return $ans;
}

$data = ['php', 'engineer', 'manager'];
$ans[formatTerm($data, [0])] = 1;

$ans = generateTerm($ans, $data, [0]);
arsort($ans);

$searches = [];
foreach ($terms as $term => $index) {
    $searches[] = (new SearchQuery())
        ->setQuery($term)
        ->setAttributesToRetrieve(['id'])
        ->setIndexUid('jobins_data')
        ->setPage(1)
        ->setHitsPerPage(1)
        ->setMatchingStrategy('all');
}

$client   = new \Meilisearch\Client('http://localhost:7700', 'masterKey');
$response = $client->multiSearch($searches);

$page     = 1;
$per_page = 10;
$offset   = ($page - 1) * $per_page;

$possibleSearchTerms = [];
$count               = 0;
$termKeys            = array_keys($terms);
$next                = $offset + $per_page;
$hasOffset           = false;
while (count($termKeys) > 0) {
    $term            = array_pop($termKeys);
    $neededForOffset = $offset - $count;
    $neededForLimit  = $offset + $per_page - $count;
    $count           = $count + $metadata[$term];

    if ($count > $offset && $count  $offset + $per_page) {
        $possibleSearchTerms[] = [
            'q'      => $term,
            'offset' => $hasOffset ? 0 : $neededForOffset,
        ];
        $hasOffset             = true;
    }

    if ($count >= $offset + $per_page) {
        $possibleSearchTerms[] = [
            'offset' => $hasOffset ? 0 : $neededForOffset,
            'q'      => $term,
            'limit'  => min($neededForLimit, $per_page),
        ];
        break;
    }
}

$searches = [];
foreach ($possibleSearchTerms as $term) {
    $searches[] = (new SearchQuery())
        ->setQuery($term['q'])
        ->setAttributesToRetrieve(['id'])
        ->setIndexUid('jobins_data')
        ->setOffset($term['offset'] ?? 0)
        ->setLimit($term['limit'] ?? $per_page)
        ->setSort(['id:desc'])
        ->setMatchingStrategy('all');
}

$response        = $client->multiSearch($searches);
$results['hits'] = collect($response['results'])->pluck('hits')->flatten(1);

const BASE_PATH = '/Users/ellite/code/office/api.jobins.test';

require_once BASE_PATH.'/vendor/autoload.php';
use Illuminate\Foundation\Console\Kernel;
use Meilisearch\Contracts\SearchQuery;

$app = require BASE_PATH.'/bootstrap/app.php';
$app->make(Kernel::class)->bootstrap();

/** Data preparation */
config()->set('scout.queue', false);
config()->set('scout.after_commit', false);

class Post extends \Illuminate\Database\Eloquent\Model
{
    use \Laravel\Scout\Searchable;

    protected $table = 'posts';

    protected $fillable = [
        'title',
        'body',
    ];

    public function searchableAs(): string
    {
        return 'posts';
    }

    public function toSearchableArray()
    {
        return $this->toArray();
    }
}

config()->set('scout.meilisearch.index-settings', [
    Post::class => [

    ],
]);

\Illuminate\Support\Facades\Artisan::call('scout:sync-index-settings');

\Illuminate\Support\Facades\Schema::dropIfExists('posts');
\Illuminate\Support\Facades\Schema::create('posts', function (\Illuminate\Database\Schema\Blueprint $table) {
    $table->id();
    $table->string('title');
    $table->text('body')->nullable();
    $table->timestamps();
});

$data = [
    ['title' => 'PHP'],
    ['title' => 'Engineer'],
    ['title' => 'Manager'],
    ['title' => 'PHP Engineer'],
    ['title' => 'PHP Manager'],
    ['title' => 'Engineer Manager'],
    ['title' => 'PHP Engineer Manager'],

    ['title' => 'Engineering'],
];

foreach ($data as $row) {
    $post = Post::query()->create($row);
}

/** End of Data Preparation*/

function formatTerm($data, array $current): string
{
    $data    = array_map(fn($item) => "'$item'", $data);
    $current = array_map(fn($item) => $data[$item], $current);

    $exclude = array_diff($data, $current);

    $current = implode(' ', $current);
    $exclude = implode(' -', $exclude);

    return trim(implode(' -', [$current, $exclude]), ' -');
}

function generateTerm(array $ans, $data, array $current)
{
    $last = end($current);

    if ($last == count($data) - 1) {
        return $ans;
    }

    $nextCurrent   = $current;
    $nextCurrent[] = $last + 1;

    array_pop($current);
    $current[] = $last + 1;

    $ans[formatTerm($data, $nextCurrent)] = count($nextCurrent);
    $ans[formatTerm($data, $current)]     = count($current);

    $ans = generateTerm($ans, $data, $nextCurrent);
    $ans = generateTerm($ans, $data, $current);

    return $ans;
}

$data = ['PHP', 'Engineer', 'manager'];

$ans[formatTerm($data, [0])] = 1;

$terms = generateTerm($ans, $data, [0]);
arsort($terms);


$searches = [];
foreach ($terms as $term => $index) {
    $searches[] = (new SearchQuery())
        ->setQuery($term)
        ->setAttributesToRetrieve(['id'])
        ->setIndexUid('posts')
        ->setPage(1)
        ->setHitsPerPage(1)
        ->setMatchingStrategy('all');
}

$client   = new \Meilisearch\Client('http://localhost:7700', 'masterKey');
$response = $client->multiSearch($searches);
$metadata = collect($response['results'])->pluck('totalHits', 'query');


$page     = 1;
$per_page = 10;
$offset   = ($page - 1) * $per_page;

$count               = 0;
$possibleSearchTerms = [];
$termKeys            = array_keys($terms);
$next                = $offset + $per_page;
$hasOffset           = false;
while (count($termKeys) > 0) {
    $term            = array_pop($termKeys);
    $neededForOffset = $offset - $count;
    $neededForLimit  = $offset + $per_page - $count;
    $count           = $count + $metadata[$term];

    if ($count > $offset && $count  $offset + $per_page) {
        $possibleSearchTerms[] = [
            'q'      => $term,
            'offset' => $hasOffset ? 0 : $neededForOffset,
        ];
        $hasOffset             = true;
    }

    if ($count >= $offset + $per_page) {
        $possibleSearchTerms[] = [
            'offset' => $hasOffset ? 0 : $neededForOffset,
            'q'      => $term,
            'limit'  => min($neededForLimit, $per_page),
        ];
        break;
    }
}

$searches = [];
foreach ($possibleSearchTerms as $term) {
    $searches[] = (new SearchQuery())
        ->setQuery($term['q'])
        ->setAttributesToRetrieve(['id'])
        ->setIndexUid('jobins_data')
        ->setOffset($term['offset'] ?? 0)
        ->setLimit($term['limit'] ?? $per_page)
        ->setSort(['id:desc'])
        ->setMatchingStrategy('all');
}

$response        = $client->multiSearch($searches);
$results['hits'] = collect($response['results'])->pluck('hits')->flatten(1);

dd($results['hits']);