[QUIZ#1] ZodiacXP (PHP)

[ZodiacXP]

Ich hoffe der Code erklärt sich von selbst
Das ganze kann man ganz kurz und schnell über RegExp lösen:

// Die gesamten Daten auslesen
$sHaystack = file_get_contents("president.txt");

// Hier wird der Suchbegriff festgelegt
$sFind = "JFK";

/* Suchbegriff unscharf machen, indem auch alle Zeichen
 * selektiert werden, die nicht einem Umbruch oder Wagenrücklauf
 * entsprechen.
 */
$sPattern = "/[^\\r\\n]*" . preg_replace("/([A-Z]|[a-z])\s*/", "$1[^\\r\\n]*", $sFind) . "/s";
// Anwenden auf den ausgelesenen Dateiinhalt
// und alle Fundstellen in $aMatch speichern
preg_match_all($sPattern, $sHaystack, $aMatch);

// Erweiterung
function Extension(&$s, $sKey, $sFind) {
	// vorberechnen der Länge für eine schnellere Schleife
	$len = strlen($sFind);
	// Vorbereitung des Suchergebnisses, damit
	// erstes und letztes Zeichen berücksichtigt
	// werden können für das folgende Pattern
	$s = " ".$s." ";
	// Jedes einzelne Zeichen des Suchberiffs durchgehen
	for ($i = 0; $i < $len; $i++) {
		// Beim ersten vorkommen dieses Zeichens
		// im aktuellen Suchergebnis < und > drum herum setzen
		$s = preg_replace("/([^<])(".$sFind[$i].")/", "$1<$2>", $s, 1);
	}
	// aufeinanderfolgende hervorhebungen entfernen (kein "><")
	// aus: <F><o><o> wird <Foo>
	$s = str_replace("><", "", $s);
	// Anfangs gesetzte leerzeichen entfernen
	$s = trim($s);
}

// die Funktion für jedes einzelne Element (Suchergebnis) durchlaufen
array_walk($aMatch[0], "Extension", $sFind);

// gewünschte Ergebnis liegt nun in $aMatch[0] bereit
// hier eine kleine Ausgabe:
echo "<pre>";
echo htmlspecialchars(print_r($aMatch, true));
echo "</pre>";

 

[ZodiacXP]

Hier die optimierte Form für alle als kurze Funktion:

function fuzzy($sHaystack, $sNeedle) {
  $sPattern = "/[^\\r\\n]*" . preg_replace("/(.)\s*/", "$1[^\\r\\n]*", $sNeedle) . "/s";
  preg_match_all($sPattern, $sHaystack, $aMatch);

  $len = strlen($sNeedle);
  for ($i = 0; $i < $len; $i++) $aMatch[0] = preg_replace("/(?=[^<])(".$sNeedle[$i].")(?=[^>])/", "<$1>", $aMatch[0], 1);

  return str_replace("><", "", $aMatch[0]);
}

Und hier mit Erklärungen und Ausgabe:

<?php
$sHaystack = file_get_contents("president.txt");
$sFind = "oooo";

function fuzzy($sHaystack, $sNeedle) {
  // unscharfes Pattern anlegen und suchen
  $sPattern = "/[^\\r\\n]*" . preg_replace("/(.)\s*/", "$1[^\\r\\n]*", $sNeedle) . "/s";
  preg_match_all($sPattern, $sHaystack, $aMatch);

  // jedes zeichen von dem Suchstring durchgehen
  $len = strlen($sNeedle);
  for ($i = 0; $i < $len; $i++) {
  	// erstes vorkommen des aktuellen Zeichens mit < und > hervorheben
  	$aMatch[0] = preg_replace("/(?=[^<])(".$sNeedle[$i].")(?=[^>])/", "<$1>", $aMatch[0], 1);
  }

  // aufeinanderfolgende hervorhebungen entfernen und array liefern
  // <F><o><o> wird zu <Foo>
  return str_replace("><", "", $aMatch[0]);

}

echo "<pre>";
echo htmlspecialchars(print_r(fuzzy($sHaystack, $sFind), true));
echo "</pre>";
?>

Passt für die Aufgabe wunderbar, lass ich auch so. Um ein Array als Haystack zu nutzen sollte man es mit join("\n", $arr) übergeben.

 

[Matthias Reitinger]

  $sPattern = "/[^\\r\\n]*" . preg_replace("/(.)\s*/", "$1[^\\r\\n]*", $sNeedle) . "/s";

Drei Anmerkungen hierzu:

1. Wieso verwendest du die Zeichenklasse [^\r\n] und den Modifikator s? Wenn du stattdessen . verwendest und den Modifikator weglässt, sollte doch dasselbe rauskommen.
2. Den gierigen * hier zu verwenden ist eine schlechte Idee, da das zu jeder Menge Backtracking führt, vor allem da du den kompletten Dateiinhalt durchsuchst.
3. Was passiert, wenn im Suchbegriff Regex-Steuerzeichen enthalten sind? Das müsste man entsprechend abfangen.

  return str_replace("><", "", $aMatch[0]);

Das klappt leider nicht immer. Was passiert, wenn die Zeichenfolge >< schon vorher im zu durchsuchenden String vorhanden war? Diese dürfte ja dann nicht entfernt werden.

Grüße,
Matthias

 

[ZodiacXP]

Wieso verwendest du die Zeichenklasse [^\r\n] und den Modifikator s? Wenn du stattdessen . verwendest und den Modifikator weglässt, sollte doch dasselbe rauskommen.

Jau stimmt. Danke! Das war ein kleiner Gedankenfurz von mir

Den gierigen * hier zu verwenden ist eine schlechte Idee, da das zu jeder Menge Backtracking führt, vor allem da du den kompletten Dateiinhalt durchsuchst.

Hm, ein bisschen RegExp-Verständis habe ich nun gesammelt, allerdings sagt mir Backtracking nichts. Wo kann man das nachlesen? Kannst das kurz erklären? (Wiki und Google helfen grad nich genug)

Was passiert, wenn im Suchbegriff Regex-Steuerzeichen enthalten sind?

Oha, stimmt. Hab das schnell in ner ruhigen Stunde durchgemacht und net gescheit Debugt. Grml. Danke auch hierfür!

Was passiert, wenn die Zeichenfolge >< schon vorher im zu durchsuchenden String vorhanden war?

Ouha! Das sollte ich irgendwie escapen, stimmt.

 

[Matthias Reitinger]

Hm, ein bisschen RegExp-Verständis habe ich nun gesammelt, allerdings sagt mir Backtracking nichts. Wo kann man das nachlesen? Kannst das kurz erklären? (Wiki und Google helfen grad nich genug)

Am besten besorgst du dir den Regex Coach und schaust damit, was die Regex-Engine Schritt für Schritt macht. Probier mal als Ausdruck o.*o.*o.*o und als Zielstring Theodore Roosevelt, wähle dann unten den Reiter "Step", klicke auf Start und dann (ziemlich oft) auf "Next Step". Ersetze danach den Ausdruck durch o.*?o.*?o.*?o und schau wie die Engine dann vorgeht. Für eine ausführliche Erklärung verweise ich mal auf den Friedl, das Standardwerk zu regulären Ausdrücken. Ansonsten sollte eine Google-Suchen nach den Begriffen "regex performance backtracking" o.ä. auch gute Ergebnisse liefern.

Grüße,
Matthias