名前の比較

Question

同じ人物を表す2つの名前の可能性を判断するための「単純な」アルゴリズムはありますか？私はカスタム部門が使用しているレベルの何かを求めていません。 「James T. Clark」が「J.」と同じ名前である可能性が高いかどうかを教えてくれる単なる盛り上がりです。トーマスクラーク "または"ジェームズクラーク "。

C＃でalgoがあれば素晴らしいですが、どの言語からでも翻訳できます。

Answer 1

私は同様の問題に直面し、まずLevensteinの距離を使用しようとしましたが、それは私にとってはうまく機能しませんでした。私は2つの文字列の間に "類似点"の値を与えるアルゴリズムを考え出しました（値が大きいほど類似した文字列、同じ文字列の場合は "1"）。この値はそれ自体ではあまり意味がありません（「1」ではなく、常に0.5以下）が、ハンガリーの行列をスローして2つの文字列のリストから一致するペアを見つけると非常にうまくいきます。

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

Answer 2

Levenshteinは近いですが、正確にはあなたが望むものではないかもしれません。

Answer 3

私は真剣にそれがコアのC＃の一部だ疑うこの問題に対する解決策がある場合でも、Customs Department doesn't seem to have a satisfactory answer ...

Answer 4

を考慮すると、そこにある疑い。私の頭の上から離れて、あなたの例のように、イニシャルのためのアカウントだけでなく、ファースト、ミドル、ラストネームのデータベースが必要です。これは、情報のデータベースに依存するかなり複雑なロジックです。

Answer 5

Levenshtein距離に2番目に、どのような言語が欲しいですか？私はcodeprojectでC＃の実装をかなり簡単に見つけることができました。

Answer 6

私が取り組んだアプリケーションでは、姓フィールドは信頼できると見なされました。 ユーザーに同じ姓のすべてのレコードがすべて提示されました。 ユーザーは他のフィールドを並べ替えて類似した名前を探すことができます。 このソリューションは、重複レコードを作成するユーザーの問題を大幅に軽減するのに十分なものでした。

基本的には、問題が人間の判断を必要とするように見えます。

Answer 7

soundex、NYSIIS、またはdouble metaphoneのような音声ベースのアルゴリズムを探しているような音です。最初の実際のはであり、いくつかの政府部門が使用しています（多くの実装で容易にavailable）。 2番目は少し複雑で、より正確なバージョンです。後者のほとんどは英語以外の名前とアルファベットで動作します。

Levenshtein distanceは、任意の2つの文字列間の距離の定義です。これは、同じ文字列間で0の距離を与え、異なる文字列間で非ゼロであることを示します。これは、カスタムアルゴリズムを作成する場合にも役立ちます。