Comparer des noms

Question

Existe-t-il un algorithme "simple" pour déterminer la probabilité de 2 noms représentant la même personne? Je ne demande pas quelque chose du niveau que le service personnalisé pourrait utiliser. Juste un simple algo qui me dirait si "James T. Clark" est probablement le même nom que "J. Thomas Clark 'ou' James Clerk '.

S'il existe un algo en C #, ce serait formidable, mais je peux traduire à partir de n'importe quelle langue.

Answer 1

J'ai rencontré un problème similaire et essayé d'utiliser d'abord la distance de Levenstein, mais cela n'a pas bien fonctionné pour moi. J'ai mis au point un algorithme qui vous donne la "similarité". valeur entre deux chaînes (une valeur plus élevée signifie plusieurs chaînes similaires, "1" pour des chaînes identiques). Cette valeur n’est pas très significative en soi (si elle n’est pas "1", toujours inférieure ou égale à 0,5), mais fonctionne assez bien lorsque vous introduisez dans Hungarian Matrix pour trouver des paires correspondantes dans deux listes de chaînes.

Utilisez comme ceci:

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

Le code derrière:

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;
    }
}

La distance 1 de Levenstein est beaucoup plus simple (adaptation de 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

On dirait que vous recherchez des algorithmes phonétiques, tels que soundex , NYSIIS ou double métaphone . Le premier est en réalité utilisé par plusieurs ministères et est simple à implémenter (avec de nombreuses implémentations facilement disponible ). La seconde est une version légèrement plus compliquée et plus précise de la première. La dernière fonctionne avec certains noms et alphabets non anglais.

La

distance de Levenshtein est une définition de la distance entre deux chaînes arbitraires. Cela vous donne une distance de 0 entre des chaînes identiques et non nulle entre différentes chaînes, ce qui peut également être utile si vous décidez de créer un algorithme personnalisé.

Answer 3

Levenshtein est proche, mais peut-être pas exactement ce que vous voulez.

Answer 4

Je doute qu'il en soit ainsi, même si Le service des douanes ne semble pas avoir de réponse satisfaisante ...

Answer 5

S'il existe une solution à ce problème, je doute sérieusement que cela fasse partie du noyau C #. De prime abord, cela nécessiterait une base de données des fréquences de prénom, de prénom et de nom, ainsi qu'un compte pour les initiales, comme dans votre exemple. C’est une logique assez complexe qui repose sur une base de données d’informations.

Answer 6

Deuxième à la distance de Levenshtein, quelle langue voulez-vous? J'ai pu facilement trouver une implémentation en C # sur codeproject.

Answer 7

Dans une application sur laquelle j'ai travaillé, le champ Nom était considéré comme fiable. Ainsi présenté tous les tous les enregistrements avec le même nom de famille à l'utilisateur. L'utilisateur peut trier les autres champs pour rechercher des noms similaires. Cette solution était suffisante pour réduire considérablement le nombre d'utilisateurs créant des enregistrements en double.

On dirait que la question nécessitera un jugement humain.