2000/Mar/22 第 136 回自然言語処理研究会 1 Unicode を用いた N-gram 索引の 一実現方式とその評価 原田昌紀・風間一洋・佐藤進也 日本電信電話 ( 株 ) 未来ねっと研究所

2000/Mar/22 第 136 回自然言語処理研究会 2 発表内容 n 研究の背景と目的 n N-gram 方式の選定理由 n Unicode ベースの N-gram 索引実現方式 – Unicode 文字シーケンスの正規化 – N-gram 長を可変とする分割アルゴリズム n WWW サーチエンジンへの適用例 n 言語に依存した検索処理 n まとめ

2000/Mar/22 第 136 回自然言語処理研究会 3 研究の背景 n Unicode – 世界中の文字を 16bit 単位の Unicode 文字で表現 するマルチスクリプト文字集合 n Unicode ベースの全文検索実現方式の検討 – HTML ， XML などの規格に対応するため – 多言語対応の情報検索システムへの第一歩

2000/Mar/22 第 136 回自然言語処理研究会 4 全文検索モジュール Jerky の 開発方針 n 言語に依存した処理の分離 – Unicode ベースの索引 – 辞書を必要としない索引づけ方式の採用 n スケーラビリティの確保 – 分散情報探索システムのノードでの利用か ら，大規模なロボット型サーチエンジンま で n マルチプラットフォーム – Java による実装

2000/Mar/22 第 136 回自然言語処理研究会 5 索引づけ方式の検討（１） n 転置索引（単語単位・形態素単位） ○ 検索精度が高い × 辞書のメンテナンスが必要 × 言語ごとに形態素解析システムが必要 n Suffix Array （文字単位） ○ 高速な文字列検索を実現できる × 索引サイズが大きい × 検索時に検索対象テキストにアクセスする必 要がある

2000/Mar/22 第 136 回自然言語処理研究会 6 索引づけ方式の検討（２） n 転置索引（ N-gram 単位） ○ 言語に依存した辞書が不要 ○ 日本語・中国語・韓国語などでの実績 ○ 単語・形態素単位とのハイブリッド方式も 可能 △検索速度・索引サイズは中程度 n 大規模システムではチューニングが必要 × 検索ノイズの発生 n 京都 → 東京都，ルパン → ダブルパンチ n N-gram 単位では不可避の問題，言語ごとに対応

2000/Mar/22 第 136 回自然言語処理研究会 7 N-gram 転置索引の構成 ．．． imode 検索 報検 アルゴリ … … … 検索シス 報検索検索エン 語彙ファイル 参照ファイル 文書 生起位置情報

2000/Mar/22 第 136 回自然言語処理研究会 8 N-gram 方式の Unicode ベースで の実現 n 課題１：同じ文字が異なる Unicode 文字 シーケンスで表されることがある → １．分割前に文字シーケンスの正規化 n 課題２：性質の異なる多様な文字の存在 → ２．文字プロパティに基づいて記号類を判 定 → ３．文字ブロックごとに異なる単位で分割

2000/Mar/22 第 136 回自然言語処理研究会 9 文字シーケンスの正規化 （１） n “Canonical Decomposition ／ Composition” – 文字をそれと本質的に同一な文字シーケンスに分 解する ／ 合成する n “Compatibility Decomposition” – （ Canonical Decomposition に加えて） 互換性のために定義されている文字を標準 的な文字シーケンスに分解する ö ⇔ o +¨ ﾔ⇒ヤﾔ⇒ヤＧ⇒GＧ⇒G ℃⇒ °+ C℃⇒ °+ C

2000/Mar/22 第 136 回自然言語処理研究会 10 文字シーケンスの正規化 （２） n N-gram で索引づけする場合 →Compatibility Decomposition で分解し た 後に， Canonical Composition で合成す る n 文字プロパティによる不要文字の判別 – 例：文字プロパティが Letter あるいは Digit 以外 の文字は空白に置換 ｺｰﾄﾞ ⇒ コート゛ ⇒ コード

2000/Mar/22 第 136 回自然言語処理研究会 11 Basic LatinU+0000 ～ U+007F Latin1 SupplementU+0080 ～ U+00FF : CyrillicU+0400 ～ U+04FF ThaiU+0E00 ～ U+0E7F : ArrowsU+2190 ～ U+21FF : HiraganaU+3040 ～ U+309F KatakanaU+30A0 ～ U+30FF CJK Unified IdeographsU+4E00 ～ U+9FFF Hangul SyllablesU+AC00 ～ U+D7A3 : Unicode 文字ブロックごとに分 割単位を設定 表： Unicode2.1 の文字ブロック（抜粋） 単語（空白区切り ) 単語（空白区切り） 4-gram 無視（索引づけしない） 3-gram 4-gram 2-gram 3-gram

2000/Mar/22 第 136 回自然言語処理研究会 12 N-gram への分割アルゴリズム n 文字ブロックごとに N-gram 長を設定 n 異なる文字ブロックが隣接する部分は 2- gram D502i を買いました ↓ 文字ブロックごとに分割 D502i ，を，買，いました ↓ Basic Latin は単語単位に， Hiragana は 3-gram 単位に分割 D502i ，を，買，いまし，ました，した，た ↓ 1-gram は 2-gram に展開 D502i ， i を，を買，買い，いまし，ました，した，た D502i を買いました ↓ 文字ブロックごとに分割 D502i ，を，買，いました ↓ Basic Latin は単語単位に， Hiragana は 3-gram 単位に分割 D502i ，を，買，いまし，ました，した，た ↓ 1-gram は 2-gram に展開 D502i ， i を，を買，買い，いまし，ました，した，た

2000/Mar/22 第 136 回自然言語処理研究会 13 N-gram 長パラメータの設定 n トレードオフの存在 → 目的に応じて決め る １． N-gram 長と検索速度 – N-gram 長が大きいほど，位置情報の I/O が減 少 – N-gram 長より短い文字列の検索には時間が かかる ２． N-gram 長と転置索引のサイズ – 語彙ファイルの大きさは指数関数的に増大 – 参照ファイルの大きさは一定

2000/Mar/22 第 136 回自然言語処理研究会 14 N-gram 転置索引の構成（再 掲） ．．． imode 検索 報検 アルゴリ … … … 検索シス 報検索検索エン 語彙ファイル 参照ファイル 文書 生起位置情報

2000/Mar/22 第 136 回自然言語処理研究会 15 実データに基づく N-gram 長の推 定 n サーチエンジン ODIN への適用結果 – 約 597 万 URL の HTML ファイルを索引づけ – 1999 年 10 月 1 日～ 10 月 31 日に使用された検索 語 85,697 語における字種の分布 – N-gram の頻度と索引ファイルにおける占有 率 – Hiragana, Katakana, CJK Unified Ideographs に 適したパラメータ

2000/Mar/22 第 136 回自然言語処理研究会 16 検索語における漢字連続長 n 字種が多いため， 3-gram 以上は非現実的 →CJK Unified Ideographs は 2-gram 単位

2000/Mar/22 第 136 回自然言語処理研究会 17 検索語におけるひらがな連続 長 n 漢字やカタカナと混在することが多い →Hiragana は 3-gram 単位

2000/Mar/22 第 136 回自然言語処理研究会 18 検索語におけるカタカナ連続 長 n カタカナは 3 文字以上連続することが多い → 平均的には Katakana は 4-gram 程度が高速

2000/Mar/22 第 136 回自然言語処理研究会 19 転置索引（参照ファイル）の占 有率 n 対象テキストにお ける字種の頻度を 反映 n 漢 - 平, 平 - 漢がなけ れば，ひらがな１ 文字を含んだ語の 検索は困難

2000/Mar/22 第 136 回自然言語処理研究会 20 言語に依存した検索処理の追 加 n 文書と検索語の言語情報が一致する場 合には検索処理を拡張可能 – ステミング，正規化，辞書の利用など – 同じ文字シーケンスでも，特定の言語にの みマッチ n 言語情報を付加した索引づけ – 可変長 N-gram による分割＋転置索引という 構成をベースに実現可能 n 語彙ファイルに N-gram と言語情報と格納

2000/Mar/22 第 136 回自然言語処理研究会 21 おわりに n まとめ – 字種によって N-gram の長さを可変とする索 引づけ方式を Unicode ベースで実現した – 日本語 WWW サーチエンジンを例に，その 適用方法を示した n 課題・今後の予定 – 日本語以外、ＣＪＫ以外への適用と評価 – N-gram と形態素解析を併用した分割

2000/Mar/22 第 136 回自然言語処理研究会 22 Unicode n 概要 – 世界中の文字を 16bit 単位の Unicode 文字で表現 – Unicode Consortium が提唱， ISO/IEC の ベ ースとなっている n 留意点 – 同じ文字が異なる Unicode 文字シーケンスで表 されることがある – マルチスクリプト文字集合 n 言語情報は別途必要

2000/Mar/22 第 136 回自然言語処理研究会 23 索引づけの流れ n １．文字シーケンスを正規化する n ２．記号類を空白に置換する n ３．文字シーケンスを空白で分割し，さ らに N-gram に分割する n ４． N-gram の位置情報を転置索引に格 納する