Asial Blog

Recruit! Asialで一緒に働きませんか?

文字列のあいまい比較

カテゴリ :
バックエンド(プログラミング)
タグ :
PHP
Python
森川です。

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関数を使用して2つの単語の類似性を計算しています。

  1. // Compute similarity of the name to the requested one
  2. if (function_exists('similar_text') && !empty($notfound)) {
  3.   similar_text($funcname, $notfound, $p); 
  4.  $temp[$entry] = $p;
  5. }

それ以外にも同じように類似性を計算するための関数として、levenshtein関数があります。計算量としてはlevenshtein関数の方が小さいようです。(参考:レーベンシュタイン距離

しかし、大量の単語リストがデータベースに保存されている場合、リストを一度取得してからPHPで計算を行わなければならないので、どうせならデータベースに関数を追加してみました。勉強がてらPL/Pythonを使ってlevenshtein関数を実装してみました。以下がプロシージャの内容になります。

  1. DROP FUNCTION IF EXISTS levenshtein(text, text);
  2. CREATE FUNCTION levenshtein (source text, target text)
  3.   RETURNS integer
  4. AS $$
  5.   if (target is None) or (source is None):
  6.     return None
  7.   len1 = len(source)
  8.   len2 = len(target)
  9.   if len1 == 0:
  10.     return len2
  11.   if len2 == 0 :
  12.     return len1
  13.   if (len1 > 255) or (len2 > 255):
  14.     return None
  15.   list1 = []
  16.   list2 = []
  17.   for i in range(len2+1):
  18.     list1.append(i)
  19.     list2.append(0)
  20.   tmp_cost = 0
  21.   for i1 in range(0, len1) :
  22.     list2[0] = list1[0] + 1
  23.     for i2 in range(0, len2) :
  24.       tmp_cost = 1
  25.       if source[i1] == target[i2] :
  26.         tmp_cost = 0
  27.       c0 = list1[i2] + tmp_cost
  28.       c1 = list1[i2 + 1] + 1
  29.       if (c1 < c0) :
  30.         c0 = c1
  31.       c2 = list2[i2] + 1
  32.       if (c2 < c0) :
  33.         c0 = c2
  34.       list2[i2+1] = c0
  35.     tmp = list1
  36.     list1 = list2
  37.     list2 = tmp
  38.   return list1[len2]
  39. $$ LANGUAGE plpythonu;

おそらく普通にPostgreSQLを使用している場合はPL/Pythonは使えなくて、configureオプションに--with-pythonが必要になります。パッケージインストールの場合は、postgresql-pythonのようなパッケージを追加でインストールします。

インストールor再コンパイルができたら、PL/Pythonをデータベースに登録します。

  1. createlang -U postgres plpythonu [db名]

あとは上記のプロシージャの内容をデータベースで実行するだけです。あ、ちなみにほとんどテストしていないので、使用する際は自己責任でお願いします。

これ、結構使えるのでは?と思ったのですが、全くスピードがでなくてすごくショック…

うーむ。どうしたらよいのだろう。。。