読者です 読者をやめる 読者になる 読者になる

CreateField Blog

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

Groonga 6.0.2から多段ドリルダウンが利用可能に

Groonga

GroongaはC/C++で書かれた国産の全文検索エンジンライブラリです。 サーバとしても組み込みのライブラリとしても利用することが可能です。

Groongaでは従来よりドリルダウン機能(ファセット)が提供されていましたが、 ドリルダウン機能の結果をつかってさらにドリルダウンするといったことはできませんでした。

Groonga6.0.2よりドリルダウン結果を使った多段のドリルダウンが利用できるようになりました。

これにより、たとえば、以下のようなユースケースで役に立つと思います。

  • タグのメタデータでのグループ
  • 大分類、中分類、小分類での段階的グループ

タグのメタデータのグループ結果

Groongaでは、以下のようにタグやカテゴリデータを別テーブルにして持つことができます。 この別テーブルにメタデータを追加で持たせることにより、さらに、そのメタデータで集計することができます。

たとえば、本の著者データに、著者の性別や、年齢、住所などを持たせて、それごとに集計することができます。

table_create Authors TABLE_PAT_KEY ShortText
[[0,0.0,0.0],true]
column_create Authors sex COLUMN_SCALAR ShortText
[[0,0.0,0.0],true]
table_create Books TABLE_HASH_KEY ShortText
[[0,0.0,0.0],true]
column_create Books authors COLUMN_VECTOR Authors
[[0,0.0,0.0],true]
load --table Books
[
{"_key": "Hello Groonga", "authors": ["Taro", "Hanako"]},
{"_key": "The first step for Groonga", "authors": ["Taro"]},
{"_key": "Mastering Groonga", "authors": ["Taro", "Hanako"]}
]
[[0,0.0,0.0],3]
load --table Authors
[
{"_key": "Taro", "sex": "Male"},
{"_key": "Hanako", "sex": "Female"}
]
[[0,0.0,0.0],2]
select Books \
  --drilldown[authors].keys authors \
  --drilldown[authors].output_columns _key,_nsubrecs \
  --drilldown[sex].table authors \
  --drilldown[sex].keys sex \
  --drilldown[sex].output_columns _key,_nsubrecs
[
  [
    0,
    0.0,
    0.0
  ],
  [
    [
      [
        3
      ],
      [
        [
          "_id",
          "UInt32"
        ],
        [
          "_key",
          "ShortText"
        ],
        [
          "authors",
          "Authors"
        ]
      ],
      [
        1,
        "Hello Groonga",
        [
          "Taro",
          "Hanako"
        ]
      ],
      [
        2,
        "The first step for Groonga",
        [
          "Taro"
        ]
      ],
      [
        3,
        "Mastering Groonga",
        [
          "Taro",
          "Hanako"
        ]
      ]
    ],
    {
      "authors": [
        [
          2
        ],
        [
          [
            "_key",
            "ShortText"
          ],
          [
            "_nsubrecs",
            "Int32"
          ]
        ],
        [
          "Taro",
          3
        ],
        [
          "Hanako",
          2
        ]
      ],
      "sex": [
        [
          2
        ],
        [
          [
            "_key",
            "ShortText"
          ],
          [
            "_nsubrecs",
            "Int32"
          ]
        ],
        [
          "Male",
          1
        ],
        [
          "Female",
          1
        ]
      ]
    }
  ]
]

メタデータを他のテーブルにして一元管理できて便利ですね。

大分類、中分類、小分類でのグループ

たとえば、日本->東京->新宿区など、階層的な分類を行うことができます。

table_create Addresses TABLE_PAT_KEY ShortText
[[0,0.0,0.0],true]
column_create Addresses country COLUMN_SCALAR ShortText
[[0,0.0,0.0],true]
table_create Authors TABLE_PAT_KEY ShortText
[[0,0.0,0.0],true]
column_create Authors address COLUMN_SCALAR Addresses
[[0,0.0,0.0],true]
table_create Books TABLE_HASH_KEY ShortText
[[0,0.0,0.0],true]
column_create Books authors COLUMN_VECTOR Authors
[[0,0.0,0.0],true]
load --table Books
[
{"_key": "Hello Groonga", "authors": ["Taro", "Hanako"]},
{"_key": "The first step for Groonga", "authors": ["Taro"]},
{"_key": "Mastering Groonga", "authors": ["Taro", "Hanako"]}
]
[[0,0.0,0.0],3]
load --table Authors
[
{"_key": "Taro", "address": "日本東京都"},
{"_key": "Hanako", "address": "アメリカニューヨーク州"}
]
[[0,0.0,0.0],2]
load --table Addresses
[
{"_key": "日本東京都", "country": "日本"},
{"_key": "アメリカニューヨーク州", "country": "アメリカ"}
]
[[0,0.0,0.0],2]
select Books \
  --drilldown[authors].keys authors \
  --drilldown[authors].output_columns _key,_nsubrecs \
  --drilldown[address].table authors \
  --drilldown[address].keys address \
  --drilldown[address].output_columns _key,_nsubrecs \
  --drilldown[country].table address \
  --drilldown[country].keys country \
  --drilldown[country].output_columns _key,_nsubrecs
[
  [
    0,
    0.0,
    0.0
  ],
  [
    [
      [
        3
      ],
      [
        [
          "_id",
          "UInt32"
        ],
        [
          "_key",
          "ShortText"
        ],
        [
          "authors",
          "Authors"
        ]
      ],
      [
        1,
        "Hello Groonga",
        [
          "Taro",
          "Hanako"
        ]
      ],
      [
        2,
        "The first step for Groonga",
        [
          "Taro"
        ]
      ],
      [
        3,
        "Mastering Groonga",
        [
          "Taro",
          "Hanako"
        ]
      ]
    ],
    {
      "authors": [
        [
          2
        ],
        [
          [
            "_key",
            "ShortText"
          ],
          [
            "_nsubrecs",
            "Int32"
          ]
        ],
        [
          "Taro",
          3
        ],
        [
          "Hanako",
          2
        ]
      ],
      "address": [
        [
          2
        ],
        [
          [
            "_key",
            "ShortText"
          ],
          [
            "_nsubrecs",
            "Int32"
          ]
        ],
        [
          "日本東京都",
          1
        ],
        [
          "アメリカニューヨーク州",
          1
        ]
      ],
      "country": [
        [
          2
        ],
        [
          [
            "_key",
            "ShortText"
          ],
          [
            "_nsubrecs",
            "Int32"
          ]
        ],
        [
          "日本",
          1
        ],
        [
          "アメリカ",
          1
        ]
      ]
    }
  ]
]

全てのレコードでグループ

これはオマケですが、今までレコード単一でしか、グループできませんでしたが、全てのレコードでグループすることができるようになりました。

私は円グラフを書くためにベクターカラムのグループ結果のレコード数の総数が欲しくてこの機能をつくりました。

table_create Authors TABLE_PAT_KEY ShortText
[[0,0.0,0.0],true]
column_create Authors sex COLUMN_SCALAR ShortText
[[0,0.0,0.0],true]
table_create Books TABLE_HASH_KEY ShortText
[[0,0.0,0.0],true]
column_create Books authors COLUMN_VECTOR Authors
[[0,0.0,0.0],true]
load --table Books
[
{"_key": "Hello Groonga", "authors": ["Taro", "Hanako"]},
{"_key": "The first step for Groonga", "authors": ["Taro"]},
{"_key": "Mastering Groonga", "authors": ["Taro", "Hanako"]}
]
[[0,0.0,0.0],3]
load --table Authors
[
{"_key": "Taro", "sex": "Male"},
{"_key": "Hanako", "sex": "Female"}
]
[[0,0.0,0.0],2]
select Books \
  --drilldown[authors].keys authors \
  --drilldown[authors].output_columns _key,_nsubrecs \
  --drilldown[authors_sum].table authors \
  --drilldown[authors_sum].output_columns _key,_sum \
  --drilldown[authors_sum].calc_target _nsubrecs \
  --drilldown[authors_sum].calc_types SUM
[
  [
    0,
    0.0,
    0.0
  ],
  [
    [
      [
        3
      ],
      [
        [
          "_id",
          "UInt32"
        ],
        [
          "_key",
          "ShortText"
        ],
        [
          "authors",
          "Authors"
        ]
      ],
      [
        1,
        "Hello Groonga",
        [
          "Taro",
          "Hanako"
        ]
      ],
      [
        2,
        "The first step for Groonga",
        [
          "Taro"
        ]
      ],
      [
        3,
        "Mastering Groonga",
        [
          "Taro",
          "Hanako"
        ]
      ]
    ],
    {
      "authors": [
        [
          2
        ],
        [
          [
            "_key",
            "ShortText"
          ],
          [
            "_nsubrecs",
            "Int32"
          ]
        ],
        [
          "Taro",
          3
        ],
        [
          "Hanako",
          2
        ]
      ],
      "authors_sum": [
        [
          1
        ],
        [
          [
            "_key",
            "ShortText"
          ],
          [
            "_sum",
            "Int64"
          ]
        ],
        [
          "_all",
          5
        ]
      ]
    }
  ]
]

おわりに

多段のドリルダウンについて紹介しました。

今後は、フィルター結果でのドリルダウンや、レンジなどで集計できたりすると、さらに集計の幅が広がりそうでよさそうですね。

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 文字の並び替えをコスト1として計算する 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になります。他のマッチングスコアとなじませるために編集距離と大小関係を逆転させています。

高速化のポイント

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

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

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

動的計画法では、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:1文字ごとにノードを構成する単純なトライであれば、1つ前の最後の1行だけを保持しておくだけで実装することもできます。パトリシアトライでは複数文字単位で遷移しちゃうのでマトリックスを保持しています。

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

MySQLでgenerated columnを使って圧縮したデータを自動的に解凍する

MySQL

MySQL5.7でできたgenerated columnってどんなのかな〜って調べていると、参照時に所定の計算結果を反映してから取得する仮想カラムVIRTUALと、更新時に所定の計算結果後の値を格納してくれるSTORED(Mariaの場合PERSISTENT)があることがわかりました。

MySQLでカラムごとに圧縮する方法 - CreateField Blog

こちらの記事ではCOMPRESS関数とUNCOMPRESS関数を使ってMySQLでカラム単位でデータを圧縮する方法を書きました。

これのCOMPRESSとUNCOMPRESSを自動的にやってくれる仮想カラムつくれるんじゃないのと思って試してみました。

MariaDB [comp]> CREATE TABLE comp (
    ->   compressed_body longblob NOT NULL,
    ->   body LONGTEXT GENERATED ALWAYS AS (UNCOMPRESS(compressed_body)) VIRTUAL
    -> ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
Query OK, 0 rows affected (0.01 sec)

MariaDB [comp]> INSERT comp(compressed_body) VALUES(COMPRESS("hoge hoge hoge hoge hoge hoge"));
Query OK, 1 row affected (0.01 sec)

MariaDB [comp]> SELECT body FROM comp;
+-------------------------------+
| body                          |
+-------------------------------+
| hoge hoge hoge hoge hoge hoge |
+-------------------------------+
1 row in set (0.01 sec)

自動的にUNCOMPRESSしてくれた。

MariaDB [comp]> CREATE TABLE comp (
    ->   body LONGTEXT NOT NULL,
    ->   compressed_body LONGBLOB GENERATED ALWAYS AS (COMPRESS(body)) PERSISTENT
    -> ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
Query OK, 0 rows affected (0.01 sec)

MariaDB [comp]> INSERT comp(body) VALUES("hoge hoge hoge hoge hoge hoge");
Query OK, 1 row affected (0.00 sec)

MariaDB [comp]> SELECT UNCOMPRESS(compressed_body) FROM comp;
+-------------------------------+
| UNCOMPRESS(compressed_body)   |
+-------------------------------+
| hoge hoge hoge hoge hoge hoge |
+-------------------------------+
1 row in set (0.00 sec)

自動的にcompressしてくれた。

MariaDB [comp]> CREATE TABLE comp (
    ->   body LONGTEXT NOT NULL,
    ->   compressed_body LONGBLOB GENERATED ALWAYS AS (COMPRESS(body)) PERSISTENT,
    ->   uncompressed_body LONGBLOB GENERATED ALWAYS AS (UNCOMPRESS(compressed_body)) VIRTUAL
    -> ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
ERROR 1900 (HY000): A computed column cannot be based on a computed column

繋げることはできなかった。

片手落ちだけど、自動的にuncompressしてくれるだけでもやや楽になったかな。

MySQLで編集距離を求めるUDF

先日、Groongaでビットパラレルで高速な編集距離の実装を検証してました。

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

編集距離とは挿入、置換、削除、並び替えの編集操作によって一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数です。 ちょこっとだけ表記ゆれしている文字列を抽出したりできます。

ちょっとMySQLでもカジュアルに使いたいなぁと思って編集距離を求めるUDFをさくっと作りました。

naoa/mysql-edit-distance · GitHub

1バイト文字であればビットパラレル法でそこそこ高速に編集距離を求めることができます。

10万レコードの比較

文字数x文字数 動的計画法 ビットパラレル固定長
62x62 11.6524 sec 0.1811 sec

とりあえず、英語で使いたかっただけということもあってビットパラレルオプションは日本語に対応していません。 ビットパラレルを使わない方であれば、日本語も対応しています。

使用例

CREATE TABLE IF NOT EXISTS `test` (
  `name` varchar(64) NOT NULL
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

INSERT INTO test VALUES("MySQL");
INSERT INTO test VALUES("MySQL2");
INSERT INTO test VALUES("MySQM");
INSERT INTO test VALUES("MySQ");
INSERT INTO test VALUES("MySLQ");
INSERT INTO test VALUES("MySOM");
INSERT INTO test VALUES("PostgreSQL");
INSERT INTO test VALUES("Oracle");

SELECT name, edit_distance(name, "MySQL") FROM test
WHERE edit_distance(name, "MySQL") < 3
ORDER BY edit_distance(name, "MySQL") ASC;

+--------+------------------------------+
| name   | edit_distance(name, "MySQL") |
+--------+------------------------------+
| MySQL  | 0                            |
| MySQL2 | 1                            |
| MySQ   | 1                            |
| MySQM  | 1                            |
| MySLQ  | 1                            |
| MySOM  | 2                            |
+--------+------------------------------+
6 rows in set (0.00 sec)

SELECT edit_distance("abc", "abd", 1);
+--------------------------------+
| edit_distance("abc", "abd", 1) |
+--------------------------------+
| 1                              |
+--------------------------------+
1 row in set (0.00 sec)

第3引数に1を指定するとビットパラレル法になります。

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

Groonga

Groongaではサジェスト機能のためにedit_distance関数が実装されています。

これはO(nm)の計算量が必要な動的計画法で文字数が多くなると結構遅くなります。

そこで、高速化するためにビットパラレル法をGroongaの関数で実装してみて比較してみました。

naoa/groonga-edit-distance · GitHub

ビットパラレル法

これのFigure 3.と4.のMyersの方の実装をしてみました。

A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances Included in the proceedings of the Prague Stringology Conference 2002 (PSC 2002). http://www.sis.uta.fi/~hh56766/pubs/psc02.pdf

ビット演算で並列に演算して高速化します。計算量はO(n/w m)のようです。 これ長い方を左にするとお得ぽいので長い方が左になるように選択しています。 64文字以下だとO(m)です。mは短い方の文字数。

とりあえず64文字までしか対応していません。64を超えると動的計画法が利用されます。

マルチバイト用の関数では文字をハッシュテーブルで整数値にマッピングしています。文字が増えれば増えるほどマッピングのコストがかかります。マッピングのコストを抑えるために1回のコマンド実行中ハッシュテーブルと左側の文字列のマッピング結果はキャッシュしています。

実験結果

100万件のレコードのscorerに実装したdamerau_edit_distance, edit_distance_bp, edit_distance_bp_varを使ってスコアを求めます。結果出力とスコア代入自体のコストもあるため、score代入のみのケースも示します。なお、全部transposition入りです(たいして差はなかったので)。

文字数x文字数 score代入のみ 動的計画法 ビットパラレル固定長 ビットパラレル可変長
62x62 0.31589 sec 74.16554 sec 1.38189 sec 6.19149 sec
3x62 0.31312 sec 5.26055 sec 0.91457 sec 5.87688 sec
62x3 0.31560 sec 5.73797 sec 0.93845 sec 1.81229 sec
15x15 0.31624 sec 5.40047 sec 0.93917 sec 2.79704 sec
3x3 0.31591 sec 1.19619 sec 0.79177 sec 1.37829 sec

ビットパラレルの方は文字が長くなってもあまり遅くなっていません。ビットパラレル可変長は文字をハッシュテーブルでマッピングしているため、文字数が3文字と非常に少ない場合は効果が低くむしろ時間がかかっています。

3x62の可変長は62x3に比べ結構遅くなっています。可変長の場合、左側の文字列とハッシュテーブルをキャッシュ*1しているのですが、右側はしていません。都度右側の長い文字列をマッピングするのに時間がかかっています(100万レコードの比較なので100万×62)。62x3の場合はキャッシュされる左側が長く、右側が3文字のマッピングだからその分速いです。固定長の方はマッピングがいらないので変わりません。

カラムの文字列をあらかじめマッピングした結果の整数ベクターカラムにしておけば、都度マッピングはいらなくなり、マッピングコストはほとんどなくなるかもしれません。ただ、それは事前に作る必要があって使いづらそうです。

感想

英語の64文字までの特に文字が長いケースで大きく速度の向上が期待できそうです。 日本語でも文字数がある程度あれば、向上が期待できますが、ハッシュテーブルにマッピングするのがめんどくさいです。

ただ、この方法では2つの文字列の比較の計算量がO(m)になったとしても100万レコードとの比較の場合、O(m)×100万が必要になっていまいます。

他の高速な編集距離の実装方法として、levenshtein automataというO(max edit distance) versionってのがあるらしく、O(n/w m)よりも大分はやそうですね。あいまい検索用途ならせいぜい1文字や2文字程度しかいらないのでよさそうです。

Levenshtein automata can be simple and fast

Luceneではこれが実装されているみたいです。

http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html

さきにこっちにきづけばよかった。。今度levenshtein automataを実装できそうだったら実装してみたいです。

このpatlの実装参考になるかな。

https://code.google.com/p/patl/source/browse/trunk/uxn/patl/levenshtein.hpp

*1:1回のselectコマンド実行中、すなわち100万レコードの比較中

Groongaでb Bit MinHashを使って高速に類似検索

Groonga Advent Calendar 2015の23日目の記事です。

はじめに

GroongaでJaccard係数を計算するプラグインを作る - CreateField Blog こちらの記事では、GroongaでJaccard係数を計算できるプラグインを作りました。しかしながら、毎回すべてのレコードについて類似度を計算すると非常に計算量が多くなってしまいます。

そこで、b Bit MinHashという方法を使って高速にJaccard係数を推定する方法を実装して試してみました。

naoa/groonga-minhash · GitHub

ハッシュ関数にはMurmur3のc port、乱数の生成にはXorShiftを利用しています。

MinHashとは

2つの集合に対するランダムなハッシュ関数による最小ハッシュ値が一致する確率は、Jaccard係数に等しいという性質を持ちます。

こちらでかなりわかりやすく説明されています。

乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩− - iwiwiの日記

www.slideshare.net

これ、結構おもしろい性質ですね。

1文書の集合の要素数をk個の最小ハッシュ値に削減することができます。kを大きくすればするほど、正しい確率に近づきます。

b Bit MinHashとは

MinHashでは集合の要素をk個の最小ハッシュ値で表現することができますが、さらに容量削減、演算量削減のため、提案されたのがb Bit MinHashです。b Bit MinHashは最小ハッシュ値の下位bビットのみを保存して演算に使うという方法です。当然ハッシュ値を少ない数値に落としますので衝突しまくります。1ビットなら50%の確率で間違っているはずです。

しかし、そのぶんkを大きくして、衝突確率を考慮して補正することにより、そこそこの精度で高速、且つ空間効率が良くJaccard係数が推定できるとして、良く利用されているようです。

b-Bit MinHashによる高速かつ省スペースな類似度判定 | SmartNews 開発者ブログ

1ビットの場合、ビット演算のみで2つの集合の最小ハッシュ値の一致数を計算できるので、非常に高速に計算できそうです。

精度

実際にどのくらいの精度が得られるか簡単に試してみました。

{A,B,C,D,....}{B,C,D,.....}と65次元ぐらいの集合を1つずつずれていくように用意してb=1ビット、k=64のb Bit MinHashでJaccard係数を推定してみます。正しければアルファベット順に類似度が低くなっていくはずです。

    [
      1000,
      [ "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa" ]
    ],
    [
      968,
      [ "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab" ]
    ],
    [
      937,
      [ "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae" ]
    ],
    [
      937,
      [ "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad" ]
    ],
    [
      937,
      [ "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac" ]
    ],
    [
      906,
      [ "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae", "af", "ag", "ah", "ai", "aj" ]
    ],
    [
      906,
      [ "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae", "af", "ag", "ah" ]
    ],
    [
      906,
      [ "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae", "af", "ag", "ah", "ai" ]
    ],
    [
      906,
      [ "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae", "af" ]
    ],
    [
      906,
      [ "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae", "af", "ag" ]
    ],
    [
      843,
      [ "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae", "af", "ag", "ah", "ai", "aj", "ak" ]
    ],
    [
      843,
      [ "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae", "af", "ag", "ah", "ai", "aj", "ak", "al", "am" ]
    ],

類似度は都合により1000倍してます。1000は1です。

B>C>[F,E,D]>[K,I,J,G,H]>[L,N] と概ね正しい順番が得られています。ただ、結構同じ類似度になってしまっていますね。 上のスライドにあるようにb Bit MinHashで高類似度は狭い範囲でスケッチを比較することにより、少し精度を出すのが難しいようです。*1

ただ、kを128とかもっと増やせば多少改善できそうですし、1ビット*kの数値だけ保存しておけば良いので、空間効率が良く類似度の演算も簡単なので結構使えそうですね*2

性能

単純にJaccard係数を求めるのと、b Bit MinHashでJaccard係数を推定する速度を比較してみました。 集合の要素数はすべて10です(k個の最小ハッシュ値しか保存してないので集合の要素数は類似度の計算には関係ありません)。

文書数 Jaccard係数 b Bit MinHash (b=1, k=64) b Bit MinHash (b=1, k=64) ソートなし
1K 0.408026218414307 sec 0.000944852828979492 sec -
10K 3.95593476295471 sec 0.0039210319519043 sec -
100K 27.2713441848755 sec 0.034470796585083 sec -
1M 363.50066947937 sec 0.344359159469604 sec 0.0878760814666748 sec
5M - 1.81920456886292 sec 0.420000314712524 sec

かなりはやいですね。5百万でも2秒かかりません。なお、この2秒は500万件のクイックソートがほとんどの時間を占めています。ソートなしだと0.4秒です。実際は高類似度だけを閾値で切ればいいので、5Mでも0.数秒で上位を計算できそうです。

おわりに

b Bit MinHashを使えば数百万以上の文書数でも高速且つそこそこの精度で類似検索ができることがわかりました。

結構使えそうなので、これを使ってレコメンドとかやってみたいなぁと考えています。

つぶやき

現在コマンドで実装されていますが、スコア関数のほうがselectで使えて使い勝手がいいのかなぁ。対象スケッチをコマンド実行中にキャッシュできればそっちでもいい気がする。

あと重み付きJaccardとかもできないか検討しよう。

上位の部分だけをあとで真のJaccard係数を計算するのもいいかもしれない。

このMinHash結構色々使えそう。たとえば文字Ngramを作って編集距離の前にざっくり文字列の類似度を求めてから編集距離を求めるとあいまい検索がはやくなりそう

*1:高類似度を改善するためにOdd Sketchesという手法が提案されているようです。すこし実装してみたのですが、うまくいかなかったのでまた今度少し検討したいと考えています。

*2:現状64までしか実装してませんが。

GroongaでJaccard係数を計算するプラグインを作る

Groonga Advent Calendar 2015の22日目の記事です。

はじめに

Groongaでのタグ検索と表記揺れとの戦い at Groonga Meatup 2015 - CreateField Blog こちらの発表では、編集距離ベースで誤字脱字ぽい類似タグを抽出して表記揺れを抽出する話をしました。

しかしながら、編集距離ベースでは文字情報しか見ていないので、文字数が少ないものや略語などの類似タグを抽出することはできません。

そこで、他のタグとの関連性で類似度を抽出するためGroongaのカラムでjaccard係数を計算できるプラグインを作りました。

naoa/groonga-minhash · GitHub

Jaccard係数とは

Jaccard係数とは、2つの集合の類似度を測る尺度です。類似ドキュメントやレコメンドなどに利用されます。 Jaccard係数は以下の式で表せられます。

J(A,B) = A∩B / A∪B

Jaccard index - Wikipedia, the free encyclopedia

A∩BはAND集合、すなわちAとBの要素のうち重なっている集合を示します。 A∪BはOR集合、すなわちAとBの要素を足し合わせた集合を示します。

たとえば、

A:{'商品A', '商品B', '商品C'} 
B:{'商品A', '商品C', '商品D'}
A∩B:{'商品A', '商品C'}
A∪B:{'商品A', '商品B', '商品C', '商品D'}

の場合、AとBのJaccard係数はA∩B/A∪B: 2/4 = 0.5となります。

column_similarityコマンド

Groongaのカラムのデータで類似度を計算できるコマンドです。現状Jaccard係数のみ実装されています。

naoa/groonga-minhash · GitHub

たとえば、以下のようにUsersというテーブルにpurchase_historiesというベクターカラムがあるとします。

plugin_register commands/recommend
[[0,0.0,0.0],true]
table_create Users TABLE_HASH_KEY ShortText
[[0,0.0,0.0],true]
column_create Users purchase_histories COLUMN_VECTOR ShortText
[[0,0.0,0.0],true]
load --table Users
[
{
  "_key": "Taro",
 "purchase_histories": ["Product A", "Product B"]
},
{
  "_key": "Jiro",
 "purchase_histories": ["Product A", "Product B", "Product C"]
},
{
  "_key": "Saburo",
 "purchase_histories": ["Product D", "Product E", "Product F"]
},
{
  "_key": "Shiro",
 "purchase_histories": ["Product A", "Product C", "Product F"]
}
]
[[0,0.0,0.0],4]

この場合、Taroというユーザのpurchase_historiesと最も似たpurchase_historiesを持つユーザはJiroであることを抽出することができます。

column_similarity Users purchase_histories \
--key Taro --output_columns _key,_score,purchase_histories
[
  [0,0.0,0.0],
  [
    [3],
    [
      ["_key","ShortText"],
      ["_score","Int32"],
      ["purchase_histories","ShortText"]
    ],
    [
      "Jiro",
      666,
      ["Product A","Product B","Product C"]
    ],
    [
      "Shiro",
      250,
      ["Product A","Product C","Product F"]
    ],
    [
      "Saburo",
      0,
      ["Product D","Product E","Product F"]
    ]
  ]
]

なお、現状_scoreはfloat出力できないため、便宜上1000倍されています。Groonga本体で小数出力ができるようになったら変更する予定です。

上記の例ではカラムは1つでしたが、複数のカラムを指定することも可能です。また、Groongaのスクリプト構文で検索した結果のみのjaccard similarityを計算することもできます。詳細はGitHubを参照してください。

今後について

テーブルの全レコードの類似度を計算するのは計算量がとても大きくなります。そこで、MinHash(b-bit MinHash, Odd Sketchesなど)と呼ばれる手法を使って高速にjaccard_similarityを推測できるコマンドを実装中です。

また、せっかくJaccard係数を実装するので簡単なレコメンド(ユーザベース協調フィルタリング)も試しに実装してみようと思っています。