Самый быстрый способ сопоставить телефонные префиксы с помощью PHP-скрипта asterisk

Вот пример кода для N-арной древовидной структуры;

class PrefixCache {
 const EOS = 'eos';
 protected $data;

 function __construct() {
  $this->data = array();
  $this->data[self::EOS] = false;
 }

 function addPrefix($str) {
  $str = (string) $str;
  $len = strlen($str);

  for ($i=0, $t =& $this->data; $i<$len; ++$i) {
   $ch = $str[$i];

   if (!isset($t[$ch])) {
    $t[$ch] = array();
    $t[$ch][self::EOS] = false;
   }

   $t =& $t[$ch];
  }

  $t[self::EOS] = true;
 }

 function matchPrefix($str) {
  $str = (string) $str;
  $len = strlen($str);

  $so_far = '';
  $best = '';

  for ($i=0, $t =& $this->data; $i<$len; ++$i) {
   $ch = $str[$i];

   if (!isset($t[$ch]))
    return $best;
   else {
    $so_far .= $ch;
    if ($t[$ch][self::EOS])
     $best = $so_far;

    $t =& $t[$ch];     
   }
  }

  return false; // string not long enough - potential longer matches remain
 }

 function dump() {
  print_r($this->data);
 }
}

тогда это можно назвать

$pre = new PrefixCache();

$pre->addPrefix('304');
$pre->addPrefix('305');
// $pre->addPrefix('3056');
$pre->addPrefix('3057');

echo $pre->matchPrefix('30561234567');

который работает как требуется (возвращает 305; если 3056 раскомментирован, вместо этого возвращает 3056).

Обратите внимание, что я добавляю флаг терминала к каждому узлу; это позволяет избежать ложных частичных совпадений, т. е. если вы добавите префикс 3056124, он будет правильно соответствовать 3056 вместо возврата 305612.

Лучший способ избежать перезагрузки каждый раз — превратить это в сервис; однако перед этим я измерил время работы с помощью APC. Это вполне может быть достаточно быстро, как есть.

Алекс: ваш ответ абсолютно правильный - но не применимый к этому вопросу :)

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

Пример кода: (обратите внимание, что для повышения производительности префиксы являются ключами в массиве, а не значениями)

// $prefixes = array(3=>1, 30=>1, 304=>1,305=>1,3056=>1,306=>1,31=>1, 40=>1);

function matchNumber($number)
{
  $prefixes = getPrefixesFromCache();

  $number = "$number";
  // try to find the longest prefix matching $number
  while ($number != '') {
    if (isset($keys[$number]))
      break;
    // not found yet, subtract last digit
    $number = substr($number, 0, -1);
  }
  return $number;
}

Другим способом было бы запросить кеш напрямую для числа — в этом случае его можно было бы дополнительно оптимизировать:

1. разделить числовую строку на 2.
2. запросите эту строку в кеше.
3. если он не существует, перейдите к 1
4. пока оно существует, сохраните это значение как результат и добавьте еще одну цифру.

Фрагмент: (обратите внимание, что query_cache_for() следует заменить любой функцией, которую использует ваш механизм кэширования)

function matchNumber($number)
{
  $temp = "$number";
  $found = false;
  while (1) {
    $temp = substr($temp, 0, ceil(strlen($temp)/2) );
    $found = query_cache_for($temp);
    if ($found)
      break;
    if (strlen($temp) == 1)
      return FALSE; // should not happen!
  }
  while ($found) {
    $result = $temp;
    // add another digit
    $temp .= substr($number, strlen($temp), 1);
    $found = query_cache_for($temp);
  }
  return $result;
}

У этого подхода есть очевидное преимущество, заключающееся в том, что каждый префикс представляет собой отдельный элемент в кеше — ключ может быть, например, 'asterix_prefix_‹number>', значение неважно (работает 1).

Поскольку вы работаете только с числами, возможно, работа напрямую со строками неэффективна.

Вы можете выполнить алгоритм бинарного поиска. Если вы сохраните все свои префиксы (в числовом виде), дополненные до 15 позиций, а затем по порядку, вы сможете отсканировать 6000 кодов приблизительно за log2(6000)~=13 шагов.

Например, если у вас есть следующие коды:

• 01, 0127, 01273, 0809, 08

Вы бы сохранили в массиве следующее:

1. 010000000000000
2. 012700000000000
3. 012730000000000
4. 080000000000000
5. 080900000000000

Шаги будут такими:

1. Сократите входящий номер до 15 знаков.
2. Выполните двоичный поиск, чтобы найти ближайший самый низкий код (и его индекс в массиве выше)
3. Найдите длину кода в отдельном массиве (используя индекс)

Пример кода, чтобы увидеть его в действии:

// Example for prefixes 0100,01,012,0127,0200
$prefixes = array('0100','0101','0120','0127','0200');
$prefix_lengths = array(4,2,3,4,4);
$longest_length_prefix = 4;

echo GetPrefix('01003508163');

function GetPrefix($number_to_check) {
    global $prefixes;
    global $prefix_lengths;
    global $longest_length_prefix;

    $stripped_number = substr($number_to_check, 0, $longest_length_prefix);

    // Binary search
    $window_floor = 0;
    $window_ceiling = count($prefixes)-1;
    $prefix_index = -1;

    do {
        $mid_point = ($window_floor+$window_ceiling)>>1;

        if ($window_floor==($window_ceiling-1)) {
            if ($stripped_number>=$prefixes[$window_ceiling]) {
                $prefix_index=$window_ceiling;
                break;
            } elseif ($stripped_number>=$prefixes[$window_floor]) {
                $prefix_index=$window_floor;
                break;
            } else {
                break;
            }
        } else {
            if ($stripped_number==$prefixes[$mid_point]) {
                $prefix_index=$mid_point;
                break;
            } elseif ($stripped_number<$prefixes[$mid_point]) {
                $window_ceiling=$mid_point;
            } else {
                $window_floor=$mid_point;
            }
        }
    } while (true);

    if ($prefix_index==-1 || substr($number_to_check, 0, $prefix_lengths[$prefix_index])!=substr($prefixes[$prefix_index],0, $prefix_lengths[$prefix_index])) {
        return 'invalid prefix';
    } else {
        return substr($prefixes[$prefix_index], 0, $prefix_lengths[$prefix_index]);
    }
}

Я делаю это, используя хэш-таблицу строк, адресатов, где ключи представляют собой строки, представляющие префикс адресата. Критическим фактором является то, что хеш-таблица должна быть отсортирована таким образом, чтобы в первую очередь проверялись самые длинные строки. Как только найден соответствующий префикс, становится известен пункт назначения вызова.

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

Я не измерял, сколько времени требуется, чтобы получить совпадение, но я подозреваю, что максимум 15 мс. Весь процесс проверки адресата, а затем баланса пользователя и, наконец, установки лимита времени звонка занимает около 150 мс. В моем случае я использую FastAGI и службу C# Windows. Пока вы занимаете менее 500 мс, это будет незаметно для ваших пользователей.

Я также запускаю приложение телефонии... то, что я сделал, это предоставление внутреннего REST API для вызова, это то, что будет кэшировать известные телефонные номера и выполнять всю проверку префиксов.

Также я предполагаю, что вы также ищете коды стран. Есть только несколько перекрывающихся кодов стран с NANP. Поэтому я сначала ищу NANP и быстро сопоставляю количество следующих цифр (7), чтобы убедиться, в противном случае я возвращаюсь к коду страны. Затем у меня есть приблизительное представление о том, сколько цифр в телефонном номере должно быть в каждой стране с помощью регулярного выражения.

Я использую XML-документ и сопоставляю XPath, а затем кэширую результат XPath, когда это возможно.

Крутая вещь в использовании REST API также заключается в том, что его можно использовать для очистки чисел, прежде чем я сохраняю их в БД для выставления счетов.

Это не точная наука, но, похоже, это работает.

Поиск самой длинной общей подпоследовательности является классическим применением динамического программирования. Решение — O(n). http://en.wikipedia.org/wiki/Longest_common_subsequence_problem