Ngram(N-gram)とは何か & 形態素解析との比較

総閲覧回数:4,034,567回 / ブログ拍手:2,630
作品DB等各サービスの機能追加情報や、技術系・面白系記事を中心に提供。
記事の投稿は基本Twitterでも告知させて頂いています。
連絡は作品DBの論客の方なら私書、DB外ユーザの方ならメールTwitterで可能です。
アクセス記録[推移 / PV内訳(過去1日 / 過去1週間) / 外部アクセス元 (昨日 / 過去1週間) / ログイン論客足跡]
プロフィール私書(メール)
   /   /送済
評価(一覧   /)
投票   /共:   /
ファン登録
作品/情報/
DB構築()
ブログ
[書く]
攻略記事リンク集
My Play List
<=次の記事 論客順位投票のバグ修正しました
=>前の記事 Yahoo::Yahoo!の別ウィンドウで開くのオプションが利かなくなっている & 事後報告

1.
2006/02/03 検索エンジン&SEO > 検索エンジンの仕組み > Ngram(N-gram)とは何か & 形態素解析との比較」
[この書込みのみ表示(記事URL紹介用) / 編集 / 削除 / トラバ送信 / 共有分類に追加(タグ付け)]拍手:25個

1. 書こうと思ったきっかけ
2. Ngram(N-gram)とは
3. 向きと不向き
4. Ngramの実装
5. NGramの例(bigram=2文字切り出し時)
6. Ngramの有名な欠点
7. 形態素解析とは
8. 形態素解析の欠点
9. 形態素解析結果の実際例
10. まとめ: とはいえ鋏と包丁は使い様
11. コードのサンプル
12. ちなみにこのサイトの検索エンジンは...
13. ということで、検索エンジンを作ってリリースしてみた

1. 書こうと思ったきっかけ

ライブドアのブログ検索がNgramを採用したと記事になっていて、単に汎用的な技術な割にはそれだけで大々的に記事になってしまっているので、Ngramについて説明してみようと思う。
表面的なことは理解されていると思うが、あまりそのデメリット等を知っている人は少ないと思うので。
ちなみに、N-gram採用の背景としては、ライブドアが買収してなくなったAAA Cafeという検索エンジンの技術の系譜で、単にN-gramを採用したのかもしれない。
2. Ngram(N-gram)とは

オープンソースの検索エンジンを含め、多くの検索システムでは、転置インデックス(キーワードとページの組み合わせ = 本の後ろの目次のような構造)が一般的であるが、その転置インデックスのキーの切り出しを、辞書や構文解析に基づくのではなく、単に一定の文字数で切り出した語を入れることで作る方式のことをN-gramという。
Nとは、切り出す文字の単位が複数ありえるということを意味する。
例えば、常に2文字の単語で切り出して、目次のキーを作る。
ちなみに、「常に」というのは、理解の都合上そういっているのであって、2文字で切り出すというルールでも、そうでない部分も必要になる(文の末尾等)。
3. 向きと不向き

どんな言語にでも適用できるので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]
で表現できる。
4. Ngramの実装

ユニグラム = unigram (1文字単位)
バイグラム = bigram (2文字単位)
トリグラム = trigram (3文字単位)
のどれかを使うのが現実的。
4文字以上は、3文字以下の検索が来た時に、凄く負荷のかかる検索の仕方をしなくてはならなくなるので、通常使わない。
基本的にN-gramとは、N文字丁度の検索が来た時に、一番効率の良い検索を可能にする。
N文字を下回ると何故遅くなるのかといえば、仕組み的にOR検索をすることになり、読まなければならない量が増えるからである。
ちなみに分かち書きの方法には、形態素解析とN-gramがあるが、それぞれ、単に分け方が異なるだけではなく、N-gramの場合には、N-gram用の特別な検索論理を用意しなければならないということでもある。
オープンソースのウェブ検索エンジンとして有名な(使いものにはならないかもしれないけど)Nutcheはその3つのどれかを選択することができるようになっている。
ちなみに、そのように、他人任せのライブラリやロジックでするのなら択一になるが、自分で作る場合には、場合場合によって、使い分けたり、全く別のロジックで切り出す賢さを発揮すべきだろう。Ngramは言語の特性を無視して適用できる技術ではあるが、逆に言うと言語の特性を反映させないと、納得するレベルのサービスの境地にまでは達することができない。
そして...日本語は、特別な処理をするに値する言語である。
5. NGramの例(bigram=2文字切り出し時)

入力文: 
ここaccessup.orgの管理人は、2009年の時点で栗田創がやっております。



bigramで分割



出力トークン: 
ここ 

accessup 
org
の管
理人
人は

2009
年の
の時
時点
点で
で栗
栗田
田創
創が
がや
って
てお
りま
ます

↑は以下の例外規則を組み合わせています。
・英数字は異なる文字の種類が出るまでを1単語と認識出来る(N-gramを適用する必要がない)
・N-GramはNを下回る文字の検索はOR検索で行うので(頭文字が指定語で始まるトークンでOR検索をする)、文の末尾はNを下回る単位になってもそこで検索できるように頭文字になるように切り出す
・「、」「。」はN-Gramの文の切れ目として活用できる
・「、」「。」「.」のような検索で意味を持たない記号はインデックス対象から外す(それでも検索できるようにしたいのなら省かない)

※フレーズ検索(トークンの並びの強制)を可能にするには、別のインデックス単位、もしくは情報が必要になります。
6. Ngramの有名な欠点

「N-gramを採用したから、部分一致検索ができる」
それは確かにその通り。
しかし、逆に「東京都」という語が含まれた文章を、「京都」でヒットさせてしまうことができる。
「意味」は解釈せず、単に字面だけで切り出した、ある意味初歩的な切り出し方の為、そういうことが起きる。
意味に基づいて語を切り出す形態素解析なら、そんなことは起きない。
形態素解析は、常に改善を志向できるが、N-gramには、常に解決できない問題が存在する。
また、処理の速度としては、検索エンジンに使う場合には、オフライン(インデックス)の速度は速くなるが、オンラインはその分逆に検索が遅くなる(不必要に分割して検索しなければならないので)という問題がある。
また、非正確な分割=>無駄な分割=>大量のHDDの利用、という形で、ディスク使用量で、無駄が多い。小規模な検索では問題にならないが、大規模になると、問題になってくる。
7. 形態素解析とは

形態素解析は、辞書や文法に基づいて分ける方式。
日本には
・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より効率的な検索ができるでしょう。
8. 形態素解析の欠点

 1. 辞書照会と最適な分割の計算が必要な為、極めて単純な原理で分割するN-Gramに比べて処理時間がかかる
 2. 辞書の単位が最小に合わせたものになっていないと検索漏れが生じる
例: 辞書に「マカデミアナッツ」として登録されていると、「ナッツ」で「マカデミアナッツ」が検索出来ない。辞書に「マカデミア」と「ナッツ」だけが登録されていれば
「マカデミアナッツ」→形態素解析→「マカデミア」 「ナッツ」
となって検索できるが。
ちなみに、「マカ」「デミア」ではこれでも検索出来ないが、それは語の最小の単位ではないので、形態素解析としては正しい。
N-Gramはここで「マカ」でも「デミ」でも「ミア」でも引っ掛けてしまうので、検索のノイズを生じさせる。
 3. 辞書を修正しても、検索入力側は即座に反映できても、オフライン側(インデックス側)は0から生成し直さないと分ち書きの仕方が合致しないので、辞書の修正で問題を解決できるとはいえ、アップデートするタイミングは正確を期すとインデックスのフルアップデートまで出来ない
9. 形態素解析結果の実際例

検索エンジンにおける形態素解析の実際例は
皆声.jpの検索結果
http://search.minakoe.jp/rsss/rsss.asp?stype=new
を見ると各URLに「分ち書き」というリンクがあるので
それをクリックしてどういうものか見てみて下さい。
(「分ち書き」機能へのリンクは一般人には無用のものとして削除しました)
例: http://sakuhindb.com/pj/6_B4C9CDFDBFCDA4B5A4F3/20081016.htmlの形態素解析結果
スプログ/の/動機/は/大きく/分け/て/2/つ/。
/ /目的/1/、/大量/に/ブログ/を/作っ/て/広告/収入/を/得る/こと/ /目的/2/、/自分/が/目的/に/する/サイト/の/リンク/スコア/を/稼ぐ/こと/ /1/について/は/、/迷惑/で/は/あり/ます/が/、/生成/者/自身/に/は/短い/目/で/は/然 /程/マイナス/は/生じ/ませ/ん/。
/ /但し/スパムブログ/が/大量/に/発生/する/ブログ/を/使っ/て/いる/周り/の/人達/は/検索/エンジン/から/の/信用/出来/ない/ドメイン/扱い/の/巻き添え/を/喰らう/こと/に/なり/ます/。
/ /例えば/、/seesaa/,/ /fc/2/と/Yahoo/など/から/あまり/インデックス/さ/れ/ない/と/言わ/れる/ブログ/ASP/は/その/せい/でしょ/う/。
/ /それ/は/、/ある/意味/それ/でも/広告/収入/が/入れ/ば/良い/や/と/し/て/き/た/ブログ /ASP/側/の/怠慢/の/つけ/が/ドメイン/の/価値/の/低下/=/>/検索/エンジン/の/評価 /の/低下/、/という/形/で/ブーメラン/の/よう/に/返っ/て/き/て/いる/と/いう/こと/です/ が/。
/ /長い/目/で/見れ/ば/その/ブログ/ASP/の/価値/を/焼畑/の/よう/に/低下/さ/せる/こと/に/なる/でしょ/う/。
/ /そういう/意味/で/も/ブログ/ASP/は/本来/きちんと/対応/し/ない/と/いけ/ませ/ん/。
/ /2/、/目的/と/する/サイト/へ/の/リンク/を/作っ/て/、/検索/エンジン/に/評価/さ/れる/「/リンク/」/を/稼ぐ/こと/。
/ /検索/エンジン/の/仕組み/を/考え/て/、/そういう/こと/を/する/こと/が/目立ち/ます/。
/ /ただ/、/これ/は/出来/た/直後/は/見逃さ/れる/こと/は/あり/ます/が/、/調べれ/ば/どの/ リンク/が/異常/に/増え/て/いる/の/か/、/という/形/で/リンク/数/の/上位/の/方/から/クリーニング/を/し/て/くる/こと/も/検索/エンジン/側/も/できる/の/で/、/ある程度/クリーニング/に /人員/を/さい/て/い/た/と/し/たら/、/それ/によって/稼げる/リンク/の/効果/は/一時/的/ に/なる/でしょ/う/。
/ /長期/的/に/言え/ば/、/必ず/そうした/不自然/な/リンク/は/見つかり/、/また/リンク/先/に対する/その/リンク/は/ポイント/を/下げ/られ/たり/、/場合/によって/は/検索/対象/から/外さ/れる/ こと/に/なり/ます/。
/ /ある/意味/、/個別/に/スパムブログ/を/見つけ/て/いく/より/も/、/リンク/数/が/多い/ところ /から/リンク/を/張っ/て/いる/ところ/を/スパム/と/判断/し/て/いく/方/が/効率/的/な/ので/、/人間/が/スパム/・/もしくは/不正/な/行為/を/し/て/いる/と/判断/できる/よう/な/行動 /は/慎む/べき/です/。
/ /そこ/を/誤解/し/て/スパムブログ/を/作る/人/が/未だ/多く/いる/よう/な/ので/、/そんな/こと/を/し/て/も/思っ/た/よう/に/得/に/は/つながら/ない/よ/、/と/諭す/為/に/動作/原理/を/書い/て/おき/ます/。

10. まとめ: とはいえ鋏と包丁は使い様

N-gramは日本語にとっては理想の単語切り出し手法ではないが、絶対に形態素解析の違いによる検索抜けを回避したい等の理由があれば、活躍する場はあるでしょう。
例えば、システム的には形態素解析をベースにしていたとしても、ノイズよりも検索漏れを避けたいような場合には、N-Gram的な処理を混ぜるというのもありでしょう(後述する作品DBの検索システムはそのように作っています)。
何事も包丁と鋏は使い様です。

一応N-Gramと形態素解析の簡単な比較です。
方式分ち書き(Index)速度必要ディスク量検索速度分ち書き単語数検索漏れ検索ノイズ
N-Gram速い遅い多い無し
形態素解析遅い速い少ない有り

11. コードのサンプル

サンプルとして、簡単な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();
}

12. ちなみにこのサイトの検索エンジンは...

このサイト(作品データベース: http://sakuhindb.com/)の検索エンジンはインデックスレベルから自作で、インデックス型検索エンジンですが、漏れはなるべく作りたくないタイプの検索対象なので、インデックサーに喰わせる前に色々なパターンを作ってから喰わせています。

例:
ドラゴンクエストⅡ -悪霊の神々-
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 )
ドラゴンクエストⅡ悪霊の神々
-悪霊
-悪霊の
-悪霊の神
-悪霊の神々
-悪霊の神々-
の神々-
エストⅡ
クエストⅡ
ゴンクエストⅡ
ストⅡ
ドラゴ
ドラゴン
ドラゴンク
ドラゴンクエ
ドラゴンクエス
ドラゴンクエスト
ドラゴンクエストⅡ
ラゴンクエストⅡ
ンクエストⅡ
悪霊の神々-
神々-
霊の神々-
といったパターンもカバーして形態素解析をさせることで、形態素解析の仕組みをキープしながら形態素漏れを防いでいます(パターンは全て自動生成です)。

また、色々なものが検索対象になっているので、まずそれを共通のフォーマットに変換してから、インデックサーに食べさせています。
namazuとかはHTMLの形式にWord, Excel, PDFなども一回変換して統一して処理をしていますね。
Googleとかも同じようなことをしているでしょう。
このサイトの場合は、RSSに形式を一度統一してから処理をしています。

なお、新しく世の中向けに検索エンジンを作って公開してみようと思うので、
「検索エンジンレポート」の方に「検索エンジンの作り方」
http://sakuhindb.com/pj/6_B4C9CDFDBFCDA4B5A4F3/6/list.html
という小分類を追加してみました。
13. ということで、検索エンジンを作ってリリースしてみた

1日を通すと平均10秒以内に検索結果が更新される、世界最高速のインデックス更新速度(?)の検索エンジン
http://minakoe.jp/
のプレビュー版リリースしました。
ブログ専用の検索エンジンになりますが。

詳しくは
http://sakuhindb.com/pj/6_B4C9CDFDBFCDA4B5A4F3/6/list.html
の「皆声.jp」の項をご参照あれ。

こちらの記事にn-gramで検索してきた方には残念(?)ですが、minakoe.jpでは形態素解析(分ち書き)を使っています。
何で形態素解析の方を採用しているのかは、上の説明の方に書いた通り。
また、日本語に特化しているので、内部の文字コードはUTF-8ではなく、EUC-JPを選んでいます。
その理由は、
日本語を対象の検索エンジンに最適な内部文字コードとは(UTF8 or EUC-JP or ?)
http://sakuhindb.com/pj/6_B4C9CDFDBFCDA4B5A4F3/20080914.html
の方に書いているので、興味がある方は読んでみてください。
なお、minakoe.jpの方では、検索結果のURLに対してコンテンツを形態素解析(分ち書き)をした結果をセレクトボックスから見ることが出来るので、検索エンジンの内部的なデータの保持の仕方に興味がある方はみてみることができます。

コメントする25個


[他の記事も読む]
<=次の記事 論客順位投票のバグ修正しました
=>前の記事 Yahoo::Yahoo!の別ウィンドウで開くのオプションが利かなくなっている & 事後報告


大分類が「検索エンジン&SEO」の記事
この論客の記事全て
↑上へ