トップ > algorithm

javascriptで実装された編集距離 (レーベンシュタイン距離, Levenshtein Distance)を検証してみました。

algorithm javascript

編集距離 (レーベンシュタイン距離, Levenshtein Distance)は２つの文字列の類似値を知る為のアルゴリズムです。

編集距離の詳細、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/