Vergleicht man Namen

Question

Gibt es einen ‚einfachen‘ Algorithmus, um die Wahrscheinlichkeit von 2 Namen zu bestimmen, die gleiche Person darstellt? Ich frage nicht nach etwas von dem Niveau, die kundenspezifische Abteilung verwenden könnte. Nur ein einfaches algo das wäre mir sagen, ob ‚James T. Clark‘ ist höchstwahrscheinlich die gleichen Namen wie ‚J. Thomas Clark‘oder 'James Clerk'.

Wenn es eine algo in C #, die groß sein würden, aber ich kann aus jeder beliebigen Sprache übersetzen.

Answer 1

Ich habe ähnliches Problem konfrontiert und versuchte, ersten Levenstein Entfernung zu verwenden, aber es hat nicht funktioniert gut für mich. Ich kam mit einem Algorithmus, die Sie „Ähnlichkeit“ Wert zwischen zwei Zeichenketten gibt (höherer Wert bedeutet mehr ähnliche Strings, „1“ für identische Strings). Dieser Wert ist nicht sehr sinnvoll für sich (wenn nicht „1“ ist, immer 0,5 oder weniger), aber funktioniert ganz gut, wenn man in der ungarischen Matrix wirft passende Paare aus zwei Listen von Zeichenkette zu finden.

Verwenden Sie wie folgt aus:

PartialStringComparer cmp = new PartialStringComparer();
tbResult.Text = cmp.Compare(textBox1.Text, textBox2.Text).ToString();

Der Code hinter:

public class SubstringRange {
    string masterString;

    public string MasterString {
        get { return masterString; }
        set { masterString = value; }
    }
    int start;

    public int Start {
        get { return start; }
        set { start = value; }
    }
    int end;

    public int End {
        get { return end; }
        set { end = value; }
    }
    public int Length {
        get { return End - Start; }
        set { End = Start + value;}
    }

    public bool IsValid {
        get { return MasterString.Length >= End && End >= Start && Start >= 0; }
    }

    public string Contents {
        get {
            if(IsValid) {
                return MasterString.Substring(Start, Length);
            } else {
                return "";
            }
        }
    }
    public bool OverlapsRange(SubstringRange range) {
        return !(End < range.Start || Start > range.End);
    }
    public bool ContainsRange(SubstringRange range) {
        return range.Start >= Start && range.End <= End;
    }
    public bool ExpandTo(string newContents) {
        if(MasterString.Substring(Start).StartsWith(newContents, StringComparison.InvariantCultureIgnoreCase) && newContents.Length > Length) {
            Length = newContents.Length;
            return true;
        } else {
            return false;
        }
    }
}

public class SubstringRangeList: List<SubstringRange> {
    string masterString;

    public string MasterString {
        get { return masterString; }
        set { masterString = value; }
    }

    public SubstringRangeList(string masterString) {
        this.MasterString = masterString;
    }

    public SubstringRange FindString(string s){
        foreach(SubstringRange r in this){
            if(r.Contents.Equals(s, StringComparison.InvariantCultureIgnoreCase))
                return r;
        }
        return null;
    }

    public SubstringRange FindSubstring(string s){
        foreach(SubstringRange r in this){
            if(r.Contents.StartsWith(s, StringComparison.InvariantCultureIgnoreCase))
                return r;
        }
        return null;
    }

    public bool ContainsRange(SubstringRange range) {
        foreach(SubstringRange r in this) {
            if(r.ContainsRange(range))
                return true;
        }
        return false;
    }

    public bool AddSubstring(string substring) {
        bool result = false;
        foreach(SubstringRange r in this) {
            if(r.ExpandTo(substring)) {
                result = true;
            }
        }
        if(FindSubstring(substring) == null) {
            bool patternfound = true;
            int start = 0;
            while(patternfound){
                patternfound = false;
                start = MasterString.IndexOf(substring, start, StringComparison.InvariantCultureIgnoreCase);
                patternfound = start != -1;
                if(patternfound) {
                    SubstringRange r = new SubstringRange();
                    r.MasterString = this.MasterString;
                    r.Start = start++;
                    r.Length = substring.Length;
                    if(!ContainsRange(r)) {
                        this.Add(r);
                        result = true;
                    }
                }
            }
        }
        return result;
    }

    private static bool SubstringRangeMoreThanOneChar(SubstringRange range) {
        return range.Length > 1;
    }

    public float Weight {
        get {
            if(MasterString.Length == 0 || Count == 0)
                return 0;
            float numerator = 0;
            int denominator = 0;
            foreach(SubstringRange r in this.FindAll(SubstringRangeMoreThanOneChar)) {
                numerator += r.Length;
                denominator++;
            }
            if(denominator == 0)
                return 0;
            return numerator / denominator / MasterString.Length;
        }
    }

    public void RemoveOverlappingRanges() {
        SubstringRangeList l = new SubstringRangeList(this.MasterString);
        l.AddRange(this);//create a copy of this list
        foreach(SubstringRange r in l) {
            if(this.Contains(r) && this.ContainsRange(r)) {
                Remove(r);//try to remove the range
                if(!ContainsRange(r)) {//see if the list still contains "superset" of this range
                    Add(r);//if not, add it back
                }
            }
        }
    }

    public void AddStringToCompare(string s) {
        for(int start = 0; start < s.Length; start++) {
            for(int len = 1; start + len <= s.Length; len++) {
                string part = s.Substring(start, len);
                if(!AddSubstring(part))
                    break;
            }
        }
        RemoveOverlappingRanges();
    }
}

public class PartialStringComparer {
    public float Compare(string s1, string s2) {
        SubstringRangeList srl1 = new SubstringRangeList(s1);
        srl1.AddStringToCompare(s2);
        SubstringRangeList srl2 = new SubstringRangeList(s2);
        srl2.AddStringToCompare(s1);
        return (srl1.Weight + srl2.Weight) / 2;
    }
}

Levenstein Abstand ist viel einfacher (angepasst von http://www.merriampark.com/ld. htm ):

public class Distance {
    /// <summary>
    /// Compute Levenshtein distance
    /// </summary>
    /// <param name="s">String 1</param>
    /// <param name="t">String 2</param>
    /// <returns>Distance between the two strings.
    /// The larger the number, the bigger the difference.
    /// </returns>
    public static int LD(string s, string t) {
        int n = s.Length; //length of s
        int m = t.Length; //length of t
        int[,] d = new int[n + 1, m + 1]; // matrix
        int cost; // cost
        // Step 1
        if(n == 0) return m;
        if(m == 0) return n;
        // Step 2
        for(int i = 0; i <= n; d[i, 0] = i++) ;
        for(int j = 0; j <= m; d[0, j] = j++) ;
        // Step 3
        for(int i = 1; i <= n; i++) {
            //Step 4
            for(int j = 1; j <= m; j++) {
                // Step 5
                cost = (t.Substring(j - 1, 1) == s.Substring(i - 1, 1) ? 0 : 1);
                // Step 6
                d[i, j] = System.Math.Min(System.Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost);
            }
        }
        // Step 7
        return d[n, m];
    }
}

Answer 2

Klingt wie Sie für eine Laut-basierte Algorithmen suchen, wie zum Beispiel soundex , NYSIIS oder double metaphone . Die erste eigentlich , welche mehr Ministerien verwenden, und ist trivial zu implementieren (mit vielen Implementierungen leicht verfügbar ). Der zweite ist ein etwas komplizierter und präzise Version der ersten. Letztere am weitesten arbeitet mit einigen nicht-englischen Namen und Alphabete.

Levenshtein Abstand ist eine Definition des Abstandes zwischen zwei beliebigen Zeichenkette. Es gibt Ihnen einen Abstand von 0 zwischen identischen Strings und Nicht-Null zwischen verschiedenen Strings, die auch nützlich sein, wenn Sie einen benutzerdefinierten Algorithmus entschließen.

Answer 3

Levenshtein ist in der Nähe, obwohl es vielleicht nicht genau, was Sie wollen.

Answer 4

Ich bezweifle es ist, wenn man bedenkt auch die Zollverwaltung scheint nicht eine befriedigende Antwort zu haben ...

Answer 5

Wenn es eine Lösung für dieses Problem ist ich, es ist ein Teil des Kerns C # ernsthaft bezweifeln. Aus der Spitze von meinem Kopf, wäre es eine Datenbank von ersten, mittleren und letzten Namen Frequenzen erfordert, sowie Rechnung für Initialen, wie in Ihrem Beispiel. Dies ist eine ziemlich komplexe Logik, die auf einer Datenbank von Informationen angewiesen ist.

Answer 6

Second Levenshtein-Distanz, welche Sprache Sie wünschen? Ich konnte eine Implementierung in C # auf Codeproject ziemlich leicht finden.

Answer 7

Bei einer Anwendung, arbeitete ich an, war das letzte Namensfeld als zuverlässig gilt. So präsentiert alle alle Datensätze mit dem gleichen Nachnamen an den Benutzer. Benutzer könnten von den anderen Feldern sortieren nach ähnlichen Namen zu suchen. Diese Lösung war gut genug, um stark die Frage des Benutzers Datensätze Erstellen doppelter zu reduzieren.

sieht im Grunde wie das Thema menschliche Beurteilung erfordert.