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

Question

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 ){
   $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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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