mysql - Perl 検索ルックアップ効率

Question

データベースを検索して一致するものを検索する必要があるか、URL にデータベース内の URL が含まれているかどうかを確認する必要がある URL のバッチがあります。

URL の例は次のとおりです。

http://www.foodandnuts.com/login.html

データベースには URL で満たされたテーブルがあります

現在、私のスクリプトは、データベース内のすべての URL を含む配列を最初に作成しました

my $results = $dbh->selectall_hashref('SELECT * FROM urltable;', 'url');
foreach my $j (keys %$results) {
push(@urldb, $j);
}

次に、配列を調べて、URL にデータベースからの URL が含まれているかどうかを確認します。

    foreach(@urldb){
            if($searchedurl=~ /$_/){
#do things here
}}

問題は、配列に 10000 を超える URL があるため非常に遅いため、検索された各 URL がその配列を通過する必要があることです。これを速くする方法はありますか？

score 3 · Accepted Answer

この質問は、3 種類の URL のうちどれを希望するかによって、異なる回答をすることができます。

正確な完全一致のみ(文字列が等しい)。たとえば、DB URL が「google.com」の場合、検索文字列「http://google.com」は一致せず、「google.com/q=a」も一致しません。

この場合、正規表現の使用をやめて、単純にを実行するかSELECT * FROM urls WHERE url="$search"、Andreas の回答の詳細としてハッシュルックアップを実行します。
検索 URL と DB 内の URL はどちらも有効な URL (例: http:// で始まる) であるため、文字列の先頭から一致する必要がありますが、検索 URL には一致する DB URL + サフィックスを含めることができます。たとえば、DB URL が " http://google.com " の場合、検索文字列は " http://google.com " AND " http://google.com/q=a " に一致します。

この場合、開始アンカーされた RegEx を実行するか、開始アンカーされた「LIKE」DB 一致を実行します。回答の次の部分で詳細を参照してください。
任意の部分文字列一致。たとえば、DB URL が「google」の場合、「google」文字列を含む URL はどこでも一致します。

この場合、単語ルックアップテーブルを実行するか、よりスマートな部分文字列ルックアップアルゴリズムを実行します。または、「|」を使用してバッチ正規表現一致を実行します複数の DB URL を結合します。回答の最後の部分で詳細を参照してください。

回答のこの部分では、DB 内の URL が検索 URL の部分文字列である可能性があると想定していますが、それらはすべて「http」で始まります。つまり、常に文字列の先頭で一致します。しかし完全一致ではありません。

開始固定マッチの解決策 1 (Perl):

正規表現が最初に固定されるように修正します。if($searchedurl=~ /^$_/){

開始固定マッチ (DB) の解決策 2:

URL フィールドで URL テーブルのインデックスを作成し、実行します (Sybase 構文)。

$query = qq[SELECT * FROM urls WHERE url LIKE "$searchurl\%"];

これにより、開始アンカーされた部分文字列の非常に効率的な DB 検索が行われます。

注: DB と Perl でのマッチングのトレードオフは次のとおりです。

1 つの DB と数百のクライアントがある場合、文字列の一致を行うために DB を過負荷にしたくありません。CPU 負荷をクライアントに分散します。
クライアントが 1 ～ 2 台しかない場合は、DB のディスク IO (テーブルのインデックスが役立ちます) およびネットワーク経由で転送されるデータが少ないため、DB の方が優れている可能性があります。

回答のこの部分では、DB 内の URL が検索 URL の完全な部分文字列である可能性があり、必ずしも完全一致またはアンカー一致であるとは限りません。

ランダム部分文字列一致の解決策 1 (Perl):

これを高速化する純粋な Perl の方法の 1 つは、検索文字列をバッチに結合することです。

@urldbループ内でから最初の N 個の要素を分割する

my $N = 10;
my $start = 0;
my $end = $N - 1;
while ($start < @urldb ) {
    search_with($searchedurl, @urldb[$start..$end]); # see next bullet
    $start += $N;
    $end += $N;
    $end = @urldb if $end > @urldb;
}

長さ N の配列のそれぞれについて、要素を「|」で結合します。そして正規表現を作成します

sub search_with {
    my $searchedurl = shift;
    my $regex_string = join("|", @_);
    if ($searchedurl =~ /($regex_string)/) {
        # Do stuff, $1 will contain what matched.
    }
}

ランダム部分文字列一致 (DB) の解決策 2:

それを行う別のよりアルゴリズム的な方法は、「単語ルックアップ」テーブル (別名インデックスですが、データベースインデックスとの混同を避けるためにインデックスという用語を使用したくない) を作成することです。

各 URL を単語に分割します。
DBで、一意のIDをURLテーブルに追加します
DB で、「単語検索」テーブルマッピング (1 対 N) の URL ID を、その URL の個々の単語 (行ごとに 1 つ) に追加します。
「単語検索」テーブルを使用して、照会する URL のリストを絞り込みます。
- 「単語検索」テーブルでデータベースインデックスを使用して、その検索を非常に高速にすることができます。
- もちろん、検索 URL も単語に分割する必要があります。
- パスからドメイン名の単語を個別にインデックス化することで、さらに高速化/絞り込みます。

注: データベース内で単純な「WHERE」句を使用して URL テーブルを検索することは、URL が最初の文字と一致しない部分文字列である可能性がある場合、非常に悪い考えです。この方法では、およびインデックスを使用できず、テーブルをスキャンするだけです。

注 2 : 文字列の配列に対してより効率的な部分文字列の照合を行うために、部分文字列のグラフに基づくより高度なアルゴリズムがあります。

注 3: Perl と DB でのマッチングのトレードオフは、回答の前半と同じです。

mysql - Perl 検索ルックアップ効率

3 に答える 3

Related

Reference