Ähnlichkeit zweier Strings bestimmen (Thema: PHP Beispiele)

Welche Funktionen von PHP angeboten werden, um die Ähnlichkeit von zwei verschiedenen Strings zu bemessen

1. Einleitung

Zur Berechnung der Ähnlichkeit zweier Strings bietet PHP die folgenden vordefinierten Funktionen an:

  • levenshtein($str1, $str2): Analysiert, wie viele Änderungen an $str1 durchgeführt werden müssen, um $str2 zu erhalten.
  • similar_text($str1, $str2, &$percentage): Berechnet die Ähnlichkeit von $str1 und $str2 als Prozentzahl.
  • soundex($str): Ermittelt den Klang des Wortes $str, welcher dann mit dem Klang eines anderen Wortes verglichen werden kann.

2. levenshtein()

Die levenshtein-Funktion bestimmt, wie viele Änderungen am Text A durchgeführt werden müssen, um Text B zu erhalten. Die Rückgabe ist ein Integer-Wert. Im nachfolgenden Beispiel wird die Funktion auf Strings mit unterschiedlicher Ähnlichkeit angewendet.

PHP-Code
<?php
	// Teil eines anderen Strings
	$str1 = 'abc';
	$str2 = 'abcdef';
	var_dump(levenshtein($str1, $str2)); // 3

	// Aehnlicher Satz
	$str1 = 'Dort, ein Haus!';
	$str2 = 'Ist das ein Haus?';
	var_dump(levenshtein($str1, $str2)); // 8

	// typischer Vertipper
	$str1 = 'kinosaal';
	$str2 = 'kinpsaal';
	var_dump(levenshtein($str1, $str2)); // 1

	// zwei voellig unterschiedliche Strings
	$str1 = 'Gartenzaun';
	$str2 = 'Weltraum';
	var_dump(levenshtein($str1, $str2)); // 7

	// Bei Anwendung auf UTF-8-Zeichen
	$str1 = 'α';
	$str2 = 'b';
	var_dump(levenshtein($str1, $str2)); // 2
?>

HTML-Code
int(3)
int(8)
int(1)
int(7)
int(2)


Der reine Integer-Wert sagt nun noch nicht viel über die Ähnlichkeit aus, denn bei sehr langen Texten ist auch zu erwarten, dass diese viele Unterschiede aufweisen. Daher kann das Ergebnis durch die Länge des ersten Strings geteilt werden, um das aussagekräftigere Verhältnis aus notwendigen Änderungen zu ursprünglicher Zeichenlänge zu erhalten. Im nächsten Beispiel wird eine dazu passende Funktion „levenshteinPerc($str1, $str2)” definiert, welche den prozentualen Unterschied zwischen den übergebenen Strings zurückgibt. Je niedriger das Ergebnis ist, desto geringer ist der Unterschied. Es können Werte über 1,0 zurückgegeben werden, wenn die Anzahl der Änderungen, die an $str1 durchgeführt werden müssten, um $str2 zu erhalten, die Zeichenlänge von $str1 übersteigt.

PHP-Code
<?php
	function levenshteinPerc($str1, $str2) {
		$len = strlen($str1);
		if ($len===0 && strlen($str2)===0) {
			return 0;
		} else {
			return ($len>0 ? levenshtein($str1, $str2) / $len : 1);
		}
	}
	
	$str1 = 'abc';
	$str2 = 'abcdef';
	var_dump(levenshteinPerc($str1, $str2)); // 1

	$str1 = 'Dort, ein Haus!';
	$str2 = 'Ist das ein Haus?';
	var_dump(levenshteinPerc($str1, $str2)); // 0.53333333333333

	$str1 = 'kinosaal';
	$str2 = 'kinpsaal';
	var_dump(levenshteinPerc($str1, $str2)); // 0.125

	$str1 = 'Gartenzaun';
	$str2 = 'Weltraum';
	var_dump(levenshteinPerc($str1, $str2)); // 0.7

	$str1 = 'α';
	$str2 = 'b';
	var_dump(levenshteinPerc($str1, $str2)); // 1
?>

HTML-Code: Ausgabe
int(1)
float(0.53333333333333)
float(0.125)
float(0.7)
int(1)


3. similar_text()

Über die Funktion similar_text($str1, $str2, &$percentage) kann die Ähnlichkeit zweier Strings in Form einer Prozentzahl bestimmt werden, welche dann in &$percentage gespeichert wird. Der Prozentwert ist ein Float zwischen 0 und 100. Je höher er ist, desto ähnlicher sind die beiden Strings. Zusätzlich gibt die Funktion einen Integer zurück, welcher der Anzahl der gleichen Zeichen in beiden Strings entspricht. Es ist zu beachten, dass similar_text() bei längeren Strings schnell sehr langsam wird und daher nur bei kurzen Zeichenketten (<50 Zeichen) verwendet werden sollte.

PHP-Code
<?php
	$i = 0;
	$p = 0;

	$str1 = 'abc';
	$str2 = 'abcdef';
	$i = similar_text($str1, $str2, $p);
	var_dump($i, $p); // 3 und 66,667

	$p = 0;
	$str1 = 'Dort, ein Haus!';
	$str2 = 'Ist das ein Haus?';
	$i = similar_text($str1, $str2, $p);
	var_dump($i, $p); // 10 und 62,5

	$str1 = 'kinosaal';
	$str2 = 'kinpsaal';
	$i = similar_text($str1, $str2, $p);
	var_dump($i, $p); // 7 und 87,5

	$str1 = 'Gartenzaun';
	$str2 = 'Weltraum';
	$i = similar_text($str1, $str2, $p);
	var_dump($i, $p); // 3 und 33,333

	$str1 = 'α';
	$str2 = 'b';
	$i = similar_text($str1, $str2, $p);
	var_dump($i, $p); // 0 und 0,0
?>

HTML-Code: Ausgabe
int(3)
float(66.666666666667)
int(10)
float(62.5)
int(7)
float(87.5)
int(3)
float(33.333333333333)
int(0)
float(0)


Will man direkt den Prozentwert zurückerhalten und sich den Umweg über &$percentage sparen, dann kann dies mit einer kleinen eigenen Funktion erledigt werden:

PHP-Code
<?php
	function directSimilarText($str1, $str2) {
		$p = 0;
		similar_text($str1, $str2, $p);
		return $p;
	}
	
	var_dump(directSimilarText('Fernseher', 'Hellseher'));
?>

HTML-Code: Ausgabe
float(66.666666666667)


Nachfolgend eine Beispieltabelle über den Zeitbedarf von similar_text(). Die Zeichenlänge der beiden verglichenen Strings steht in der ersten Spalte (kommagetrennt für Länge(String A), Länge(String B)), die zweite Spalte enthält den Zeitbedarf für 1000 Iterationen von similar_text(). Der genaue Zeitbedarf hängt offensichtlich von der verwendeten Hardware und der Systemkonfiguration ab. Gut zu erkennen ist jedoch, dass auch bei langen Strings das Hinzufügen von ca. 15 Zeichen den Zeitbedarf um etwa 20% erhöht.

Stringlänge Zeitbedarf
(1.000 Iterationen)
15, 17 0.002 Sekunden
30, 34 0.007 Sekunden
45, 51 0.019 Sekunden
60, 68 0.039 Sekunden
75, 85 0.07 Sekunden
90, 102 0.117 Sekunden
105, 119 0.174 Sekunden
120, 136 0.252 Sekunden
135, 153 0.348 Sekunden
150, 170 0.467 Sekunden
165, 187 0.61 Sekunden
180, 204 0.783 Sekunden
195, 221 0.982 Sekunden
210, 238 1.215 Sekunden
225, 255 1.477 Sekunden
240, 272 1.78 Sekunden
255, 289 2.112 Sekunden
270, 306 2.489 Sekunden
285, 323 2.921 Sekunden
300, 340 3.393 Sekunden

Das Skript zum Erzeugen der vorherigen Tabelle:

PHP-Code
<?php
	function similarTextCalculateTime($str1, $str2, $iterations) {
		$start = microtime(true);
		for ($x=0; $x<$iterations; $x++) {
			similar_text($str1, $str2);
		}
		return round(microtime(true) - $start, 3);
	}
	
	$baseStr1 = 'abc defg hijkl ';
	$baseStr2 = 'defg abc xhijklm ';
	
	$stringPairs = array();
	
	for ($x=0; $x<20; $x++) {
		$s1 = str_repeat($baseStr1, 1 + $x * 1);
		$s2 = str_repeat($baseStr2, 1 + $x * 1);
		$stringPairs[] = array($s1, $s2);
	}
?>

<table id="php-similar-text-performance">
	<thead>
		<tr>
			<td>Stringl&auml;nge</td>
			<td>Zeitbedarf<br />(1.000 Iterationen)</td>
		</tr>
	</thead>
	<tbody>
		<?php foreach ($stringPairs as $pair): ?>
			<tr>
				<td><?php echo strlen($pair[0]).", ".strlen($pair[1]); ?></td>
				<td><?php echo similarTextCalculateTime($pair[0], $pair[1], 1000) ?> Sekunden</td>
			</tr>
		<?php endforeach; ?>
	</tbody>
</table>

4. soundex()

Die Funktion soundex($str) prüft den Klang eines Wortes. Ihre Rückgabe ist eine vierstellige Zeichenkette. Das erste Zeichen entspricht dem ersten Buchstaben des Strings, danach folgen drei Zahlen. Je näher die Zahlen beieinander liegen, desto ähnlicher ist der Klang. Die Funktion ist auf die englische Sprache ausgerichtet und sollte nur für diese verwendet werden. Eine mögliche Version, die an die deutsche Sprache angepasst ist, kann unter php.net gefunden werden. Auch für die englische Sprache sind die Ergebnisse aber eher dürftig, wie das nachfolgende Beispiel zeigt:

PHP-Code
<?php
	$str1 = 'Earth';
	$str2 = 'Earl';
	var_dump(soundex($str1), soundex($str2)); // E630, E640

	$str1 = 'Eater';
	$str2 = 'Creeper';
	var_dump(soundex($str1), soundex($str2)); // E360, C616

	$str1 = 'mayor';
	$str2 = 'major';
	var_dump(soundex($str1), soundex($str2)); // M600, M260

	$str1 = 'screen';
	$str2 = 'spleen';
	var_dump(soundex($str1), soundex($str2)); // S650, S145

	$str1 = 'railway';
	$str2 = 'space';
	var_dump(soundex($str1), soundex($str2)); // R400, S120

	$str1 = 'destroy';
	$str2 = 'deploy';
	var_dump(soundex($str1), soundex($str2)); // D236, D140
?>

HTML-Code: Ausgabe
string(4) "E630"
string(4) "E640"
string(4) "E360"
string(4) "C616"
string(4) "M600"
string(4) "M260"
string(4) "S650"
string(4) "S145"
string(4) "R400"
string(4) "S120"
string(4) "D236"
string(4) "D140"


Kommentare (0)

Von neu nach alt