开发者

In PHP, what is a fast way to search an array for values which contain a substring?

I have an array of street names sorted alphabetically that I have gathered from a web service. This array exists on the server side.

On the client side, a user starts typing the name of the street he lives on and AJAX is used to return a list of the closest match to the partial street name, plus the next 9 street names in the array (the list is updated while he is typing).

For example, if the user typed "al", I would expect the results to be something like the following:

  • Albany Hwy
  • Albens Vale
  • Alcaston Rd
  • Alex Wood Dr
  • Alice Rd
  • Allawah Ct
  • Allen Rd
  • Alloway Pl
  • Allwood Av
  • Alola St
  • Amanda Dr

This is my try at it:

$matches = array();
for($i = 0; $i < count($streetNames); $i++)
{
  if( (stripos($streetNames, $input) === 0 && count($matches) == 0) || count($matches) < 10 ){
   开发者_如何学C$matches[] = $streetNames[$i];
  } else {
   break;
  }
}

Does anyone else know a faster way?

Please note: I have no control over how this list is obtained from the database - it's from an external web service.


Use preg_grep():

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

Note: this method like yours will be a brute force search. If you're searching a huge list of names (hundreds of thousands) or searching a huge number of times then you may need something better. For small data sets this is fine however.


The only way to get faster than looking through all the strings would be to have a data structure optimized for this kind of thing, a trie. You may not have control over what the webservice gives you, but if you can cache the result on your server and reuse it for serving many requests, then building a trie and using that would be much faster.


I think what you're looking for is preg_grep()

You can search either for elements starting with the input text:

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

or for elements that contain the text in any place:

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

or you can also anchor the search to the end but that doesn't look so useful


Can't really tell if it is faster, but this is my version of it.

$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);

This creates a weighted list of matches. They are sorted according to the distance between the input string and the street name. 0 represents a true match.

Resulting array looks like this

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

Where 0 => street name and 1 => levenshtein distance

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜