是否有任何"简单"算法来确定两个代表同一个人的姓名的相似性？我并不是在询问海关部门可能使用的水平。只是一个简单的算法就能告诉我'James T. Clark'是否最有可能与'J.托马斯·克拉克(Thomas Clark)或者"詹姆斯·克拉克(James Clerk)"。

如果C语言中有一种算法，那会很棒，但是我可以从任何语言进行翻译。

解决方案

回答

莱文施泰因(Levenshtein)距离酒店很近，尽管可能不完全是我们想要的。

回答

我怀疑那里是否存在，考虑到海关部门似乎也没有令人满意的答案...

回答

如果有解决此问题的方法，我将严重怀疑它是否是核心C＃的一部分。就像示例一样，在我的头上，它需要一个包含名字，中间名和姓氏频率的数据库，并且要考虑首字母缩写。这是相当复杂的逻辑，它依赖于信息数据库。

回答

仅次于L​​evenshtein距离，我们想要哪种语言？我很容易在Con codeproject中找到一个实现。

回答

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

基本上，问题似乎需要人为判断。

回答

听起来我们正在寻找基于语音的算法，例如soundex，NYSIIS或者双音素。第一个实际上是几个政府部门使用的，并且实现起来很简单(许多实现很容易获得)。第二个是第一个的稍微复杂和精确的版本。后一个最适合某些非英语名称和字母。

Levenshtein距离是两个任意字符串之间的距离的定义。它使我们在相同的字符串之间的距离为0，而在不同的字符串之间的距离为非零，如果我们决定进行自定义算法，这也可能很有用。

回答

我也遇到过类似的问题，并尝试首先使用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];
    }
}