スキップしてメイン コンテンツに移動

Search::Fulltext で N-gram 検索できるように Search::Fulltext::Tokenizer::Ngram を書いた

ラベル:

2014-01-01: CPAN にアップロードしたので追記。

要旨

Search::Fulltext という大変シンプルな全文検索モジュールがリリースされていたので、N-gram トークナイザを提供する Search::Fulltext::Tokenizer::Ngram を書きました。

これを使うと日本語として怪しい表現でもとりあえずヒットするような全文検索ができます。

動機

大変シンプルなモジュールだったのでシンプルに使ってみようと思ったら現在のところ日本語のトークナイザは Search::Fulltext::Tokenizer::MeCab のみでした。Text::MeCab のインストールが億劫なのと、ワンダー日本語が跋扈している Web 文書なんかの検索だと N-gram の方が都合が良いこともあるので作ってみました。

念の為: N-gram って何

テキストを N 文字毎に区切ったもの。e.g., "色彩を持たない多崎つくると、彼の巡礼の年" から 2-gram を作ると "色彩", "彩を", "を持", ... "の年" といった具合になる。 要は文書中に出現する N 文字の組合せを網羅するので、N-gram を使ってインデックスを作ると N 文字以上のクエリにヒットする文書は一切取り零さなくなる。 短所は形態素の区切りを知らないので "京都" というクエリで "東京都" という語を含んだ文書までヒットする、N 文字以下のクエリは一切ヒットしない、N が小さいとインデックスが大きくなるなど。

使い方

インストール

cpanm などを使ってインストールできます: 
cpanm Search::Fulltext::Tokenizer::Ngram
Dist::Zilla (dzil) が必要です。面倒なら CPAN に上がるのを待つか `lib/` 以下をコピーで動きます。 
git clone git@github.com:sekia/Search-Fulltext-Tokenizer-Ngram.git    
cd Search-Fulltext-Tokenizer-Ngram
dzil test
dzil install

使用例

1-gram, 2-gram, 3-gram が使えます。

use strict;
use warnings;
use utf8;
use Search::Fulltext;
use Search::Fulltext::Tokenizer::Unigram;  # 1-gram tokenizer
use Search::Fulltext::Tokenizer::Bigram;   # 2-gram tokenizer
use Search::Fulltext::Tokenizer::Trigram;  # 3-gram tokenizer

my $search_engine = Search::Fulltext->new(
  docs => [
    'ハンプティ・ダンプティ 塀の上',
    'ハンプティ・ダンプティ 落っこちた',
    '王様の馬みんなと 王様の家来みんなでも',
    'ハンプティを元に 戻せなかった',
  ],
  # 3-gram を使う
  tokenizer => q/perl 'Search::Fulltext::Tokenizer::Trigram::create_token_iterator_generator'/,
);

# search はヒットした文書のインデックスを返す。ここでは [0, 1, 3]。
my $hit_documents1 = $search_engine->search('ハンプティ');

# ヒットしない。
# インデックスが 3-gram で構築されているため2文字の "王様" は載っていない。
my $hit_documents2 = $search_engine->search('王様')

4文字以上の N-gram が必要なら Search::Fulltext::Tokenizer::Ngram を継承して作ることができます:

package MyTokenizer::42gram {
  use parent qw/Search::Fulltext::Tokenizer::Ngram/;

  sub create_token_iterator_generator {
    sub { __PACKAGE__->new(42)->create_token_iterator(@_) };
  }
}
my $search_engine = Search::Fulltext->new(
   docs => [ ... ],
   tokenizer => q/perl 'MyTokenizer::42gram::create_token_iterator_generator'/,
);

TODO

  • Documentation.
  • Upload to CPAN.

まとめ

大変シンプルなモジュールを大変シンプルに使うことができるようになりました。Enjoy!

参考文献

コメント

  1. laysakura2013年11月23日 17:07:00 JST

    Search::Fulltextの作者です．
    Search::Fulltext::Tokenizer::* をどなたかが作ってくださるのを期待していたので，大変嬉しく思っております．

    よろしければ，Search::Fulltext::Tokenizer::NgramをCPANにアップロードなさいませんか?
    大まかな手順としてはこちらのサイトが参考になります．
    http://blog.livedoor.jp/sasata299/archives/51284970.html

    Search::Fulltext::Tokenizer::* に期待されるREADME(Pod)の書き方などはこちらをご覧いただければと思います．
    https://github.com/laysakura/Search-Fulltext-Tokenizer-MeCab

    楽な作業とは言えませんが，是非ご検討くださいませ．

    返信削除

コメントを投稿

このブログの人気の投稿

Perl 5 to 6 - コンテキスト

2011-02-27: コメント欄で既に改訂された仕様の指摘がありました ので一部補足しました。 id:uasi に感謝します。 これはMoritz Lenz氏のWebサイト Perlgeek.de で公開されているブログ記事 "Perl 5 to 6" Lesson 06 - Contexts の日本語訳です。 原文は Creative Commons Attribution 3.0 Germany に基づいて公開されています。 本エントリには Creative Commons Attribution 3.0 Unported を適用します。 Original text: Copyright© 2008-2010 Moritz Lenz Japanese translation: Copyright© 2011 SATOH Koichi NAME "Perl 5 to 6" Lesson 06 - コンテキスト SYNOPSIS my @a = <a b c> my $x = @a; say $x[2]; # c say (~2).WHAT # Str() say +@a; # 3 if @a < 10 { say "short array"; } DESCRIPTION 次のように書いたとき、 $x = @a Perl5では $x は @a より少ない情報—— @a の要素数だけ——しか持ちません。 すべての情報を保存しておくためには明示的にリファレンスを取る必要があります: $x = \@a Perl6ではこれらは反対になります: デフォルトでは何も失うことなく、スカラ変数は配列を単に格納します。 これは一般要素コンテキスト(Perl5で scalar と呼ばれていたもの)及びより特化された数値、整数、文字列コンテキストの導入によって可能となりました。無効コンテキストとリストコンテキストは変更されていません。 特別な構文でコンテキストを強制できます。 構文 コンテキスト ~stuff 文字列 ?stuff 真理値 +stuff ...
2 件のコメント
続きを読む

Project Euler - Problem 27

問題 しばらく止まってましたが今日から再開。 原文 Considering quadratics of the form: n 2 + an + b, where |a| < 1000 and |b| < 1000 Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0. 日本語訳 |a| < 1000, |b| < 1000 として以下の二次式を考える (ここで|a|は絶対値): n 2 + an + b n=0から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数a, bの積を答えよ. 解答 最大探索範囲は-999 <= a <= 999、-999 <= b <= 999なので、およそ4,000,000通りの係数の組合せを試すことになります。組合せ毎に数列を生成して、それが素数か判定するわけですからたまりません。簡単な検討を加えて範囲を絞りましょう。 与えられた二次式をf(n)とおくと、f(0) = b、f(1) = a + b + 1です。 f(n)が長さ2以上の素数列を生成するならこれらは素数ですから、次のことがいえます： bは素数である a + b + 1は素数である b = 2のとき、aは偶数である それ以外のとき、aは奇数である 素数判定関数 is_prime には同じ引数が与えられることがよくあるのでメモ化しています。 #!/usr/bin/perl use strict; use warnings; use feature qw/say/; sub prime_seq_len($$) { my ($coeff_a, $coeff_b) = @_; my $len = 0; my $n = 0; $len++, $n++ while is_prime($n * ($n + $coeff_a) ...
2 件のコメント
続きを読む

Perl 5 to 6 - ツイジル

これはMoritz Lenz氏のWebサイト Perlgeek.de で公開されているブログ記事 "Perl 5 to 6" Lesson 15 - Twigils の日本語訳です。 原文は Creative Commons Attribution 3.0 Germany に基づいて公開されています。 本エントリには Creative Commons Attribution 3.0 Unported を適用します。 Original text: Copyright© 2008-2010 Moritz Lenz Japanese translation: Copyright© 2011 SATOH Koichi NAME "Perl 5 to 6" Lesson 15 - ツイジル SYNOPSIS class Foo { has $.bar; has $!baz; } my @stuff = sort { $^b[1] <=> $^a[1]}, [1, 2], [0, 3], [4, 8]; my $block = { say "This is the named 'foo' parameter: $:foo" }; $block(:foo<bar>); say "This is file $?FILE on line $?LINE" say "A CGI script" if %*ENV.exists('DOCUMENT_ROOT'); DESCRIPTION いくつかの変数にはツイジルという第2のシジルがあります。これは基本的にはその変数が「普通」ではないということです。違いはいくつかあり、例えばスコープの違いなどです。 オブジェクトのパブリックな属性とプライベートな属性がそれぞれ . と ! というツイジルを持つことは既に紹介しました; それらは通常の変数ではなく self に結びつけられています。 ツイジル ^ はPerl5で例外的に扱われていたケースを一般化します。次のように書けます # 注意: Perl5のコードです sort ...
コメントを投稿
続きを読む

Project Euler - Problem 18

問題 原文 Find the maximum total from top to bottom of the triangle 日本語訳 三角形を頂点から下まで移動するとき、その最大の合計値を求めよ。 解答 動的計画法 を使ってボトムアップで簡単に解くことができる問題です。 簡単のため、小さい三角形で考えることにします： 0: j 1: h i 2: e f g 3: a b c d 2行目の各点を頂点として、2行の小さい三角形が作れることが分かります。 上の例で言えば、(e, a, b)と(f, b, c)、(g, c, d)の3つです。 (e, a, b)の頂点eから末端（a、b、c、dのいずれか）に移動したとき、その数値の合計は最大でe + max(a, b)となります（maxは最大値を選ぶ関数）。同様に他の2つもf + max(b, c)、g + max(c, d)と表せます。 これらをE、F、Gとおくことにして、例を次のように書き換えます： 0: j 1: h i 2: E F G (h, E, F)からなる三角形の最大値はH = h + max(E, F)、(i, F, G)からなる三角形のそれはI = i + max(F, G)です。 Eは「頂点eから末端に至る経路の最大値」で、FやGも同様ですから、HとIは「頂点h（やi）から末端に至る経路の最大値」となります。 これを先ほどと同様に置き換えて： 0: j 1: H I 頂点jから末端に至る経路の最大値はJ = j + max(H, I)となり、これが解です。 #!/usr/bin/perl use strict; use warnings; use feature qw/say/; use List::Util qw/max/; my @rows = map { [ split /\s+/ ] } <DATA>; until (@rows == 1) { my $curr_row = $rows[-2]; my $bigger_branch; for (my $i = 0; $i < @$curr_row; $i++) { $bigger_branch = ma...
3 件のコメント
続きを読む

Perl 7 より先に Perl 5.34 が出るぞという話

Perl 5 の次期バージョンとして一部後方互換でない変更 (主に間接オブジェクト記法の削除とベストプラクティスのデフォルトでの有効化) を含んだメジャーバージョンアップである Perl 7 がアナウンスされたのは昨年の 6 月 のことだったが、その前に Perl 5 の次期周期リリースである Perl 5.34 が 5 月にリリース予定 である。 現在開発版は Perl 5.33.8 がリリースされておりユーザから見える変更は凍結、4 月下旬の 5.33.9 で全コードが凍結され 5 月下旬に 5.34.0 としてリリース予定とのこと。 そういうわけで事前に新機能の予習をしておく。 8進数数値リテラルの新構文 見た瞬間「マジかよ」と口に出た。これまで Perl はプレフィクス 0 がついた数値リテラルを8進数と見做してきたが、プレフィクスに 0o (zero, small o) も使えるようになる。 もちろんこれは2進数リテラルの 0b や 16進数リテラルの 0x との一貫性のためである。リテラルと同じ解釈で文字列を数値に変換する組み込み関数 oct も` 新構文を解するようになる。 昨今無数の言語に取り入れられているリテラル記法ではあるが、この記法の問題は o (small o) と 0 (zero) の区別が難しいことで、より悪いことに大文字も合法である： 0O755 Try / Catch 構文 Perl 5 のリリース以来 30 年ほど待たれた実験的「新機能」である。 Perl 5 における例外処理が特別な構文でなかったのは予約語を増やさない配慮だったはずだが、TryCatch とか Try::Tiny のようなモジュールが氾濫して当初の意図が無意味になったというのもあるかも知れない。 use feature qw/ try / ; no warnings qw/ experimental::try / ; try { failable_operation(); } catch ( $e ) { recover_from_error( $e ); } Raku (former Perl 6) だと CATCH (大文字なことに注意) ブロックが自分の宣言されたスコープ内で投げられた例外を捕らえる...
1 件のコメント
続きを読む