字串、段落、文章相似度比對(Levenshtein distance)

之前介紹過文章相似度比對，今天要來介紹一個舉凡是兩個字串(string)都可以拿來算相似度的方法，且運算速度還比較快。

Levenshtein distance(萊文斯坦距離)，其核心概念很簡單就是A字串要變的跟B字串一模一樣需要增加、刪除幾個字元，若增修的字元越少表示兩個字串越相似。

舉例:1234變成123編輯距離就是1。
相關的source code網路上資源有很多，隨意貼一個C#版本。
public static int LevenshteinDistance(string s, string t)
    {
        int n = s.Length;
        int m = t.Length;
        int[,] d = new int[n + 1, m + 1];

        if (n == 0)
        {
            return m;
        }

        if (m == 0)
        {
            return n;
        }

        for (int i = 0; i <= n; d[i, 0] = i++)
        {
        }

        for (int j = 0; j <= m; d[0, j] = j++)
        {
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

                d[i, j] = Math.Min(
                    Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                    d[i - 1, j - 1] + cost);
            }
        }
        return d[n, m];
    }
因此即可將你要比較的兩個字串丟到function計算，那編輯距離多少才能算相似呢?
一般來講要依比較的句子浮動，太長的句子編輯距離就可以多一點，依此類推。
門檻值可以經過實驗判定，是否找出來真的過於相似的兩個句子。
similarVaule = LevenshteinDistance(para[i], para[j]);
double threshold = para[i].Length * 0.7;
//相似度大於門檻值，則提醒
if (similarVaule <= threshold)
{
       string similar = similarVaule.ToString();
       dt.Rows.Add(para[i], para[j], similar);
}
上面的範例碼就是段落長度*0.7

在演算法有再談如何用遞迴(Recursive)的方式去計算編輯距離，不過這篇就以實作為主。