CreateField Blog

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

Mroonga 7.06からMySQLのgenerated column/MariaDBのvirtual columnが利用可能に

全文検索エンジンGroongaMySQLストレージエンジンであるMroongaのソースをいじる機会があったので、ついでにMySQLのgenerated columnMariaDBvirtual column(computed column)の対応をしました。
次回リリースのMroonga 7.06からはgenerated columnを作ってそれに全文インデックスを使って高速に全文検索できるようになります。

MySQL5.7ではJSON型に対してFulltextインデックスを作るのが許可されていないのですが、generated columnJSON関数を使うことにより、JSONの中の特定の値に対して、全文検索を行うことができるようになります。

たとえば、JSON型のカラムにログを蓄積しておき、必要になったタイミングで特定の値のみをgenerated columnを作って全文検索を行ったりできます。 OAuthのAPI取得結果をJSONで入れておいて、後で必要になったら名前とかプロフィールを引っ張りだして検索するとか。

mysql> CREATE TABLE logs (
    ->   id INT,
    ->   record JSON,
    ->   message VARCHAR(255) GENERATED ALWAYS AS (json_extract(`record`, '$.message')) STORED,
    ->   FULLTEXT INDEX(message) comment 'tokenizer "TokenBigramSplitSymbolAlphaDigit"'
    -> ) ENGINE=Mroonga DEFAULT CHARSET=utf8mb4;
Query OK, 0 rows affected, 1 warning (0.01 sec)

mysql>
mysql> INSERT INTO logs(id, record) VALUES (1, '{"level": "info", "message": "start"}');
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO logs(id, record) VALUES (2, '{"level": "info", "message": "restart"}');
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO logs(id, record) VALUES (3, '{"level": "warn", "message": "abort"}');
Query OK, 1 row affected (0.00 sec)

mysql>
mysql> SELECT * FROM logs WHERE MATCH(message) AGAINST("ar" IN BOOLEAN MODE);
+------+-----------------------------------------+-----------+
| id   | record                                  | message   |
+------+-----------------------------------------+-----------+
|    1 | {"level": "info", "message": "start"}   | "start"   |
|    2 | {"level": "info", "message": "restart"} | "restart" |
+------+-----------------------------------------+-----------+
2 rows in set (0.04 sec)

Inplace alter tableの対応もいれれたので、既存のテーブルに対しても追加するカラムに対する値のコピーの負荷のみでスキーマ変更ができます(ALTER TABLE ADD col GENERATED ALWAYS..で自動的に値はコピーされる)。

検索時に毎回関数を評価しなくていいように、2つの日付のうち、最先の日のカラムを作っておくとかもできるかな。

mysql> CREATE TABLE Docs (
    ->   id INT,
    ->   app_date DATE,
    ->   priority_date DATE,
    ->   earliest_date DATE GENERATED ALWAYS AS (LEAST(app_date,priority_date)) STORED,
    ->   INDEX(earliest_date)
    -> ) ENGINE=Mroonga DEFAULT CHARSET=utf8mb4;
Query OK, 0 rows affected (0.01 sec)

mysql>
mysql> INSERT INTO Docs(id, app_date, priority_date) VALUES (1, "2017-01-01", "2016-12-24");
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO Docs(id, app_date, priority_date) VALUES (2, "2017-02-01", "2016-11-24");
Query OK, 1 row affected (0.00 sec)

mysql>
mysql> EXPLAIN SELECT * FROM Docs WHERE earliest_date > "2016-12-23";
+----+-------------+-------+------------+-------+---------------+---------------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type  | possible_keys | key           | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+-------+---------------+---------------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | Docs  | NULL       | range | earliest_date | earliest_date | 4       | NULL |    1 |   100.00 | Using where |
+----+-------------+-------+------------+-------+---------------+---------------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> SELECT * FROM Docs WHERE earliest_date > "2016-12-23";
+------+------------+---------------+---------------+
| id   | app_date   | priority_date | earliest_date |
+------+------------+---------------+---------------+
|    1 | 2017-01-01 | 2016-12-24    | 2016-12-24    |
+------+------------+---------------+---------------+
1 row in set (0.01 sec)

なお、MySQL5.7では、VIRTUALなgenerated columnには、Fulltextインデックスが許可されていないので、インデックスを作りたい場合は、 STOREDで作る必要があります。 MariaDBのInnoDBラッパーモードであれば、たぶんVIRTUALでもFulltextインデックスが作れると思います。 また、ストレージモードのVIRTUALカラムに対するインデックスは対応していません。

Mroongaを脱却してGroonga直接構成にしようと思ったりもしていましたが、MySQL Routerを使うと、mroonga_commandUDFでも向き先をちゃんと変更してくれたり、mroonga_commandのエスケープの問題も少し緩和されたようなので、まだしばらくMroonga構成で行こうと思っています。

特許の検索・分析サービスPatentfieldをリニューアルしました

はじめに

私は、2015年1月よりIP Nexusというスタートアップに所属しています。

仕事でPG書いたことがない人間が知財のWeb系のスタートアップに転職した話 - CreateField Blog

IP Nexusのメンバーは、投資銀行での経歴をもつ米国とドイツの知財訴訟弁護士や米国特許商標庁の元特許審査官の経歴をもつ弁護士など、知財に関する専門知識と知財専門家や投資家などとのグローバルなネットワークに強みを持っています。

そこで、IP Nexusは、2016年後半より大学や研究機関、個人発明家の知的財産である研究内容や発明(シーズ)を商業化、事業化につなげるお手伝いをはじめました。資金調達、法人化、商品開発などをハンズオンでお手伝いしています。

実際に、今、とある海外の個人発明家がもつ特許ポートフォリオをもとに、世界で商業化させるプロジェクトが走っており、現在、日本では京都大学のインキュベーション施設にオフィスを借りてオペレーションを開始しています。

このプロジェクトに注力するようになり、少しシステム開発に余力ができたため、元々私が個人で開発していた特許の検索サービスPatentfieldをフルリニューアルして、新たに事業として立ち上げることになりました。

独学で特許の全文検索サービスを開発しました - CreateField Blog

prtimes.jp

こちらは、基本的にシステム開発部分は私一人で8ヶ月ぐらいかけてリニューアルしました。

なぜやるか

特許権は、新規な技術の公開を代償に独占排他権を付与させるものですが、日本において公開された特許情報は一部の知財専門家以外にはあまり広く活用、認知されていないと感じています。

本来、公開技術情報はもっと使いたおされなければ、特許制度が産業の発達に寄与することはできず、むしろ阻害要因になるという考えさえあります。

たとえば、事業を行っていて、いきなり第三者からその機能は特許があるとイチャモンをつけられると、特許制度自体にとても悪いイメージを持つ事業者は多いのではないでしょうか。*1

現状、日本においては、公開技術情報の活用度合いと独占排他権のバランスが著しく悪いと考えています。 その関係を少しでも是正すべく、特許情報、発明情報の活用をより普及させることができる特許検索・分析ツール、プラットフォームを提供したいと考えています。

主な機能

Patentfieldでは、主に以下のような機能があります。

  • 最新の審査・審判経過情報を含む100種類以上の多様な検索項目と、ブーリアン検索、近傍検索、曖昧検索、前方一致検索など多様な検索手法による高速且つ柔軟な特許検索・分析
  • 機械学習を活用したセマンティックサーチ・類似検索
  • 出願人、被引用件数および特許分類など最大で120種類以上の特許データの属性情報を可視化
  • 40種類以上の特許審査・審判結果および経過情報によるカスタマイズ可能なパテントスコア
  • パテントスコアまたは出願件数による特許ランキング
  • 引用分析(サイテーションマップ)
  • 競合引用分析
  • Emailアラート
  • PDF一括ダウンロード
  • エクセルエクスポート

特許出願後の審査、審判手続きに基づいた絞込やスコアリング、集計など非常に高速かつ柔軟に検索・分析を行えます。

検索・分析機能は、すべてカラムストア機能付きの全文検索エンジンGroongaを拡張して利用しています。

曖昧検索や検索の高速化、バグ修正など一般的に利用できる部分は随時オープンソースとしてコントリビュートしました。

ミドルウェアの基礎的な部分のオープンソース開発に携わることにより、一部にとっては不利になる実装であっても 特許検索・分析のシチュエーションでは有利になるといった改修や機能拡張を、自分自身でC/C++で実装することができるようになりました。

セマンティックサーチ

Patentfieldでは、単純なキーワード検索の他にセマンティックサーチの機能も提供しています。

たとえば、以下の3つの文書は、人間が見れば、1.と3.の文書はほぼ同じ内容であり、2.の文書は他とは違うことが理解できます。 しかし、単純にそれぞれのキーワードに別の単語IDを割り振って、類似度を計算すると、1.の文書に対し、2.と3.の文書は同じ類似度になってしまいます。

  1. 情報処理装置/は/、/A/の/処理/を/行う
  2. 情報処理装置/は/、/B/の/処理/を/行う
  3. コンピュータ/は/、/A/の/処理/を/行う

セマンティックサーチでは、あらかじめ、機械学習によって「情報処理装置」と「コンピュータ」が同じぐらいの意味であることを学習させて、その学習結果にもとづき、類似検索を行います。 これにより、1.の文書に対しては、2.の文書よりも3.の文書のが似ているといった検索が可能となります。

この他、高速化など色々やっているのですが、それについては、そのうち解説するかもしれません。

今後について

収録国の拡充、UIの改善、検索精度・速度の改善、分析手法の拡充、知財訴訟データとの連携などたくさんやりたいことがあります。

現在は、京都大学 吉田キャンパス内にオフィスを借りて仕事をしており、つい先日、京都大学の学生さんのバイトを数名採用したところです。

デザイナーやエンジニアの方で特許や知財に関して興味がある方は、是非お気軽にお問い合わせ下さい。

*1:特にソフトウェア関係においては。

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

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のパトリシアトライを使って高速なあいまい検索を実装した

はじめに

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

レーベンシュタイン距離(レーベンシュタインきょり、英: 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:枝刈りの条件をもう少し厳しくできる気がしているのですが、今のところうまい方法は思いついていません。

ビットパラレルを使って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からword2vecを使って類似文書を取得してみる

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

全文検索エンジンGroongaからword2vecを簡単に使えるプラグイン - CreateField Blog こちらで作ったプラグインのsentence_vectorsオプションを試してみました。

naoa/groonga-word2vec · GitHub

  • 学習ファイル生成
dump_to_train_file docs companies_[company:],categories_[category:],title/,body/@$ \
  --filter 'year >= 2010' --sentence_vectors 1

130万文書ぐらい

  • 学習
word2vec_train --min_count 1 --window 20 --cbow 0 --threads 12 --iter 10 --sentence_vectors 1
  • 元の文書
> select docs --filter "_id == 10876407" --limit 1 --offset 0
--n_sort 1 --output_columns app_id,title,company,body --output_pretty yes
[
  [0,1449906004.79365,0.00154924392700195],
  [
    [
      [1],
      [
        ["app_id","ShortText"],
        ["title","LongText"],
        ["company","company"],
        ["body","LongText"]
      ],
      [
        "JP20100000014",
        "画像形成装置、印刷データ生成装置、プログラム、及び印刷データ生成方法",
        [
          "コニカミノルタビジネステクノロジーズ株式会社"
        ],
        "複数の演算部を用いてPDLデータから印刷データを生成する際の処理速度を向上させる。
【解決手段】本発明に係る画像形成装置は、PDLデータを受信する受信部と、複数の演算部を有し、
前記複数の演算部のそれぞれがページ単位で処理を行うタスク又はバンド単位で処理を行うタスクを
実行することにより、前記PDLデータに基づいて印刷データを生成する画像処理部と、前記PDL
データを解析して印刷ページ数を取得し、当該取得された印刷ページ数に応じて、前記ページ単位で
処理を行うタスクと前記バンド単位で処理を行うタスクのそれぞれに割り当てる前記演算部の数を
動的に設定する制御部と、前記生成された印刷データに基づき印刷媒体に画像を形成する印刷部と、
を備える。【選択図】図5A"
      ]
    ]
  ]
]
  • 類似文書
> word2vec_distance "doc_id:10876407" --sentence_vectors 1
 --limit 10 --offset 0  --n_sort 10 
 --table ftext --column app_id,title,company,body --output_pretty yes
[
  [0,1449906234.40363,1.26499772071838],
  [
    [10],
    [
      ["app_id","ShortText"],
      ["title","LongText"],
      ["company","company"],
      ["body","LongText"]
    ],
    [
      "JP20100000012",
      "画像形成装置、印刷データ生成装置、プログラム、及び印刷データ生成方法",
      [
        "コニカミノルタビジネステクノロジーズ株式会社"
      ],
      "(57)【要約】【課題】複数の演算部を用いてPDLデータから印刷データを生成する場合に、
印刷対象となる個々のPDLデータに応じて最適な演算部の割り当てを行うことを可能とする。
【解決手段】本発明に係る画像形成装置は、PDLデータを受信する受信部と、複数の演算部を有し、
前記複数の演算部のそれぞれが前記PDLデータの言語解析処理又は前記言語解析処理後のラスタライズ
処理を実行することにより、前記PDLデータに基づいて印刷データを生成する画像処理部と、前記
PDLデータに基づいて前記ラスタライズ処理の重み値を算出し、当該算出された重み値に応じて、
前記言語解析処理と前記ラスタライズ処理のそれぞれに割り当てる前記演算部の数を動的に設定する
制御部と、前記生成された印刷データに基づき印刷媒体に画像を形成する印刷部と、を備える。
【選択図】図5A"
    ],
    [
      "JP20110129405",
      "画像形成装置、画像形成方法、及びコンピュータプログラム",
      [
        "キヤノン株式会社"
      ],
      "【要約】【課題】 1ページを複数のブロックに分割するための処理の負荷を分散させる。
【解決手段】 PDLデータから中間データを生成する処理と、中間データを画像データに変換する
処理とを、別々のハードウェア(CPU106、描画処理H/W109)で実現する。CPU106は、
複数のバンドに分割された中間データを生成する。描画処理H/W109は、1つのバンドを複数の
ブロックに分割し、各ブロックの画像データを生成する。【選択図】 図1"
    ],
    [
      "JP20100228837",
      "画像形成装置、画像処理方法、プログラム",
      [
        "株式会社リコー"
      ],
      "【要約】【課題】描画部の監視を必要としないで描画部への描画範囲の割り当てを動的に行う
ことができる画像形成装置及び画像処理方法を提供すること。【解決手段】外部から取得した印刷データ
の画像を転写媒体に印刷する画像形成装置150であって、印刷データを解析し、描画対象とされる
オブジェクトの描画命令をページ毎に記述した描画命令データを生成する描画命令生成手段12と、
描画命令データを記憶する描画命令データ記憶手段15と、描画命令データを読み出して、予め分割
されている描画範囲に対応づけられた描画命令を実行して描画処理する複数の描画処理手段302と、
第一の描画範囲の描画処理が終了した第一の描画処理手段から描画終了の通知を受けた第二の描画
処理手段が第二の描画範囲を分割して、第一の描画処理手段に第二の描画範囲の一部の描画を要求する
描画範囲制御手段303を有する。【選択図】図1"
    ],
    [
      "JP20120013853",
      "画像処理装置,画像形成装置及び画像処理方法",
      [
        "セイコーエプソン株式会社"
      ],
      "【要約】【課題】複数種類のフォーマットの画像データを所定形式の変換データに変換
する画像処理装置において、処理を効率的に行う。【解決手段】画像データの印刷要求を入力し、
入力された印刷要求で要求された印刷対象の画像データのフォーマットを判定し、判定された
フォーマットに応じて、変換処理に用いられるリソースを確保する処理でありフォーマット毎に
異なる所定のリソース確保処理としてのフォーマットA用リソース確保処理又はフォーマットB用
リソース確保処理を実行する(ステップS100〜S240)。続いて、判定されたフォーマット
に応じて、確保されたリソースを用いて印刷対象の画像データから変換データを作成する変換処理
を実行する(ステップS250)。そして、判定されたフォーマットに応じたリソースが既に確保
されているときには(ステップS130,S190でYES)、変換処理前のリソース確保処理を
省略する。【選択図】図2"
    ],
    [
      "JP20130191649",
      "画像形成装置、画像形成装置における画像処理方法及びプログラム",
      [
        "株式会社リコー"
      ],
      "【要約】【課題】  プリンタ描画の初期化処理を高速に行うことで、画像形成効率を向上
させる。【解決手段】画像形成装置であって、フレームメモリ211aに記憶したビットマップ
イメージを、当該ビットマップイメージを生成した印刷データに基づき消去する、それぞれクリア
処理部206の第1の消去手段及び前記フレームメモリ211aに記憶したビットマップイメージ
を全面消去する第2の消去手段と、第1または第2の消去手段によりフレームメモリ211aに
記憶されたビットマップイメージの消去に掛かる時間と、次に記憶するビットマップイメージの
生成に掛かる時間を比較する比較手段204aと、前記比較手段204aの比較結果に基づき、
当該生成されたビットマップイメージの消去手段として、第1または第2の消去手段のいずれかを
選択する選択手段204bを有する。【選択図】図2"
    ],
    [
      "JP20130192449",
      "印刷システム、印刷方法および印刷プログラム",
      [
        "コニカミノルタ株式会社"
      ],
      "【要約】【課題】印刷の全体処理時間を短縮できる印刷装置を提供する。【解決手段】
複数の描画用オブジェクトの画像データおよび印刷設定を含む印刷ジョブから、印刷ジョブに
属する各ページにおける前記描画用オブジェクト毎の配置位置情報および描画用オブジェクト
毎に必要な画像生成機能を解析して、解析結果情報を生成する解析部と、異なる画像生成機能
を有し、描画用オブジェクトの画像データから印刷用画像データを生成可能な複数の画像生成部と、
解析結果情報に基づいて、描画用オブジェクトの画像データおよび配置位置情報を、それぞれ
必要な画像生成機能を有する画像生成部に振り分ける振分部と、複数の画像生成部において
生成された複数の印刷用画像データおよび対応する配置位置情報を収集して、解析結果情報に
基づいて、ページ単位に印刷用画像データを合成して、ページ画像を生成する合成部と、ページ
画像を印刷する印刷部と、を有する。【選択図】図13"
    ],
    [
      "JP20120024523",
      "画像形成装置、その制御方法、及びプログラム",
      [
        "キヤノン株式会社"
      ],
      "【要約】【課題】複数ページの画像出力を行う際に、当該複数ページ間の出力形態に
応じた関連性をプレビュー表示する画像形成装置、その制御方法、及びプログラムを提供する。
【解決手段】本画像形成装置は、印刷データの設定情報から、ページ間における出力形態に
応じた所定の関連性を解析し、所定の関連性が特定されたページについては、当該所定の関連性
を有する複数のページをグループとしたプレビュー画像を生成し、所定の関連性が特定され
なかったページについては、当該ページのみのプレビュー画像を生成し、プレビュー画像を
ページ順に表示部に表示する。【選択図】図3"
    ],
    [
      "JP20110015400",
      "画像形成装置、画像形成装置の制御方法、プログラム",
      [
        "キヤノン株式会社"
      ],
      "【要約】【課題】 複数のレコードを含むVDPジョブにおいて有効な試し印刷が可能
な画像形成装置を提供する。【解決手段】 VDPジョブを処理するプリンタ103であって、
試し印刷ジョブであると判定されたVDPジョブに含まれる複数のレコードのうち一部の
レコードを試し印刷をプリンタ部407に行わせ、一部のレコードの印刷が行われた後に、
印刷されていないレコードの印刷指示を受け付け、受け付けた印刷指示に応じて、試し印刷
により印刷されていないレコードの印刷をプリンタ部407に行わせる制御部403と有する。
【選択図】 図5"
    ],
    [
      "JP20140008836",
      "印刷制御装置の制御方法、印刷制御装置の制御プログラム、および印刷制御装置の制御プログラムを記録したコンピューター読み取り可能な記録媒体",
      [
        "コニカミノルタ株式会社"
      ],
      "【要約】【課題】クライアントPCのユーザーが、編集対象のジョブを簡単に見つける
ことを可能にする印刷制御装置の制御方法を提供する。【解決手段】本発明の印刷制御装置の
制御方法は、印刷制御装置の記憶部に記憶されている一のジョブについて、ラスタライズ処理
を実行してジョブ識別用の画像データを生成するステップS107と、ジョブ識別用の画像
データが生成された後、記憶部に記憶されているジョブの中に、ジョブ識別用の画像データが
未生成のジョブがあるか否かを判断するステップS108と、ジョブ識別用の画像データが
未生成のジョブがあると判断される場合、ステップS107およびステップS108を繰り返す
一方で、ジョブ識別用の画像データが未生成のジョブがないと判断される場合、ジョブ識別用の
画像データが生成済みのジョブについて、ラスタライズ処理を実行してジョブ編集用の画像
データを生成するステップS111を有する。【選択図】図8"
    ],
    [
      "JP20110137220",
      "画像形成装置、画像形成装置の制御方法、及びプログラム",
      [
        "キヤノン株式会社"
      ],
      "【要約】【課題】PDLデータの複数ページを並列で処理する画像形成装置における
PDLデータの処理状況を適切にユーザに提示すること。【解決手段】PDLデータの複数
ページを並列で処理する画像形成装置101は、出力モードとして、印刷データの処理と
印刷出力を並行して実行する第1出力モード(RIP while Print)、又は、全ページについて
印刷データの処理が完了してから印刷出力を実行する第2出力モード(RIP then Print)の
設定入力をユーザから受け付けて、不揮発性メモリに保持しておく。そして、画像形成装置
101は、出力モードが第1出力モードの場合、PDLデータの処理が完了したページの中で、
連続出力可能ページ数として1ページ目から連続したページ番号の最大値を特定できる情報を
ユーザに提示する。また、出力モードが第2出力モードの場合、展開済ページ数としてPDL
データの処理が完了しているページの数を特定できる情報をユーザに提示する。【選択図】図1"
    ]
  ]
]

このプラグインでは元のテーブルとカラムを指定することにより、テーブルの内容を出力することができます。

  • 元の文書2
> select ftext --filter "_id == 10876408" --limit 1 --offset 0
--output_columns app_id,title,company,abstract --output_pretty yes
[
  [0,1449913923.39666,0.000921726226806641],
  [
    [
      [1],
      [
        ["app_id","ShortText"],
        ["title","LongText"],
        ["company","company"],
        ["abstract","LongText"]
      ],
      [
        "JP20100000015",
        "心室の拡張機能を改善するためのインビボ装置",
        [
          "コルアシスト カルジオヴァスキュラー リミテッド"
        ],
        "(57)【要約】【課題】生体の臓器または組織に内科的または外科的装置を
接続するために適した接続要素を提供すること。【解決手段】薄い織物のパッチの
形態のガードルを含み、そのガードルの側方の端部から延びた複数のタブが反対側
のものと対をなすように配置され、各タブはその反対側のものと結合することができ、
それによりループを形成し、該ループ内に、該臓器または組織と接続されることとな
る装置の一部分を挿入する接続要素。【選択図】図11"
      ]
    ]
  ]
]

*類似文書例2

> word2vec_distance "doc_id:10876408" --sentence_vectors 1 --limit 5 --offset 0
 --n_sort 5 --prefix_filter "doc_id:"
 --table ftext --column app_id,title,company,abstract --output_pretty yes
[
  [0,1449919740.36363,1.23700165748596],
  [
    [5],
    [
      ["app_id","ShortText"],
      ["title","LongText"],
      ["company","company"],
      ["abstract","LongText"]
    ],
    [
      "JP20150021968",
      "心臓病態を治療するための補助及びリコイル機能を備える二相性及び動的調整可能サポートデバイス及び方法",
      [
        "ザ  テキサス  エー  アンド  エム  ユニヴァーシティー  システム",
        "コーイノーヴァ  インコーポレイテッド"
      ],
      "【要約】【課題】心臓の成長及びリモデリングのための、回復及び自然に
潜在的リハビリとなる機械的環境を最適化するように設計された機械的配向デバイス
及び療法を提供する。【解決手段】鬱血性心不全及び関連する心臓病態に罹患している
患者に移植されるように適合した直接心臓接触デバイスであって、心室補助、心室
サポート及び拡張期リコイルを提供する、又は心室サポート及び拡張期リコイル
のみを提供する手段を有する心臓デバイスである。【選択図】図1"
    ],
    [
      "JP20130542174",
      "装着用ガイドルーメン",
      [
        "アビオメド  インコーポレイテッド",
        "タオ  ゼンホン",
        "ボーガン  ステファン",
        "モンゴー  マリー‐イブ"
      ],
      "【要約】心臓内ポンプデバイスの中を第一の開口部から第二の開口部まで
延在しているガイドワイヤ通路を有する該ポンプデバイスと;該ポンプデバイス
の外部に位置する第一の末端を起点に、ポンプデバイスの第一の開口部を通って
該ポンプデバイスの中に入り、ガイドワイヤ通路に沿って延び、第二の開口部を
通って該ポンプデバイスから出て、該ポンプデバイスの外部に位置する第二の
末端まで延在しているルーメンとを含む装置を開示する。ルーメンは、該ルーメン
の中をガイドワイヤが第一の末端から第二の末端まで通るときに該ガイドワイヤが
前記通路に沿って配置されるように、ガイドワイヤを収容すべく構成されている。"
    ],
    [
      "JP20120511994",
      "マルチルーメンカニューレ",
      [
        "ソラテック コーポレーション"
      ],
      "【要約】本出願は、血流を血液ポンプレシピエントに提供するための
方法及び材料に関する。例えば、哺乳動物の循環系に接続し、血液ポンプ(12)
(例えば、補助装置)と共に使用することができる、カニューレ(11)を提供
する。【選択図】図3"
    ],
    [
      "JP20140525200",
      "カウンターパルセーション及び血流導管の結合のための装置、方法、およびシステム",
      [
        "アビオメド  インコーポレイテッド",
        "クン  ボブ",
        "グラッツ  エリック",
        "ザイス  トーステン",
        "シュパニアー  ゲルト",
        "スペンス  ポール",
        "ダウリング  ロブ",
        "ヘイスティー  ケイトリン"
      ],
      "【要約】内腔の第一の部分を画定する第一の導管部分と、内腔の第二の
部分を画定する第二の導管部分とを含む、血流導管を開示する。第一または
第二の導管部分のうち少なくとも一方が先端部分を含み得、第一または第二の
導管部分のうちもう一方が、膨らんだ領域を含み得る。"
    ],
    [
      "JP20110123146",
      "カニューレおよび補助循環装置",
      [
        "国立大学法人 東京大学",
        "ニプロ株式会社"
      ],
      "【要約】【課題】血液の補助循環における循環効率の向上を図ることが
可能なカニューレおよび補助循環装置を提供する。【解決手段】先端31および
基端32,33を有する管状に構成され、先端31側には第1開口部11および
第2開口部21が設けられ、補助循環を行なうために先端31が心臓60に直接
穿刺された状態においては、第1開口部11は大動脈66内に位置し、第2開口部
21は心室64内に位置するカニューレ100は、第1開口部11を含み、
第1開口部31から基端32に向かって延在する第1内腔10と、第1開口部11
よりも基端33側の部分に形成された第2開口部21を含み、第2開口部21から
基端33に向かって第1内腔10と並んで延在する第2内腔20と、を備える。
【選択図】図6"
    ]
  ]
]

Patricia Trieを使ってdoc_id:のベクトルのみを距離演算していますが、130万件ほどの文書に対して1.3secぐらいかかっています。 もし使うなら、もうちょっと高速化したいところだなぁ。

結果はそこそこ分類されていますが、この結果だともうちょっと頑張らないとって感じかなぁ。

全文検索エンジンGroongaからword2vecを簡単に使えるプラグイン

はじめに

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

GroongaはC/C++で書かれた高速な国産の全文検索エンジンです。

word2vecは、Googleが研究評価用に作った単語の特徴をベクトルで表現しニューラルネットモデルで教師なし学習をさせるツールです。

単語を文脈も考慮させたベクトルで表現しニューラルネットで学習することで、単語の意味的な足し引きができているんじゃないか( kingからman引いてwoman足したらqueenがでてきましたよとか。)ということで少し前に結構流行ったようです。

また、word2vecの作者が簡易的にsentenceのベクトル表現を使えるようにしたword2vecのコードもあるようです。

普段、Groongaを使ったそこそこの規模のデータベースをもっているので、Groongaに格納されたデータからword2vec/sentence2vecで簡単に学習させることができ、また、Groongaから単語ベクトルの演算ができるプラグインを作成しました*1

naoa/groonga-word2vec · GitHub

dump_to_train_fileコマンド Groongaのカラムから学習ファイル生成

Groongaのカラムからword2vecで学習できるように整形してファイルに出力します。

形態素解析やノーマライズ、記号削除などの前処理がオプション指定で行えるようになっています。

sentence_vectorsオプションを使うとdoc_id:とGroongaのテーブルの_idが紐付けられて出力されます。これにより後のベクトル演算時に元のテーブルと関連付ける事が可能です。

また、column名の後にカッコでカテゴリなど特定のカラムに格納されたタグ等に任意のラベルを付与できます。 たとえば、category:カテゴリAやcompany:会社名Aなどの形で学習させることで類似するカテゴリや会社のみを抽出することができます。

実行例

dump_to_train_file docs companies_[company:],categories_[category:],title/,body/@$ \
  --filter 'year >= 2010' --sentence_vectors 1

会社名とカテゴリは、スペースを_でつなげてフレーズ化してラベルをつけ、TitleとBodyは形態素解析、記号削除などをおこなっています。また--filterでテーブルの検索結果のみを出力することができます。

word2vec_trainコマンド word2vecコマンドを実行して学習

これはオプションを少しいじって実行パスにあるword2vecコマンドを実行するだけです。 このプラグインをインストールすると上記のsentence vector追記版のword2vecが自動的にbindirにインストールされます*2。 学習はGroongaを介して実行しなくても構いません。

word2vec_train --window 20 --cbow 0 --threads 12 --iter 10 --sentence_vectors 1

word2vec_distanceコマンド ベクトル距離を演算

word2vecで学習させたバイナリファイルを読み込み、単語ベクトルを演算します。初回のみバイナリファイル読み込んでをメモリに展開するため、少し時間がかかります。Groongaを常駐でサーバ実行している場合は一度読みこめば2度目からは素早く計算することができます。同時に複数のモデルファイルを読み込むことができます(20個まで)。

word2vecに付属しているdistanceコマンドをベースに以下を改良しています。

  • スペースと+/- で単語ベクトルの演算可
  • offset,limit,thresholdなどページ制御のためのオプション
  • sentence_vectorの場合、元のテーブルをひも付けてカラム出力、ソート
  • 高速化のため語彙表を配列ではなくPatricia Trieで保持

元々のdistance.cは語彙表から一致する単語を探すのに線形探索をしていますが、Patricia Trieを使うことによりマッチ時間の短縮が見込めます。

doc_id:や、category:など特定のラベル付けしたもののみを取得するような場合、Patricia Trieで非常に高速な前方一致検索が可能です。

以下の例では、2sec近くかかっていたのが0.01sec以下で類似カテゴリが取得可能となっています。

  • 改良前(全ワード+正規表現"company:.*"で絞込)
> word2vec_distance "company:apple" --is_phrase 1 --limit 5 --offset 0 \
  --n_sort 5 --white_term_filter "company:.*" --output_pretty yes
[
  [
    0,
    1449782162.00164,
    2.34969544410706
  ],
  [
    [
      5
    ],
    [
      [
        "_key",
        "ShortText"
      ],
      [
        "_value",
        "Float"
      ]
    ],
    [
      "company:google technology holdings",
      0.644274830818176
    ],
    [
      "company:research in motion",
      0.641874372959137
    ],
    [
      "company:htc",
      0.63908725976944
    ],
    [
      "company:lenovo (singapore) pte",
      0.63323575258255
    ],
    [
      "company:blackberry",
      0.622487127780914
    ]
  ]
]
  • 改良後(パトリシアトライで"company:"に前方一致)
> word2vec_distance "company:apple" --is_phrase 1 --limit 5 --offset 0 \
  --n_sort 5 --prefix_filter "company:" --output_pretty yes
[
  [
    0,
    1449781678.28364,
    0.00766372680664062
  ],
  [
    [
      5
    ],
    [
      [
        "_key",
        "ShortText"
      ],
      [
        "_value",
        "Float"
      ]
    ],
    [
      "company:google technology holdings",
      0.644274830818176
    ],
    [
      "company:research in motion",
      0.641874372959137
    ],
    [
      "company:htc",
      0.63908725976944
    ],
    [
      "company:lenovo (singapore) pte",
      0.63323575258255
    ],
    [
      "company:blackberry",
      0.622487127780914
    ]
  ]
]

このようにGroongaは全文検索だけでなくPatricia Trie、Double Array、HashのCライブラリとしても有用に使うことができます。今回のケースでは更新をしないので、Marisa Trieが使えたらより省メモリで構築できてよいかもしれません。

word2vec実行例

会社名のラベルをつけて類似会社名のみを取得してみます。

> word2vec_distance "company:トヨタ自動車株式会社" --limit 10 --offset 0 \
 --n_sort 10 --prefix_filter "company:" --output_pretty yes
[
  [
    0,
    1449815073.42663,
    0.138718605041504
  ],
  [
    [
      5
    ],
    [
      [
        "_key",
        "ShortText"
      ],
      [
        "_value",
        "Float"
      ]
    ],
    [
      "company:日産自動車株式会社",
      0.911168932914734
    ],
    [
      "company:三菱自動車工業株式会社",
      0.891977429389954
    ],
    [
      "company:富士重工業株式会社",
      0.870425820350647
    ],
    [
      "company:ダイハツ工業株式会社",
      0.858096361160278
    ],
    [
      "company:本田技研工業株式会社",
      0.839616179466248
    ]
  ]
]

類似しているぽい会社名が取得できました。

ベクトルの加減算も自由に行えます。

> word2vec_distance "company:トヨタ自動車株式会社 - company:日産自動車株式会社 + company:グーグル_インコーポレイテッド" \
--limit 5 --n_sort 5 --output_pretty yes
[
  [
    0,
    1449815137.37063,
    0.501566171646118
  ],
  [
    [
      5
    ],
    [
      [
        "_key",
        "ShortText"
      ],
      [
        "_value",
        "Float"
      ]
    ],
    [
      "company:グーグル__インコーポレイテッド",
      0.87317681312561
    ],
    [
      "company:グーグル・インコーポレーテッド",
      0.868086099624634
    ],
    [
      "company:ヤフー!_インコーポレイテッド",
      0.836208581924438
    ],
    [
      "company:アリババ・グループ・ホールディング・リミテッド",
      0.827649772167206
    ],
    [
      "company:マイクロソフト_コーポレーション",
      0.825306117534637
    ]
  ]
]

あ、表記ゆれが結構あるな。。

会社名の総数は単語の語彙数よりは数が少ないのでそこそこ高速に検索できています。最初にカテゴリーかなにかで分類すれば、結構高速に得られますね。

sentence2vec実行例

dump_to_train_file Entries title,tag,tags --sentence_vectors 1
word2vec_train --min_count 1 --cbow 1 --sentence_vectors 1
word2vec_distance "doc_id:2" --sentence_vectors 1 --table Entries --column _id,title,tag
[
  [
    0,
    0.0,
    0.0
  ],
  [
    [
      2
    ],
    [
      [
        "_id",
        "UInt32"
      ],
      [
        "title",
        "ShortText"
      ],
      [
        "tag",
        "Tags"
      ]
    ],
    [
      3,
      "Database",
      "Server"
    ],
    [
      1,
      "FulltextSearch",
      "Library"
    ]
  ]
]

doc_idを指定することにより(たぶん)類似する文書の取得でき、そのカラムを直接取得することができます。

実際の実行例のせようと思ってたのですが、min_countオプションを指定するのを忘れてdoc_idが除去されてしまいました。min_conutのデフォルトは5で出現数が5に満たない語彙は捨てられます。sentence vectorの場合は、--min_count 1にして除外されないようにしないといけませんね。実験結果はそのうち載せようと思います。

試してみました。

Groongaからword2vecを使って類似文書を取得してみる - CreateField Blog

おわりに

Groongaからword2vecを簡単に使うためのプラグインを紹介しました。 GroongaはMySQLでテーブル構築やデータ管理ができるMroongaや、PosrgreSQLからGroongaのインデックスを使うことができるPGroongaが開発されています。これらを使えば簡単にGroongaのテーブルを作ることができ、このプラグインを使えばword2vecを簡単に試すことができます。私はMroongaからこのプラグインを利用しています。GroongaやMySQLにデータがあって、わざわざ整形したりするのが面倒という場合はこのプラグインを使ってみてはいかがでしょうか。

word2vecと似たようなものでGloVeというのもあるみたいです。

この発表では編集距離ベースに誤記の表記揺れを抽出した例を紹介しましたが、word2vecをうまく使えば、略語や言い換えなど意味的な表記揺れもある程度取得可能かもしれませんね*3

*1:普通の人はgensimなどでPythonから使いたいでしょうが、なぜかGroonga first脳なので

*2:インストールしないことも可能

*3:ノイズも多いでしょうが