simplecontent

PHP Snippets und Beispiele

Inhaltsverzeichnis A-Z Register
Beispiel ausführen

Die größte Übereinstimmung zweier Strings ermitteln

Hier ein einfacher Algorithmus um aus zwei Zeichenketten den längsten gemeinsamen Teilstring zu ermitteln. Halbiere den String B (den kürzeren) und prüfe jeden Teilstring auf Übereinstimmungen in A. Wenn es keine Treffer gibt halbiere erneut usw. Wenn es Treffer gibt werden die Teilstrings gespeichert (jeweils mit ihrer Position in A und B Benachbarte Strings werden "zusammengeklebt". Dann noch zeichenweise an Anfang und Ende auf weitere Übereinstimmungen des Teilstrings in A mit B prüfen und diese ggf. mit Anfügen. Dann den längsten Treffer auswählen. Das klappt auch bei längeren Texten in einer akzeptablen Geschwindigkeit. Zum Vergleich habe ich auch mal die "Holzhammer"-Methode umgesetzt die über zwei for-Schleifen alle möglichen Teilstrings durchgeht. Die ist natürlich erwartungsgemäß bei längeren Zeichenketten hoffnungslos überfordert, und braucht dann gerne mal ein paar Sekunden. Das PHP Code Beispiel:
<?php
/**
* Die größte Übereinstimmung zweier Strings ermitteln
*
*/



// $b = file_get_contents('a.txt');
// $a = file_get_contents('b.txt');

$a = <<< EOT
Hier wird die größte Übereinstimmung von zwei Strings ermittelt.
Also der längste Teiltring welcher in beiden Zeichenketten identisch vorkommt.
EOT;

$b = <<< EOT
Der längste Teilstring welcher identisch vorkommt wird in zwei Strings ermittelt
um die beste Übereinstimmung zu erhalten.
EOT;



function simtext($a, $b)
{
 if (strlen($a)<strlen($b)){
     $tmp = $a;
    $a = $b;
    $b = $tmp;
    unset($tmp);
 }
 $tmp = gimme_some_matches($a, $b);
 $tmp = glue_it($tmp);
 $tmp = expand_right($tmp, $a, $b);
 $tmp = expand_left($tmp, $a, $b);

 $best = '';
 foreach ($tmp as $s){
     if (strlen($s[0])>strlen($best)){
        $best = $s[0];
    }
 }
 return $best;

}


function expand_right($arr, $a, $b)
{
    $stack = array();
    foreach ($arr as $one){

        $n_a = strpos($a, $one[0]);

        $n_b = strpos($b, $one[0]);
        if ($n_a === false || $n_b === false){
            die ("NOPE");
        }

        $pos_a = $n_a + strlen($one[0])+0;
        $pos_b = $n_b + strlen($one[0])+0;
        while (($char_a = substr($a,$pos_a,1)) && 
($char_b = substr($b,$pos_b,1)) && $char_a == $char_b && $char_a != false){
            $pos_a++;
            $pos_b++;
        }

        $one[0] = substr($a, $n_a, ($pos_a-$n_a));
        $stack[] = $one;

    }

    return $stack;
}



function expand_left($arr, $a, $b)
{
    $stack = array();
    foreach ($arr as $one):

        $n_a = strpos($a, $one[0]);

        $n_b = strpos($b, $one[0]);
        if ($n_a === false || $n_b === false){
            die ("NOPE");
        }

        $pos_a = $n_a-1;
        $pos_b = $n_b-1;
        while (($char_a = substr($a, $pos_a, 1)) &&
           ($char_b = substr($b, $pos_b, 1)) &&
            $char_a == $char_b && ($pos_a >= 0)):
            $pos_a--;
            $pos_b--;
        endwhile;

        $one[0] = substr($a, $pos_a+1, ($n_a-$pos_a+strlen($one[0])-1));
        $stack[] = $one;

    endforeach;

    return $stack;
}


function glue_it($arr)
{
    $tmp = array();
    $nbr = count($arr);
    $n = 1;
    $current = 0;
    while ($current < ($nbr) && $n < $nbr){

        if ($arr[$current][1] + strlen($arr[$current][0]) == $arr[$n][1]){
            $arr[$current][0] .= $arr[$n][0];
            unset($arr[$n]);
            $n++;
        }else{
            $current++;
            $n = $current+1;
        }
    }

    return $arr;
}



function gimme_some_matches($a, $b)
{
    $l = floor(strlen($b)/2);
    $hit = false;
    $hits = array();
    while (!$hit && $l > 1 ):

        $tmp = split_string($b, $l);
        foreach ($tmp as $s):

            if (($n = strpos($a, $s[0])) !== false){
                $hit = true;
                $hits[] = array($s[0], $n, $s[1]);

            }
        endforeach;
        $l = ceil($l/2);

    endwhile;

    return $hits;
}

function split_string($s, $len = 1)
{
    $tmp = array();
    $l = strlen($s);

    for ($i = 0; $i < $l; $i += $len){
        $tmp[] = array(substr($s, $i, $len), intval($i));
    }

    if (($l % $len) != 0){
        array_pop($tmp);
    }


    return $tmp;
}

function holzhammer($a, $b)
{
     if (strlen($a)<strlen($b)):
         $tmp = $a;
        $a = $b;
        $b = $tmp;
        unset($tmp);
     endif;

    $stack = array();
    $a_len = strlen($a);
    $b_len = strlen($b);
    $pos = 0;
    $hit_len = 0;
    for ($pos = 0; $pos < $b_len;$pos++):
        for ($i = $b_len;$i > $pos; $i--):
            $c_len = $i - $pos;
            if ($c_len < $hit_len):
                continue;
            endif;
            $cmp = substr($b, $pos, ($c_len));
            if (($n = strpos($a, $cmp)) !== false):
                $hit_len = max(strlen($cmp), $hit_len);
                $stack[] = $cmp;
            endif;
        endfor;
    endfor;
 $best = '';
 foreach ($stack as $s):
     if (strlen($s)>strlen($best)):
        $best = $s;
    endif;
 endforeach;
 return $best;
}


$c = simtext($a, $b);
echo $c;

echo '<hr>';

// Zum Vergleich die Holzhammer-Methode
$c = holzhammer($a,$b);
 echo $c;

?>

Dieses PHP Snippet soll in erster Linie als Beispiel und Anregung für eigene Bemühungen dienen.
Gerne darf man es für Projekte aller Art benutzen.
Möchte jemand das Snippet also solches in ähnlicher oder anderer Form veröffentlichen ist ein kleiner Hinweis auf simplecontent.net nicht zuviel verlangt oder Herr Koch?
Für die Abwesenheit von Fehlern kann natürlich keine Gewähr gegeben werden.