2

是否有任何简单的算法来确定代表同一个人的 2 个名字的可能性?

我不是要求自定义部门可能使用的级别。只是一个简单的算法,它会告诉我“James T. Clark”是否很可能与“J. Clark”同名。托马斯·克拉克”或“詹姆斯·克拉克”。

如果有一个算法C#会很棒,但我可以翻译任何语言。

4

7 答案 7

4

听起来您正在寻找基于语音的算法,例如soundexNYSIISdouble metaphone。第一个实际上几个政府部门使用的,实施起来很简单(有许多现成的实施。第二个是第一个稍微复杂和更精确的版本。后者最适用于一些非英文名称和字母。

Levenshtein 距离是两个任意字符串之间距离的定义。它为您提供相同字符串之间的距离为 0,不同字符串之间的距离为非零,如果您决定制作自定义算法,这也可能很有用。

于 2008-09-16T01:22:33.863 回答
3

Levenshtein很接近,虽然可能不是你想要的。

于 2008-09-16T01:06:39.237 回答
2

我遇到过类似的问题并尝试先使用 Levenstein 距离,但它对我来说效果不佳。我想出了一种算法,它可以为您提供两个字符串之间的“相似性”值(更高的值意味着更多相似的字符串,“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;
    }
}

Levenstein 距离一要简单得多(改编自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];
    }
}
于 2008-09-16T01:32:58.753 回答
0

我怀疑有,考虑到即使是海关部门似乎也没有令人满意的答案......

于 2008-09-16T01:09:21.430 回答
0

如果这个问题有解决方案,我严重怀疑它是核心 C# 的一部分。在我的脑海中,它需要一个包含名字,中间名和姓氏频率的数据库,以及首字母缩写,就像你的例子一样。这是一个相当复杂的逻辑,依赖于信息数据库。

于 2008-09-16T01:11:46.167 回答
0

仅次于 Levenshtein 距离,你想要什么语言?我能够很容易地在 codeproject 上找到 C# 中的实现。

于 2008-09-16T01:13:34.680 回答
0

在我处理的一个应用程序中,姓氏字段被认为是可靠的。因此将所有具有相同姓氏的所有记录呈现给用户。用户可以按其他字段排序以查找相似的名称。该解决方案足以大大减少用户创建重复记录的问题。

基本上看起来这个问题需要人工判断。

于 2008-09-16T01:16:07.890 回答