狗狗的日记本本

这几日闲暇都在读SimMetrics的代码，前一段还有读WatiN的代码。发觉两者大量使用接口和抽象类的知识，特别恶补了一下这方面的东西。记录如下，与其说这两者是一个编程问题，不如说是哲学问题。

一、抽象类

抽象类是对【类】的一种再抽象，猫、狗、猪，都是一类动物，对对象某种层次的抽象，爱尔兰梗犬和英格兰梗犬则是更低一层的抽象，直到某一只狗，才是对象。对猫的更高一层抽象是猫科动物，再高一层则是哺乳动物。

对类的抽象则是抽象类，在上例中，猫科动物就是对各种【属】的猫的一个高层次抽象，而哺乳动物则是更高层的抽象。

二、接口

接口是对行为的抽象，对类局部行为的抽象。不同的抽象类之间也许会有同一种行为，抽象类是对【属性】、【方法】、【字段】的抽象，接口是对两种类共有行为的抽象。一个类可以继承多个接口，多个类继承多个接口。

三、具体实现

涉及到了重构等知识，SimMetrics包首先写接口，然后是抽象类，最后由具体类---【功能包】继承抽象类和接口，实现设计上的清晰划分。功能和类别都划分地很清晰。

WatiN则复杂得多，实现了Brower抽象类后，具体的类则是本地的某种游览器，接口功能则优先于抽象类。设计远比SimMetrics复杂。

Jaro-Winkler distance算法C#实现版本，其实就是单独把SimMetrics包中的实现抽取出来，加上了C# 3.0的扩展方法后得到的程序段。用法十分简单了~~

var d="baidu.com".GetSimilarity("baidugoogle.com");

d既是两者的Jaro-Winkler相似度。用法是将以下代码拷贝粘贴到一个static 中去即可，具体参考【C# 3.0的扩展方法】。

public static class Jaro
    {
    /// 
    /// implements the Jaro string Metric.
    /// 

        const double defaultMismatchScore = 0.0;
        /// 
        /// a constant for calculating the estimated timing cost.
        /// 
        const double estimatedTimingConstant = 4.12e-005F;

        /// 
        /// gets the similarity of the two strings using Jaro distance.
        /// 
        /// 
        /// 
        /// a value between 0-1 of the similarity
        public static double GetSimilarity(this string firstWord, string secondWord) {
            if ((firstWord != null) && (secondWord != null)) {
                //get half the length of the string rounded up - (this is the distance used for acceptable transpositions)
                int halflen = Math.Min(firstWord.Length, secondWord.Length) / 2 + 1;
                //get common characters
                StringBuilder common1 = GetCommonCharacters(firstWord, secondWord, halflen);
                int commonMatches = common1.Length;
                //check for zero in common
                if (commonMatches == 0) {
                    return defaultMismatchScore;
                }
                StringBuilder common2 = GetCommonCharacters(secondWord, firstWord, halflen);
                //check for same length common strings returning 0.0f is not the same
                if (commonMatches != common2.Length) {
                    return defaultMismatchScore;
                }
                //get the number of transpositions
                int transpositions = 0;
                for (int i = 0; i < commonMatches; i++) {
                    if (common1[i] != common2[i]) {
                        transpositions++;
                    }
                }

                //calculate jaro metric
                transpositions /= 2;
                double tmp1;
                tmp1 = commonMatches / (3.0 * firstWord.Length) + commonMatches / (3.0 * secondWord.Length) +
                       (commonMatches - transpositions) / (3.0 * commonMatches);
                return tmp1;
            }
            return defaultMismatchScore;
        }

        /// 
        /// returns a string buffer of characters from string1 within string2 if they are of a given
        /// distance seperation from the position in string1.
        /// 
        /// string one
        /// string two
        /// separation distance
        /// a string buffer of characters from string1 within string2 if they are of a given
        /// distance seperation from the position in string1
        static StringBuilder GetCommonCharacters(string firstWord, string secondWord, int distanceSep) {
            if ((firstWord != null) && (secondWord != null)) {
                StringBuilder returnCommons = new StringBuilder();
                StringBuilder copy = new StringBuilder(secondWord);
                for (int i = 0; i < firstWord.Length; i++) {
                    char ch = firstWord[i];
                    bool foundIt = false;
                    for (int j = Math.Max(0, i - distanceSep);
                         !foundIt && j < Math.Min(i + distanceSep, secondWord.Length);
                         j++) {
                        if (copy[j] == ch) {
                            foundIt = true;
                            returnCommons.Append(ch);
                            copy[j] = '#';
                        }
                    }
                }

                return returnCommons;
            }
            return null;
        } 
    }

【本文章尚不完全，具体请参见维基百科】

==========================

主要应用在电信领域Hamming distance算法是比较定长字符串之间的字符差异算法。算法表述很简单：

• 1011101 and 1001001 is 2.
• 2173896 and 2233796 is 3.
• "toned" and "roses" is 3.

【本文章尚不完全，具体请参见维基百科】

==========================

• m为匹配的字符数（无关顺序）
• S的绝对值表达的是字符串的长度
• T：为了使两个字符串相等，需要交换的字符的次数（比如：CRATE 到 TRACE，只需要一次，于是T=1）

不买太多关子，目的非常简单。扩展SQL SERVER 2005/2008的字符串相似度算法函数，因为LD算法的计算量很大，涉及到矩阵运算，且随着字符串的长度复杂度递增，按照说明，起码为O(LENA*LENB)。还有很多通用的算法计算量都相当大，所以可以使用SQL CLR来封装现有的DLL。

1. Hamming distance
2. Levenshtein distance
3. Needleman-Wunch distance or Sellers Algorithm
4. Smith-Waterman distance
5. Gotoh Distance or Smith-Waterman-Gotoh distance
6. Block distance or L1 distance or City block distance
7. Monge Elkan distance
8. Jaro distance metric
9. Jaro Winkler
10. SoundEx distance metric
11. Matching Coefficient
12. Dice’s Coefficient
13. Jaccard Similarity or Jaccard Coefficient or Tanimoto coefficient
14. Overlap Coefficient
15. Euclidean distance or L2 distance
16. Cosine similarity
17. Variational distance
18. Hellinger distance or Bhattacharyya distance
19. Information Radius (Jensen-Shannon divergence)
20. Harmonic Mean
21. Skew divergence
22. Confusion Probability
23. Tau
24. Fellegi and Sunters (SFS) metric
25. TFIDF or TF/IDF
26. FastA
27. BlastP
28. Maximal matches
29. q-gram
30. Ukkonen Algorithms

OK，以上列表是为了搜索引擎，链接请看open source library of Similarity metrics，这个包是由NLP小组写作的扩展包，包含.NET语言以及JAVA语言。以上30个常用的NLP相关算法都已经集成进去了。

还有什么好说的，查看源码后你会发觉基本上都是最优解了（比如刚学会的LD算法，写得代码太优美了，LD算法能考虑到的极端边界情况这个库都考虑到了）

下一步就是结合这个已有的算法包，一个个算法试用了。JAVA版本优先开发，.NET是后面才开始的。像TFIDF or TF/IDF这样的算法都集成进去了，NLP的底层通用算法算是彻底一网打尽了~~~

==============

UPDATE:如果你仔细看过页面，会发现，很多算法SimMetrics包并未实现，当时是我一时激动，因为它实现了Jaro Winkler算法，就以为它实现了30个算法呢，不过这也是一份很好的参考。

另，其中有很多算法过于专业，一般都应用在生物学领域。