1

我有一批 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 都必须通过该数组。有什么办法可以让这更快吗？

4

3 回答 3

3

根据您希望匹配的 3 种 URL 中的哪一种，可以对问题做出不同的回答：

  1. 仅完全匹配（字符串相等）。例如，如果 DB url 是“google.com”，那么搜索字符串“ http://google.com ”将不匹配，“google.com/q=a”也不会匹配。

    在这种情况下，放弃使用正则表达式，或者简单地做SELECT * FROM urls WHERE url="$search"，或者做一个哈希查找作为 Andreas 的答案细节。

  2. 搜索 URL 和 DB 中的 URL 都是有效 URL（例如以 http:// 开头），因此必须从字符串开头匹配，但搜索 URL 可以包含要匹配的 DB URL+后缀。例如，如果 DB URL 是“ http://google.com ”，则搜索字符串“ http://google.com ”和“ http://google.com/q=a ”匹配。

    在这种情况下，要么开始锚定正则表达式，要么开始锚定“LIKE”数据库匹配 - 请参阅答案下一部分中的详细信息。

  3. 任何子字符串匹配。例如，如果 DB URL 是“google”，那么任何包含“google”字符串的 URL 都匹配任何地方。

    在这种情况下，要么做单词查找表，要么做更智能的子串查找算法；或使用“|”进行批量正则表达式匹配 加入多个数据库网址。请参阅答案的最后一部分中的详细信息。

这部分答案假设您在 DB 中的 URL 可以是搜索 URL 的子字符串，但它们都以“http”开头，这意味着它们始终在字符串的开头匹配；但不是完全匹配。

开始锚定匹配的解决方案 1 (Perl)：

将您的正则表达式固定在开头：if($searchedurl=~ /^$_/){

开始锚定匹配 (DB) 的解决方案 2：

按 URL 字段索引您的 URL 表，然后执行（Sybase 语法）

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

这将对开始锚定的子字符串进行非常有效的数据库搜索。

注意：在 DB 和 Perl 中进行匹配之间的权衡是：

  • 如果您有 1 个 DB 和 100 个客户端，您不希望在进行字符串匹配时使 DB 过载。将 CPU 负载分配给客户端。

  • 如果您只有 1-2 个客户端，则 DB 可能会更好，因为您将从 DB 中的磁盘 IO 传输更少的数据（表上的索引会有所帮助）和通过网络传输。

这部分答案假设您在 DB 中的 URL 可以是搜索 URL 的完整子字符串，不一定是完全匹配甚至是锚定匹配。

随机子字符串匹配的解决方案 1 (Perl)：

一种可以加快速度的纯粹 Perl 方法是将搜索字符串组合成批处理：

  • @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 拆分为单词。
  • 在数据库中，将唯一 ID 添加到 URL 表
  • 在数据库中，将“单词查找”表映射（1 对 N）URL ID 添加到该 URL 中的每个单词（每行 1 个）
  • 使用“单词查找”表缩小要查询的 URL 列表。
    • 您可以在“单词查找”表上使用数据库索引来使搜索速度非常快。
    • 当然，您还需要将搜索 URL 拆分为单词。
    • 通过从路径中单独索引域名词进一步加速/缩小。

注意：如果 URL 可以是与第一个字符不匹配的子字符串，则在数据库中使用简单的“WHERE”子句来搜索您的 URL 表是一个非常糟糕的主意 - 这样，您就不能使用和索引并且会只需扫描表格。

注意2：为了更有效地匹配字符串数组的子字符串，有更高级的基于子字符串图的算法。

注意 3：在 Perl 和 DB 中进行匹配之间的权衡与答案的前半部分相同。

于 2013-04-30T07:32:42.907 回答
1

@DVK 是正确的，如果您可以在开始时锚定比赛，它通常会更有效。这样你就可以使用标准的 btree 索引来搜索（MySQL 没有 PostgreSQL 更丰富的索引类型 afaik）。

我不同意他/她在哪里进行匹配。在数据库本身中执行此操作几乎总是有意义的。这就是数据库的用途。

最有效的方法可能是这样的：

  1. 创建一个临时表来保存您的目标网址
  2. 将您的目标批量插入该临时表
  3. 在它们上创建一个索引（假设索引在这里会有所帮助）
  4. 使用 LIKE 匹配从您的主 url 表加入您的目标。

即使你不能使用索引，数据库也应该比你的 perl 快。您正在读取整个表，将原始数据打包到传输协议中，传输它，将其解析为 perl 值，组装散列然后检查它。假设您的目标 url 列表比数据库中的完整列表小得多，您只需不传输太多数据即可获胜。

于 2013-04-30T10:05:02.360 回答
0

注意：OP 要求搜索字符串应包含 url 的解决方案。我已经更改了我的解决方案以尝试规范化 url，以便在得到评论后哈希匹配是精确的查找。

此代码未经测试，它应该作为某种形式的伪代码，可能有效

创建哈希而不是数组。哈希是有序的，更适合作为查找。

my $results = $dbh->selectall_hashref('SELECT * FROM urltable;', 'url');
my %urldb = map { normalize($_) => 1 } keys %$results;

sub normalize {
  my $url = shift;
  $url =~ s|http://||; # strip away http:// if present
  $url =~ s|www\.||;   # strip away www if present
  $url =~ s|/.*||;     # strip away anything after and including /
  return $url;
}

然后你会搜索

if (exists($urldb{normalize($searchedurl)})) {
  #do things here
}
于 2013-04-30T07:35:06.277 回答