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

Question

并提前感谢您的帮助.

背景 - 我正在编写一个PHP脚本,需要找出调用者试图达到的目的地.电话号码前缀是标识目的地的字符串.对于每个调用,程序必须找到与字符串匹配的最长前缀.例如,数字30561234567将匹配305但不匹配3057或304.如果存在3056,则它将是首选匹配.

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

要求 - 性能绝对至关重要.检查这些前缀所花费的时间会延迟调用,并且每个服务器都必须处理大量调用,因此数据结构必须存储在内存中.目前大约有6000个前缀.

问题 - 每次服务器收到呼叫时都会运行脚本,因此数据必须保存在某种缓存服务器中.在检查了memcached和APC(高级PHP缓存)后,我决定使用APC,因为它[更快] [3](它是一个本地内存存储)

我遇到的问题是数组数组最多可以变成10个数组,并且将是一个非常复杂的数据结构,如果我作为对象添加到缓存中,将需要很长时间来反序列化.

但是,如果我将每个单独的数组分别添加到缓存中(使用一些逻辑命名结构可以很容易地找到它,就像数组3中的3一样,那么30代表数组30,305代表该补丁后面的数组等...)I将不得不从缓存中多次获取不同的数组(每次调用最多10个),这让我经常点击缓存.

我是以正确的方式来做这件事的吗？也许有另一种解决方案？或者我提议的方法之一优于另一方法？

谢谢你输入,

亚历克斯

Answer 1

这是 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 来测量运行时间。它可能已经足够快了。

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