Die nächste Übereinstimmung der Zeichenfolge erhalten

Question

Ich brauche eine Möglichkeit, mehrere Zeichenfolgen mit einer Testzeichenfolge zu vergleichen und die Zeichenfolge zurückzugeben, die ihr am ähnlichsten ist:

TESTSTRING: DER BRAUNE FUCHS SPRANG ÜBER DIE ROTE KUH

WAHL A   : DIE ROTE KUH SPRANG ÜBER DAS GRÜNE HUHN
WAHL B   : DIE ROTE KUH SPRANG ÜBER DIE ROTE KUH
WAHL C   : DER ROTE FUCHS SPRANG ÜBER DIE BRAUNE KUH

(Wenn ich das richtig gemacht habe) Die ähnlichste Zeichenfolge zum "TESTSTRING" sollte "WAHL C" sein. Was ist der einfachste Weg, dies zu tun?

Ich plane, dies in mehreren Sprachen wie VB.net, Lua und JavaScript zu implementieren. Zu diesem Zeitpunkt ist Pseudocode akzeptabel. Wenn Sie ein Beispiel für eine bestimmte Sprache bereitstellen können, wäre das ebenfalls sehr hilfreich!

Answer 1

Hier können Sie einen Golang-POC für die Berechnung der Abstände zwischen den angegebenen Wörtern haben. Sie können die minDistance und difference für andere Bereiche anpassen.

Spielplatz: https://play.golang.org/p/NtrBzLdC3rE

package main

import (
    "errors"
    "fmt"
    "log"
    "math"
    "strings"
)

var data string = `DIE ROTE KUH SPRANG ÜBER DAS GRÜNE HUHN-DIE ROTE KUH SPRANG ÜBER DIE ROTE KUH-DER ROTE FUCHS SPRANG ÜBER DIE BRAUNE KUH`

const minDistance float64 = 2
const difference float64 = 1

type word struct {
    data    string
    letters map[rune]int
}

type words struct {
    words []word
}

// Print macht die Daten in Wort übersichtlich
func (w word) Print() {
    var (
        leng int
        c      int
        i      int
        key    rune
    )
    fmt.Printf("Daten: %s\n", w.data)
    leng = len(w.letters) - 1
    c = 0
    for key, i = range w.letters {
        fmt.Printf("%s:%d", string(key), i)
        if c != leng {
            fmt.Printf(" | ")
        }
        c++
    }
    fmt.Printf("\n")
}

func (ws words) fuzzySearch(data string) ([]word, error) {
    var (
        w      word
        err    error
        founds []word
    )
    w, err = initWord(data)
    if err != nil {
        log.Printf("Fehler: %s\n", err.Error())
        return nil, err
    }
    // Alle Wörter durchlaufen
    for i := range ws.words {
        letters := ws.words[i].letters
        //
        var similar float64 = 0
        // Durchlaufen der Buchstaben der Eingabedaten
        for key := range w.letters {
            if val, ok := letters[key]; ok {
                if math.Abs(float64(val-w.letters[key])) <= minDistance {
                    similar += float64(val)
                }
            }
        }

        lenSimilarity := math.Abs(similar - float64(len(data)-strings.Count(data, " ")))
        log.Printf("Vergleiche %s mit %s, ich habe %f ähnliche Buchstaben gefunden, mit Gewicht %f", data, ws.words[i].data, similar, lenSimilarity)
        if lenSimilarity <= difference {
            founds = append(founds, ws.words[i])
        }
    }

    if len(founds) == 0 {
        return nil, errors.New("keine Ähnlichkeiten gefunden für Daten: " + data)
    }

    return founds, nil
}

func initWords(data []string) []word {
    var (
        err   error
        words []word
        word  word
    )
    for i := range data {
        word, err = initWord(data[i])
        if err != nil {
            log.Printf("Fehler im Index [%d] für Daten: %s", i, data[i])
        } else {
            words = append(words, word)
        }
    }
    return words

}

func initWord(data string) (word, error) {
    var word word

    word.data = data
    word.letters = make(map[rune]int)
    for _, r := range data {
        if r != 32 { // Leerzeichen nicht speichern
            word.letters[r]++
        }

    }
    return word, nil
}
func main() {
    var ws words
    words := initWords(strings.Split(data, "-"))
    for i := range words {
        words[i].Print()
    }
    ws.words = words

    solution, _ := ws.fuzzySearch("DIE BRAUNE FUCHS SPRANG ÜBER DIE ROTE KUH")
    fmt.Println("Mögliche Lösungen: ", solution)

}

Answer 2

Eine Probe mit C# finden Sie hier.

public static void Main()
{
    Console.WriteLine("Hallo Welt " + LevenshteinDistance("Hallo","Welt"));
    Console.WriteLine("Wahl A " + LevenshteinDistance("DER BRAUNE FUCHS SPRANG ÜBER DIE ROTE KUH","DIE ROTE KUH SPRANG ÜBER DAS GRÜNE HUHN"));
    Console.WriteLine("Wahl B " + LevenshteinDistance("DER BRAUNE FUCHS SPRANG ÜBER DIE ROTE KUH","DIE ROTE KUH SPRANG ÜBER DIE ROTE KUH"));
    Console.WriteLine("Wahl C " + LevenshteinDistance("DER BRAUNE FUCHS SPRANG ÜBER DIE ROTE KUH","DER ROTE FUCHS SPRANG ÜBER DIE BRAUNE KUH"));
}

public static float LevenshteinDistance(string a, string b)
{
    var rowLen = a.Length;
    var colLen = b.Length;
    var maxLen = Math.Max(rowLen, colLen);

    // Schritt 1
    if (rowLen == 0 || colLen == 0)
    {
        return maxLen;
    }

    /// Erstelle die beiden Vektoren
    var v0 = new int[rowLen + 1];
    var v1 = new int[rowLen + 1];

    /// Schritt 2
    /// Initialisiere den ersten Vektor
    for (var i = 1; i <= rowLen; i++)
    {
        v0[i] = i;
    }

    // Schritt 3
    /// Für jede Spalte
    for (var j = 1; j <= colLen; j++)
    {
        /// Setze das 0-te Element auf die Spaltennummer
        v1[0] = j;

        // Schritt 4
        /// Für jede Zeile
        for (var i = 1; i <= rowLen; i++)
        {
            // Schritt 5
            var cost = (a[i - 1] == b[j - 1]) ? 0 : 1;

            // Schritt 6
            /// Finde das Minimum
            v1[i] = Math.Min(v0[i] + 1, Math.Min(v1[i - 1] + 1, v0[i - 1] + cost));
        }

        /// Tausche die Vektoren aus
        var vTmp = v0;
        v0 = v1;
        v1 = vTmp;
    }

    // Schritt 7
    /// Die Vektoren wurden am Ende der letzten Schleife noch einmal ausgetauscht,
    /// deshalb ist das Ergebnis jetzt in v0 anstatt in v1
    return v0[rowLen];
}

Die Ausgabe ist:

Hallo Welt 4
Wahl A 15
Wahl B 6
Wahl C 8

Answer 3

Es gibt noch eine Ähnlichkeitsmaßnahme, die ich einmal in unserem System implementiert habe und die zufriedenstellende Ergebnisse lieferte:

Anwendungsfall

Es gibt eine Benutzerabfrage, die mit einer Reihe von Dokumenten abgeglichen werden muss.

Algorithmus

1. Extrahieren Sie Schlüsselwörter aus der Benutzerabfrage (relevante POS-TAGS - Substantiv, Eigennamen).
2. Berechnen Sie nun den Score basierend auf der unten stehenden Formel zur Messung der Ähnlichkeit zwischen Benutzerabfrage und gegebenem Dokument.

Für jedes aus der Benutzerabfrage extrahierte Schlüsselwort:

• Beginnen Sie mit der Suche im Dokument nach dem gegebenen Wort und verringern Sie für jede folgende Vorkommen dieses Wortes im Dokument die belohnten Punkte.

Im Wesentlichen wird, wenn das erste Schlüsselwort 4 Mal im Dokument erscheint, der Score wie folgt berechnet:

• Das erste Auftreten bringt '1' Punkt.
• Das zweite Auftreten trägt 1/2 zum berechneten Score bei.
• Das dritte Auftreten fügt 1/3 zum Gesamtwert hinzu.
• Das vierte Auftreten erhält 1/4.

Gesamte Ähnlichkeitsscore = 1 + 1/2 + 1/3 + 1/4 = 2,083

Gleiches berechnen wir für andere Schlüsselwörter in der Benutzerabfrage.

Letztendlich repräsentiert der Gesamtscore das Ausmaß der Ähnlichkeit zwischen Benutzerabfrage und gegebenem Dokument.