Wie finde ich ähnliche Ergebnisse und sortiere nach Ähnlichkeit?

Wie frage ich nach Datensätzen, die nach Ähnlichkeit geordnet sind?

Z.B. Die Suche nach "Stock Overflow" würde zurückkehren

1. Paketüberfluss
2. SharePoint-Überlauf
3. Mathe-Überlauf
4. Politischer Überlauf
5. VFX-Überlauf

Z.B. Suche nach "LO" würde zurückgeben:

1. Pablo Picasso
2. michelangeLO
3. jackson polLOck

Womit ich Hilfe brauche:

1. Verwenden einer Suchmaschine zum Indizieren und Durchsuchen einer MySQL-Tabelle für bessere Ergebnisse

   • Verwendung der Sphinx- Suchmaschine mit PHP

   • Verwendung der Lucene- Engine mit PHP

2. Verwenden der Volltextindizierung, um ähnliche / enthaltende Zeichenfolgen zu finden

Was funktioniert nicht gut

• Die Levenshtein-Entfernung ist sehr unregelmäßig. ( UDF , Abfrage ) Die
  Suche nach "Hund" gibt mir:
  1. Hund
  2. Moor
  3. vor
  4. groß
  5. Echo
• LIKE Gibt bessere Ergebnisse zurück, gibt jedoch nichts für lange Abfragen zurück, obwohl ähnliche Zeichenfolgen vorhanden sind
  1. Hund
  2. dogid
  3. dogaral
  4. Dogma

Ich habe herausgefunden, dass der Levenshtein-Abstand gut sein kann, wenn Sie eine vollständige Zeichenfolge gegen eine andere vollständige Zeichenfolge suchen. Wenn Sie jedoch nach Schlüsselwörtern innerhalb einer Zeichenfolge suchen, gibt diese Methode (manchmal) nicht die gewünschten Ergebnisse zurück. Darüber hinaus ist die SOUNDEX-Funktion nicht für andere Sprachen als Englisch geeignet, sodass sie recht eingeschränkt ist. Sie könnten mit LIKE davonkommen, aber es ist wirklich für einfache Suchen. Möglicherweise möchten Sie andere Suchmethoden untersuchen, um herauszufinden, was Sie erreichen möchten. Zum Beispiel:

Sie können Lucene als Suchbasis für Ihre Projekte verwenden. Es ist in den meisten gängigen Programmiersprachen implementiert und sehr schnell und vielseitig einsetzbar. Diese Methode ist wahrscheinlich die beste, da nicht nur nach Teilzeichenfolgen gesucht wird, sondern auch nach Buchstabenumsetzung, Präfixen und Suffixen (alle kombiniert). Sie müssen jedoch einen separaten Index führen (die Verwendung von CRON zum gelegentlichen Aktualisieren von einem unabhängigen Skript funktioniert jedoch).

Wenn Sie eine MySQL-Lösung wünschen, ist die Volltextfunktionalität ziemlich gut und sicherlich schneller als eine gespeicherte Prozedur. Wenn Ihre Tabellen nicht MyISAM sind, können Sie eine temporäre Tabelle erstellen und dann Ihre Volltextsuche durchführen:

CREATE TABLE IF NOT EXISTS `tests`.`data_table` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `title` varchar(2000) CHARACTER SET latin1 NOT NULL,
  `description` text CHARACTER SET latin1 NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 COLLATE=utf8_bin AUTO_INCREMENT=1 ;

Verwenden Sie einen Datengenerator , um zufällige Daten zu generieren, wenn Sie sich nicht die Mühe machen möchten, diese selbst zu erstellen ...

** HINWEIS **: Der Spaltentyp sollte latin1_bindarin bestehen, eine Suche ohne Berücksichtigung der Groß- und Kleinschreibung durchzuführen latin1. Für Unicode-Zeichenfolgen würde ich für Suchvorgänge ohne Berücksichtigung der utf8_binGroß- und utf8_general_ciKleinschreibung empfehlen .

DROP TABLE IF EXISTS `tests`.`data_table_temp`;
CREATE TEMPORARY TABLE `tests`.`data_table_temp`
   SELECT * FROM `tests`.`data_table`;

ALTER TABLE `tests`.`data_table_temp`  ENGINE = MYISAM;

ALTER TABLE `tests`.`data_table_temp` ADD FULLTEXT `FTK_title_description` (
  `title` ,
  `description`
);

SELECT *,
       MATCH (`title`,`description`)
       AGAINST ('+so* +nullam lorem' IN BOOLEAN MODE) as `score`
  FROM `tests`.`data_table_temp`
 WHERE MATCH (`title`,`description`)
       AGAINST ('+so* +nullam lorem' IN BOOLEAN MODE)
 ORDER BY `score` DESC;

DROP TABLE `tests`.`data_table_temp`;

Weitere Informationen finden Sie auf der MySQL API-Referenzseite

Der Nachteil dabei ist, dass es nicht nach Buchstabenumsetzung oder "ähnlichen, klingt wie" Wörtern sucht.

** UPDATE **

Wenn Sie Lucene für Ihre Suche verwenden, müssen Sie lediglich einen Cron-Job erstellen (alle Webhosts verfügen über diese "Funktion"), bei dem dieser Job einfach ein PHP-Skript ausführt (z. B. "cd / path / to / script; php searchindexer.php"). ), die die Indizes aktualisiert. Der Grund dafür ist, dass das Indizieren von Tausenden von "Dokumenten" (Zeilen, Daten usw.) einige Sekunden oder sogar Minuten dauern kann. Dies soll jedoch sicherstellen, dass alle Suchvorgänge so schnell wie möglich ausgeführt werden. Daher möchten Sie möglicherweise einen Verzögerungsjob erstellen, der vom Server ausgeführt wird. Es kann über Nacht sein oder in der nächsten Stunde liegt es an Ihnen. Das PHP-Skript sollte ungefähr so ​​aussehen:

$indexer = Zend_Search_Lucene::create('/path/to/lucene/data');

Zend_Search_Lucene_Analysis_Analyzer::setDefault(
  // change this option for your need
  new Zend_Search_Lucene_Analysis_Analyzer_Common_Utf8Num_CaseInsensitive()
);

$rowSet = getDataRowSet();  // perform your SQL query to fetch whatever you need to index
foreach ($rowSet as $row) {
   $doc = new Zend_Search_Lucene_Document();
   $doc->addField(Zend_Search_Lucene_Field::text('field1', $row->field1, 'utf-8'))
       ->addField(Zend_Search_Lucene_Field::text('field2', $row->field2, 'utf-8'))
       ->addField(Zend_Search_Lucene_Field::unIndexed('someValue', $someVariable))
       ->addField(Zend_Search_Lucene_Field::unIndexed('someObj', serialize($obj), 'utf-8'))
  ;
  $indexer->addDocument($doc);
}

// ... you can get as many $rowSet as you want and create as many documents
// as you wish... each document doesn't necessarily need the same fields...
// Lucene is pretty flexible on this

$indexer->optimize();  // do this every time you add more data to you indexer...
$indexer->commit();    // finalize the process

Dann suchen Sie im Grunde so (einfache Suche):

$index = Zend_Search_Lucene::open('/path/to/lucene/data');

// same search options
Zend_Search_Lucene_Analysis_Analyzer::setDefault(
   new Zend_Search_Lucene_Analysis_Analyzer_Common_Utf8Num_CaseInsensitive()
);

Zend_Search_Lucene_Search_QueryParser::setDefaultEncoding('utf-8');

$query = 'php +field1:foo';  // search for the word 'php' in any field,
                                 // +search for 'foo' in field 'field1'

$hits = $index->find($query);

$numHits = count($hits);
foreach ($hits as $hit) {
   $score = $hit->score;  // the hit weight
   $field1 = $hit->field1;
   // etc.
}

Hier finden Sie großartige Websites zu Lucene in Java , PHP und .Net .

Zusammenfassend hat jede Suchmethode ihre eigenen Vor- und Nachteile:

• Sie haben die Sphinx-Suche erwähnt und sie sieht sehr gut aus, solange Sie den Deamon auf Ihrem Webhost ausführen können.
• Zend Lucene benötigt einen Cron-Job, um die Datenbank neu zu indizieren. Dies ist zwar für den Benutzer recht transparent, bedeutet jedoch, dass neue Daten (oder gelöschte Daten!) Nicht immer mit den Daten in Ihrer Datenbank synchronisiert sind und daher nicht sofort bei der Benutzersuche angezeigt werden.
• Die MySQL FULLTEXT-Suche ist gut und schnell, bietet Ihnen jedoch nicht die Leistung und Flexibilität der ersten beiden.

Bitte zögern Sie nicht zu kommentieren, wenn ich etwas vergessen / verpasst habe.

1. Ähnlichkeit

Für Levenshtein in MySQL habe ich dies unter www.codejanitor.com/wp/2007/02/10/levenshtein-distance-as-a-mysql-stored-function gefunden

SELECT 
    column, 
    LEVENSHTEIN(column, 'search_string') AS distance 
FROM table 
WHERE 
    LEVENSHTEIN(column, 'search_string') < distance_limit
ORDER BY distance DESC

2. Enthält Groß- und Kleinschreibung

Verwenden Sie die LIKEAnweisung von MySQL, bei der die Groß- und Kleinschreibung standardmäßig nicht berücksichtigt wird. Das %ist ein Platzhalter, daher kann es vorher und nachher eine beliebige Zeichenfolge geben search_string.

SELECT 
    *
FROM 
    table
WHERE 
    column_name LIKE "%search_string%"

3. Enthält Groß- und Kleinschreibung

Das MySQL-Handbuch hilft:

Der Standardzeichensatz und die Sortierung sind latin1 und latin1_swedish_ci, sodass bei nicht-binären Zeichenfolgenvergleichen standardmäßig die Groß- und Kleinschreibung nicht berücksichtigt wird. Dies bedeutet, dass Sie bei der Suche mit col_name LIKE 'a%' alle Spaltenwerte erhalten, die mit A oder a beginnen. Stellen Sie sicher, dass bei einem der Operanden zwischen Groß- und Kleinschreibung oder binärer Sortierung unterschieden wird. Wenn Sie beispielsweise eine Spalte und eine Zeichenfolge vergleichen, die beide den Zeichensatz latin1 haben, können Sie den Operator COLLATE verwenden, um zu bewirken, dass jeder Operand die Sortierung latin1_general_cs oder latin1_bin hat ...

Mein MySQL-Setup unterstützt latin1_general_csoder nicht latin1_bin, aber es hat gut funktioniert, wenn ich die Sortierung utf8_binals binäres utf8 verwende. Dabei wird zwischen Groß- und Kleinschreibung unterschieden:

SELECT 
    *
FROM 
    table
WHERE 
    column_name LIKE "%search_string%" COLLATE utf8_bin

2. / 3. sortiert nach Levenshtein Distance

SELECT 
    column, 
    LEVENSHTEIN(column, 'search_string') AS distance // for sorting
FROM table 
WHERE 
    column_name LIKE "%search_string%"
    COLLATE utf8_bin // for case sensitivity, just leave out for CI
ORDER BY
    distance
    DESC

Es scheint, dass Ihre Definition von Ähnlichkeit semantische Ähnlichkeit ist. Um eine solche Ähnlichkeitsfunktion aufzubauen, sollten Sie semantische Ähnlichkeitsmaße verwenden. Beachten Sie, dass der Umfang der Arbeit an dem Problem von wenigen Stunden bis zu Jahren variieren kann. Es wird daher empfohlen, den Umfang zu bestimmen, bevor Sie mit der Arbeit beginnen. Ich habe nicht herausgefunden, welche Daten Sie haben, um die Ähnlichkeitsrelation aufzubauen. Ich gehe davon aus, dass Sie Zugriff auf einen Datensatz von Dokumenten und einen Datensatz von Abfragen haben. Sie können mit dem gleichzeitigen Auftreten der Wörter beginnen (z. B. bedingte Wahrscheinlichkeit). Sie werden schnell feststellen, dass Sie die Liste der Stoppwörter erhaltenwie verwandt die meisten Wörter einfach, weil sie sehr beliebt sind. Wenn Sie den Lift der bedingten Wahrscheinlichkeit verwenden, werden die Stoppwörter berücksichtigt, aber die Beziehung wird in geringer Anzahl fehleranfällig (in den meisten Fällen). Sie könnten Jacard ausprobieren, aber da es symmetrisch ist, wird es viele Beziehungen geben, die es nicht finden wird. Dann könnten Sie Beziehungen in Betracht ziehen, die nur in kurzer Entfernung vom Basiswort erscheinen. Sie können (und sollten) Beziehungen in Betracht ziehen, die auf allgemeinen Korpus (z. B. Wikipedia) und benutzerspezifischen (z. B. seinen E-Mails) basieren.

In Kürze werden Sie viele Ähnlichkeitsmaße haben, wenn alle Maße gut sind und einen Vorteil gegenüber den anderen haben.

Um solche Maßnahmen zu kombinieren, möchte ich das Problem in ein Klassifizierungsproblem reduzieren.

Sie sollten einen Datensatz mit Pariser Wörtern erstellen und diese als "verwandt" kennzeichnen. Um einen großen beschrifteten Datensatz zu erstellen, können Sie:

• Verwenden Sie Quellen für bekannte verwandte Wörter (z. B. gute alte Wikipedia-Kategorien) für Positive
• Die meisten Wörter, die nicht als verwandt bekannt sind, sind nicht verwandt.

Verwenden Sie dann alle Kennzahlen, die Sie als Merkmale der Paare haben. Jetzt befinden Sie sich im Bereich des überwachten Klassifizierungsproblems. Erstellen Sie einen Klassifikator für den Datensatz, bewerten Sie ihn gemäß Ihren Anforderungen und erhalten Sie ein Ähnlichkeitsmaß, das Ihren Anforderungen entspricht.