Längste gemeinsame Teilfolge (LCS) in PHP

Längste gemeinsame Teilfolge – Rekursive Umsetzung des LCS Problems in PHP – Hauptprogramm, Initialisierung, Berechnung der LCS Anzahl und Ausgabe der Folge.

Inhaltsverzeichnis

Hauptprogramm – lcs.php

Erklärung der Pfeile

Initialisierungsprogramm – LCS_initial.php

Berechnung der LCS Anzahl – LCS_rekursiv.php

Ausgabe der LCS Folge

Programmausgabe

Test mit anderen Folgen

Ergebnis der anderen Folgen

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

https://de.wikipedia.org/wiki/Optimierungsproblem

https://de.wikipedia.org/wiki/Dynamische_Programmierung

Längste gemeinsame Teilfolge (LCS) in PHP

Hauptprogramm – lcs.php

Einbinden aller Hilfsfunktionen
Deklaration der LCS Folgen $x und $y
LCS Indizes sollen mit 1 und nicht mit 0 starten
Deswegen Leerzeichen und Trennung des Strings in ein Array
Aufruf der Initialisierungsmethode
Ausgabe der zweidimensionalen Matrix $c und $b
$c enthält die Anzahl an gefundenen LCS (Integer)
$b enthält den Pfad / Pfeile zur Ausgabe der Zeichenkette der Lösung
Funktionsaufruf zur Ausgabe der Lösung

<?php

include("Gib_LCS_aus.php");
include("LCS_initial.php");
include("LCS_rekursiv.php");

// First Element must be empty space
$x = " ABCBDAB";
$y = " BDCABA";

// Convert String to Array
$x = str_split($x, 1);
$y = str_split($y, 1);
// Delete the first Element - empty space
// Let the Array beginn with index 1 - first character
unset($x[0]);
unset($y[0]);

LCS_initial($x, $y, $c, $b);

print_r($c);
print_r($b);


$ausgabe = Gib_LCS_aus($x, $b, sizeof($x), sizeof($y));
echo $ausgabe;

?>

Erklärung der Pfeile

Rekonstruktion der Ergebnisreihenfolge

https://algorithms.tutorialhorizon.com/dynamic-programming-longest-common-subsequence/

Initialisierungsprogramm – LCS_initial.php

Zweidimensionales Array $c initialisieren (Speicherung der Anzahl an gefundenen LCS)
Erste Spalte und Zeile des Arrays $c muss 0 sein, da hieraus alle anderen Werte abgeleitet werden
und zudem es bei der Länge 0 keine gefundene LCS geben kann, erst ab Länge 1
Alle anderen Werte mit -1 initialisieren (Normaler Wertebereich ab 0)
Ausgabe der Arrays mit den beiden LCS Folgen $x und $y
Aufruf der LCS_rekursiv Funktion zur Ermittlung der Anzahl an gefundenen Übereinstimmungen
Ausgeben des Integer Wertes (Anzahl gefundene LCS)

<?php

function LCS_initial($x, $y, $c, $b) {

  echo "Funktionsaufruf LCS_initial mit Parametern x $x y $y c $c b $b\n";

  // Erste Spalte ist Null
  // Bei Laenge 0 gibt es keine LCS
  for($i = 0; $i < sizeof($x); $i++) {
    $c[$i][0] = 0;
  }

  // Erste Zeile ist Null
  for($j = 1; $j < sizeof($y); $j++) {
    $c[0][$j] = 0;
  }

  // Alle anderen Werte werden mit -1 initialisiert
  for($i = 1; $i < sizeof($x); $i++) {
    for($j = 1; $j < sizeof($y); $j++) {
      $c[$i][$j] = -1;
    }
  }

  echo "Funktionsaufruf LCS_rekursiv mit Parametern x $x y $y c $c b $b\n";
  echo "sizeof x ".sizeof($x)." sizeof y ".sizeof($y)."\n";

  print_r($x);
  print_r($y);

  $anzahl = LCS_rekursiv($x, $y, $c, $b, sizeof($x), sizeof($y));
  echo "LCS Anzahl ist $anzahl\n";

}

?>

Berechnung der LCS Anzahl – LCS_rekursiv.php

Wenn der Wert von $c[$i][$j] bereits bestimmt wurde, ist dieser größer als -1
dann kann man sich die erneute Berechnung sparen
$i und $j dürfen nicht negativ sein, da $i die aktuelle Position auf Array $x und $j für $y widerspiegelt
Wenn die beiden realen LCS Zeichen übereinstimmen wurde ein Ergebnis gefunden
erhöhe die Anzahl in Ergebnismatrix $c um eins (bei jeder Erhöhung wurde eine weitere LCS gefunden)
Wenn Zeichen übereinstimmen berechnet sich der Wert aus dem Zeichen oben links (diagonal davon) + 1
Speichere den Pfeil als „d“ ab – diagonal / oben links
Wird für die Rückführung auf die Ergebnis Zeichenkette benötigt
Wenn Zeichen nicht übereinstimmen prüfe den Wert links und überhalb – der eigentliche Rekursionsschritt
Übernehme das Maximum aus Zeichen links und überhalb (Speichere Pfeil links oder oben)
Schritt weiter bis wieder ein übereinstimmendes Zeichen gefunden wurde oder die ursprüngliche Zeichenkette endet

<?php

// Komplexitaet Theta n mal m

// Kodierung der Pfeile / Pfade - b
// links - l
// oben - o
// links oben / diagonal - d

// x ist Zeichenkette / eindimensionales Array Nummer 1
// y ist Zeichenkette / eindimensionales Array Nummer 2
// c ist das zweidimensionale Array mit der Laenge der LCS (integer Werte)
// b ist das zweidimensionale Array mit Richtungen der Pfeile (links, oben, oben links / diagonal)
// Die Pfeile werden benoetigt um die Ergebnis Folge korrekt auszugeben
// i ist die aktuelle Position auf dem Array x
// j ist die aktuelle Position auf dem Array y

function LCS_rekursiv($x, $y, $c, $b, $i, $j) {

  global $c, $b;

  echo "Funktionsaufruf LCS_rekursiv mit Parametern x $x y $y c $c b $b i $i j $j\n";
  //print_r($c);

  // Wenn Wert schon berechnet - direkt zurueckgeben ohne erneute Berechnung
  if($c[$i][$j] > -1) {
    return $c[$i][$j];
  }

// i oder j darf nicht negativ sein - echt groesser
if($i > 0 && $j > 0) {
  // Wenn Zeichen uebereinstimmen - LCS gefunden - Wert oben links + 1 und in c abspeichern
  // In b wird Nummer 3 abgespeichert - Nummer 3 steht fuer einen Pfeil nach oben links
  if($x[$i] == $y[$j]) {
   $c[$i][$j] = LCS_rekursiv($x, $y, $c, $b, $i - 1, $j - 1) + 1;
   echo "Zeichen gleich i $i j $j c i j ".$c[$i][$j]."\n";
   $b[$i][$j] = "d";
  }
  // Wenn Zeichen nicht uebereinstimmen
  else {
    // Berechne Wert links davon
    $a = LCS_rekursiv($x, $y, $c, $b, $i - 1, $j);
    // Berechne Wert oberhalb
    $d = LCS_rekursiv($x, $y, $c, $b, $i, $j - 1);

    // Wenn linker Wert groesser als Wert oberhalb
    if($a >= $d) {
      $c[$i][$j] = $a;
      // Speichere Pfeil nach links - Kodiert als 1
      $b[$i][$j] = "l";
    }
    else {
      $c[$i][$j] = $d;
      // Speichere Pfeil nach oben - Kodiert als 2
      $b[$i][$j] = "o";
    }
}
  return $c[$i][$j];

  }

}

?>

Ausgabe der LCS Folge

Aus der Matrix mit den Pfeilen $b kann die Ergebnisfolge extrahiert werden
Nullen müssen nicht betrachtet werden – keine LCS gefunden
Wenn ein diagonaler Pfeil gefunden wurde (zeigt nach oben links) wurde der erste LCS Wert gefunden (Char aus Array $x)
Sonst wird bei einem linken Pfeil weiter nach links gelaufen ($i – 1)
oder bei einem Pfeil nach oben dieser Weg weiter gegangen

<?php

// Komplexitaet Theta n + m

function Gib_LCS_aus($x, $b, $i, $j) {

  echo "Funktionsaufruf Gib_LCS_aus x $x b $b i $i j $j\n";

  if($i == 0 OR $j == 0) {
    return;
  }

  if($b[$i][$j] == "d") {
    Gib_LCS_aus($x, $b, $i - 1, $j - 1);
    echo $x[$i];
  }
  else {
    if($b[$i][$j] == "l") {
      Gib_LCS_aus($x, $b, $i - 1, $j);
    }
    else {
      Gib_LCS_aus($x, $b, $i, $j - 1);
    }
  }

}

?>

Programmausgabe

Ausgabe der ursprünglichen Zeichenfolge $x und $y beginnend mit Stelle 1
Viele rekursive Funktionsaufrufe
Finden eines doppelt vorkommenden Zeichens
Ausgabe der LCS Anzahl 4 – in diesem Fall mit den $x und $y Werten
Ausgabe der Matrix $c mit der Anzahl an gefundenen LCS
Ausgabe der Matrix $b mit den Pfeilen / dem Weg zur Ergebnisfolge der Char Stellen des Arrays
Ausgabe der Funktionsaufrufe / dem Weg zum Ziel der Pfeile
Ausgabe der Lösung BCBA – in diesem Fall $x und $y

Test mit anderen Folgen

Hauptprogramm wird für $x und $y angepasst. Andere Funktionsdateien bleiben gleich.

<?php

include("Gib_LCS_aus.php");
include("LCS_initial.php");
include("LCS_rekursiv.php");

// First Element must be empty space
//$x = " ABCBDAB";
//$y = " BDCABA";

$x = " 10010101";
$y = " 010110110";

// Convert String to Array
$x = str_split($x, 1);
$y = str_split($y, 1);
// Delete the first Element - empty space
// Let the Array beginn with index 1 - first character
unset($x[0]);
unset($y[0]);

LCS_initial($x, $y, $c, $b);

print_r($c);
print_r($b);


$ausgabe = Gib_LCS_aus($x, $b, sizeof($x), sizeof($y));
echo $ausgabe;

?>

Ergebnis der anderen Folgen

Längste gemeinsame Teilfolge (LCS) in PHP

Hauptprogramm – lcs.php

Erklärung der Pfeile

Initialisierungsprogramm – LCS_initial.php

Berechnung der LCS Anzahl – LCS_rekursiv.php

Ausgabe der LCS Folge

Programmausgabe

Test mit anderen Folgen

Ergebnis der anderen Folgen

About The Author

mattionline

Kommentar verfassen Kommentieren abbrechen