CreateField Blog

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

JSでWebに注釈をつけるAnnotatorで専用のサーバープログラムを使わなくてもannotationを保存、復元する方法

Webページにコメントなどの注釈をつけることができるJavascriptのライブラリannotatorがあります。

こちらの注釈の保存は、基本的には以下のPython製のバックエンドを利用することが想定されています。

https://github.com/openannotation/annotator-store

他には、ブラウザのローカルストレージに保存するプラグインもあります。 https://github.com/aron/annotator.offline.js

しかし、別サーバーを立てて管理はしたくなく、自前のWebサーバーでユーザーごとに紐付けて管理したいことがあると思います。

以下のようにannotationCreatedイベントのannotationからhighlightsのDOMを除外してどこかに保存し、@annotator.loadAnnotations(annotations)すれば、annotationを復元できそうだなぁってところまで調査しました。

    Annotator.Plugin.StoreLogger = (element) ->
      pluginInit: ->
        annotation = Cookies.get("annotator_test")
        if annotation?
          annotation = JSON.parse(annotation)
          @annotator.loadAnnotations([annotation])
        @annotator.subscribe('annotationCreated', (annotation) ->
          storable = jQuery.extend({}, annotation)
          delete storable.highlights
          Cookies.set("annotator_test", JSON.stringify(storable))
          console.info 'The annotation: %o has just been created!', annotation
        ).subscribe('annotationUpdated', (annotation) ->
          console.info 'The annotation: %o has just been updated!', annotation
        ).subscribe 'annotationDeleted', (annotation) ->
          console.info 'The annotation: %o has just been deleted!', annotation

    content = $('.target').annotator()
    content.annotator('addPlugin', 'StoreLogger')

後は適当に調整して、RailsにCRUD生やせば、ユーザーごとのannotationを管理できそうです。

が、デザインの変更やコンテンツの変更などでDOMがずれるとannotationを復元できなそうなので、今のところ、採用は見合わせることにしました。

一応のメモ書きで残しておきます。

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:枝刈りの条件をもう少し厳しくできる気がしているのですが、今のところうまい方法は思いついていません。

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

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を指定するとビットパラレル法になります。