2

同じ人物を表す2つの名前の可能性を判断するための簡単なアルゴリズムはありますか?

カスタム部門が使用している可能性のあるレベルのものを求めているのではありません。'JamesT.Clark'が'Jと同じ名前である可能性が高いかどうかを教えてくれる単純なアルゴリズム。トーマスクラーク」または「ジェームズクラーク」。

アルゴリズムがあればそれはC#素晴らしいことですが、私はどの言語からでも翻訳できます。

4

7 に答える 7

4

soundexNYSIIS、またはdouble metaphoneなどの音声ベースのアルゴリズムを探しているようです。1 つ目は、実際にいくつかの政府部門が使用しているものであり、簡単に実装できます (多くの実装がすぐに利用可能です)。2 番目のバージョンは、最初のバージョンよりも少し複雑で正確なバージョンです。後者のほとんどは、英語以外の名前とアルファベットで機能します。

レーベンシュタイン距離は、任意の 2 つの文字列間の距離の定義です。これにより、同一の文字列間の距離が 0 になり、異なる文字列間の距離が 0 以外になります。これは、カスタム アルゴリズムを作成する場合にも役立ちます。

于 2008-09-16T01:22:33.863 に答える
3

レーベンシュタインは近いですが、あなたが望むものではないかもしれません.

于 2008-09-16T01:06:39.237 に答える
2

私は同様の問題に直面し、最初にレーベンスタイン距離を使用しようとしましたが、うまくいきませんでした。私は、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;
    }
}

レーベンスタイン距離 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];
    }
}
于 2008-09-16T01:32:58.753 に答える
0

関税局でさえ満足のいく答えを持っていないように見えることを考えると、私はそうではないと思います...

于 2008-09-16T01:09:21.430 に答える
0

この問題の解決策があれば、それがコア C# の一部であるとは思えません。私の頭の上では、あなたの例のように、名、ミドルネーム、姓の頻度のデータベースと、イニシャルを説明する必要があります。これは、情報のデータベースに依存するかなり複雑なロジックです。

于 2008-09-16T01:11:46.167 に答える
0

レーベンシュタイン距離に次ぐ言語は何ですか? codeproject で C# の実装を簡単に見つけることができました。

于 2008-09-16T01:13:34.680 に答える
0

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

基本的に、この問題は人間の判断が必要なようです。

于 2008-09-16T01:16:07.890 に答える