Fastest way to match telephony prefixes using asterisk PHP script

Question

and thanks in advance for the help.

Background - I am writing a PHP script that needs to figure out the destination the caller is trying to reach. Telephony prefixes are strings that identify a destination. For each call, the program must find the longest prefix that matches the string. For example the number 30561234567 would be matched by 305 but not by 3057 or 304. If 3056 existed it would be the preferred match.

After investigating several data structures, a tree in which each node stores a digit and contains pointers to the other 10 possible choices seems ideal. This could be implemented as an array of arrays, where the script could check 3, find an array there, then check 0 on that new array, find another array and so on until it finds a value instead of an array. This value would be the destination id (the output of the script).

Requirements - Performance is absolutely critical. Time spent checking these prefixes delays the call, and each server has to handle large amounts of calls, so the data structure must be stored in memory. There are approximately 6000 prefixes at the moment.

Problem - The script is run each time the server receives a call, so the data must be held in a cache server of some sort. After checking memcached and APC (Advanced PHP Cache), I decided to use APC because it is [much faster][3] (it is a local memory store)

The problem I have is that the array of arrays can become up to 10 arrays deep, and will be a very complex data structure that, if I add to the cache as an object, will take a long time to de-serialize.

However if I add every single array to the cache separately (with some logical naming structure to be able to find it easily like 3 for array 3, then 30 for array 30, 305 for the array that follows that patch etc...) I will have to fetch different arrays from the cache many times (up to 10 per call), making me hit the cache too often.

Am I going about this the right way? Maybe there is another solution? Or is one of the methods I have proposed superior to the other?

Thank you for you input,

Alex

Answer 1

Here is some sample code for an N-ary tree structure;

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

this can then be called as

$pre = new PrefixCache();

$pre->addPrefix('304');
$pre->addPrefix('305');
// $pre->addPrefix('3056');
$pre->addPrefix('3057');

echo $pre->matchPrefix('30561234567');

which performs as required (returns 305; if 3056 is uncommented, returns 3056 instead).

Note that I add a terminal-flag to each node; this avoids false partial matches, ie if you add prefix 3056124 it will properly match 3056 instead of returning 305612.

The best way to avoid reloading each time is to turn it into a service; however, before doing so I would measure run-times with APC. It may well be fast enough as is.

Alex: your answer is absolutely correct - but not applicable to this question :)

Answer 2

The way i see it, using a simple array structure should work ok...

Sample code: (note that for performance the prefixes are the keys in the array, not values)

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

Another way would be to query the cache directly for the number - in this case, it could be further optimized:

1. split number string in 2.
2. query that string in the cache.
3. if it doesn't exist, goto 1
4. while it exists, store that value as result, and add another digit.

Snippet: (note that query_cache_for() should be replaced by whatever function your caching mechanism uses)

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

This approach has the obvious advantage that each prefix is a single element in the cache - the key could be 'asterix_prefix_<number>' for example, the value is unimportant (1 works).