İşte bir N-li ağaç yapısı için bazı örnek kod;

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

bu daha sonra da adlandırılabilir

$pre = new PrefixCache();

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

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

gerektiği gibi (ki 305 döndürür; 3056 uncommented ise, bunun yerine 3056 döndürür) gerçekleştirir.

Ben her düğüm için bir terminal-bayrak ekleyin unutmayın; Eğer önek 3056124 eklerseniz, bu yanlış kısmi eşleşmeleri önler, yani düzgün yerine 305.612 dönen 3056 maç olacak.

Her zaman yeniden önlemek için en iyi yolu hizmete açmak için; Ancak, bunu yapmadan önce ben APC ile çalışma sürelerini ölçmek istiyorsunuz. Biliyorsunuz yeterince hızlı olarak olabilir.

Alex: Cevabınız kesinlikle doğru - ama bu soruya geçerli değildir :)

Ben basit bir dizi yapısını kullanarak, onu görmek yolu ok çalışması gerekir ...

Örnek kod: (performans için önek dizi değil, değerleri anahtarı olduğunu unutmayın)

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

Başka bir yol numarası için doğrudan önbellek sorgulamak olur - bu durumda, bu daha da optimize edilebilir:

1. 2 sayı dize bölmek.
2. önbellek bu dize sorgulamak.
3. o yoksa goto 1
4. while it exists, store that value as result, and add another digit.

Pasajı: ((ki query_cache_for unutmayın) önbelleğe alma mekanizması kullanır ne olursa olsun işlevi tarafından değiştirilmesi gerektiğini)

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

Bu yaklaşım, her önek önbellekte tek bir unsurdur bariz bir avantaja sahiptir - anahtarı, örneğin 'asterix_prefix_ ' olabilir, değer (1 çalışır) önemsizdir.

Ben tuşları hedef önek temsil dizeleri dize, hedef bir hashtable kullanarak bunu. Kritik faktör, en uzun şeritler ilk olarak kontrol edilir, böylece hashtable sıralanması olmasıdır. En kısa sürede bir eşleşen önek olarak bulunursa çağrı hedef bilinmektedir.

Bunu da daha kıvrık yer için normal ifadelerin bir yuvarlak var ve hedef önekleri önce düzenli ifadeler kontrol edin.

Ben bir maçı almak için ne kadar sürer ölçülen değil ama 15ms max sanıyorum. Desitnation kontrol ve daha sonra kullanıcının dengesi ve nihayet bir çağrı zaman sınırı ayarı tüm süreç 150ms sürer. Benim durumumda FastAGI ve C # Windows hizmetini kullanıyorum. Sürece az 500ms almak gibi sizin kullanıcılara impercetible olacaktır.

Ben de bir telefon uygulamayı çalıştırmak ... ben ne yaptım aramak için dahili bir REST API sağlanır, bu bilinen telefon numaralarını önbelleğe ve önek denetimi yapacağız budur.

Ayrıca ben de ülke kodları arıyoruz varsayalım. NANP ile birkaç örtüşen ülke kodları vardır. Yani ben başka bir ülke koduna geri düşmek, bir NANP için ilk bakmak, ve (7) emin olmak için aşağıdaki numaralardan sayısında hızlı bir maç yapmak. Sonra bir telefon numarasına her ülkenin düzenli bir ifade ile olması gerekiyordu kaç sayı aa kaba bir fikrim yok.

Ben mümkün olduğunda sonra XPath sonucunu önbelleğe alma, XPath bir XML belgesi ve eşleştirme kullanıyorum.

De bir REST API kullanarak serin şey hakkında, ben fatura için DB saklayabilirsiniz önce sayıları temizlemek için kullanılabilir olmasıdır.

Bu kesin bir bilim değil ama iş gibi görünüyor.

Uzun ortak dizilerine bulma dinamik programlama klasik bir uygulamadır. Çözelti O (n) 'dir. http://en.wikipedia.org/wiki/Longest%5Fcommon%5Fsubsequence%5Fproblem

Eğer sadece numaraları ile çalışıyoruz beri, belki dizeleri ile doğrudan çalışan verimsiz.

Bir ikili arama algoritması gerçekleştirebilir. Tüm önekleri (sayısal) saklıyorsanız, 15 yerlere doldurulur ve daha sonra sırayla, yaklaşık log2 (6000) ~ = 13 adım 6000 kodlarını tarayabilirsiniz.

Örneğin aşağıdaki kodları varsa:

• 01, 0127, 01273, 0809, 08

Siz bir dizi aşağıdaki saklamak istiyorsunuz:

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

Adımlar olacaktır:

1. Strip incoming number down to 15 places.
2. Perform binary search to find the nearest lowest code (and it's index in the array above)
3. Look up the length of the code in a separate array (using the index)

Eylem görmek için bazı örnek kod:

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