| プロフィール | 私書(メール) 受/送/送済 | 評価(一覧/絞) 投票/共:受/送 | ファン登録 OP/ED | DB構築(受) | 書き物 [書く] | 攻略記事 | リンク集 My Play List |
| RSS購読 |
|---|
| RSS |
| 日記表示スタイル |
| リスト/携帯(QRｺｰﾄﾞ) 画像/動画/音声/リンク |
| 表示開始年月 |
| 日記内検索 |
| 分類 |
| 日記の主な内容 ･ｻｲﾄ運営/開発 ･検索ｴﾝｼﾞﾝ情報 ･技術ﾈﾀ(Berkeley DB, Linux, Perl, ｻｲﾄ作成)等 自分その他 My English Blog 皆声ﾌﾞﾛｸﾞﾗﾝｸ ｻｲﾄ管理 全まとめ ｻｰﾊﾞｰ管理 定期処理状況 開発予定 削除提案 作品追加依頼 OP/ED追加依頼 OP/ED not found 作品提案承認欄 格言 fromｽｸﾗｲﾄﾞ この世の理は即ち速さ 20年かければ馬鹿でも 傑作小説を書ける 助けられたら助け返す それが俺のﾙｰﾙ 強くなるには 一番弱い考えをする事だ そしてその考えに反逆する ﾁｬｯﾄ>開発/運用/質問 重要ﾀｽｸﾒﾓ ･StatNumDBのﾘﾘｰｽ ･CGI::Accessupの公開 ･lib1stclassの公開 ･libbdbwrapperの公開 ･ﾕｰｻﾞ数上限問題対応 ･ﾃﾞｨｽｸﾌﾙ問題対応 ･文字ｻｲｽﾞの可変化 ･ﾃﾞｻﾞｲﾝCSS化 ･HTML標準の適用 ･ﾊﾞｯｸｱｯﾌﾟの多段化 ･ﾛｸﾞｲﾝのｾｯｼｮﾝ化 ･暗号化推進 ･ｼﾘｰｽﾞ化対応 ･ｿｰｼｬﾙ対応推進 |
1. 書こうと思ったきっかけ
2. Ngram(N-gram)とは
3. 向きと不向き
4. Ngramの実装
5. NGramの例(bigram=2文字切り出し時)
6. Ngramの有名な欠点
7. 形態素解析とは
8. 形態素解析の欠点
9. 形態素解析結果の実際例
10. まとめ: とはいえ鋏と包丁は使い様
11. コードのサンプル
12. ちなみにこのサイトの検索エンジンは...
13. ということで、検索エンジンを作ってリリースしてみた
ライブドアのブログ検索がNgramを採用したと記事になっていて、単に汎用的な技術な割にはそれだけで大々的に記事になってしまっているので、Ngramについて説明してみようと思う。
表面的なことは理解されていると思うが、あまりそのデメリット等を知っている人は少ないと思うので。
最近は自分は、自分で作った検索エンジンということもあり、Ask.jp(http://ask.jp/blghome.asp)
皆声.jp(http://minakoe.jp/)
しかブログ検索では使わないので、あんまり近頃のライブドア検索のことは知らないのだが。
ライブドアのブログ検索は、Ask, Goo, Google, Yahooといった検索専用の会社がサービス提供を開始するまでは、なかなか面白い存在ではあったと思う。
ちなみに、N-gram採用の背景としては、ライブドアが買収してなくなったAAA Cafeという検索エンジンの技術の系譜で、単にN-gramを採用したのかもしれない。
オープンソースの検索エンジンを含め、多くの検索システムでは、転置インデックス(キーワードとページの組み合わせ = 本の後ろの目次のような構造)が一般的であるが、その転置インデックスのキーの切り出しを、辞書や構文解析に基づくのではなく、単に一定の文字数で切り出した語を入れることで作る方式のことをN-gramという。
Nとは、切り出す文字の単位が複数ありえるということを意味する。
例えば、常に2文字の単語で切り出して、目次のキーを作る。
ちなみに、「常に」というのは、理解の都合上そういっているのであって、2文字で切り出すというルールでも、そうでない部分も必要になる(文の末尾等)。
どんな言語にでも適用できるのでI18N(国際化)向きの技術ではあるが、日本でしか使わないソフトの為なら、あまり使われない。
米国の会社とかが、それを使おうと思うのは、単一のロジックでどんな国の言語にでも使えるという意味で、分ることであるが、日本だけの範囲の場合には、一般的に形態素解析に比べて、欠点が目立つ。
極論すれば、形態素解析は常に正解を目指しているが、Ngramは、常に目隠しして、失敗を志向している為である。
Ngramは、基本的には、国際化を楽して(手抜きして)成功させることのできる技術と言える。韓国語でも中国語でも日本語でも、簡単に適用できる。
但し、手抜きが出来るというメリットは凄く大きいが、結果として、結果にも手抜きとして現れることになる。
また、その為、格納するキーの文字列は、複数の言語を表現できるUTF8を文字コードとするのが一般的である。
N-gramを適用する時には、利用する文字コードの体系において、一文字をどのように表現できるか把握しておく必要がある。
ちなみに、UTF-8の文字コードレンジは、正規表現にすると
| [\x00-\x7F] [\xC0-\xDF][\x80-\xBF] [\xE0-\xEF][\x80-\xBF][\x80-\xBF] [\xF0-\xF7][\x80-\xBF][\x80-\xBF][\x80-\xBF] [\xF8-\xFB][\x80-\xBF][\x80-\xBF][\x80-\xBF][\x80-\xBF] [\xFC-\xFD][\x80-\xBF][\x80-\xBF][\x80-\xBF][\x80-\xBF][\x80-\xBF] |
ユニグラム = unigram (1文字単位)
バイグラム = bigram (2文字単位)
トリグラム = trigram (3文字単位)
のどれかを使うのが現実的。
4文字以上は、3文字以下の検索が来た時に、凄く負荷のかかる検索の仕方をしなくてはならなくなるので、通常使わない。
基本的にN-gramとは、N文字丁度の検索が来た時に、一番効率の良い検索を可能にする。
N文字を下回ると何故遅くなるのかといえば、仕組み的にOR検索をすることになり、読まなければならない量が増えるからである。
ちなみに分かち書きの方法には、形態素解析とN-gramがあるが、それぞれ、単に分け方が異なるだけではなく、N-gramの場合には、N-gram用の特別な検索論理を用意しなければならないということでもある。
オープンソースのウェブ検索エンジンとして有名な(使いものにはならないかもしれないけど)Nutcheはその3つのどれかを選択することができるようになっている。
ちなみに、そのように、他人任せのライブラリやロジックでするのなら択一になるが、自分で作る場合には、場合場合によって、使い分けたり、全く別のロジックで切り出す賢さを発揮すべきだろう。Ngramは言語の特性を無視して適用できる技術ではあるが、逆に言うと言語の特性を反映させないと、納得するレベルのサービスの境地にまでは達することができない。
そして...日本語は、特別な処理をするに値する言語である。
| 入力文: ここaccessup.orgの管理人は、2009年の時点で栗田創がやっております。 ↓ bigramで分割 ↓ 出力トークン: ここ こ accessup org の管 理人 人は は 2009 年の の時 時点 点で で栗 栗田 田創 創が がや って てお りま ます す |
「N-gramを採用したから、部分一致検索ができる」
それは確かにその通り。
しかし、逆に「東京都」という語が含まれた文章を、「京都」でヒットさせてしまうことができる。
「意味」は解釈せず、単に字面だけで切り出した、ある意味初歩的な切り出し方の為、そういうことが起きる。
意味に基づいて語を切り出す形態素解析なら、そんなことは起きない。
形態素解析は、常に改善を志向できるが、N-gramには、常に解決できない問題が存在する。
また、処理の速度としては、検索エンジンに使う場合には、オフライン(インデックス)の速度は速くなるが、オンラインはその分逆に検索が遅くなる(不必要に分割して検索しなければならないので)という問題がある。
また、非正確な分割=>無駄な分割=>大量のHDDの利用、という形で、ディスク使用量で、無駄が多い。小規模な検索では問題にならないが、大規模になると、問題になってくる。
形態素解析は、辞書や文法に基づいて分ける方式。
日本には
・Chasen(http://chasen.naist.jp/hiki/ChaSen/)
・Mecab(http://mecab.sourceforge.net/)
のような、フリーの形態素解析ライブラリが公開されていることもあり、形態素解析がかなり一般的。
ただ、1行に8192bytes以上あると問題にあたり、その制限を解除してもint値の制限(32,768bytes)の問題にあたる等、オープンソースなりの問題がある。
そうした問題の特定や、自分で対応が出来るのなら修正が出来るのもオープンソースの特徴ではありますが。
Google, Yahoo!, MSN等、ビッグカンパニーは、形態素解析を使っている。
精度は、形態素解析エンジンにより、それぞれ結構異なるし癖も違う。
ただ、世界に出ているようなこのクラスの検索エンジンは、どの国にも対応している形態素解析ライブラリを好む & それを提供できる会社は少ない。
ということで、大体特定の会社の製品を利用することになる。
公表されている情報によると、Basis Technorogy(http://www.basistech.jp/customers/)の提供する言語処理ライブラリが多くの検索エンジンの会社には使われている。
日本語だけでなく、中国語、韓国語、アラビア語等多言語対応が出来ている。
色々なソフトの日本語等へのI18N(Internationalization)化、L10N(Localization)化作業なども昔は手がけていた会社だったので、会社は米国のBasis Technologyはボストンなどにありますが、私もWeb検索のI18N&L10Nプロジェクトで3ヶ月程ボストンのオフィスにお世話になりに行っていたことがあります。
ちなみに、昔は、Googleにおいて、形態素解析の問題で、ゲイツ=>ゲイ ツと分けられていて、ゲイでゲイツが引っかかっていたというのは、かなり有名なことであるが、改善により、現在はこの問題は解決しています(他にもこういうパターンはありえますが)。
ちなみに、これはN-Gramだと性質上常に起きます。
ロジックや辞書のチューニングは常に必要だけど、改善すれば、それだけ精度が改善するのが、形態素解析の特徴と言えます。
ただ、改善すると、切り方が過去と変わってしまうので、過去のデータとの整合性をどうとるのかが、一つのボトルネックにはなるでしょう。
形態素解析は、辞書と確率論だけで解決しようとするI18N向けの汎用的なロジックと、各言語の特性を反映したカスタマイズされたロジック部の組み合わせで性能を出すわけですが、それぞれの実装のロジックが違うので、製品により、かなり性能が異なります。
ちなみに、形態素解析エンジンは、オープンソースから、製品版まで、色々とありますが、構文解析等複雑な計算と辞書参照が必要になる為、一般的に、Ngramで処理するより、インデックスする時には負荷がかかります。
但し、より無駄がない(正解を志向している)為、オンライン側に当たる検索システム側では、Ngramより効率的な検索ができるでしょう。
1. 辞書照会と最適な分割の計算が必要な為、極めて単純な原理で分割するN-Gramに比べて処理時間がかかる
2. 辞書の単位が最小に合わせたものになっていないと検索漏れが生じる
例: 辞書に「マカデミアナッツ」として登録されていると、「ナッツ」で「マカデミアナッツ」が検索出来ない。辞書に「マカデミア」と「ナッツ」だけが登録されていれば
「マカデミアナッツ」→形態素解析→「マカデミア」 「ナッツ」
となって検索できるが。
ちなみに、「マカ」「デミア」ではこれでも検索出来ないが、それは語の最小の単位ではないので、形態素解析としては正しい。
N-Gramはここで「マカ」でも「デミ」でも「ミア」でも引っ掛けてしまうので、検索のノイズを生じさせる。
3. 辞書を修正しても、検索入力側は即座に反映できても、オフライン側(インデックス側)は0から生成し直さないと分ち書きの仕方が合致しないので、辞書の修正で問題を解決できるとはいえ、アップデートするタイミングは正確を期すとインデックスのフルアップデートまで出来ない
検索エンジンにおける形態素解析の実際例は
皆声.jpの検索結果
http://search.minakoe.jp/rsss/rsss.asp?stype=new
を見ると各URLに「分ち書き」というリンクがあるので
それをクリックしてどういうものか見てみて下さい。
例: http://www.accessup.org/pj/6_B4C9CDFDBFCDA4B5A4F3/20081016.htmlの形態素解析結果
| スプログ/の/動機/は/大きく/分け/て/2/つ/。 / /目的/1/、/大量/に/ブログ/を/作っ/て/広告/収入/を/得る/こと/ /目的/2/、/自分/が/目的/に/する/サイト/の/リンク/スコア/を/稼ぐ/こと/ /1/について/は/、/迷惑/で/は/あり/ます/が/、/生成/者/自身/に/は/短い/目/で/は/然 /程/マイナス/は/生じ/ませ/ん/。 / /但し/スパムブログ/が/大量/に/発生/する/ブログ/を/使っ/て/いる/周り/の/人達/は/検索/エンジン/から/の/信用/出来/ない/ドメイン/扱い/の/巻き添え/を/喰らう/こと/に/なり/ます/。 / /例えば/、/seesaa/,/ /fc/2/と/Yahoo/など/から/あまり/インデックス/さ/れ/ない/と/言わ/れる/ブログ/ASP/は/その/せい/でしょ/う/。 / /それ/は/、/ある/意味/それ/でも/広告/収入/が/入れ/ば/良い/や/と/し/て/き/た/ブログ /ASP/側/の/怠慢/の/つけ/が/ドメイン/の/価値/の/低下/=/>/検索/エンジン/の/評価 /の/低下/、/という/形/で/ブーメラン/の/よう/に/返っ/て/き/て/いる/と/いう/こと/です/ が/。 / /長い/目/で/見れ/ば/その/ブログ/ASP/の/価値/を/焼畑/の/よう/に/低下/さ/せる/こと/に/なる/でしょ/う/。 / /そういう/意味/で/も/ブログ/ASP/は/本来/きちんと/対応/し/ない/と/いけ/ませ/ん/。 / /2/、/目的/と/する/サイト/へ/の/リンク/を/作っ/て/、/検索/エンジン/に/評価/さ/れる/「/リンク/」/を/稼ぐ/こと/。 / /検索/エンジン/の/仕組み/を/考え/て/、/そういう/こと/を/する/こと/が/目立ち/ます/。 / /ただ/、/これ/は/出来/た/直後/は/見逃さ/れる/こと/は/あり/ます/が/、/調べれ/ば/どの/ リンク/が/異常/に/増え/て/いる/の/か/、/という/形/で/リンク/数/の/上位/の/方/から/クリーニング/を/し/て/くる/こと/も/検索/エンジン/側/も/できる/の/で/、/ある程度/クリーニング/に /人員/を/さい/て/い/た/と/し/たら/、/それ/によって/稼げる/リンク/の/効果/は/一時/的/ に/なる/でしょ/う/。 / /長期/的/に/言え/ば/、/必ず/そうした/不自然/な/リンク/は/見つかり/、/また/リンク/先/に対する/その/リンク/は/ポイント/を/下げ/られ/たり/、/場合/によって/は/検索/対象/から/外さ/れる/ こと/に/なり/ます/。 / /ある/意味/、/個別/に/スパムブログ/を/見つけ/て/いく/より/も/、/リンク/数/が/多い/ところ /から/リンク/を/張っ/て/いる/ところ/を/スパム/と/判断/し/て/いく/方/が/効率/的/な/ので/、/人間/が/スパム/・/もしくは/不正/な/行為/を/し/て/いる/と/判断/できる/よう/な/行動 /は/慎む/べき/です/。 / /そこ/を/誤解/し/て/スパムブログ/を/作る/人/が/未だ/多く/いる/よう/な/ので/、/そんな/こと/を/し/て/も/思っ/た/よう/に/得/に/は/つながら/ない/よ/、/と/諭す/為/に/動作/原理/を/書い/て/おき/ます/。 |
N-gramは日本語にとっては理想の単語切り出し手法ではないが、絶対に形態素解析の違いによる検索抜けを回避したい等の理由があれば、活躍する場はあるでしょう。
例えば、システム的には形態素解析をベースにしていたとしても、ノイズよりも検索漏れを避けたいような場合には、N-Gram的な処理を混ぜるというのもありでしょう(後述する作品DBの検索システムはそのように作っています)。
何事も包丁と鋏は使い様です。
一応N-Gramと形態素解析の簡単な比較です。
| 方式 | 分ち書き(Index)速度 | 必要ディスク量 | 検索速度 | 分ち書き単語数 | 検索漏れ | 検索ノイズ |
| N-Gram | 速い | 大 | 遅い | 多い | 無し | 大 |
| 形態素解析 | 遅い | 中 | 速い | 少ない | 有り | 小 |
サンプルとして、簡単なNgram.pm を作ってみました。
どうやって実装するのかの理解に読んで理解して頂ければ。
UnigramとBigramに対応しています。
| #!/usr/bin/perl -w =pod [Usage] input file's name must be "utf8.txt" output file will become unigram.txt or bigram.txt. Default output file is unigram.txt if you type perl Ngram.pm --bigram bigram will be used. =cut package Ngram; use strict; use CGI::Accessup; use Carp; use Jcode; use FileHandle; my $pro=new Ngram; $pro->run(); sub new(){ my $self={}; return bless $self; } sub run(){ my $self=shift; $self->init_vars(); $self->ngram_text(); } sub init_vars(){ my $self=shift; $self->{'c'}=new CGI::Accessup; $self->{'out'}='unigram.txt'; $self->{'in'}='utf8.txt'; $self->{'mode'}=$ARGV[0] || ''; if($self->{'mode'} eq '--bigram'){ $self->{'out'}='bigram.txt'; } $self->{'utf8chars'}=join('|', '[\x00-\x7F]', '[\xC0-\xDF][\x80-\xBF]', '[\xE0-\xEF][\x80-\xBF][\x80-\xBF]', '[\xF0-\xF7][\x80-\xBF][\x80-\xBF][\x80-\xBF]', '[\xF8-\xFB][\x80-\xBF][\x80-\xBF][\x80-\xBF][\x80-\xBF]', '[\xFC-\xFD][\x80-\xBF][\x80-\xBF][\x80-\xBF][\x80-\xBF][\x80-\xBF]'); } sub ngram_text(){ my $self=shift; # norm_str(INPUT, CHAR_CODE) = Normalize: 全角英数字→半角英数字など my $input_content=$self->{'c'}->norm_str($self->{'c'}->readf($self->{'in'}), 'utf8') || Carp::croak("Failed to read input file."); $euc=$self->{'c'}->norm_str($euc); my $cleaned_content=''; my %index=(); my $entry=0; my $index=0; my $rem=''; my $out=''; my $pre=''; # 文字切り出し $tmp=~ s{$self->{'utf8chars'}}{ my $char=lc $1; if($char=~ m!。|、|【|】|「|」|・|…|―! || $char=~ m!^(?:\W|\s)$! ){ if($rem ne ''){ $out.=$rem."\n"; $entry++; unless(exists($index{$rem})){ $index++; $index{$rem}=''; } $rem=''; $pre=''; } if($pre ne ''){ $out.=$pre."\n"; $entry++; unless(exists($index{$pre})){ $index++; $index{$pre}=''; } $pre=''; } } else{ if($char=~ m![a-z\d]!){ $rem.=$char; } else{ if($rem ne ''){ $out.=$rem."\n"; $entry++; unless(exists($index{$rem})){ $index++; $index{$rem}=''; } $rem=''; $pre=''; } if($self->{'mode'} eq 'bigram'){ if($pre ne ''){ $out.=$pre.$char."\n"; $entry++; unless(exists($index{$pre.$char})){ $index++; $index{$pre.$char}=''; } } $pre=$char; } else{ $out.=$char."\n"; $entry++; unless(exists($index{$char})){ $index++; $index{$char}=''; } $pre=''; } } } # $cleand_content.=$1; }gesx; if($rem ne ''){ $out.=$rem."\n"; $entry++; unless(exists($index{$rem})){ $index++; $index{$rem}=''; } $rem=''; } $out.="#######################\n"; $out.='Index keys(Unigram):'.$index."\n"; $out.='Entries(Unigram):'.$entry."\n"; my $ofh=new FileHandle('> '.$self->{'out'}) || Carp::croak("Failed to open output file."); print $ofh $out; $ofh->close(); } |
このサイト(作品データベース: http://www.accessup.org/anime/)の検索エンジンはインデックスレベルから自作で、インデックス型検索エンジンですが、漏れはなるべく作りたくないタイプの検索対象なので、インデックサーに喰わせる前に色々なパターンを作ってから喰わせています。
例:
| ドラゴンクエスト�� -悪霊の神々- Dragon Warrior II (Dragon Quest 2) どらごんくえすと2 |
| ドラゴンクエスト�� -悪霊の神々- どらごんくえすと2 Dragon Quest2 Dragon Warrior II (Dragon Quest 2) Dragon Quest 2 Dragon Warrior II (Dragon Quest 2)。 ドラゴンクエスト�� -悪霊の神々- ドラゴンクエスト2 -悪霊の神々- ドラゴンクエスト II -悪霊の神々- Dragon Warrior II (Dragon Quest II ) ドラゴンクエスト�彊�霊の神々 -悪霊 -悪霊の -悪霊の神 -悪霊の神々 -悪霊の神々- の神々- エスト�� クエスト�� ゴンクエスト�� スト�� ドラゴ ドラゴン ドラゴンク ドラゴンクエ ドラゴンクエス ドラゴンクエスト ドラゴンクエスト�� ラゴンクエスト�� ンクエスト�� 悪霊の神々- 神々- 霊の神々- |
1日を通すと平均10秒以内に検索結果が更新される、世界最高速のインデックス更新速度(?)の検索エンジン
http://minakoe.jp/
のプレビュー版リリースしました。
詳しくは
http://www.accessup.org/pj/6_B4C9CDFDBFCDA4B5A4F3/6/list.html
の「皆声.jp(Devour)」の項をご参照あれ。
こちらの記事にn-gramで検索してきた方には残念(?)ですが、minakoe.jpでは形態素解析(分ち書き)を使っています。
何で形態素解析の方を採用しているのかは、上の説明の方に書いた通り。
また、日本語に特化しているので、内部の文字コードはUTF-8ではなく、EUC-JPを選んでいます。
その理由は、
| 日本語を対象の検索エンジンに最適な内部文字コードとは(UTF8 or EUC-JP or ?) http://www.accessup.org/pj/6_B4C9CDFDBFCDA4B5A4F3/20080914.html |
[コメントする(論客以外もコメント可能記事)/9個
| ブックマーク | Buzzurl | Fc2 | Hatena | Nifty | Yahoo | 皆声まとめ |
[他の記事も読む]
<=新記事2006/02/03 論客順位投票のバグ修正しました
=>古記事2006/02/02 Yahoo::Yahoo!の別ウィンドウで開くのオプションが利かなくなっている & 事後報告
・この論客の大分類が「検索エンジンレポート」の記事
・この論客の記事全て
・他論客の記事を含んだ新着日記記事一覧
・作品DBのトップに戻る