CreateField Blog

オープンソースを使って個人でWebサービスを開発・運営していたブログ

Groongaのパトリシアトライを使って高速なあいまい検索を実装した

Groonga

はじめに

あいまい検索はたとえば、編集距離を求めることによって実現することができます。

レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される。

レーベンシュタイン距離 - Wikipedia

最もベーシックな動的計画法によって編集距離を求める場合、計算量はO(nm)であり、レコード郡から編集距離が近いものだけを列挙する場合、さらにレコード数分の比較が必要になり計算量がとても大きくなってしまいます。

文字列の比較自体は、ビット演算を用いることによりそこそこ高速化できますが*1、この場合でもレコード数に対しては線形的に演算量が増えてしまいます。

色々調べていると、トライの構造を利用することにより、結構簡単に演算量を抑えられることがわかりました。 Fast and Easy Levenshtein distance using a Trie

そこで、この方法を全文検索エンジンGroongaのパトリシアトライで使えるようにして、高速なあいまい検索を実装してみました。

pat: Add grn_pat_fuzzy_search() by naoa · Pull Request #460 · groonga/groonga · GitHub

fuzzy_search関数(Groonga 6.0.0から)

fuzzy_search(column, query,
{"max_distance": 1, 
 "prefix_length": 0,
 "max_expansion": 0,
 "with_transposition": true}
)

{}は省略可能

  • option
property description default
max_distance 抽出する最大編集距離、これが小さいほど高速化が見込める 1
prefix_length 共通接頭辞の文字数、これを増やすとかなりの高速化が見込める 0
max_expansion 最大拡張数、文字数が短い場合などでキーが増えすぎるの抑制できる 0
with_transposition 文字の並び替えをコスト１として計算する false

パトリアトライを使って高速なあいまい検索をする場合、対象のカラムにTABLE_PAT_KEYのインデックスを張るか、TABLE_PAT_KEYの_keyである必要があります。インデックスがない場合は、シーケンシャルにレコードごとに編集距離を求めます。

ユースケース

名称や住所など表記ゆれが含まれやすいケースであいまいにマッチさせることができます。

> select companies --filter 'fuzzy_search(_key, "MICROSOFT")' 
  --output_columns '_key,_score' --output_pretty yes
[
  [
    0,
    1456591234.55597,
    0.0919983386993408
  ],
  [
    [
      [
        14
      ],
      [
        [
          "_key",
          "ShortText"
        ],
        [
          "_score",
          "Int32"
        ]
      ],
      [
        "MICROSOFT",
        2
      ],
      [
        "MICCROSOFT",
        1
      ],
      [
        "MICOSOFT",
        1
      ],
      [
        "MICDROSOFT",
        1
      ],
      ...
    ]
  ]
]

スコアは最大編集距離 - 実際の編集距離 + 1です。完全に一致したものは最大編集距離+1、最も遠いものが1になります。他のマッチングスコアとなじませるために編集距離と大小関係を逆転させています。

高速化のポイント

高速化の主要なポイントは以下の２つです。

  1. できるだけ同じ接頭辞の部分の計算結果を使い回す
  2. 求めたい最大編集距離のパラメータを渡すことにより、最大編集距離以下にならないことが確定した時点でその子ノードの探索、編集距離演算をスキップする

共通接頭辞の演算結果使い回し

動的計画法では、２つの文字列をマトリックスのx軸とy軸にマッピングし、行ごとに

  • 左隣+1(挿入)
  • 上+1(削除)
  • 左斜め上+1(置換)
  • 左斜め上と等しい場合、左斜め上+0

の最小値を計算していって最後に最も右下の値をとりだすことにより、編集距離を計算できます。

入力keyがdateでパトリシアトライのキーがdataだとすると以下のようにして1が求められます。

d a t e
0 1 2 3 4
d 1 0 1 2 3
a 2 1 0 1 2
t 3 2 1 0 1
a 4 3 2 1 1

パトリシアトライでは辞書順にキーを取り出すことができます。dataの次がdatabだったすると以下のようにして2が求められます。

d a t e
0 1 2 3 4
d 1 0 1 2 3
a 2 1 0 1 2
t 3 2 1 0 1
a 4 3 2 1 1
b 5 4 3 2 2

ここで、dataまでの1~4行は上の表と同じでまったく変更が必要ありません。そのため、この途中の行の計算結果を使い回すことができます。 これで5行の計算から1行の計算だけに抑えることができます。*2

最大編集距離以上になる子ノードの枝刈り

パトリシアトライでは各ノードが共通の接頭辞でまとめられており、子ノードの編集距離は概ね親ノードの編集距離より大きくなります。

https://upload.wikimedia.org/wikipedia/commons/a/ae/Patricia_trie.svg

基数木 - Wikipedia

具体的には動的計画法では1行ごとに左隣、上、斜めだけしか見てないということから、子ノードの編集距離が親ノードの最終行の最小値未満になることはありません。そこで、求めたい最大編集距離のパラメータを渡すことにより、子ノードの探索をがっつりとやめることができます。*3

例えば、最大編集距離1が与えられた場合、上記のようにdatabで最終行の最小値は2ですので、次にどんな文字が来ようと、編集距離は1にはなり得ません。

さらにdatabaやdatabaseという子ノードがあっても、これらの探索、編集距離の演算をスキップすることができます。

これらにより、特にmax_distanceが十分に小さい範囲ではとても高速に編集距離が近いキーが列挙できます。

実験結果

日本語wikipediaのタイトル30万件と実際に使っている英語DBの全文検索用の語彙表でキー数が1785万件(これは多すぎでもうちょっと丁寧にトークンをフィルターすべきな気がしますが）でmax_distanceと文字数を変化させた実行時間を以下に示します。 それぞれ100件の実行時間の平均値で単位は秒(sec)です。

比較対象として、レコードごとに動的計画法で同じものを求めた結果(edit max_d=1)を示しています。

  • CPU Intel(R) Xeon(R) CPU E5620 @ 2.40GHz

日本語wikipediaタイトル キー数30万件

image 1

n_chars pat max_d=1 pat max_d=2 pat max_d=3 pat max_d=5 pat max_d=10 edit max_d=1
1 0.0372 0.066 0.0818 0.117 0.1312 0.1691
5 0.0801 0.1269 0.1703 0.2084 0.2328 0.52
10 0.1282 0.2465 0.2705 0.3091 0.381 0.9158
20 0.2055 0.3312 0.4291 0.5307 0.5319 1.6355
30 0.3007 0.4634 0.5278 0.6064 0.6419 2.3025

English lexicon キー数1785万件

image 2

n_chars pat max_d=1 pat max_d=2 pat max_d=3 pat max_d=5 pat max_d=10 edit max_d=1
1 0.012 0.028 0.233 2.099 6.334 13.712
5 0.007 0.103 0.782 3.62 11.075 44.911
10 0.021 0.171 1.168 6.293 16.482 80.639
20 0.01 0.149 1.701 10.762 32.621 152.047
30 0.019 0.23 2.674 15.95 53.588 223.545

max_distanceが1や2では、枝刈りがかなり効いて文字数やキー数が増えても実行時間が大きく増えないことがわかります。

日本語の方がキー数が大分すくないのにmax_distance=1や2のときに時間がかかっているのは、日本語の方が文字種が多いからだと思われます。英語だとアルファベットと記号、数字ぐらいしか使われていません。

max_distanceが大きく、キー数が増えすぎると結構遅くなってしまうので、最初にprefixで絞れるオプションも入れています。prefix_lengthを1だけでもいれるとキー数1785万件、文字数10、max_distanceが5で1.5sec(prefix_length=0の場合、11sec)ぐらいで求めることができました。

参考

http://stevehanov.ca/blog/index.php?id=114 https://murilo.wordpress.com/2011/02/01/fast-and-easy-levenshtein-distance-using-a-trie-in-c/

*1:ビットパラレルを使ってGroongaで高速な編集距離関数の検証 - CreateField Blog

*2:１文字ごとにノードを構成する単純なトライであれば、１つ前の最後の１行だけを保持しておくだけで実装することもできます。パトリシアトライでは複数文字単位で遷移しちゃうのでマトリックスを保持しています。

*3:枝刈りの条件をもう少し厳しくできる気がしているのですが、今のところうまい方法は思いついていません。