代码之家 › 专栏 › 技术社区 › Alex Recarey

使用星号PHP脚本匹配电话前缀的最快方法

asterisk caching performance php

Alex Recarey · 技术社区 · 17 年前

提前谢谢你的帮助。

背景 -

在研究了几种数据结构之后,一个树(其中每个节点存储一个数字,并包含指向其他10种可能选择的指针)似乎很理想。这可以实现为一个数组数组,脚本可以检查3,在那里找到一个数组,然后在新数组上检查0,找到另一个数组,依此类推,直到找到一个值而不是数组。该值将是目标id(脚本的输出)。

要求 -

我这样做对吗?也许还有别的解决办法?还是我提出的方法之一优于另一种?

6 回复 | 直到 17 年前

Hugh Bothwell 17 年前

下面是一些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');

注意,我为每个节点添加了一个终端标志;这避免了错误的部分匹配,即如果添加前缀3056124,它将正确匹配3056,而不是返回305612。

避免每次重新加载的最佳方法是将其转换为服务;然而,在这样做之前,我将使用APC测量运行时间。它很可能已经足够快了。

亚历克斯:你的答案绝对正确——但不适用于这个问题:)

J.C. Inacio 17 年前

示例代码:(注意,对于性能而言,前缀是数组中的键,而不是值)

// $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

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

Guillermo Phillips 17 年前

您可以执行二进制搜索算法。如果您存储所有前缀(数字),填充到15个位置,然后按顺序,您可以在大约log2(6000)~=13个步骤中扫描6000个代码。

例如,如果您有以下代码:

010000000000000
012700000000000
012730000000000
080900000000000

这些步骤将是:

将输入号码减至15
最接近的最低代码(及其在上面数组中的索引)
在列表中查找代码的长度

一些示例代码可以查看它的实际操作:

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

sipsorcery 17 年前

实际上,我还有一轮正则表达式,用于更复杂的目标,并在目标前缀之前检查正则表达式。

我还没有测量需要多长时间才能找到匹配,但我怀疑最长15毫秒。检查设计、用户余额以及最终设置通话时间限制的整个过程大约需要150毫秒。就我而言,我使用的是FastAGI和C#Windows服务。只要你的时间少于500毫秒,你的用户就无法察觉。

null 17 年前

我还假设您也在寻找国家代码。只有少数国家代码与NANP重叠。因此,我首先查找NANP,并快速匹配以下数字(7)以确保,否则我会使用国家代码。然后,通过正则表达式,我大致知道每个国家的电话号码中应该有多少个数字。

我使用一个XML文档并匹配XPath,然后尽可能缓存XPath结果。

使用RESTAPI最酷的一点是,在我将数字存储在DB中进行计费之前,它可以用来清理数字。

Alex Weinstein 17 年前

寻找最长公共子序列是动态规划的一个经典应用。解为O(n)。 http://en.wikipedia.org/wiki/Longest_common_subsequence_problem