1. 首页
  2. 问答
  3. 比较姓名

比较姓名

2008-09-16 51 views
2

是否有任何“简单”算法来确定代表同一人的两个名字的可能性？我并没有要求Custom部门可能使用的级别。只是一个简单的算法，可以告诉我'詹姆斯T.克拉克'是否最有可能与'J'同名。托马斯克拉克'或'詹姆斯秘书'。比较姓名

如果在C＃中有算法会很好，但我可以从任何语言进行翻译。

来源

2008-09-16 ADB

回答

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

编辑距离一个简单得多（改编自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-16 01:32:58

0

如果有这个问题，我严重怀疑它的核心C＃的一部分的解决方案。除了我的头顶，它需要一个包含名字，中间和姓氏的数据库，并且需要输入姓名首字母缩写，如你的例子。这是相当复杂的依赖于信息数据库的逻辑。

来源

2008-09-16 01:11:46

0

第二次到Levenshtein距离，你想要什么语言？我能够很容易地在C＃上找到一个在codeproject上的实现。

来源

2008-09-16 01:13:34

0

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

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

来源

2008-09-16 01:16:07 Lee

4

听起来像您正在寻找基于语音的算法，如soundex,NYSIIS或double metaphone。实际上第一个是几个政府部门使用的，并且实施起来微不足道（许多实现很容易available）。第二个是第一个稍微更复杂，更精确的版本。后者大多与一些非英文名字和字母一起工作。

Levenshtein distance是两个任意字符串之间距离的定义。它给你在相同的字符串之间的距离为0，在不同的字符串之间为非零的距离，如果你决定做一个自定义的算法，这也可能是有用的。

来源

2008-09-16 01:22:33

相关问题

 相关问题