Schnellster Weg, um Telefonie-Präfixe mit dem Asterisk-PHP-Skript abzugleichen

Question

Und danke im Voraus für die Hilfe.

Hintergrund - Ich schreibe ein PHP-Skript, das herausfinden muss, welches Ziel der Anrufer erreichen möchte. Telefoniervorwahlen sind Zeichenfolgen, die ein Ziel identifizieren. Das Programm muss für jeden Anruf die längste Präfix finden, die mit der Zeichenfolge übereinstimmt. Zum Beispiel würde die Nummer 30561234567 von 305, aber nicht von 3057 oder 304 übereinstimmen. Wenn 3056 existierte, wäre dies das bevorzugte Ergebnis.

Nachdem ich mehrere Datenstrukturen untersucht habe, scheint ein Baum, in dem jeder Knoten eine Ziffer speichert und Verweise auf die anderen 10 möglichen Optionen enthält, ideal zu sein. Dies könnte als Array von Arrays implementiert werden, in dem das Skript 3 überprüfen könnte, ein Array dort finden, dann 0 in diesem neuen Array überprüfen könnte, ein weiteres Array finden und so weiter, bis es einen Wert anstelle eines Arrays findet. Dieser Wert wäre die Ziel-ID (die Ausgabe des Skriptes).

Anforderungen - Leistung ist absolut kritisch. Die Zeit, die für die Überprüfung dieser Präfixe aufgewendet wird, verzögert den Anruf, und jeder Server muss eine große Anzahl von Anrufen verarbeiten, daher muss die Datenstruktur im Speicher gespeichert werden. Es gibt derzeit ungefähr 6000 Präfixe.

Problem - Das Skript wird jedes Mal ausgeführt, wenn der Server einen Anruf empfängt, daher müssen die Daten in einem Cache-Server von irgendeiner Art gespeichert werden. Nachdem ich memcached und APC (Advanced PHP Cache) überprüft habe, habe ich mich entschieden, APC zu verwenden, weil es [viel schneller][3] ist (es handelt sich um einen lokalen Speicher).

Das Problem, das ich habe, ist, dass das Array von Arrays bis zu 10 Ebenen tief werden kann und eine sehr komplexe Datenstruktur darstellt, die, wenn ich sie als Objekt dem Cache hinzufüge, lange Zeit braucht, um deserialisiert zu werden.

Wenn ich jedoch jedes einzelne Array einzeln in den Cache hinzufüge (mit einer logischen Namensstruktur, um es einfach finden zu können, z.B. 3 für Array 3, dann 30 für Array 30, 305 für das Array, das diesen Pfad folgt usw.), muss ich verschiedene Arrays mehrmals aus dem Cache abrufen (bis zu 10 pro Anruf), was dazu führt, dass ich den Cache zu oft treffe.

Gehe ich das Richtige an? Vielleicht gibt es eine andere Lösung? Oder ist eine der von mir vorgeschlagenen Methoden der anderen überlegen?

Danke für Ihre Meinung,

Alex

Answer 1

Meiner Ansicht nach sollte es mit einer einfachen Array-Struktur funktionieren...

Beispielcode: (Beachten Sie, dass aus Leistungsgründen die Präfixe die Schlüssel im Array sind, nicht die Werte)

// $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";
  // Versuche das längste passende Präfix für $number zu finden
  while ($number != '') {
    if (isset($keys[$number]))
      break;
    // noch nicht gefunden, ziehe die letzte Ziffer ab
    $number = substr($number, 0, -1);
  }
  return $number;
}

Eine andere Möglichkeit wäre, die Daten direkt aus dem Cache abzurufen - in diesem Fall könnte es weiter optimiert werden:

1. Nummernzeichenfolge in 2 aufteilen.
2. Die Zeichenfolge im Cache abfragen.
3. Wenn sie nicht existiert, wieder bei 1 starten
4. Solange sie existiert, diesen Wert als Ergebnis speichern und eine weitere Ziffer hinzufügen.

Ausschnitt: (Beachten Sie, dass query_cache_for() durch die Funktion ersetzt werden sollte, die Ihr Caching-Mechanismus verwendet)

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; // sollte nicht passieren!
  }
  while ($found) {
    $result = $temp;
    // füge eine weitere Ziffer hinzu
    $temp .= substr($number, strlen($temp), 1);
    $found = query_cache_for($temp);
  }
  return $result;
}

Dieser Ansatz hat den offensichtlichen Vorteil, dass jedes Präfix ein einzelnes Element im Cache ist - der Schlüssel könnte beispielsweise 'asterix_prefix_' sein, der Wert ist unwichtig (1 funktioniert).

Answer 2

Hier ist ein Beispielcode für eine N-äre Baumstruktur;

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

dies kann dann aufgerufen werden als

$pre = new PrefixCache();

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

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

was wie erforderlich funktioniert (gibt 305 zurück; wenn 3056 nicht auskommentiert ist, gibt es stattdessen 3056 zurück).

Beachten Sie, dass ich jedem Knoten ein Terminal-Flag hinzufüge; dies vermeidet falsche partielle Übereinstimmungen, d. h. wenn Sie das Präfix 3056124 hinzufügen, wird es ordnungsgemäß mit 3056 anstatt mit 305612 übereinstimmen.

Der beste Weg, um ein erneutes Laden jedes Mal zu vermeiden, besteht darin, es in einen Dienst umzuwandeln; bevor dies jedoch getan wird, würde ich die Laufzeiten mit APC messen. Es könnte durchaus schnell genug sein, wie es ist.

Alex: Deine Antwort ist absolut korrekt - aber nicht auf diese Frage anwendbar :)

Answer 3

Da du nur mit Zahlen arbeitest, ist es möglicherweise ineffizient, direkt mit Zeichenfolgen zu arbeiten.

Sie könnten einen Binärsuchalgorithmus durchführen. Wenn Sie alle Ihre Präfixe (numerisch), auf 15 Stellen aufgefüllt und dann in der Reihenfolge, speichern, können Sie ungefähr log2(6000)~=13 Schritte benötigen, um 6000 Codes zu durchsuchen.

Zum Beispiel, wenn Sie die folgenden Codes haben:

• 01, 0127, 01273, 0809, 08

Würden Sie folgendes in einem Array speichern:

1. 010000000000000
2. 012700000000000
3. 012730000000000
4. 080000000000000
5. 080900000000000

Die Schritte wären:

1. Eingehende Nummer auf 15 Stellen reduzieren.
2. Führen Sie eine binäre Suche durch, um den nächstniedrigeren Code (und seinen Index im obigen Array) zu finden.
3. Schauen Sie die Länge des Codes in einem separaten Array nach (unter Verwendung des Index).

Einige Beispielcode, um es in Aktion zu sehen:

// Beispiel für Präfixe 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);

    // Binäre Suche
    $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 'Ungültiges Präfix';
    } else {
        return substr($prefixes[$prefix_index], 0, $prefix_lengths[$prefix_index]);
    }
}

Answer 4

Ich mache das, indem ich eine Hashtable von String, Ziel verwende, wobei die Schlüssel Strings sind, die das Präfix des Ziels darstellen. Der entscheidende Faktor ist, dass die Hashtable sortiert sein muss, so dass die längsten Strings zuerst überprüft werden. Sobald ein übereinstimmendes Präfix gefunden wird, ist das Ziel des Anrufs bekannt.

Ich habe tatsächlich auch eine Runde regulärer Ausdrücke, die für kompliziertere Ziele sind und die regulären Ausdrücke überprüfen, bevor die Zielpräfixe überprüft werden.

Ich habe nicht gemessen, wie lange es dauert, einen Treffer zu bekommen, aber ich vermute max. 15ms. Der gesamte Prozess, das Ziel zu überprüfen, dann den Kontostand des Benutzers und schließlich eine Anrufzeitbegrenzung festzulegen, dauert ca. 150ms. In meinem Fall verwende ich FastAGI und C# Windows-Dienst. Solange es weniger als 500ms dauert, wird es für Ihre Benutzer unbemerkt bleiben.

Answer 5

Ich betreibe auch eine Telefonieanwendung... was ich getan habe, ist eine interne REST-API zur Verfügung zu stellen, um diese aufzurufen, dies ist was bekannte Telefonnummern zwischenspeichert und alle Prefix-Überprüfungen durchführt.

Ich gehe auch davon aus, dass Sie auch nach Ländervorwahlen suchen. Es gibt nur wenige sich überschneidende Ländervorwahlen mit dem NANP. Daher suche ich zuerst nach einem NANP und mache einen Schnellabgleich mit der Anzahl der folgenden Zahlen (7), um sicherzustellen, ansonsten falle ich auf eine Ländervorwahl zurück. Ich habe dann eine grobe Vorstellung davon, wie viele Zahlen eine Telefonnummer in jedem Land haben soll, über einen regulären Ausdruck.

Ich verwende ein XML-Dokument und gleiche auf XPath ab, dann zwischenspeichere ich das Ergebnis, wenn möglich.

Das Gute am Verwenden einer REST-API ist auch, dass sie verwendet werden kann, um Nummern zu bereinigen, bevor ich sie in der Datenbank für die Abrechnung speichere.

Es ist keine exakte Wissenschaft, aber es scheint zu funktionieren.