javascriptで実装された編集距離 (レーベンシュタイン距離, Levenshtein Distance)を検証してみました。
編集距離 (レーベンシュタイン距離, Levenshtein Distance)は2つの文字列の類似値を知る為のアルゴリズムです。
編集距離の詳細、perlでの実装はid:naoyaさんが書かれています。
http://d.hatena.ne.jp/naoya/20090329/1238307757
どうゆう機能で使用されるのか?
百聞は一見に如かず…という事でhttp://book.cakephp.org/view/3/The-Manual
の検索フォームにvali等を入力すると候補が出てくると思います。
そのように入力されたテキストも類似値が計算出来るので、近似値でソートする事が出来ます。
javascriptでの実装
実際にbook.cakephp.orgで使用されているlevenshtein関数を使用してサンプルを実行してみました。
levanshtein.js
function levenshtein (s1, s2) { // http://kevin.vanzonneveld.net // + original by: Carlos R. L. Rodrigues (http://www.jsfromhell.com) // + bugfixed by: Onno Marsman // + revised by: Andrea Giammarchi (http://webreflection.blogspot.com) // + reimplemented by: Brett Zamir (http://brett-zamir.me) // + reimplemented by: Alexander M Beedie // * example 1: levenshtein('Kevin van Zonneveld', 'Kevin van Sommeveld'); // * returns 1: 3 if (s1 == s2) { return 0; } var s1_len = s1.length; var s2_len = s2.length; if (s1_len === 0) { return s2_len; } if (s2_len === 0) { return s1_len; } // BEGIN STATIC var split = false; try{ split=!('0')[0]; } catch (e){ split=true; // Earlier IE may not support access by string index } // END STATIC if (split){ s1 = s1.split(''); s2 = s2.split(''); } var v0 = new Array(s1_len+1); var v1 = new Array(s1_len+1); var s1_idx=0, s2_idx=0, cost=0; for (s1_idx=0; s1_idx<s1_len+1; s1_idx++) { v0[s1_idx] = s1_idx; } var char_s1='', char_s2=''; for (s2_idx=1; s2_idx<=s2_len; s2_idx++) { v1[0] = s2_idx; char_s2 = s2[s2_idx - 1]; for (s1_idx=0; s1_idx<s1_len;s1_idx++) { char_s1 = s1[s1_idx]; cost = (char_s1 == char_s2) ? 0 : 1; var m_min = v0[s1_idx+1] + 1; var b = v1[s1_idx] + 1; var c = v0[s1_idx] + cost; if (b < m_min) { m_min = b; } if (c < m_min) { m_min = c; } v1[s1_idx+1] = m_min; } var v_tmp = v0; v0 = v1; v1 = v_tmp; } return v0[s1_len]; }
var list = [ {"body":"livlis"}, {"body":"caramel"}, {"body":"camelmasa"}, {"body":"cat"}, {"body":"masa"}, {"body":"masaaaaaaaaaaa"} ]; for(var i=0;i<list.length;i++){ list[i].no = levenshtein('camelmasa', list[i].body); } list.sort(function(a, b) {return a.no-b.no}); for(var i=0;i<list.length;i++){ document.write(list[i].no+':'+list[i].body+'<br />'); }
実行結果
0:camelmasa 5:masa 6:caramel 7:livlis 7:cat 11:masaaaaaaaaaaa
きちんとソート出来ているのが確認出来ました。
phpでの場合は?
phpの場合はlevenshtein関数があります。
http://php.net/manual/ja/function.levenshtein.php
まとめ
http://www.livlis.com/で便利な機能を実装出来る様、編集距離アルゴリズム以外にも色々調べてみようと思います。
[PR]Spreeの情報を集めています。
ECを持ちたい方、仕事でECを使いたい方向けのコミュニティサイトです。
このサイトでは世界で最も使用されているECの1つであるSpreeについての情報を提供しています。
http://spreecommerce.jp/