Unicodeを用いたN-gram索引の一実現方式とその評価

Unicodeを用いたN-gram索引の
一実現方式とその評価
原田昌紀・風間一洋・佐藤進也
日本電信電話(株)
未来ねっと研究所
2000/Mar/22
第136回自然言語処理研究会
1
発表内容
研究の背景と目的
 N-gram方式の選定理由
 UnicodeベースのN-gram索引実現方式

–
–
Unicode文字シーケンスの正規化
N-gram長を可変とする分割アルゴリズム
WWWサーチエンジンへの適用例
 言語に依存した検索処理
 まとめ

2000/Mar/22
第136回自然言語処理研究会
2
研究の背景

Unicode
–

世界中の文字を16bit単位のUnicode文字で表現
するマルチスクリプト文字集合
Unicodeベースの全文検索実現方式の検討
–
–
2000/Mar/22
HTML，XMLなどの規格に対応するため
多言語対応の情報検索システムへの第一歩
第136回自然言語処理研究会
3
全文検索モジュールJerkyの開
発方針

言語に依存した処理の分離
–
–

スケーラビリティの確保
–

Unicodeベースの索引
辞書を必要としない索引づけ方式の採用
分散情報探索システムのノードでの利用から，
大規模なロボット型サーチエンジンまで
マルチプラットフォーム
–
2000/Mar/22
Javaによる実装
第136回自然言語処理研究会
4
索引づけ方式の検討（１）

転置索引（単語単位・形態素単位）
○ 検索精度が高い
× 辞書のメンテナンスが必要
× 言語ごとに形態素解析システムが必要

Suffix Array（文字単位）
○ 高速な文字列検索を実現できる
× 索引サイズが大きい
× 検索時に検索対象テキストにアクセスする必要
がある
2000/Mar/22
第136回自然言語処理研究会
5
索引づけ方式の検討（２）

転置索引（N-gram単位）
○ 言語に依存した辞書が不要
○ 日本語・中国語・韓国語などでの実績
○ 単語・形態素単位とのハイブリッド方式も可能
△ 検索速度・索引サイズは中程度
 大規模システムではチューニングが必要
× 検索ノイズの発生
 京都→東京都，ルパン→ダブルパンチ
 N-gram単位では不可避の問題，言語ごとに対応
2000/Mar/22
第136回自然言語処理研究会
6
N-gram転置索引の構成
imode
…
アルゴリ
…
生起位置情報
検索
…
報検
語彙ファイル
参照ファイル
報検索
文書
2000/Mar/22
．．．
検索エン
検索シス
第136回自然言語処理研究会
7
N-gram方式のUnicodeベースでの
実現

課題１：同じ文字が異なるUnicode文字シー
ケンスで表されることがある
→１．分割前に文字シーケンスの正規化

課題２：性質の異なる多様な文字の存在
→２．文字プロパティに基づいて記号類を判定
→３．文字ブロックごとに異なる単位で分割
2000/Mar/22
第136回自然言語処理研究会
8
文字シーケンスの正規化（１）

“Canonical Decomposition／Composition”
–
文字をそれと本質的に同一な文字シーケンスに分解
する／合成する
ö ⇔ o +¨
 “Compatibility Decomposition”
–
（ Canonical Decomposition に加えて）
互換性のために定義されている文字を標準的な文字
シーケンスに分解する
ﾔ⇒ヤ
2000/Mar/22
Ｇ ⇒G
℃⇒ °+ C
第136回自然言語処理研究会
9
文字シーケンスの正規化（２）

N-gramで索引づけする場合
→Compatibility Decompositionで分解した
後に，Canonical Compositionで合成する
ｺｰﾄﾞ⇒コート゛ ⇒コード

文字プロパティによる不要文字の判別
–
2000/Mar/22
例：文字プロパティがLetterあるいはDigit以外の
文字は空白に置換
第136回自然言語処理研究会
10
Unicode文字ブロックごとに分割
単位を設定
Basic Latin
Latin1 Supplement
:
Cyrillic
Thai
:
Arrows
:
Hiragana
Katakana
CJK Unified Ideographs
Hangul Syllables
:
U+0000～U+007F
U+0080～U+00FF
単語（空白区切り)
単語（空白区切り）
U+0400～U+04FF
U+0E00～U+0E7F
単語（空白区切り）
4-gram
U+2190～U+21FF
無視（索引づけしない）
U+3040～U+309F
U+30A0～U+30FF
U+4E00～U+9FFF
U+AC00～U+D7A3
3-gram
4-gram
2-gram
3-gram
表：Unicode2.1の文字ブロック（抜粋）
2000/Mar/22
第136回自然言語処理研究会
11
N-gramへの分割アルゴリズム
文字ブロックごとにN-gram長を設定
 異なる文字ブロックが隣接する部分は2-gram

D502iを買いました
↓
文字ブロックごとに分割
D502i，を，買，いました
↓
Basic Latinは単語単位に，
Hiraganaは3-gram単位に分割
D502i，を，買，いまし，ました，した，た
↓
1-gramは2-gramに展開
D502i，iを，を買，買い，いまし，ました，した，た
2000/Mar/22
第136回自然言語処理研究会
12
N-gram長パラメータの設定
トレードオフの存在→目的に応じて決める
１．N-gram長と検索速度

–
–
N-gram長が大きいほど，位置情報のI/Oが減少
N-gram長より短い文字列の検索には時間がか
かる
２．N-gram長と転置索引のサイズ
–
–
2000/Mar/22
語彙ファイルの大きさは指数関数的に増大
参照ファイルの大きさは一定
第136回自然言語処理研究会
13
N-gram転置索引の構成（再掲）
imode
…
アルゴリ
…
生起位置情報
検索
…
報検
語彙ファイル
参照ファイル
報検索
文書
2000/Mar/22
．．．
検索エン
検索シス
第136回自然言語処理研究会
14
実データに基づくN-gram長の推定

サーチエンジンODINへの適用結果
–
約597万URLのHTMLファイルを索引づけ
–
1999年10月1日～10月31日に使用された検索
語85,697語における字種の分布
N-gramの頻度と索引ファイルにおける占有率
–
–
2000/Mar/22
Hiragana, Katakana, CJK Unified Ideographsに
適したパラメータ
第136回自然言語処理研究会
15
検索語における漢字連続長

字種が多いため，3-gram以上は非現実的
→CJK Unified Ideographsは2-gram単位
20000
18000
16000
14000
12000
10000
8000
6000
4000
2000
0
全体
字種混在
1
2000/Mar/22
2
3
4
5
6
7
8
第136回自然言語処理研究会
9
10
11
12
16
検索語におけるひらがな連続長

漢字やカタカナと混在することが多い
→Hiraganaは3-gram単位
6000
全体
字種混在
5000
4000
3000
2000
1000
0
1
2000/Mar/22
2
3
4
5
6
7
8
第136回自然言語処理研究会
9
10 11 12
17
検索語におけるカタカナ連続長

カタカナは3文字以上連続することが多い
→平均的にはKatakanaは4-gram程度が高速
7000
全体
字種混在
6000
5000
4000
3000
2000
1000
0
1
2000/Mar/22
2
3
4
5
6
7
8
第136回自然言語処理研究会
9
10 11 12
18
転置索引（参照ファイル）の占有率


対象テキストにおけ
る字種の頻度を反映
片４片‐漢漢１
片３
片２
片１
平‐片
漢２
漢-平,平-漢がなけれ
ば，ひらがな１文字
を含んだ語の検索は
困難
平‐３
漢‐平
平２
平１
2000/Mar/22
第136回自然言語処理研究会
平‐漢
19
言語に依存した検索処理の追加

文書と検索語の言語情報が一致する場合
には検索処理を拡張可能
–
–

ステミング，正規化，辞書の利用など
同じ文字シーケンスでも，特定の言語にのみ
マッチ
言語情報を付加した索引づけ
–
可変長N-gramによる分割＋転置索引という構
成をベースに実現可能
 語彙ファイルにN-gramと言語情報と格納
2000/Mar/22
第136回自然言語処理研究会
20
おわりに

まとめ
–
–

字種によってN-gramの長さを可変とする索引
づけ方式をUnicodeベースで実現した
日本語WWWサーチエンジンを例に，その適
用方法を示した
課題・今後の予定
–
–
2000/Mar/22
日本語以外、ＣＪＫ以外への適用と評価
N-gramと形態素解析を併用した分割
第136回自然言語処理研究会
21

Download Report