Class: Groonga::PatriciaTrie

Inherits:
Table
  • Object
show all
Includes:
GrnTableKeySupport
Defined in:
ext/rb-grn-patricia-trie.c,
lib/groonga/patricia-trie.rb,
ext/rb-grn-patricia-trie.c

Overview

各レコードをパトリシアトライで管理するテーブル。ハッシュテーブルに比べて完全一致検索の速度がやや遅いが、前方一致検索・共通接頭辞探索などの検索ができる。またカーソルを用いてキーの昇降順にレコードを取り出すことができる。

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from Table

#[], #add_column, #clear_lock, #column, #column_value, #columns, #define_column, #define_index_column, #delete, #difference!, #each, #group, #initialize, #inspect, #intersection!, #lock, #locked?, #merge!, open, #open_cursor, #records, #select, #set_column_value, #set_value, #size, #sort, #truncate, #union!, #unlock, #value

Constructor Details

This class inherits a constructor from Groonga::Table

Class Method Details

.Groonga::PatriciaTrie.create(options = {}) ⇒ Groonga::PatriciaTrie .Groonga::PatriciaTrie.create(options = ) { ... } ⇒ Object

各レコードをパトリシアトライで管理するテーブルを生成する。ブロックを指定すると、そのブロックに生成したテーブルが渡され、ブロックを抜けると自動的にテーブルが破棄される。

optionsに指定可能な値は以下の通り。

:context

テーブルが利用するGroonga::Context。省略するとGroonga::Context.defaultを用いる。

:name

テーブルの名前。名前をつけると、Groonga::Context#[]に名前を指定してテーブルを取得することができる。省略すると無名テーブルになり、テーブルIDでのみ取得できる。

:path

テーブルを保存するパス。パスを指定すると永続テーブルとなり、プロセス終了後もレコードは保持される。次回起動時にGroonga::PatriciaTrie.openで保存されたレコードを利用することができる。省略すると一時テーブルになり、プロセスが終了するとレコードは破棄される。

:persistent

trueを指定すると永続テーブルとなる。pathを省略した場合は自動的にパスが付加される。:contextで指定したGroonga::Contextに結びついているデータベースが一時データベースの場合は例外が発生する。

:key_normalize

trueを指定するとキーを正規化する。

:key_with_sis

trueを指定するとキーの文字列の全suffixが自動的に登録される。

:key_type

キーの種類を示すオブジェクトを指定する。キーの種類には型名（“Int32”や“ShortText”など）またはGroonga::Typeまたはテーブル（Groonga::Array、Groonga::Hash、Groonga::PatriciaTrieのどれか）を指定する。

Groonga::Typeを指定した場合は、その型が示す範囲の値をキーとして使用する。ただし、キーの最大サイズは4096バイトであるため、Groonga::Type::TEXTやGroonga::Type::LONG_TEXT は使用できない。

テーブルを指定した場合はレコードIDをキーとして使用する。指定したテーブルのGroonga::Recordをキーとして使用することもでき、その場合は自動的にGroonga::RecordからレコードIDを取得する。

省略した場合は文字列をキーとして使用する。この場合、4096バイトまで使用可能である。

:value_type

値の型を指定する。省略すると値のための領域を確保しない。値を保存したい場合は必ず指定すること。

参考: Groonga::Type.new

:default_tokenizer

Groonga::IndexColumnで使用するトークナイザを指定する。デフォルトでは何も設定されていないので、テーブルにGroonga::IndexColumnを定義する場合は"TokenBigram"などを指定する必要がある。

:sub_records

trueを指定すると#groupでグループ化したときに、Groonga::Record#n_sub_recordsでグループに含まれるレコードの件数を取得できる。

使用例:

無名一時テーブルを生成する。

Groonga::PatriciaTrie.create

無名永続テーブルを生成する。

Groonga::PatriciaTrie.create(:path => "/tmp/hash.grn")

名前付き永続テーブルを生成する。ただし、ファイル名は気にしない。

Groonga::PatriciaTrie.create(:name => "Bookmarks",
                             :persistent => true)

それぞれのレコードに512バイトの値を格納できる無名一時テーブルを生成する。

Groonga::PatriciaTrie.create(:value => 512)

キーとして文字列を使用する無名一時テーブルを生成する。

Groonga::PatriciaTrie.create(:key_type => Groonga::Type::SHORT_TEXT)

キーとして文字列を使用する無名一時テーブルを生成する。（キーの種類を表すオブジェクトは文字列で指定。）

Groonga::PatriciaTrie.create(:key_type => "ShortText")

キーとしてBookmarksテーブルのレコードを使用する無名一時テーブルを生成する。

bookmarks = Groonga::PatriciaTrie.create(:name => "Bookmarks")
Groonga::PatriciaTrie.create(:key_type => bookmarks)

キーとしてBookmarksテーブルのレコードを使用する無名一時テーブルを生成する。（テーブルは文字列で指定。）

Groonga::PatriciaTrie.create(:name => "Bookmarks")
Groonga::PatriciaTrie.create(:key_type => "Bookmarks")

全文検索用のトークンをバイグラムで切り出す無名一時テーブルを生成する。

bookmarks = Groonga::PatriciaTrie.create(:name => "Bookmarks")
bookmarks.define_column("comment", "Text")
terms = Groonga::PatriciaTrie.create(:name => "Terms",
                                     :default_tokenizer => "TokenBigram")
terms.define_index_column("content", bookmarks,
                          :source => "Bookmarks.comment")

Overloads:



155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
 
# File 'ext/rb-grn-patricia-trie.c', line 155

static VALUE
rb_grn_patricia_trie_s_create (int argc, VALUE *argv, VALUE klass)
{
    grn_ctx *context;
    grn_obj *key_type = NULL, *value_type = NULL, *table;
    const char *name = NULL, *path = NULL;
    unsigned name_size = 0;
    grn_obj_flags flags = GRN_TABLE_PAT_KEY;
    VALUE rb_table;
    VALUE options, rb_context, rb_name, rb_path, rb_persistent;
    VALUE rb_key_normalize, rb_key_with_sis, rb_key_type;
    VALUE rb_value_type;
    VALUE rb_default_tokenizer, rb_sub_records;

    rb_scan_args(argc, argv, "01", &options);

    rb_grn_scan_options(options,
      "context", &rb_context,
      "name", &rb_name,
                        "path", &rb_path,
      "persistent", &rb_persistent,
      "key_normalize", &rb_key_normalize,
      "key_with_sis", &rb_key_with_sis,
      "key_type", &rb_key_type,
      "value_type", &rb_value_type,
      "default_tokenizer", &rb_default_tokenizer,
      "sub_records", &rb_sub_records,
      NULL);

    context = rb_grn_context_ensure(&rb_context);

    if (!NIL_P(rb_name)) {
        name = StringValuePtr(rb_name);
  name_size = RSTRING_LEN(rb_name);
  flags |= GRN_OBJ_PERSISTENT;
    }

    if (!NIL_P(rb_path)) {
        path = StringValueCStr(rb_path);
  flags |= GRN_OBJ_PERSISTENT;
    }

    if (RVAL2CBOOL(rb_persistent))
  flags |= GRN_OBJ_PERSISTENT;

    if (RVAL2CBOOL(rb_key_normalize))
  flags |= GRN_OBJ_KEY_NORMALIZE;

    if (RVAL2CBOOL(rb_key_with_sis))
  flags |= GRN_OBJ_KEY_WITH_SIS;

    if (NIL_P(rb_key_type)) {
  flags |= GRN_OBJ_KEY_VAR_SIZE;
    } else {
  key_type = RVAL2GRNOBJECT(rb_key_type, &context);
    }

    if (!NIL_P(rb_value_type))
  value_type = RVAL2GRNOBJECT(rb_value_type, &context);

    if (RVAL2CBOOL(rb_sub_records))
  flags |= GRN_OBJ_WITH_SUBREC;

    table = grn_table_create(context, name, name_size, path,
           flags, key_type, value_type);
    if (!table)
  rb_grn_context_check(context, rb_ary_new4(argc, argv));
    rb_table = GRNOBJECT2RVAL(klass, context, table, RB_GRN_TRUE);

    if (!NIL_P(rb_default_tokenizer))
  rb_funcall(rb_table, rb_intern("default_tokenizer="), 1,
       rb_default_tokenizer);

    if (rb_block_given_p())
        return rb_ensure(rb_yield, rb_table, rb_grn_object_close, rb_table);
    else
        return rb_table;
}

Instance Method Details

#prefix_search(prefix) ⇒ Groonga::Hash

キーがprefixに前方一致するレコードのIDがキーに入っているGroonga::Hashを返す。マッチするレコードがない場合は空のGroonga::Hashが返る。

Returns:



443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
 
# File 'ext/rb-grn-patricia-trie.c', line 443

static VALUE
rb_grn_patricia_trie_prefix_search (VALUE self, VALUE rb_prefix)
{
    grn_ctx *context;
    grn_obj *table, *key, *domain, *result;
    grn_id domain_id;
    VALUE rb_result;

    rb_grn_table_key_support_deconstruct(SELF(self), &table, &context,
           &key, &domain_id, &domain,
           NULL, NULL, NULL,
           NULL);

    result = grn_table_create(context, NULL, 0, NULL,
            GRN_OBJ_TABLE_HASH_KEY,
            table, 0);
    rb_grn_context_check(context, self);
    rb_result = GRNOBJECT2RVAL(Qnil, context, result, RB_GRN_TRUE);

    GRN_BULK_REWIND(key);
    RVAL2GRNKEY(rb_prefix, context, key, domain_id, domain, self);
    grn_pat_prefix_search(context, (grn_pat *)table,
        GRN_BULK_HEAD(key), GRN_BULK_VSIZE(key),
        (grn_hash *)result);
    rb_grn_context_check(context, self);

    return rb_result;
}

#scan(string) ⇒ Array #scan(string) {|record, word, start, length| ... } ⇒ Object

stringを走査し、patricia_trie内に格納されているキーにマッチした部分文字列の情報をブロックに渡す。複数のキーがマッチする場合は最長一致するキーを優先する。

record

マッチしたキーのGroonga::Record。

word

マッチした部分文字列。

start

string内でのwordの出現位置。（バイト単位）

length

wordの長さ。（バイト探知）

ブロックを指定しない場合は、マッチした部分文字列の情報をまとめて配列として返す。

words = Groonga::PatriciaTrie.create(:key_type => "ShortText",
                                     :key_normalize => true)
words.add("リンク")
adventure_of_link = words.add('リンクの冒険')
words.add('冒険')
gaxtu = words.add('ｶﾞｯ')
muteki = words.add('ＭＵＴＥＫＩ')

text = 'muTEki リンクの冒険 ミリバール ガッ'
words.scan(text).each do |record, word, start, length|
  p [record.key, word, start, length]
    # -> ["ＭＵＴＥＫＩ", "muTEki", 0, 6]
    # -> ["リンクの冒険", "リンクの冒険", 7, 18]
    # -> ["ｶﾞｯ", "ガッ", 42, 6]
end

words.scan(text)
  # -> [[muteki, "muTEki", 0, 6],
  #     [adventure_of_link, "リンクの冒険", 7, 18],
  #     [gaxtu, "ガッ", 42, 6]]

Overloads:

  • #scan(string) ⇒ Array

    Returns:

  • #scan(string) {|record, word, start, length| ... } ⇒ Object

    Yields:

    • (record, word, start, length) 


373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
 
# File 'ext/rb-grn-patricia-trie.c', line 373

static VALUE
rb_grn_patricia_trie_scan (VALUE self, VALUE rb_string)
{
    grn_ctx *context;
    grn_obj *table;
    VALUE rb_result = Qnil;
    grn_pat_scan_hit hits[1024];
    const char *string;
    long string_length;
    rb_grn_boolean block_given;

    string = StringValuePtr(rb_string);
    string_length = RSTRING_LEN(rb_string);

    rb_grn_table_key_support_deconstruct(SELF(self), &table, &context,
           NULL, NULL, NULL,
           NULL, NULL, NULL,
           NULL);

    block_given = rb_block_given_p();
    if (!block_given)
  rb_result = rb_ary_new();

    while (string_length > 0) {
  const char *rest;
  int i, n_hits;
  long previous_offset = 0;

  n_hits = grn_pat_scan(context, (grn_pat *)table,
            string, string_length,
            hits, sizeof(hits) / sizeof(*hits),
            &rest);
  for (i = 0; i < n_hits; i++) {
      VALUE record, term, matched_info;

      if (hits[i].offset < previous_offset)
    continue;

      record = rb_grn_record_new(self, hits[i].id, Qnil);
      term = rb_grn_context_rb_string_new(context,
            string + hits[i].offset,
            hits[i].length);
      matched_info = rb_ary_new3(4,
               record,
               term,
               UINT2NUM(hits[i].offset),
               UINT2NUM(hits[i].length));
      if (block_given) {
    rb_yield(matched_info);
      } else {
    rb_ary_push(rb_result, matched_info);
      }
      previous_offset = hits[i].offset;
  }
  string_length -= rest - string;
  string = rest;
    }

    return rb_result;
}

#search(key, options = nil) ⇒ Groonga::Hash

keyにマッチするレコードのIDがキーに入っているGroonga::Hashを返す。マッチするレコードがない場合は空のGroonga::Hashが返る。

optionsで:resultを指定することにより、そのテーブルにマッチしたレコードIDがキーのレコードを追加することができる。:resultにテーブルを指定した場合は、そのテーブルが返る。

optionsに指定可能な値は以下の通り。

:result

結果を格納するテーブル。

:operator

マッチしたレコードをどのように扱うか。指定可能な値は以下の通り。省略した場合はGroonga::Operation::OR。

Groonga::Operation::OR

マッチしたレコードを追加。すでにレコードが追加されている場合は何もしない。

Groonga::Operation::AND

マッチしたレコードのスコアを増加。マッチしなかったレコードを削除。

Groonga::Operation::BUT

マッチしたレコードを削除。

Groonga::Operation::ADJUST

マッチしたレコードのスコアを増加。

:type

?????

複数のキーで検索し、結果を1つのテーブルに集める。

result = nil
keys = ["morita", "gunyara-kun", "yu"]
keys.each do |key|
  result = users.search(key, :result => result)
end
result.each do |record|
  user = record.key
  p user.key # -> "morita"または"gunyara-kun"または"yu"
end

Returns:



280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
 
# File 'ext/rb-grn-patricia-trie.c', line 280

static VALUE
rb_grn_patricia_trie_search (int argc, VALUE *argv, VALUE self)
{
    grn_rc rc;
    grn_ctx *context;
    grn_obj *table;
    grn_id domain_id;
    grn_obj *key, *domain, *result;
    grn_operator operator;
    grn_search_optarg search_options;
    rb_grn_boolean search_options_is_set = RB_GRN_FALSE;
    VALUE rb_key, options, rb_result, rb_operator, rb_type;

    rb_grn_table_key_support_deconstruct(SELF(self), &table, &context,
           &key, &domain_id, &domain,
           NULL, NULL, NULL,
           NULL);

    rb_scan_args(argc, argv, "11", &rb_key, &options);

    RVAL2GRNKEY(rb_key, context, key, domain_id, domain, self);

    rb_grn_scan_options(options,
      "result", &rb_result,
      "operator", &rb_operator,
      "type", &rb_type,
      NULL);

    if (NIL_P(rb_result)) {
  result = grn_table_create(context, NULL, 0, NULL,
          GRN_OBJ_TABLE_HASH_KEY | GRN_OBJ_WITH_SUBREC,
          table, 0);
  rb_grn_context_check(context, self);
  rb_result = GRNOBJECT2RVAL(Qnil, context, result, RB_GRN_TRUE);
    } else {
  result = RVAL2GRNOBJECT(rb_result, &context);
    }

    operator = RVAL2GRNOPERATOR(rb_operator);

    rc = grn_obj_search(context, table, key,
      result, operator,
      search_options_is_set ? &search_options : NULL);
    rb_grn_rc_check(rc, self);

    return rb_result;
}

#tag_keys(text) ⇒ Object

call-seq:

patricia_trie.tag_keys(text) {|record, word| ...} -> String

textを走査し、レコードのキーとマッチする部分文字列ごとにそのレコードがrecordとして、その部分文字列がwordとして、ブロックが呼び出される。ブロックから返された文字列が元の部分文字列と置換される。全てのヒットに対してのその置換処理が行われた文字列が返される。



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/groonga/patricia-trie.rb', line 28

def tag_keys(text)
  position = 0
  result = ''
  if text.respond_to?(:encoding)
    encoding = text.encoding
    bytes = text.dup.force_encoding("ascii-8bit")
  else
    encoding = nil
    bytes = text
  end
  scan(text) do |record, word, start, length|
    previous_text = bytes[position...start]
    previous_text.force_encoding(encoding) if encoding
    result << previous_text
    result << yield(record, word)
    position = start + length
  end
  last_text = bytes[position..-1]
  unless last_text.empty?
    last_text.force_encoding(encoding) if encoding
    result << last_text
  end
  result
end