最快的PHP例程匹配单词

Question

在PHP中，最快的方法是将关键词列表与搜索结果（如标题数组）进行匹配，以匹配所有单词？

例如，如果我的关键字短语是“great leather shoes”，那么以下标题将会被匹配...

• Get Some Really Great Leather Shoes
• Leather Shoes Are Great
• Great Day! Those Are Some Cool Leather Shoes!
• Shoes, Made of Leather, Can Be Great

而这些则不会匹配：

• Leather Shoes on Sale Today!
• You'll Love These Leather Shoes Greatly
• Great Shoes Don't Come Cheap

我想有一些技巧可以使用数组函数或正则表达式来快速实现。

- Volomike

---

我会使用explode、array_merge/array_unique和count的组合来完成这个任务，但我无法确定它的速度有多快。 - svens

Answer 1

我会为标题中的单词使用索引，并测试每个搜索项是否在该索引中：

$terms = explode(' ', 'great leather shoes');
$titles = array(
    'Get Some Really Great Leather Shoes',
    'Leather Shoes Are Great',
    'Great Day! Those Are Some Cool Leather Shoes!',
    'Shoes, Made of Leather, Can Be Great'
);
foreach ($titles as $title) {
    // extract words in lowercase and use them as key for the word index
    $wordIndex = array_flip(preg_split('/\P{L}+/u', mb_strtolower($title), -1, PREG_SPLIT_NO_EMPTY));
    // look up if every search term is in the index
    foreach ($terms as $term) {
        if (!isset($wordIndex[$term])) {
            // if one is missing, continue with the outer foreach
            continue 2;
        }
    }
    // echo matched title
    echo "match: $title";
}

- Gumbo

Answer 2

你可以使用 preg_grep() 函数来将你的数组与类似以下内容进行匹配：

 /^(?=.*?\bgreat)(?=.*?\bleather)(?=.*?\shoes)/

或者（可能更快）单独 grep 每个单词，然后将结果 array_intersect。

- user187291

Answer 3

这可能是一个相当幼稚的解决方案（很可能存在更有效/优雅的解决方案），但我可能会做以下操作：

$keywords = array(
    'great',
    'leather',
    'shoes'
);

$titles = array(
    'Get Some Really Great Leather Shoes',
    'Leather Shoes Are Great',
    'Great Day! Those Are Some Cool Leather Shoes!',
    'Shoes, Made of Leather, Can Be Great',
    'Leather Shoes on Sale Today!',
    'You\'ll Love These Leather Shoes Greatly',
    'Great Shoes Don\'t Come Cheap'
);

$matches = array();
foreach( $titles as $title )
{
  $wordsInTitle = preg_split( '~\b(\W+\b)?~', $title, null, PREG_SPLIT_NO_EMPTY );
  if( array_uintersect( $keywords, $wordsInTitle, 'strcasecmp' ) == $keywords )
  {
    // we have a match
    $matches[] = $title;
  }
}

var_dump( $matches );

没有想法这个基准测试的表现如何。

- Decent Dabbler

Answer 4

我不能给你一个明确的答案，但我建议你尝试一下每个建议的解决方案并从一些in_array开始链接。

if (in_array('great', $list) && in_array('leather', $list) && in_array('shoes', $list)) {
    // Do something
}

- Danten

Answer 5

你可以使用

。

/(?=.*?\great\b)(?=.*?\bshoes\b)(?=.*?\bleather\b)/

注意几点：

a) 两端都需要单词边界，否则可能会匹配包含您要查找的单词的单词，例如“皮革鞋带来伟大”。

b) 我使用懒惰通配符匹配（即.*？）。这提高了效率，因为默认情况下*是贪婪的（即它消耗尽可能多的字符，并仅在整体匹配的情况下放弃它们）。因此，如果我们没有尾随的?，.*将匹配行中的所有内容，然后回溯以匹配“great”。然后对“shoes”和“leather”重复相同的过程。通过使*变得懒惰，我们避免了这些不必要的回溯。

- Jasmeet

---

Jasmeet，看一下我对一个非常接近你的RegExp的评论，这是Alan Moore的。看一下我的评论，以“Works on…”开头。你有什么想法，问题可能是什么？ - Volomike

@Volomike，我不太确定，特别是因为我甚至无法在Perl上编译Alan Moore的正则表达式。我得到一个有关嵌套量词（像*、+等被包含在另一个量词中）的错误，这是为了防止大规模回溯。我知道Alan使用占有量词，它使正则表达式避免额外的回溯。但Perl仍然不喜欢它，考虑到Perl和PHP都使用基于NFA的正则表达式引擎，我怀疑你可能遇到了类似的问题。 - Jasmeet

Answer 6

我不知道最快的方法，但这可能是使用正则表达式完成它的最快方法：

'#(?:\b(?>great\b()|leather\b()|shoes\b()|\w++\b)\W*+)++\1\2\3#i'

这段代码匹配字符串中的每个单词，如果该单词恰好是您的关键字之一，则空捕获组将其“勾选”。一旦字符串中的所有单词都被匹配，反向引用(\1\2\3)确保每个关键字至少出现了一次。

通常推荐的基于前瞻的方法需要多次扫描整个字符串——每个关键字扫描一次。而这个正则表达式只需要扫描一次字符串——事实上，占有性量词++, *+和原子组(?>...)禁止回溯。

话虽如此，除非我知道它会成为瓶颈，否则我仍然会选择前瞻的方法。在大多数情况下，可读性更强，从而在性能上做出权衡。

- Alan Moore

---

哇，这真是令人印象深刻！不过我会采纳你的建议，选择更易读的方式，以免让未来的程序员感到不满。 - Volomike

适用于几个由1到3个单词的关键字短语。但是当我有一个$KP为“电台之夜”，一个$RegExp为'#(?:\b(?>radio\b()|night\b()|\w++\b)\W*+)++\1\2\3#i'，以及一个$Title为“广播电视媒体史”时，我收到了错误消息“Compilation failed: reference to non-existent subpattern at offset 48”。我可以通过try/catch块来修复，但是最好首先修复RegExp中的错误吧？ - Volomike

你的正则表达式中只有两个捕获组，所以需要去掉\3。 - Alan Moore

你如何动态地使用正则表达式？假设我想让它通过一个字符串数据库，并动态设置字符串中单词的数量。 - pfunc

@pfunc：我会为每个单词创建一个替代方案，例如：$word . '\b()|'，将它们插入上述结构中，并添加所需数量的反向引用。确保每个单词都以单词字符（[A-Za-z0-9_]）开头和结尾，以便\b边界正常工作。但是，如果您无论如何都要使用过程性代码来生成正则表达式，那么您应该考虑直接编写解决方案。这样做更易于维护和扩展。 - Alan Moore