В PHP, что такое быстрый способ поиска в массиве значений, которые содержат подстроку? - PullRequest
Новая
       25

В PHP, что такое быстрый способ поиска в массиве значений, которые содержат подстроку?

5 голосов
/ 21 января 2010

У меня есть массив названий улиц, отсортированных в алфавитном порядке, которые я собрал из веб-службы. Этот массив существует на стороне сервера.

На стороне клиента пользователь начинает вводить название улицы, на которой он живет, и AJAX используется для возврата списка наиболее близкого совпадения к частичному названию улицы, а также следующих 9 названий улиц в массиве (список обновляется, пока он печатает).

Например, если пользователь введет «al», я ожидаю, что результаты будут примерно такими:

  • Олбани Хуай
  • Албенс Вейл
  • Alcaston Rd
  • Алекс Вуд, доктор
  • Алиса Rd
  • Аллах, Ct
  • Allen Rd
  • Alloway Pl
  • Allwood Av
  • Алола ул
  • Аманда Д-р

Это моя попытка: 

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

Кто-нибудь еще знает более быстрый путь?

Пожалуйста, обратите внимание: я не контролирую, как этот список получается из базы данных - это из внешнего веб-сервиса.

Ответы [ 4 ]

5 голосов
/ 21 января 2010

Использование preg_grep(): 

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

Примечание: этот метод, подобный вашему, будет перебором методом грубой силы. Если вы ищете огромный список имен (сотни тысяч) или огромное количество раз, тогда вам может понадобиться что-то лучшее. Однако для небольших наборов данных это нормально.

4 голосов
/ 21 января 2010

Не могу сказать, действительно ли он быстрее, но это моя версия. 

$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 => расстояние Левенштейна

4 голосов
/ 21 января 2010

Единственный способ ускорить просмотр всех строк - оптимизировать структуру данных для такого рода вещей, например trie . Вы можете не иметь контроля над тем, что дает вам веб-служба, но если вы можете кэшировать результат на своем сервере и повторно использовать его для обслуживания многих запросов, то создание дерева и использование этого будет намного быстрее.

4 голосов
/ 21 января 2010

Я думаю, что вы ищете preg_grep ()

Вы можете искать элементы, начинающиеся с введенного текста: 

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

или для элементов, которые содержат текст в любом месте: 

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

или вы также можете привязать поиск к концу, но это не выглядит так полезно

...