مقارنة أسماء

Question

هل هناك أي 'بسيطة' خوارزمية لتحديد لاحتمالية 2 أسماء تمثل نفس الشخص ؟ أنا لا أطلب شيئا من المستوى أن إدارة الجمارك قد تستخدم.مجرد algo أن تقول لي إذا كان 'جيمس ت.كلارك هو على الأرجح نفس اسم 'جيتوماس كلارك " أو "جيمس كلارك'.

إذا كان هناك algo في C# من شأنها أن تكون كبيرة, لكن لا يمكن أن يترجم من أي لغة.

Answer 1

لقد واجهت نفس المشكلة و حاولت استخدام واستعرضت اللجنة المسافة أولا ، لكنها لم تعمل بشكل جيد بالنسبة لي.لقد جاء مع خوارزمية أن يعطيك "التشابه" قيمة بين سلسلتين (أعلى قيمة يعني أكثر مماثلة سلاسل "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];
    }
}

Answer 2

يبدو أنك تبحث عن لفظي على أساس خوارزميات مثل soundex, NYSIIS, أو مزدوجة metaphone.الأولى فعلا هو ماذا العديد من الإدارات الحكومية واستخدام تافهة لتنفيذ (مع العديد من التطبيقات بسهولة المتاحة).والثاني هو قليلا أكثر تعقيدا وأكثر دقة من النسخة الأولى.هذا الأخير الأكثر يعمل مع بعض غير الإنجليزية أسماء الحروف الهجائية.

Levenshtein المسافة هو تعريف المسافة بين اثنين التعسفي السلاسل.يعطيك مسافة 0 بين سالسل متطابقة وغير صفر بين سلاسل مختلفة ، والتي قد يكون من المفيد أيضا إذا كنت ترغب في جعل خوارزمية مخصصة.

Answer 3

Levenshtein ، على الرغم من أن ربما ليس بالضبط ما تريد.

Answer 4

لا شك أن هناك بالنظر حتى إدارة الجمارك لا يبدو أن لديها إجابة مرضية...

Answer 5

إذا كان هناك حل لهذه المشكلة أشك أنها جزء من جوهر C#.من على قمة رأسي ، فإنه يتطلب قاعدة بيانات من الأول والأوسط والأخير اسم الترددات ، وكذلك حساب الحروف ، كما في المثال الخاص بك.هذا هو المنطق المعقدة إلى حد ما يعتمد على قاعدة بيانات من المعلومات.

Answer 6

الثاني أن Levenshtein المسافة ، أي لغة تريد ؟ كنت قادرا على العثور على التنفيذ في C# على codeproject بسهولة جدا.

Answer 7

في تطبيق عملت على آخر اسم الميدان يعتبر موثوق بها.لذا عرض جميع السجلات مع نفس اسم المستخدم.يمكن للمستخدم النوع من الحقول الأخرى للبحث عن أسماء مشابهة.هذا الحل كان جيدا بما فيه الكفاية إلى حد كبير في الحد من العدد من المستخدمين إنشاء سجلات مكررة.

في الأساس يبدو أن المسألة تتطلب الإنسان الحكم.