読者です 読者をやめる 読者になる 読者になる
ようこそ。睡眠不足なプログラマのチラ裏です。

レーベンシュタイン距離とN-gramモデルのアルゴリズム。それは擬似Google Suggestっぽい何か。

プログラミング アルゴリズム LINQ C#3.0

きっかけは

レーベンシュタイン距離 - shin5papaの日記
http://d.hatena.ne.jp/shin5papa/20090311/1236745197




レーベンシュタイン距離とN-gramモデルで、擬似的なGoogle Suggest

レーベンシュタイン距離を使うことによって、擬似的にGoogle先生の「もしかして」とか、
Google Suggestっぽいことができそうかなーと思って、面白そうなのでお勉強してみた。
PHPでは標準で関数があるのかー。んー、面白いですねコレ。ということで、さっそくC#で書いてみることにしました。
ただ、このレーベンシュタイン距離のみの判定だけでは、距離が等しい結果が複数あるような場合の結果が、
イマイチ納得のゆくものにはならなかったので、更に N-gram *1による共起頻度での判定も併用することにしました。



Wikipedia - レーベンシュタイン距離

using System;

namespace ClassLibrary1
{
    /// <summary>
    /// レーベンシュタイン距離
    /// </summary>
    public static class LevenshteinDistance
    {
        public static int Compute(string s, string t)
        {
            if (s == null) throw new ArgumentNullException("s");
            if (t == null) throw new ArgumentNullException("t");

            int x = s.Length;
            int y = t.Length;

            if (x == 0) return y;
            if (y == 0) return x;

            int[,] d = new int[x + 1, y + 1];

            for (int i = 0; i <= x; d[i, 0] = i++) ;
            for (int j = 0; j <= y; d[0, j] = j++) ;

            int cost = default(int);
            for (int i = 1; i <= x; i++)
            {
                for (int j = 1; j <= y; j++)
                {
                    cost = (s.Substring(i - 1, 1) != t.Substring(j - 1, 1) ? 1 : 0);
                    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[x, y];
        }
    }
}

N-gramモデルを利用したテキスト分析

using System;
using System.Collections.Generic;

namespace ClassLibrary1
{
    /// <summary>
    /// N-gram
    /// </summary>
    public class Ngram
    {
        /// <summary>
        /// Unigram
        /// </summary>
        /// <param name="s"></param>
        /// <param name="t"></param>
        /// <returns></returns>
        public static decimal CompareUnigram(string s, string t)
        {
            return Compare(1, s, t);
        }

        /// <summary>
        /// Bigram
        /// </summary>
        /// <param name="s"></param>
        /// <param name="t"></param>
        /// <returns>
        /// </returns>
        public static decimal CompareBigram(string s, string t)
        {
            return Compare(2, s, t);
        }

        /// <summary>
        /// Trigram
        /// </summary>
        /// <param name="s"></param>
        /// <param name="t"></param>
        /// <returns></returns>
        public static decimal CompareTrigram(string s, string t)
        {
            return Compare(3, s, t);
        }

        private static decimal Compare(int n, string s, string t)
        {
            if (s == null) throw new ArgumentNullException("s");
            if (t == null) throw new ArgumentNullException("t");

            var noise = new List<string>();
            for (int i = 0; i < s.Length - (n - 1); i++)
            {
                var ngitem = s.Substring(i, n);
                if (!noise.Contains(ngitem)) { noise.Add(ngitem); }
            }
            if (noise.Count == 0) return 0;

           int coincidence = 0;
            for (int i = 0; i < t.Length - (n - 1); i++)
            {
                var ngitem = t.Substring(i, n);
                if (noise.Contains(ngitem)) { coincidence++; }
            }
            return (decimal)coincidence / noise.Count;
        }
    }
}

もしかして…

using System;
using System.Collections.Generic;

namespace ClassLibrary1
{
    public static class Utility
    {
        /// <summary>
        /// もしかして…
        /// </summary>
        /// <param name="s"></param>
        /// <param name="source"></param>
        /// <returns></returns>
        public static string GetPossibility(string s, IEnumerable<string> source)
        {
            if (s == null) throw new ArgumentNullException("s");
            if (source == null) throw new ArgumentNullException("source");

            List<string> possibilityList = new List<string>();
            int mincost = int.MaxValue;
            string moshikashite = null;
            foreach (string t in source)
            {
                int cost = LevenshteinDistance.Compute(s, t);
                if (cost == 0) return t;
                if (cost <= mincost)
                {
                    mincost = cost;
                    possibilityList.Add(t);
                }
            }

            decimal k = -1m;
            foreach (string t in possibilityList)
            {
                decimal result = Ngram.CompareBigram(s, t);
                if (k == -1m || result > k)
                {
                    k = result;
                    moshikashite = t;
                }
            }
            return moshikashite;
        }
    }
}

もしかして…ほにゃらら的な何か

using System;
using System.Collections.Generic;
using System.Linq;
using ClassLibrary1;

namespace ConsoleApplication1
{
    class program
    {
        public static void Main()
        {
            List<string> list = new List<string>();
            list.Add("クロワッサン");
            list.Add("クリイム");
            list.Add("クレーム");
            list.Add("クライム");
            list.Add("コロネパン");
            list.Add("クリーナ");
            list.Add("リクーム");
            list.Add("クローバースタジオ");
            list.Add("クローム");
            list.Add("クラウド");
            list.Add("クリゴハン");
            list.Add("クリキントン");
            list.Add("クリームパン");
            list.Add("クリスティーナ");
            list.Add("クロノトリガー");

            Console.WriteLine(">>もしかして…ほにゃらら的な何か");
            Console.WriteLine();
            while (true)
            {
                Console.WriteLine("何かキーワードを入力してください... ( exit で終了します。)");
                var input = Console.ReadLine();
                if (input == "exit") break;

                var candidate = (from s in list
                                 let ld = LevenshteinDistance.Compute(input, s)
                                 let bigram = Ngram.CompareBigram(input, s)
                                 orderby bigram descending
                                 orderby ld ascending 
                                 select new { LD = ld, Value = s }).Take(5);
               
                foreach (var item in candidate)
                    Console.WriteLine("LD [{0}] : {1}", item.LD, item.Value);
 
                Console.WriteLine();
                Console.WriteLine("もしかして…‘{0}’", Utility.GetPossibility(input, list));
                if (!list.Contains(input)) list.Add(input);
                Console.WriteLine();
            }
        }
    }
}


Google SuggestではN-gram形態素解析を併用して実現されているようですね。
形態素解析を使っているという点で、今回の作ったやつとはまったくの別物。サンプルはあくまで擬似に過ぎない。
ちなみに、Google Suggestで使われている形態素解析システムはGoogleお手製のではなくて、
他社のベイシス・テクノロジー社製のものを使っているようです。
Googleはなんでもセルフオーダーメイドするイメージがあったから、ちょっと意外。


おまけ

残念ながら商用利用は禁止されているようですが、
Googleから大規模日本語 N-gramデータ*2が提供されています。
http://googlejapan.blogspot.com/2007/11/N-gram.html


そういえば、Sennaなんてのも話題になっていたのを思い出しました。
http://qwik.jp/senna/FrontPageJ.html

*1:ある文字列の中で、N個の文字列または単語の組み合わせが、どの程度出現するかを調査する言語モデル

*2:Web から抽出した約200億文(約2550億単語)の日本語データから作成したN-gramデータ