文字列のあいまい比較
森川です。
PHPで関数のマニュアルを探すさいに、chmを使うことも多いですが、僕はよくブラウザのアドレスに直接 www.php.net/[関数名] として検索を行っています。
そうすると、ちゃんとした関数名を忘れていても、似通った関数名の一覧が表示されるので結構便利です。該当する関数がない場合に似通った単語を探すという処理をマニュアルページでは行っています。
PHPマニュアルのページはソースを見ることができます。間違った関数を指定した場合、「http://jp2.php.net/manual-lookup.php?pattern=str_repsdflaceeee&lang=ja」にリダイレクトされ、その中の「show source」リンクをクリックすると「http://jp2.php.net/source.php?url=/quickref.php」にジャンプします。
実際には、以下のようにsimilar_text関数を使用して２つの単語の類似性を計算しています。
// Compute similarity of the name to the requested one
if (function_exists('similar_text') & & !empty($notfound)) {
similar_text($funcname, $notfound, $p);
$temp[$entry] = $p;
}
それ以外にも同じように類似性を計算するための関数として、levenshtein関数があります。計算量としてはlevenshtein関数の方が小さいようです。（参考：レーベンシュタイン距離）
しか し、大量の単語リストがデータベースに保存されている場合、リストを一度取得してからPHPで計算を行わなければならないので、どうせならデータベースに関数を追加してみました。勉強がてらPL/Pythonを使ってlevenshtein関数を実装してみました。以下がプロシージャの内容になります。
DROP FUNCTION IF EXISTS levenshtein(text, text);
CREATE FUNCTION levenshtein (source text, target text)
RETURNS integer
AS $$
if (target is None) or (source is None):
return None
len1 = len(source)
len2 = len(target)
if len1 == 0:
return len2
if len2 == 0 :
return len1
if (len1 > 255) or (len2 > 255):
return None
list1 = []
list2 = []
for i in range(len2+1):
list1.append(i)
list2.append(0)
tmp_cost = 0
for i1 in range(0, len1) :
list2[0] = list1[0] + 1
for i2 in range(0, len2) :
tmp_cost = 1
if source[i1] == target[i2] :
tmp_cost = 0
c0 = list1[i2] + tmp_cost
c1 = list1[i2 + 1] + 1
if (c1 < c0) :
c0 = c1
c2 = list2[i2] + 1
if (c2 < c0) :
c0 = c2
list2[i2+1] = c0
tmp = list1
list1 = list2
list2 = tmp
return list1[len2]
$$ LANGUAGE plpythonu;
おそらく普通にPostgreSQLを使用している場合はPL/Pythonは使えなくて、configureオプションに–with-pythonが必要になります。パッケージインストールの場合は、postgresql-pythonのようなパッケージを追加でインストールします。
インストールor再コンパイルができたら、PL/Pythonをデータベースに登録します。
createlang -U postgres plpythonu [db名]
あとは上記のプロシージャの内容をデータベースで実行するだけです。あ、ちなみにほとんどテストしていないので、使用する際は自己責任でお願いします。
これ、結構使えるのでは？と思ったのですが、全くスピードがでなくてすごくショック…
うーむ。 どうしたらよいのだろう。。。
