Groonga - fulltext search engine.

[Groonga-commit] groonga/groonga [master] Support GRN_OP_SIMILAR in grn_expr

null+****@clear***** null+****@clear*****
2012年 4月 23日 (月) 21:43:18 JST

• 前の記事 [Groonga-commit] groonga/groonga [master] test: add missing parameter for geo_in_circle(), geo_distance().
• 次の記事 [Groonga-commit] groonga/groonga [master] apt: enable security repository
• 記事の並び順: [ 日付 ] [ スレッド ] [ 件名 ] [ 著者 ]

Kouhei Sutou	2012-04-23 21:43:18 +0900 (Mon, 23 Apr 2012)

  New Revision: ce283e3a7a9233b0d2613050beecc4ea245936b7

  Log:
    Support GRN_OP_SIMILAR in grn_expr
    
    With this patch, similar search by select --filter "column *S 'TEXT'"
    is also available.
    
    fixes #1342

  Added files:
    test/function/suite/select/filter/similar.expected
    test/function/suite/select/filter/similar.test
  Modified files:
    lib/db.c
    lib/expr.c
    lib/ii.c

  Modified: lib/db.c (+2 -0)
===================================================================
--- lib/db.c    2012-04-23 19:00:50 +0900 (61471b1)
+++ lib/db.c    2012-04-23 21:43:18 +0900 (b540ef8)
@@ -8083,6 +8083,7 @@ grn_column_index(grn_ctx *ctx, grn_obj *obj, grn_operator op,
     case GRN_OP_PREFIX :
     case GRN_OP_SUFFIX :
     case GRN_OP_MATCH :
+    case GRN_OP_SIMILAR :
       for (hooks = DB_OBJ(obj)->hooks[GRN_HOOK_SET]; hooks; hooks = hooks->next) {
         default_set_value_hook_data *data = (void *)NEXT_ADDR(hooks);
         grn_obj *target = grn_ctx_at(ctx, data->target);
@@ -8150,6 +8151,7 @@ grn_column_index(grn_ctx *ctx, grn_obj *obj, grn_operator op,
       }
       break;
     case GRN_OP_MATCH :
+    case GRN_OP_SIMILAR :
       {
         grn_accessor *a = (grn_accessor *)obj;
         if (a->action == GRN_ACCESSOR_GET_KEY) {

  Modified: lib/expr.c (+9 -1)
===================================================================
--- lib/expr.c    2012-04-23 19:00:50 +0900 (d569318)
+++ lib/expr.c    2012-04-23 21:43:18 +0900 (eb43802)
@@ -942,6 +942,7 @@ grn_expr_append_obj(grn_ctx *ctx, grn_obj *expr, grn_obj *obj, grn_operator op,
     case GRN_OP_TABLE_CREATE :
     case GRN_OP_EXPR_GET_VAR :
     case GRN_OP_MATCH :
+    case GRN_OP_SIMILAR :
     case GRN_OP_PREFIX :
     case GRN_OP_SUFFIX :
     case GRN_OP_NOT_EQUAL :
@@ -3579,6 +3580,7 @@ scan_info_build(grn_ctx *ctx, grn_obj *expr, int *n,
   for (stat = SCAN_START, c = e->codes, ce = &e->codes[e->codes_curr]; c < ce; c++) {
     switch (c->op) {
     case GRN_OP_MATCH :
+    case GRN_OP_SIMILAR :
     case GRN_OP_PREFIX :
     case GRN_OP_SUFFIX :
     case GRN_OP_EQUAL :
@@ -3641,6 +3643,7 @@ scan_info_build(grn_ctx *ctx, grn_obj *expr, int *n,
   for (i = 0, stat = SCAN_START, c = e->codes, ce = &e->codes[e->codes_curr]; c < ce; c++) {
     switch (c->op) {
     case GRN_OP_MATCH :
+    case GRN_OP_SIMILAR :
     case GRN_OP_PREFIX :
     case GRN_OP_SUFFIX :
     case GRN_OP_EQUAL :
@@ -4111,13 +4114,18 @@ grn_table_select(grn_ctx *ctx, grn_obj *table, grn_obj *expr,
               }
               break;
             case GRN_OP_MATCH :
+            case GRN_OP_SIMILAR :
               {
                 grn_obj wv, **ip = &GRN_PTR_VALUE(&si->index);
                 int j = GRN_BULK_VSIZE(&si->index)/sizeof(grn_obj *);
                 int32_t *wp = &GRN_INT32_VALUE(&si->wv);
                 grn_search_optarg optarg;
                 GRN_INT32_INIT(&wv, GRN_OBJ_VECTOR);
-                optarg.mode = GRN_OP_EXACT;
+                if (si->op == GRN_OP_MATCH) {
+                  optarg.mode = GRN_OP_EXACT;
+                } else {
+                  optarg.mode = si->op;
+                }
                 optarg.similarity_threshold = 0;
                 optarg.max_interval = 0;
                 optarg.weight_vector = (int *)GRN_BULK_HEAD(&wv);

  Modified: lib/ii.c (+8 -3)
===================================================================
--- lib/ii.c    2012-04-23 19:00:50 +0900 (32cdc3e)
+++ lib/ii.c    2012-04-23 21:43:18 +0900 (caec749)
@@ -6016,9 +6016,14 @@ grn_ii_sel(grn_ctx *ctx, grn_ii *ii, const char *string, unsigned int string_len
   {
     grn_select_optarg arg = {GRN_OP_EXACT, 0, 0, NULL, 0, NULL, NULL, 0};
     if (!s) { return GRN_INVALID_ARGUMENT; }
-    if (optarg && optarg->vector_size > 0) {
-      arg.weight_vector = optarg->weight_vector;
-      arg.vector_size = optarg->vector_size;
+    if (optarg) {
+      if (optarg->mode == GRN_OP_SIMILAR) {
+        arg.mode = optarg->mode;
+      }
+      if (optarg->vector_size > 0) {
+        arg.weight_vector = optarg->weight_vector;
+        arg.vector_size = optarg->vector_size;
+      }
     }
     /* todo : support subrec
     grn_rset_init(ctx, s, grn_rec_document, 0, grn_rec_none, 0, 0);

  Added: test/function/suite/select/filter/similar.expected (+66 -0) 100644
===================================================================
--- /dev/null
+++ test/function/suite/select/filter/similar.expected    2012-04-23 21:43:18 +0900 (6804053)
@@ -0,0 +1,66 @@
+table_create Documents TABLE_HASH_KEY ShortText
+[[0,0.0,0.0],true]
+column_create Documents content COLUMN_SCALAR Text
+[[0,0.0,0.0],true]
+table_create Terms TABLE_PAT_KEY|KEY_NORMALIZE ShortText --default_tokenizer TokenBigram
+[[0,0.0,0.0],true]
+column_create Terms document_index COLUMN_INDEX|WITH_POSITION Documents content
+[[0,0.0,0.0],true]
+load --table Documents
+[
+["_key", "content"],
+["groonga の概要", "groonga は転置索引を用いた高速・高精度な全文検索エンジンであり、登録された文書をすぐに検索結果に反映できます。また、参照をブロックせずに更新できることから、即時更新の必要なアプリケーションにおいても高い性能を発揮します。\n\n全文検索エンジンとして開発された groonga ですが、独自のカラムストアを持つ列指向のデータベースとしての側面も持っています。そのため、MySQL ã‚„ PostgreSQL など、既存の代表的なデータベースが苦手とする集計クエリを高速に処理できるという特徴があり、組み合わせによって弱点を補うような使い方もできます。\n\ngroonga の基本機能は C ライブラリとして提供されていますが、MySQL ã‚„ PostgreSQL と連携させたり、Ruby から呼び出したりすることもできます。そのため、任æ
 „ã®ã‚¢ãƒ—リケーションに組み込むことが可能であり、多様な使い方が考えられます。 興味のある方は 利用例 をご覧ください。"],
+["全文検索と即時更新", "一般的なデータベースにおいては、追加・削除などの操作がすぐに反映されます。一方、全文検索においては、転置索引が逐次更新の難しいデータ構造であることから、文書の追加・削除に対応しないエンジンが少なくありません。\n\nこれに対し、転置索引を用いた全文検索エンジンでありながら、groonga は文書を短時間で追加・削除することができます。その上、更新しながらでも検索できるという優れた特徴を持っているため、全文検索エンジンとしてはとても柔軟性があります。また、複数の転置索引を統合するような重い処理を必要としないので、安定して高い性能を発揮することが期待できます。"],
+["カラムストアと集計クエリ", "現代は、インターネットを情報源とすれば、いくらでも情報を収集できる時代です。しかし、膨大な情報から有益な情報を引き出すのは困難であり、多面的な分析による試行錯誤が必要となります。たとえば、日付や時間帯により絞り込んでみたり、地域により絞り込んでみたり、性別や年齢により絞り込んでみたりすることでしょう。そして、そのようなときに便利な存在が集計クエリです。\n\n集計クエリとは、指定したカラムの値によってレコードをグループ化し、各グループに含まれるレコードの数を求めるクエリです。たとえば、地域の ID を格納しているカラムを指定すれば、地域毎のレコード数が求まります。日付のカラムを指定したときの出力をグラフ化すれば、レコード数の時間変化を
 視覚化することができます。さらに、地域による絞り込みと日付に対する集計クエリを組み合わせれば、特定の地域におけるレコード数の時間変化を視覚化ことも可能です。このように、尺度を自由に選択して絞り込み・集計できることは、膨大な情報を扱う上でとても重要になります。\n\ngroonga が集計クエリを高速に処理できる理由は、データベースの論理構造にカラムストアを採用しているからです。集計クエリが参照するのは指定されたカラムのみであるため、カラム単位でデータを格納する列指向のデータベースでは、必要なカラムのみを無駄なく読み出せることが利点となります。一方、レコード単位でデータを格納する行指向のデータベースでは、隣接するカラムをまとめて読み出してしまうことが欠点となります。"],
+["転置索引とトークナイザ", "転置索引は大規模な全文検索に用いられる伝統的なデータ構造です。転置索引を用いた全文検索エンジンでは、文書を追加するときに索引語を記録しておき、検索するときはクエリを索引語に分割して出現文書を求めます。そのため、文書やクエリから索引語を抜き出す方法が重要になります。\n\nトークナイザは、文字列から索引語を抜き出すモジュールです。日本語を対象とする全文検索においては、形態素を索引語として抜き出す方式と文字 N-gram を抜き出す方式のいずれか、あるいは両方を用いるのが一般的です。形態素方式は検索時間や索引サイズの面で優れているほか、検索結果に不要な文書が含まれにくいという利点を持っています。一方、N-gram 方式には検索漏れが発生しにくいという利点ã
 Œã‚り、状況によって適した方式を選択することが望ましいとされています。\n\ngroonga は形態素方式と N-gram 方式の両方に対応しています。初期状態で利用できるトークナイザは空白を区切り文字として用いる方式と N-gram 方式のみですが、形態素解析器 MeCab を組み込んだときは MeCab による分かち書きの結果を用いる形態素方式が有効になります。トークナイザはプラグインとして追加できるため、特徴的なキーワードのみを索引語として採用するなど、独自のトークナイザを開発することが可能です。"],
+["共有可能なストレージと参照ロックフリー", "CPU のマルチコア化が進んでいるため、同時に複数のクエリを実行したり、一つのクエリを複数のスレッドで実行したりすることの重要性はますます高まっています。\n\ngroonga のストレージは、複数のスレッド・プロセスで共有することができます。また、参照ロックフリーなデータ構造を採用しているため、更新クエリを実行している状況でも参照クエリを実行することができます。参照クエリを実行できる状態を維持しながら更新クエリを実行できるので、リアルタイムなシステムに適しています。さらには、MySQL を介して更新クエリを実行している最中に groonga の HTTP サーバを介して参照クエリを実行するなど、多彩な運用が可能となっています。"],
+["位置情報（緯度・経度）検索", "GPS に代表される測位システムを搭載した高機能な携帯端末の普及などによって、位置情報を扱うサービスはますます便利になっています。たとえば、近くにあるレストランを探しているときは、現在地からの距離を基準として検索をおこない、検索結果を地図上に表示してくれるようなサービスが便利です。そのため、位置情報検索を高速に実現できることが重要になっています。\n\ngroonga では転置索引を応用して高速な位置情報検索を実現しています。矩形・円による範囲検索に対応しているほか、基準点の近くを優先的に探索させることができます。また、距離計算をサポートしているので、位置情報検索の結果を基準点からの距離によって整列することも可能です。"],
+["groonga ライブラリ", "Groonga の基本機能は C ライブラリとして提供されているので、任意のアプリケーションに組み込んで利用することができます。C/C++ 以外については、Ruby から groonga を利用するライブラリなどが関連プロジェクトにおいて提供されています。詳しくは 関連プロジェクト を参照してください。"],
+["groonga サーバ", "groonga にはサーバ機能があるため、レンタルサーバなどの新しいライブラリをインストールできない環境においても利用できます。対応しているのは HTTP, memcached binary プロトコル、およびに groonga の独自プロトコルである gqtp です。サーバとして利用するときはクエリのキャッシュ機能が有効になるため、同じクエリを受け取ったときは応答時間が短くなるという特徴があります。"],
+["groonga ストレージエンジン", "groonga は独自のカラムストアを持つ列指向のデータベースとしての側面を持っていますが、既存の RDBMS のストレージエンジンとして利用することもできます。たとえば、groonga をベースとする MySQL のストレージエンジンとして mroonga が開発されています。mroonga は MySQL のプラグインとして動的にロードすることが可能であり、groonga のカラムストアをストレージとして利用したり、全文検索エンジンとして groonga を MyISAM や InnoDB と連携させたりすることができます。groonga 単体での利用、およびに MyISAM, InnoDB との連携には一長一短があるので、用途に応じて適切な組み合わせを選ぶことが大切です。詳しくは 関連プロジェクト を参照してください。"]
+]
+[[0,0.0,0.0],9]
+select Documents --filter 'content *S "MySQLで全文検索"' --output_columns '_key, _score, content'
+[
+  [
+    0,
+    0.0,
+    0.0
+  ],
+  [
+    [
+      [
+        3
+      ],
+      [
+        [
+          "_key",
+          "ShortText"
+        ],
+        [
+          "_score",
+          "Int32"
+        ],
+        [
+          "content",
+          "Text"
+        ]
+      ],
+      [
+        "groonga の概要",
+        419432,
+        "groonga は転置索引を用いた高速・高精度な全文検索エンジンであり、登録された文書をすぐに検索結果に反映できます。また、参照をブロックせずに更新できることから、即時更新の必要なアプリケーションにおいても高い性能を発揮します。\n\n全文検索エンジンとして開発された groonga ですが、独自のカラムストアを持つ列指向のデータベースとしての側面も持っています。そのため、MySQL や PostgreSQL など、既存の代表的なデータベースが苦手とする集計クエリを高速に処理できるという特徴があり、組み合わせによって弱点を補うような使い方もできます。\n\ngroonga の基本機能は C ライブラリとして提供されていますが、MySQL や PostgreSQL と連携させたり、Ruby から呼び出したりすることもできます。そのため、任意のアプリ
 ケーションに組み込むことが可能であり、多様な使い方が考えられます。 興味のある方は 利用例 をご覧ください。"
+      ],
+      [
+        "共有可能なストレージと参照ロックフリー",
+        209716,
+        "CPU のマルチコア化が進んでいるため、同時に複数のクエリを実行したり、一つのクエリを複数のスレッドで実行したりすることの重要性はますます高まっています。\n\ngroonga のストレージは、複数のスレッド・プロセスで共有することができます。また、参照ロックフリーなデータ構造を採用しているため、更新クエリを実行している状況でも参照クエリを実行することができます。参照クエリを実行できる状態を維持しながら更新クエリを実行できるので、リアルタイムなシステムに適しています。さらには、MySQL を介して更新クエリを実行している最中に groonga の HTTP サーバを介して参照クエリを実行するなど、多彩な運用が可能となっています。"
+      ],
+      [
+        "groonga ストレージエンジン",
+        419432,
+        "groonga は独自のカラムストアを持つ列指向のデータベースとしての側面を持っていますが、既存の RDBMS のストレージエンジンとして利用することもできます。たとえば、groonga をベースとする MySQL のストレージエンジンとして mroonga が開発されています。mroonga は MySQL のプラグインとして動的にロードすることが可能であり、groonga のカラムストアをストレージとして利用したり、全文検索エンジンとして groonga を MyISAM や InnoDB と連携させたりすることができます。groonga 単体での利用、およびに MyISAM, InnoDB との連携には一長一短があるので、用途に応じて適切な組み合わせを選ぶことが大切です。詳しくは 関連プロジェクト を参照してください。"
+      ]
+    ]
+  ]
+]

  Added: test/function/suite/select/filter/similar.test (+21 -0) 100644
===================================================================
--- /dev/null
+++ test/function/suite/select/filter/similar.test    2012-04-23 21:43:18 +0900 (7451353)
@@ -0,0 +1,21 @@
+table_create Documents TABLE_HASH_KEY ShortText
+column_create Documents content COLUMN_SCALAR Text
+
+table_create Terms TABLE_PAT_KEY|KEY_NORMALIZE ShortText --default_tokenizer TokenBigram
+column_create Terms document_index COLUMN_INDEX|WITH_POSITION Documents content
+
+load --table Documents
+[
+["_key", "content"],
+["groonga の概要", "groonga は転置索引を用いた高速・高精度な全文検索エンジンであり、登録された文書をすぐに検索結果に反映できます。また、参照をブロックせずに更新できることから、即時更新の必要なアプリケーションにおいても高い性能を発揮します。\n\n全文検索エンジンとして開発された groonga ですが、独自のカラムストアを持つ列指向のデータベースとしての側面も持っています。そのため、MySQL ã‚„ PostgreSQL など、既存の代表的なデータベースが苦手とする集計クエリを高速に処理できるという特徴があり、組み合わせによって弱点を補うような使い方もできます。\n\ngroonga の基本機能は C ライブラリとして提供されていますが、MySQL ã‚„ PostgreSQL と連携させたり、Ruby から呼び出したりすることもできます。そのため、任æ
 „ã®ã‚¢ãƒ—リケーションに組み込むことが可能であり、多様な使い方が考えられます。 興味のある方は 利用例 をご覧ください。"],
+["全文検索と即時更新", "一般的なデータベースにおいては、追加・削除などの操作がすぐに反映されます。一方、全文検索においては、転置索引が逐次更新の難しいデータ構造であることから、文書の追加・削除に対応しないエンジンが少なくありません。\n\nこれに対し、転置索引を用いた全文検索エンジンでありながら、groonga は文書を短時間で追加・削除することができます。その上、更新しながらでも検索できるという優れた特徴を持っているため、全文検索エンジンとしてはとても柔軟性があります。また、複数の転置索引を統合するような重い処理を必要としないので、安定して高い性能を発揮することが期待できます。"],
+["カラムストアと集計クエリ", "現代は、インターネットを情報源とすれば、いくらでも情報を収集できる時代です。しかし、膨大な情報から有益な情報を引き出すのは困難であり、多面的な分析による試行錯誤が必要となります。たとえば、日付や時間帯により絞り込んでみたり、地域により絞り込んでみたり、性別や年齢により絞り込んでみたりすることでしょう。そして、そのようなときに便利な存在が集計クエリです。\n\n集計クエリとは、指定したカラムの値によってレコードをグループ化し、各グループに含まれるレコードの数を求めるクエリです。たとえば、地域の ID を格納しているカラムを指定すれば、地域毎のレコード数が求まります。日付のカラムを指定したときの出力をグラフ化すれば、レコード数の時間変化を
 視覚化することができます。さらに、地域による絞り込みと日付に対する集計クエリを組み合わせれば、特定の地域におけるレコード数の時間変化を視覚化ことも可能です。このように、尺度を自由に選択して絞り込み・集計できることは、膨大な情報を扱う上でとても重要になります。\n\ngroonga が集計クエリを高速に処理できる理由は、データベースの論理構造にカラムストアを採用しているからです。集計クエリが参照するのは指定されたカラムのみであるため、カラム単位でデータを格納する列指向のデータベースでは、必要なカラムのみを無駄なく読み出せることが利点となります。一方、レコード単位でデータを格納する行指向のデータベースでは、隣接するカラムをまとめて読み出してしまうことが欠点となります。"],
+["転置索引とトークナイザ", "転置索引は大規模な全文検索に用いられる伝統的なデータ構造です。転置索引を用いた全文検索エンジンでは、文書を追加するときに索引語を記録しておき、検索するときはクエリを索引語に分割して出現文書を求めます。そのため、文書やクエリから索引語を抜き出す方法が重要になります。\n\nトークナイザは、文字列から索引語を抜き出すモジュールです。日本語を対象とする全文検索においては、形態素を索引語として抜き出す方式と文字 N-gram を抜き出す方式のいずれか、あるいは両方を用いるのが一般的です。形態素方式は検索時間や索引サイズの面で優れているほか、検索結果に不要な文書が含まれにくいという利点を持っています。一方、N-gram 方式には検索漏れが発生しにくいという利点ã
 Œã‚り、状況によって適した方式を選択することが望ましいとされています。\n\ngroonga は形態素方式と N-gram 方式の両方に対応しています。初期状態で利用できるトークナイザは空白を区切り文字として用いる方式と N-gram 方式のみですが、形態素解析器 MeCab を組み込んだときは MeCab による分かち書きの結果を用いる形態素方式が有効になります。トークナイザはプラグインとして追加できるため、特徴的なキーワードのみを索引語として採用するなど、独自のトークナイザを開発することが可能です。"],
+["共有可能なストレージと参照ロックフリー", "CPU のマルチコア化が進んでいるため、同時に複数のクエリを実行したり、一つのクエリを複数のスレッドで実行したりすることの重要性はますます高まっています。\n\ngroonga のストレージは、複数のスレッド・プロセスで共有することができます。また、参照ロックフリーなデータ構造を採用しているため、更新クエリを実行している状況でも参照クエリを実行することができます。参照クエリを実行できる状態を維持しながら更新クエリを実行できるので、リアルタイムなシステムに適しています。さらには、MySQL を介して更新クエリを実行している最中に groonga の HTTP サーバを介して参照クエリを実行するなど、多彩な運用が可能となっています。"],
+["位置情報（緯度・経度）検索", "GPS に代表される測位システムを搭載した高機能な携帯端末の普及などによって、位置情報を扱うサービスはますます便利になっています。たとえば、近くにあるレストランを探しているときは、現在地からの距離を基準として検索をおこない、検索結果を地図上に表示してくれるようなサービスが便利です。そのため、位置情報検索を高速に実現できることが重要になっています。\n\ngroonga では転置索引を応用して高速な位置情報検索を実現しています。矩形・円による範囲検索に対応しているほか、基準点の近くを優先的に探索させることができます。また、距離計算をサポートしているので、位置情報検索の結果を基準点からの距離によって整列することも可能です。"],
+["groonga ライブラリ", "Groonga の基本機能は C ライブラリとして提供されているので、任意のアプリケーションに組み込んで利用することができます。C/C++ 以外については、Ruby から groonga を利用するライブラリなどが関連プロジェクトにおいて提供されています。詳しくは 関連プロジェクト を参照してください。"],
+["groonga サーバ", "groonga にはサーバ機能があるため、レンタルサーバなどの新しいライブラリをインストールできない環境においても利用できます。対応しているのは HTTP, memcached binary プロトコル、およびに groonga の独自プロトコルである gqtp です。サーバとして利用するときはクエリのキャッシュ機能が有効になるため、同じクエリを受け取ったときは応答時間が短くなるという特徴があります。"],
+["groonga ストレージエンジン", "groonga は独自のカラムストアを持つ列指向のデータベースとしての側面を持っていますが、既存の RDBMS のストレージエンジンとして利用することもできます。たとえば、groonga をベースとする MySQL のストレージエンジンとして mroonga が開発されています。mroonga は MySQL のプラグインとして動的にロードすることが可能であり、groonga のカラムストアをストレージとして利用したり、全文検索エンジンとして groonga を MyISAM や InnoDB と連携させたりすることができます。groonga 単体での利用、およびに MyISAM, InnoDB との連携には一長一短があるので、用途に応じて適切な組み合わせを選ぶことが大切です。詳しくは 関連プロジェクト を参照してください。"]
+]
+
+select Documents --filter 'content *S "MySQLで全文検索"' --output_columns '_key, _score, content'

• 前の記事 [Groonga-commit] groonga/groonga [master] test: add missing parameter for geo_in_circle(), geo_distance().
• 次の記事 [Groonga-commit] groonga/groonga [master] apt: enable security repository
• 記事の並び順: [ 日付 ] [ スレッド ] [ 件名 ] [ 著者 ]