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 // 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 ?>
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
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
?>
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 $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 ?>
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
function directSimilarText($str1, $str2) {
$p = 0;
similar_text($str1, $str2, $p);
return $p;
}
var_dump(directSimilarText('Fernseher', 'Hellseher'));
?>
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
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ä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 $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 ?>
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"