N-Gram

検索エンジン全文検索エンジン

N-Gramとは?

 状態:-  閲覧数:661  投稿日:2017-03-17  更新日:2017-03-23  
与えられた文字列中のn文字の連続した文字列
・文脈や単語を考慮せず、文字数の単位(N=2の場合は2文字毎)で文字を分解する

「N文字分の文字の連なり」をキーとしてインデックスを作成する全文検索の古典的な手法
・単純に文字の並びを見出し語としてインデックスを作成
・検索に漏れが発生しない一方で、検索結果にノイズが多くなったり、インデクスのサイズが肥大化したりする傾向がある

形態素解析との比較

 閲覧数:219 投稿日:2017-03-18 更新日:2017-03-18 

キーの数が大きくなる


文字の連なりがインデックスのキーとなる
・そのため、形態素解析の分かち書きで作られた文字列キーよりもキーの数が大きくなる


辞書のメンテナンスが不要


形態素解析を行わない
・そのため、形態素解析用の辞書のメンテナンスが不要

N-Gramの種類

 閲覧数:268 投稿日:2017-03-19 更新日:2017-03-23 

3種類


ユニグラム
・1文字を元にインデックスを作成する方法

バイグラム
・2文字の並びを元にインデックスを作成する方法

トリグラム
・3文字の並びを元にインデックスを作成する方法


バイグラム方式 / 例1


2文字ごとに切り出す

14文字からなる文章だった場合
・13個のNgramを抽出
・添字はそのNgramの出現位置を表す

14文字からなる文章
私は今、日本に住んでいます。

13個のNgramを抽出
Array
(
   [0] => 私は
   [1] => は今
   [2] => 今、
   [3] => 、日
   [4] => 日本
   [5] => 本に
   [6] => に住
   [7] => 住ん
   [8] => んで
   [9] => でい
   [10] => いま
   [11] => ます
   [12] => す。
)


バイグラム方式 / 例2


「これはペンです」をNを2としてNgramで分解
・「これ れは はペ ペン ンで です」
※配列でなくても良い


何文字でも良い


n-gramで”abcd”という文字列をトークナイズする
N=1 : 'a', 'b', 'c', 'd';
N=2 : 'ab', 'bc', 'cd';
N=3 : 'abc', 'bcd';
N=4 : 'abcd';



転置インデックス

フレーズ検索

コメント投稿(ログインが必要)



類似度ページランキング
順位 ページタイトル抜粋
1 PNG 44
2 GNU 44
3 Chromecast 38
4 Same-origin policy 33
5 AirPlay 31
6 article 31
7 K-means 法(K平均法) 29
8 Markdown 29
9 Basecamp 29
10 Morris-Pratt algorithm 29
11 Hibernate 27
12 attribute 27
13 MPEG-DASH 27
14 memcached 27
15 Apache Solr 24
16 mod_deflate 24
17 Morris-Pratt algorithm border 23
18 CGM 22
19 Git 22
20 Ordinal Scale 21
2022/7/01 5:42 更新
週間人気ページランキング / 6-24 → 6-30
順位 ページタイトル抜粋 アクセス数
1 Flash Video | コンテナフォーマット | プログラミング用語 306
2 curl | HTTPクライアント(ネットワーク) | プログラミング用語 286
3 ルーター | ネットワーク | プログラミング用語 281
3 ユースケース | 開発 | プログラミング用語 281
4 ベクトル | 数学 | プログラミング用語 236
5 デーモン | Linux | プログラミング用語 227
6 正規表現 | プログラミング | プログラミング用語 194
7 YouTube | API | プログラミング用語 171
8 チェックアウト | バージョン管理システム(開発) | プログラミング用語 117
9 分かち書き | 形態素解析 | プログラミング用語 63
10 Linux | プログラミング用語 57
11 リバースエンジニアリング | 開発 | プログラミング用語 54
12 ネットワークアドレス | ネットワーク | プログラミング用語 50
13 PowerShell | スクリプト | プログラミング用語 44
14 クローラ | 検索エンジン | プログラミング用語 31
14 可搬性 | プログラミング | プログラミング用語 31
15 Subversion | バージョン管理システム(開発) | プログラミング用語 27
16 アンチパターン | プログラミング | プログラミング用語 11
17 プログラミング用語 9
18 deflate | ネットワーク | プログラミング用語 8
2022/7/1 1:01 更新