代码之家  ›  专栏  ›  技术社区  ›  ADB

比较名字

  •  2
  • ADB  · 技术社区  · 16 年前

    是否有任何“简单”的算法来确定代表同一个人的两个名字的相似性?我不是在要求海关部门可能使用的级别。只是一个简单的算法,它可以告诉我‘詹姆斯·T·克拉克’是否最可能与‘J·托马斯·克拉克’或‘詹姆斯·克拉克’同名。

    如果C语言中有一个algo,那就太好了,但是我可以从任何语言中翻译。

    7 回复  |  直到 16 年前
        1
  •  2
  •   Stanislav Kniazev    16 年前

    我也遇到过类似的问题,我试着先用水平距离,但对我来说效果并不好。我想出了一个算法,它给出了两个字符串之间的“相似性”值(值越大表示相似的字符串越多,“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;
        }
    }
    

    距离1的水平面更简单(改编自 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];
        }
    }
    
        2
  •  4
  •   Andrey Fedorov    16 年前

    听起来您在寻找基于语音的算法,例如 soundex , NYSIIS double metaphone . 第一个事实上 多个政府部门使用的,并且实施起来很简单(许多实施都很容易实现) available )第二个版本是第一个版本的一个稍微复杂和更精确的版本。后者大多数与一些非英语名称和字母一起使用。

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

        3
  •  3
  •   Antti    16 年前

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

        5
  •  0
  •   Lucas Oman    16 年前

    如果有解决这个问题的方法,我严重怀疑它是核心C的一部分。在我的头上,它将需要一个数据库的名字,中间和姓氏频率,以及帐户的首字母,在您的例子中。这是一个相当复杂的逻辑,它依赖于一个信息数据库。

        6
  •  0
  •   George Mauer    16 年前

    其次是列文斯坦距离,你想要什么语言?我可以很容易地在代码项目的C中找到一个实现。

        7
  •  0
  •   Lee    16 年前

    在我研究的一个应用程序中,姓氏字段被认为是可靠的。 所以向用户展示了所有具有相同姓氏的记录。 用户可以按其他字段排序以查找相似的名称。 这个解决方案非常好,可以大大减少用户创建重复记录的问题。

    从根本上看,这个问题需要人类的判断。