Sortierung String basierend auf Ähnlichkeiten

Question

beachten Sie die folgenden Strings:

• er llo
• Abschied
• hallo
• = (Auf Wiedersehen)
• (er) (llo)
• Abschied
• Helium

Ich versuche, diese so zu sortieren, dass ähnliche Wörter zusammen kommt, ich weiß

1. alphanumerical sorting keine Option
2. Entfernen Sonderzeichen ist ",-_ and etc dann ist sicherlich hilfreich zu vergleichen, aber Ergebnisse nicht sei so gut wie ich hoffe.

HINWEIS:

könnte es einige unterschiedliche gewünschte ouput dafür sein, eine davon ist:

SOLL OUTPUT:

1. hallo
2. er llo
3. (er) (llo)
4. Helium
5. Abschied
6. Abschied
7. = (Auf Wiedersehen)

so meine Frage ist, dass, wenn es ein Java-Paket, das Strings vergleicht und sie schließlich die Suchergebnisse basierend darauf.

Ich habe von Begriffen wie n-gram und skip-gram gehört, aber sie nicht ganz verstanden. Ich bin mir nicht einmal sicher, ob sie mir überhaupt nützlich sein können.

UPDATE: Finden von Ähnlichkeiten ist sicherlich ein Teil meiner Frage, aber das Hauptproblem ist der sortierende Teil.

Answer 1

Hier ist ein möglicher Ansatz.

Berechnen Sie die edit distance/Levenshtein distance zwischen jedem Paar von Zeichenfolgen, und verwenden Sie dann die Zeichenfolgen als vollständiges Diagramm, wobei die Kantengewichte aus der Bearbeitungsentfernung stammen. Wählen Sie einen Schwellenwert für diese Gewichtungen und entfernen Sie alle zu hohen Gewichte. Dann finden Sie die cliques in diesem Diagramm. Wenn Ihr Schwellenwert ziemlich niedrig ist, ist es vielleicht sogar möglich, verbundene Komponenten zu finden.

Hinweis: Vielleicht wäre es besser, eine Editierdistanz durch einen der Ähnlichkeitsmaße im Link zu ersetzen, den @dognose gepostet hat. Beachten Sie auch, dass das Finden von Cliquen sehr langsam ist, wenn Sie eine große Anzahl von Strings haben