レーベンシュタイン距離とN-gramモデルのアルゴリズム。それは擬似Google Suggestっぽい何か。
きっかけは
レーベンシュタイン距離 - shin5papaの日記
http://d.hatena.ne.jp/shin5papa/20090311/1236745197
レーベンシュタイン距離とN-gramモデルで、擬似的なGoogle Suggest
レーベンシュタイン距離を使うことによって、擬似的にGoogle先生の「もしかして」とか、Google Suggestっぽいことができそうかなーと思って、面白そうなのでお勉強してみた。
PHPでは標準で関数があるのかー。んー、面白いですねコレ。ということで、さっそくC#で書いてみることにしました。
ただ、このレーベンシュタイン距離のみの判定だけでは、距離が等しい結果が複数あるような場合の結果が、
イマイチ納得のゆくものにはならなかったので、更に N-gram *1による共起頻度での判定も併用することにしました。
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]; } } }
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
