6

并提前感谢您的帮助。

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

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

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

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

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

但是，如果我将每个数组分别添加到缓存中（使用一些逻辑命名结构可以轻松找到它，例如数组 3 的 3，数组 30 的 30，补丁后的数组的 305 等）我将不得不多次从缓存中获取不同的数组（每次调用最多 10 个），这使我经常访问缓存。

我会以正确的方式解决这个问题吗？也许还有另一种解决方案？还是我提出的一种方法优于另一种？

谢谢你的输入，

亚历克斯

4

6 回答 6

2

我看到它的方式，使用一个简单的数组结构应该可以工作......

示例代码：（请注意，为了性能，前缀是数组中的键，而不是值）

// $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 有效）。

于 2009-09-28T22:32:52.570 回答
2

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

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

于 2009-09-28T23:35:33.223 回答
1

由于您只使用数字，因此直接使用字符串可能效率低下。

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

例如，如果您有以下代码：

  • 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]);
    }
}
于 2009-09-29T11:59:11.683 回答
0

我通过使用字符串的哈希表来做到这一点，其中键是代表目标前缀的字符串。关键因素是必须对哈希表进行排序，以便首先检查最长的字符串。一旦找到匹配的前缀，就知道呼叫目的地。

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

我没有测量匹配需要多长时间，但我怀疑最多 15 毫秒。从查询目的地到用户余额到最后设置通话时限的整个过程大约需要150ms。就我而言，我使用的是 FastAGI 和 C# Windows 服务。只要您花费的时间少于 500 毫秒，您的用户就无法察觉。

于 2009-09-28T21:44:49.503 回答
0

我还运行一个电话应用程序......我所做的是提供一个内部 REST API 来调用，这将缓存已知电话号码并进行所有前缀检查。

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

我正在使用 XML 文档并在 XPath 上进行匹配，然后尽可能缓存 XPath 结果。

使用 REST API 的一个很酷的事情是，它可以在我将数字存储在数据库中进行计费之前清理它们。

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

于 2009-09-28T21:55:42.800 回答
0

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

于 2009-09-28T22:52:49.970 回答