PHP nasıl iki dizeleri arasındaki büyük Ortak Altdiziden bulabilirim?

6 Cevap php

Iki dizeleri büyük Ortak Altdiziden bulmak için hızlı bir algoritma var mı yoksa bir NPComplete sorundur?

PHP, bir samanlıkta iğne bulabilirsiniz:

<?php

if (strstr("there is a needle in a haystack", "needle")) {
    echo "found<br>\n";
}
?>

Ben dizelerinden biri üzerinde bir döngü içinde bunu sanırım ama çok pahalı olurdu! Bu benim uygulama e-postanın bir veritabanı arama ve spam (aynı kişi tarafından gönderilen yani benzer e-postalar) bakmaktır Özellikle beri.

Kimse onlar orada dışarı atmak herhangi bir PHP kodu var mı?

6 Cevap

Ben beri bulduk a relevant wikipedia article. Bu bir dinamik programlama algoritması kullanılarak O (mn) zaman yapılabilir, NP tam problem değil.

PHP ben similar_text function çok yararlı buldum. İşte metin e-posta ve içlerinden döngü bir dizi almak ve birbirine% 90 benzer olanları bulmak için bir kod örneği var. Note: Something like this is NOT scalable,

<?php
// Gather all messages by a user into two identical associative arrays
$getMsgsRes = mysql_query(SELECT * FROM email_messages WHERE from = '$someUserID');
while($msgInfo = mysql_fetch_assoc($getMsgsRes))
{
    $msgsInfo1[] = $msgInfo;
    $msgsInfo2[] = $msgInfo;
}

// Loop over msgs and compare each one to every other
foreach ($msgsInfo1 as $msg1)
    foreach ($msgsInfo2 as $msg2)
    	similar_text($msg1['msgTxt'],$msg2['msgTxt'],$similarity_pst);
    	if ($similarity_pst > 90)
    		echo "{$msg1['msgID']} is ${similarity_pst}% to {$msg2['msgID']}\n";
?>

similar_text fonksiyonu istediğiniz ne olabilir.

Bu iki dizeleri arasındaki benzerliği hesaplar. Her iki dizeleri eşleşen karakter sayısını döndürür

Ayrıca levenshtein bakmak isteyebilirsiniz

Bu benim uygulama e-postanın bir veritabanı arama ve spam (aynı kişi tarafından gönderilen yani benzer e-postalar) bakmaktır Özellikle beri.

Ben uzun ortak alt dize mutlaka, Bayesian spam çıkarım algoritmaları değil bakıyor gerektiğini düşünüyorum.

http://www.devshed.com/c/a/PHP/Implement-Bayesian-inference-using-PHP-Part-1/

Vikikitap'taki Algorithm implementation/Strings/Longest common substring bir göz atınız. Ben PHP uygulama test değil ama Vikipedi sayfasında genel algoritması maç gibi görünüyor.

Burada bu partiye geç, ama dizeleri bir dizi büyük ortak altdizesine bulmak için bir yoldur.

http://www.christopherbloom.com/2011/02/24/find-the-longest-common-substring-using-php/

Bu cevapların bazıları aşırı biraz karmaşık gibi görünüyor. Ben şahsen bu kullanın:

function getShortestCommonString(array $strings, &$result) {

  $result = $strings[0];

  array_walk($strings, function($item){
    global $result;
    $result = substr($result, 0, similar_text($result, $item));
  });

}

Bu böyle seslendi:

<?php

$strings = array(
  'thisisone',
  'thisistwo',
  'thisithree',
  'thisfour',
  'thifive'
);
$result = '';

getShortestCommonString($strings, $result);
echo $result;

Bu çıkış vererek:

thi

etiketler