Самый быстрый способ соответствовать префиксам телефонии с помощью Сценария PHP звездочки

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

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

// $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_ ', например, значение неважно (работает 1).

I do it by using a hashtable of string, destination where the keys are strings that represent the prefix of the destination. The critical factor is that the hashtable must be sorted so that the longest strings are checked first. As soon as a matching prefix is found the call destination is known.

I actually also have a round of regular expressions that for more convoluted destinations and check the regular expressions before the destination prefixes.

I haven't measured how long it takes to get a match but I suspect 15ms max. The whole process of checking the desitnation and then the user's balance and finally setting a call time limit takes around 150ms. In my case I am using FastAGI and C# Windows service. As long as you take less than 500ms it will be impercetible to your users.

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

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

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

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

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

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

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

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

• 01, 0127, 01273, 0809, 08

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

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

Шаги будут следующими:

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

Some sample code to see it in action:

// 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]);
    }
}