Datensätze nach Ähnlichkeit sortieren

Question

Hallo allerseits,

wie kann ich Daten aus einer MySQL-Tabelle so sortieren, dass das oberste Wort am ähnlichsten zum eingegebenen Wort ist und darunter die Ähnlichkeit immer mehr abnimmt? Momentan sortiert er nach dem Alphabet, aber ich möchte eine Sortierung nach der Ähnlichkeit mit dem eingegebenen Wort. Also zum Beispiel:

Eingegebenes Wort: Haus
1. Ergebnis = Haus
2. Ergebnis = Rathaus
3. Ergebnis = durchaus

Ich habe versucht, es mit levenshtein zu realisieren:

SELECT * FROM ".$table
." WHERE irgendwas like '%".$search."%' or irgendwas2 like '%".$search."%' order by ".levenshtein(???)."

Muss ich zwei Abfragen machen? Die erste fragt nach der Ähnlichkeit ab und die zweite selected dann die Datensätze und sortiert sie nach dem levenshtein-Wert? Oder kann ich das ganze mit was anderem als levenshtein machen?

Vielen Dank

Answer 1

Levenshtein ist in MySQL nicht implementiert. Du kannst SOUNDEX() verwenden, was natürlich nur mit einer Spalte klappt:

$sSql= "SELECT *
FROM $sTable
WHERE spalte LIKE '%$sSearch%'
ORDER BY soundex(spalte)";

Eine Nutzung von levenshtein() unter PHP erfordert etwas mehr Aufwand, siehe auch sämtliche Kommentare zu de.php.net/levenshtein

Answer 2

Mit SOUNDEX ist merkwürdigerweise gar kein Unterschied zu der von mir oben angegebenen MySQL-Suche zu erkennen.
Aber möglicherweise könnte eine Kombination von levenshtein und SOUNDEX zum Ziel führen.

Bei deinem Link gibt es jemanden vom 07-Mar-2005 05:01, der folgendermaßen seine Suchergebnisse sortiert:

<?php
// PHP CODE INCLUDING DB LOOKUPS HERE
usort($searchresults, "finallevenshteinsortfunction");

function finallevenshteinsortfunction($a, $b)
{
if(($a['levenshtein'] > $b['levenshtein']) || ( $a['levenshtein'] == $b['levenshtein'] && strnatcasecmp( $a['Last_Name'], $b['Last_Name']) >= 1) ){ return $a['levenshtein'];} // Ok... The levenstein is greater OR with the same levenshtein, the last name is alphanumerically first
elseif($a['levenshtein'] == $b['levenshtein']){ return '0';} // The levenstein matches
elseif($a['levenshtein'] < $b['levenshtein']){ return -$a['levenshtein'];}
else{die("<!-- a horrable death -->");}
}
?>

Jedoch frage ich mich nun wie man nun mithilfe der Funktion die ähnlichsten Datensätze auswählt.
Ich dachte vielleicht mit:

while $search_array = mysql_fetch_array($searchresults) {
$reihenfolge = finallevenshteinsortfunction($sucheingabe, $search_array["irgendwas"]);
SELECT ... ORDER BY ".$reihenfolge."...

Aber wie mir gerade beim Schreiben auffällt, ist das ziemlich falsch. Man müsste die Abfrage mit ORDER BY außerhalb der WHILE-Schleife durchführen.


Vielleicht kann mir jemand weiterhelfen

Answer 3

Wie gesagt, es ist nicht das einfachste. Das Beispiel hab ich ebenfalls gesehen, allerdings nicht nachvollziehen können, da levenshtein() immer einen Wert für zwei Strings ermittelt - somit kann man einem alleine keinen Wert zuordnen und dann einfach nach diesen sortieren. Die Funktion im Beispiel ist übrigens speziell eine für usort().

Und nochmal: zielführend ist es, zunächst alle Ergebnisse der Abfrage in einem Feld zu speichern. Danach erfolgt die eigentliche Sortierarbeit innerhalb von PHP (und nicht mehr unter MySQL, wie du es dauernd mit ORDER BY machen willst).

Vielleicht ist das die Lösung:
codingforums.com/showthread.php?p=612198
Der Aufruf wäre dann in etwa:

$aSortiert= getSimilar( $sSuchwort, $aAbfrageErgebnisse );

Answer 4

Danke für den Link. Was mache ich aber jetzt? Ich habe jetzt den Array, der die Zahlen enthält, welche die jeweilige Ähnlichkeit angeben. Wenn ich das $aSortiert mit foreach ausgebe erhalte ich ungefähr 100342111. Erstens frage ich mich, warum das Script nicht alle Datensätze, die selected wurden, berücksichtigt und zweitens was man jetzt mit dem $aSortiert macht.

Muss man jetzt noch eine weitere Abfrage durchführen, in der man nach $aSortiert ordnet?

Vielen Dank.

Answer 5

Zunächst ein vollständiges, voll funktionales Beispiel:

<?php

function getSimilar( $sSuch, $aErg ) {
$ar= array();
foreach( $aErg as $v1 ) {
$iSim= similar_text( $sSuch, $v1 );
$iLev= levenshtein( $sSuch, $v1 );
if ( $iSim!= 0 ) {
$iLevError= intval( $iLev/ strlen( $v1 )* 100 );
$iPerSim= intval( $iSim/ strlen( $v1 ) )* 100;
$iTotal= $iPerSim- $iLevError;
} else {
$iTotal= 0;
}
$ar[$v1]= $iTotal;
}
arsort( $ar );
return $ar;
}

$aAbfrageErgebnisse= array( 'jany', 'hotel', 'jane', 'jaine', 'gun', 'jaimy', 'june', 'rain', 'house' );
$sSuchwort= 'jane';

$aSortiert= getSimilar( $sSuchwort, $aAbfrageErgebnisse );
print_r( $aSortiert );

?>

Wenn ich das $aSortiert mit foreach ausgebe erhalte ich ungefähr 100342111.

Dann sag einfach, wie dein $aSortiert überhaupt aussah (Ergebnis von print_r($aAbfrageErgebnisse) hier posten)

Erstens frage ich mich, warum das Script nicht alle Datensätze, die selected wurden, berücksichtigt

Es berücksichtigt alle - vermutlich baust du dein Array falsch auf?

und zweitens was man jetzt mit dem $aSortiert macht. Muss man jetzt noch eine weitere Abfrage durchführen, in der man nach $aSortiert ordnet?

Wie oft denn noch? Du hast doch schon längst alle Ergebnisse der Abfrage, wieso willst du sie immer wieder nochmal abfragen?? $aSortiert enthält die Wörter geordnet nach ihrer Relevanz. Und falls du mehr als die Wörter ausgeben willst, assoziierst du diese einfach mit deinen Abfrageergebnissen:

foreach( $aSortiert as $k1=> $v1) {
foreach( $aAbfrageErgebnisse as $k2=> $v2 ) {
if ( $v2['spalte']== $k1 ) {
print_r( $v2 );
break;
}
}
}

Answer 6

Vielen Dank.
Bei print_r($aSortiert) wird folgendes ausgegeben:

Array ( [jane] => 100 [jaine] => -20 [june] => -25 [jany] => -25 [jaimy] => -60 [rain] => -75 [house] => -80 [hotel] => -80 [gun] => -100 )

Das

foreach( $aSortiert as $k1=> $v1

bewirkt in diesem Beispiel nichts.

Ich lese nun also die Daten aus der Datenbank aus:

$query = "SELECT * FROM words WHERE deutsch like '%".$search."%'

$resultID = @mysql_query($query);

Die Variable $search enthält das Wort "Haus". Ich mache nun alle Ergebnisse in ein Array:

$results = mysql_fetch_array($resultID);

Anschließend verwende ich die Funktion:

$aSortiert= getSimilar( $search, $results );

Mit

foreach( $aSortiert as $k1=> $v1) {
foreach( $results as $k2=> $v2 ) {
if ( $v2['deutsch']== $k1 ) {
print_r( $v2 );
break;
}
}
}

erhalte ich als Ausgabe: 4Ärmliches Haus7

Answer 7

Ich weiß doch selber, was ich rausbekomme - du sollst jetzt konkret die Ausgabe von deinem
print_r( $results );
vor dem Aufruf an getSimilar..() posten.

Und du weißt hoffentlich, dass mysql_fetch_array() lediglich einen Datensatz zurückgibt..?

Answer 8

Würdest du denn alle Datensätze mit

$num = mysql_num_rows($result);
for ($i=0; $i<$num; $i++)
{
$de = mysql_result($res, $i, "deutsch");
usw.
}

auswählen?

Answer 9

Statt

$de = mysql_result($res, $i, "deutsch");

meine ich

$de = mysql_result($result, $i, "deutsch");

Answer 10

Ach und mit print_r erhalte ich:

Array ( [0] => 7 [id] => 7 [1] => Ärmliches Haus [deutsch] => Ärmliches Haus [2] => &#966;&#964;&#969;&#967;&#953;&#954;&#972; [griechisch] => &#966;&#964;&#969;&#967;&#953;&#954;&#972; [3] => [zusatz] => [4] => Unbekannt [artikel] => Unbekannt [5] => Substantiv [wortart] => Substantiv [6] => 4 [genitiv] => 4 [7] => [gen_ersatz] => [8] => 0 [plural] => 0 )

Also alle Daten der Spalten eines einzelnen Datensatzes.
Wichtig ist, dass diese Daten trotz der Sortierung erhalten bleiben.