在PHP中，快速搜索包含子字符串的值的数组的有效方法是什么？

Question

我有一个按字母顺序排列的街道名称数组，这些名称是通过网络服务获取的。该数组存在于服务器端。

在客户端，用户开始输入他所住街道的名称，并使用AJAX返回与部分街道名称最接近的匹配项列表，以及数组中接下来的9个街道名称（在用户输入时更新列表）。

例如，如果用户键入“al”，我期望结果类似于以下内容：

- Albany Hwy - Albens Vale - Alcaston Rd - Alex Wood Dr - Alice Rd - Allawah Ct - Allen Rd - Alloway Pl - Allwood Av - Alola St - Amanda Dr 这是我的尝试：

$matches = array();
for($i = 0; $i < count($streetNames); $i++)
{
  if( (stripos($streetNames, $input) === 0 && count($matches) == 0) || count($matches) < 10 ){
   $matches[] = $streetNames[$i];
  } else {
   break;
  }
}

还有其他人知道更快的方法吗？

请注意：我无法控制此列表从数据库中获取的方式-它来自外部网络服务。

- Iain Fraser

---

要找到最快的方法，您必须进行基准测试以确保。但如果这来自外部网络服务，我会说建立与网络服务的连接将比您获得答案的任何代码都要慢。 - Gordon

是的，我通过将从Web服务器返回的数据缓存24小时来解决了这个问题。我们市政府的街道名称通常不会发生太大变化，但有很多开发项目正在进行中，新的街道随时都会出现，所以24小时似乎是一个不错的时间间隔。 - Iain Fraser

Answer 1

使用 preg_grep() 函数：

$matches = preg_grep('/al/', $streetNames);

注意：这种方法像你的方法一样，属于暴力搜索。如果你正在搜索一个巨大的名称列表（数十万个）或者需要频繁进行大量搜索，那么你可能需要更好的方法。对于小数据集来说，这种方法是可以接受的。

- cletus

---

谢谢Cletus。虽然我在这种特定情况下不会使用这种方法，但你让我认识到了一个我总是忽视的函数。我一定会在未来的某个时候使用它。再次感谢:) - Iain Fraser

这永远不会是一种快速的方式 :| - s3v3n

Answer 2

我无法确定它是否更快，但这是我的版本。

$input = 'al';
$matches = array_filter($streetNames, create_function('$v','return (stripos($v,'.$input.') !== false ? true : false);'));
$weight = array_map(create_function('$v','return array($v,levenshtein('.$input.',$v));'),$matches);
uasort($weight, create_function('$a,$b', 'if ($a[1] == $b[1]) {return 0;} return ($a[1] < $b[1]) ? -1 : 1;'));
$weight = array_slice($weight, 0, 10);

这将创建一个加权匹配列表。它们根据输入字符串和街道名称之间的距离进行排序。 0 表示完全匹配。

生成的数组如下所示

array (
  0 => 
  array (
    0 => 'Alola St',
    1 => 7,
  ),
  1 => 
  array (
    0 => 'Allen Rd',
    1 => 7,
  )
)

0表示街道名称，1表示Levenshtein距离。

- Peter Lindqvist

---

对我来说，自动完成功能如果没有加权或者其他你想要称呼的东西就不算完整。当然，这不是唯一的方法。只是一个快速的概念验证。 - Peter Lindqvist

Answer 3

我想你需要的是preg_grep()函数。

您可以搜索以输入文本开头的元素：

$result = preg_grep('/^$input/', $streetNames);

或者针对包含文本的任何位置的元素：

$result = preg_grep('/$input/', $streetNames);

或者你也可以将搜索锚定到末尾，但那看起来并不是很有用。

- Matteo Riva

---

谢谢你的回答，伙计。我实际上从来没有听说过 preg_grep。虽然我在这种情况下不会使用它，但它看起来非常方便，我会将其存档以备将来使用 :) - Iain Fraser

Answer 4

要比遍历所有字符串更快的唯一方法是使用针对此类事物进行优化的数据结构，即Trie树。您可能无法控制Web服务提供的内容，但如果您可以在服务器上缓存结果并重用它以服务于许多请求，则构建Trie树并使用它将会更快。

- Michael Borgwardt

---

有趣的是，我实际上正在从Web服务器缓存数据。我一定会研究这个问题 :) - Iain Fraser

伙计，回复太棒了！我还找到了一个非常好的 PHP 资源：http://phpir.com/tries-and-wildcards。 - Iain Fraser