最快的方式匹配的电话使用的前缀号PHP script

https://stackoverflow.com/questions/1489487

18-09-2019
|

题

并预先感谢所有帮助。

背景 - 我正在写一PHP script，需要找出目的地的来电是试图达到。电话前缀字符识别的目的地。各程序必须找到最长的前缀相匹配。例如数30561234567会，以此配合305但不是通过3057或304。如果3056存在，这将是优选的匹配。

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

要求 - 性能是绝对至关重要的。花费的时间检查这些前缀延误的呼吁，每一个服务器已经处理大量的电话，所以数据结构必须保存在记忆。大约有6000前缀的时刻。

的问题 - 脚本是每次运行服务器接收到一个电话，所以数据必须保持在一个高速缓存服务器。在检查之后缓存和APC(高级PHP缓)，我决定使用APC，因为它是[更快][3](这是一个当地的存储器中存储)

我的问题是，列阵列可以成为达到10阵列深，并且将是一个非常复杂的数据结构，如果我加入到缓存作为一个目的，将需要很长的时间来de-serialize.

然而，如果我添加的每一单列的高速缓存分(有一些逻辑命名结构能够很容易地找到它喜欢3列3，然后30阵30,305阵列如下，修补等等...)我将不得不取不同的阵列从高速缓冲多次(最多10每次呼叫)，使我打高速缓存太多。

我会约这个正确的方式？也许还有另一种解决方案吗？或是一种方法，我们建议优于其他?

谢谢你的投入，

亚历克斯

解决方案

下面是用于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它可以正确匹配，而不是返回305612 3056。

，以避免重新加载，每次是将其变为一个服务的最佳方式;然而，在这方面，我会用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;
}

另一个办法是查询缓直接的号码-在这种情况下，它可以进一步优化：

分拆数字符串中2.
查询这个字符串中的高速缓存。
如果不存在，goto1
同时，它的存在、储存价值作为结果，并添加另一位数。

片段：(注意，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

你会商店下面的一个阵列：

010000000000000
012700000000000
012730000000000
080000000000000
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]);
    }
}

我通过使用串，目的地的散列表，其中键是代表目标的前缀字符串做到这一点。关键的因素是，哈希表必须进行排序，使最长的字符串第一个测试。一旦匹配前缀发现呼叫目的地是已知的。

其实，我也有更多的令人费解的目的地圆正则表达式和目标前缀之前检查正则表达式。

我没有测量需要多长时间获得一个比赛，但我怀疑15ms的最大值。检查desitnation，然后在用户的天平终于呼叫设置时间限制的，整个过程大约需要150毫秒。在我来说，我使用FastAGI和C＃Windows服务。只要你把超过500ms少这将是impercetible给用户。

我也办一个电话应用......我所做的是提供一个内部REST API调用，这是将缓存知道电话号码和做所有的前缀检查。

此外，我认为你正在寻找的国家代码为好。有与NANP只有几个重叠的国家代码。所以，我先看看一个NANP，并做以下电话号码（7），以确保数量的快速匹配，否则我回落到一个国家代码。然后，我有一个每个国家是如何在一个电话号码多的数字应该有通过正则表达式一个大概的了解。

我使用XPath的XML文档和匹配，那么高速缓存中的XPath结果时可能的。

有关使用REST API以及很酷的事情是，它可以用来之前，我在DB存放，以备结算清理号码。

这是不是一门精确的科学，但它似乎工作。

寻找最长公共子序列是动态编程的一个传统的应用程序。该解决方案是O（n）。 http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow