Сравнение имен

Question

Существует ли какой-нибудь "простой" алгоритм для определения вероятности появления двух имен, представляющих одного и того же человека?Я не прошу чего-то такого уровня, который мог бы использовать Пользовательский отдел.Просто простой алгоритм, который сказал бы мне, если бы "Джеймс Т.Кларк" - это, скорее всего, то же имя, что и "Дж.Томас Кларк" или "Джеймс Клерк".

Если в C # есть алгоритм, это было бы здорово, но я могу перевести с любого языка.

Answer 1

Я столкнулся с подобной проблемой и сначала попытался использовать расстояние Левенштейна, но у меня это плохо получилось.Я придумал алгоритм, который дает вам значение "сходства" между двумя строками (более высокое значение означает больше похожих строк, "1" для идентичных строк).Это значение само по себе не очень значимо (если не "1", то всегда 0,5 или меньше), но работает довольно хорошо, когда вы вводите венгерскую матрицу, чтобы найти совпадающие пары из двух списков строк.

Используйте вот так:

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

Код, стоящий за:

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

Первое расстояние Левенштейна намного проще (адаптировано из 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

Похоже, вы ищете алгоритмы, основанные на фонетике, такие как саундекс, НИЗИС, или двойной метафон.Первый на самом деле является то, что используют несколько правительственных ведомств, и тривиально для реализации (со многими готовыми реализациями Доступно).Вторая - это немного более сложная и точная версия первой.Последнее-большинство работает с некоторыми неанглоязычными названиями и алфавитами.

Расстояние Левенштейна это определение расстояния между двумя произвольными строками.Это дает вам расстояние, равное 0 между одинаковыми строками, и ненулевое между разными строками, что также может быть полезно, если вы решите создать собственный алгоритм.

Answer 3

Левенштейн это близко, хотя, возможно, не совсем то, что вы хотите.

Answer 4

Я сомневаюсь, что это так, учитывая даже Похоже, у Таможенного департамента нет удовлетворительного ответа...

Answer 5

Если есть решение этой проблемы, я серьезно сомневаюсь, что это часть ядра C #.С моей точки зрения, для этого потребовалась бы база данных частот имен, отчеств и фамилий, а также учет инициалов, как в вашем примере.Это довольно сложная логика, которая опирается на информационную базу данных.

Answer 6

Второе расстояние до Левенштейна, какой язык вы хотите?Мне удалось довольно легко найти реализацию на C # в codeproject.

Answer 7

В приложении, над которым я работал, поле Фамилии считалось надежным.Таким образом, пользователю были представлены все записи с одинаковой фамилией.Пользователь может выполнить сортировку по другим полям, чтобы найти похожие имена.Это решение было достаточно хорошим, чтобы значительно уменьшить проблему создания пользователями дублирующихся записей.

В принципе, похоже, что этот вопрос потребует человеческого суждения.