テキスト検索は 文字列検索でも木検索でもない

Presentation on theme: "テキスト検索は 文字列検索でも木検索でもない"— Presentation transcript:

1 テキスト検索は 文字列検索でも木検索でもない
京都大学人文科学研究所附属漢字情報研究センター 安岡孝一

2 テキスト処理とコンピュータの出会い IBM 704 (1954) FORTRAN I (1956) 入出力にCPY命令を使用
連続したメモリの内容を順次入出力 FORTRAN I (1956) 「Hollerith field」をFORMAT文に導入 定数長の連続した文字の列 メモリ空間上に連続的に配置

3 文字列(string)の登場 ALGOL 60 (1960) BNFによって定式化 「string」を1次元の文字の列として定義
<proper string> ::= <any sequence of basic symbols not containing ‘ or ’>|<empty> <open string> ::= <proper string>|‘<open string>’|<open string><open string> <string> ::= ‘<open string>’ 多くの実装では「string」をメモリに連続配置

4 文字列処理の実用化 IBM System/360 (1964) PL/I (1964) メモリ単位を8bit=1byteに
1文字=1byte (EBCDIC) PL/I (1964) CHARACTER型を規定 文字列に対する比較操作が可能に

5 文字列検索アルゴリズムの登場 Morris-Pratt (1970) Knuth-Morris-Pratt (1974)
部分マッチング後の検索キーのシフト量を増加 Knuth-Morris-Pratt (1974) Morris-Prattをさらに改良 Aho-Corasick (1975) 複数の検索キーに対し平行して検索

6 Aho-Corasickアルゴリズム ex) ITALYとTIEとTULIAを検索
INSTITUTE FOR RESEARCH IN HUMANITIES

7 Aho-Corasickアルゴリズム ex) ITALYとTIEとTULIAを検索
INSTITUTE FOR RESEARCH IN HUMANITIES

8 Aho-Corasickアルゴリズム ex) ITALYとTIEとTULIAを検索
INSTITUTE FOR RESEARCH IN HUMANITIES

9 Aho-Corasickアルゴリズム ex) ITALYとTIEとTULIAを検索
INSTITUTE FOR RESEARCH IN HUMANITIES

10 Aho-Corasickアルゴリズム ex) ITALYとTIEとTULIAを検索
INSTITUTE FOR RESEARCH IN HUMANITIES

11 Aho-Corasickアルゴリズム ex) ITALYとTIEとTULIAを検索
INSTITUTE FOR RESEARCH IN HUMANITIES

12 Aho-Corasickアルゴリズム ex) ITALYとTIEとTULIAを検索
INSTITUTE FOR RESEARCH IN HUMANITIES

13 Aho-Corasickアルゴリズム ex) ITALYとTIEとTULIAを検索
INSTITUTE FOR RESEARCH IN HUMANITIES

14 Aho-Corasickアルゴリズム ex) ITALYとTIEとTULIAを検索
INSTITUTE FOR RESEARCH IN HUMANITIES

15 逆方向文字列マッチング Boyer-Moore (1977) Commentz-Walter (1979)
検索キーの末尾からマッチングをおこなう 非マッチング時の検索キーのシフト量を増加 Commentz-Walter (1979) 複数の検索キーに対しBoyer-Mooreを適用

16 Commentz-Walterアルゴリズム
ex) ITALYとTIEとTULIAを検索 I T A L 4 3 5 6 7 U E Y L 1 I T 2 U 3 その他 INSTITUTE FOR RESEARCH IN HUMANITIES

17 Commentz-Walterアルゴリズム
ex) ITALYとTIEとTULIAを検索 I T A L 4 3 5 6 7 U E Y L 1 I T 2 U 3 その他 INSTITUTE FOR RESEARCH IN HUMANITIES

18 Commentz-Walterアルゴリズム
ex) ITALYとTIEとTULIAを検索 I T A L 4 3 5 6 7 U E Y L 1 I T 2 U 3 その他 INSTITUTE FOR RESEARCH IN HUMANITIES

19 Commentz-Walterアルゴリズム
ex) ITALYとTIEとTULIAを検索 I T A L 4 3 5 6 7 U E Y L 1 I T 2 U 3 その他 INSTITUTE FOR RESEARCH IN HUMANITIES

20 Commentz-Walterアルゴリズム
ex) ITALYとTIEとTULIAを検索 I T A L 4 3 5 6 7 U E Y L 1 I T 2 U 3 その他 INSTITUTE FOR RESEARCH IN HUMANITIES

21 Commentz-Walterアルゴリズム
ex) ITALYとTIEとTULIAを検索 I T A L 4 3 5 6 7 U E Y L 1 I T 2 U 3 その他 INSTITUTE FOR RESEARCH IN HUMANITIES

22 単純なバイト列マッチングでは検索に失敗？
漢字テキスト検索への応用 1文字≠1byte ex) 「安岡の1族」を日本語EUCで表現 安 岡 の 族 B0 C2 B2 AC A4 CE 31 C2 B2 単純なバイト列マッチングでは検索に失敗？

23 漢字テキスト検索への応用 1文字≠1byte 異体字による曖昧検索 幾何級数的に組み合わせが増える ex) 「帝國大學」の検索
「帝国大学」も「帝國大学」も「帝国大學」も… 「國」の異体字: 国、囯、囻、圀、囶 「學」の異体字: 学、斈、斆、斅 幾何級数的に組み合わせが増える

24 漢字テキスト検索への応用 篠原－有川 (1985) Aho-Corasickを漢字テキスト用に改良
ex) 日本語EUCで「十週休」と「十周休」を検索 BD B5 A1～AF B1～FE A1～FE D9 BC FE

25 漢字における逆方向マッチング 日本語EUCやシフトJISでは難しい UTF-8を考案(1993)
ISO (Unicode)の変形の一種 1文字を1～6バイトで表現 1バイト目には00～7F、C0～FEを使用 2バイト目以降には80～BFを使用 安 岡 の 族 E5 AE 89 E5 B2 A1 E3 81 AE 31 E6 97 8F 安 岡 の 族 E5 AE 89 E5 B2 A1 E3 81 AE 31 E6 97 8F

26 UTF-8での逆方向マッチング Commentz-Walterを使用可能 ∵ 文字間にマッチングすることはありえない
ex) 「大学」「大學」「大斈」を検索 88 1 96 2 A4 5 A6 A7 4 AD B8 E5 3 E6 他 6 7 8 9 10 11 A6 B8 AD 88 96 E6 E5 A4 A7

27 漢字テキスト検索への応用 1文字≠1byte 異体字による曖昧検索 テキストの非１次元性

28 漢字テキストの非１次元性 私は安岡孝一です。 私は安岡孝一です。 ルビつきテキストの検索 安岡孝一です やす おか こう いち

29 漢字テキストの非１次元性 私は安岡孝一です。 私は安岡孝一です。 ルビつきテキストの検索 私はやすおか やす おか こう いち

30 漢字テキストの非１次元性 私は安岡孝一です。 私は安岡孝一です。 ルビつきテキストの検索 安岡こういち やす おか こう いち

31 漢字テキストの非１次元性 ルビつきテキストの検索 私は安岡孝一です。 やす おか こう いち

32 漢字テキストの非１次元性 故宮の神(玄の避諱)武門に向かった。 故宮の神(玄の避諱)武門に向かった。 ルビつきテキストの検索
本文に埋め込まれた注の検索 故宮の神(玄の避諱)武門に向かった。 故宮の神(玄の避諱)武門に向かった。 神武門

33 漢字テキストの非１次元性 故宮の神(玄の避諱)武門に向かった。 故宮の神(玄の避諱)武門に向かった。 ルビつきテキストの検索
本文に埋め込まれた注の検索 故宮の神(玄の避諱)武門に向かった。 故宮の神(玄の避諱)武門に向かった。 故宮の玄武門

34 漢字テキストの非１次元性 ルビつきテキストの検索 本文に埋め込まれた注の検索 故宮の神(玄の避諱)武門に向かった。

35 テキスト検索は文字列検索ではない テキストの非１次元性にどう対処するか XML/XHTMLを使う？
ex) XHTMLにおけるRuby Annotation (2001) <p>私は<ruby xml:lang=“ja”> <rbc><rb>安</rb><rb>岡</rb><rb>孝</rb><rb>一</rb></rbc> <rtc><rt>やす</rt><rt>おか</rt><rt>こう</rt><rt>いち</rt></rtc> </ruby>です。</p>

36 p ruby rbc rb rtc rt <p>私は<ruby xml:lang=“ja”>
<rbc><rb>安</rb><rb>岡</rb><rb>孝</rb><rb>一</rb></rbc> <rtc><rt>やす</rt><rt>おか</rt><rt>こう</rt><rt>いち</rt></rtc> </ruby>です。</p> p ruby rbc rb rtc rt 安 岡 孝 一 やす おか こう いち 私は です。

37 木構造がテキストの流れと合致しない p ruby rbc rb rtc rt 安 岡 孝 一 やす おか こう いち 私は です。

38 テキスト検索は文字列検索ではない 検索アルゴリズムは？ テキストの非１次元性にどう対処するか
Directed Acyclic Graphでテキストを実装？ 検索アルゴリズムは？

39 DAGテキストの検索アルゴリズム Aho-Corasick風アルゴリズム Commentz-Walter風アルゴリズム
深さ優先で容易に実装可能 パスが縮退した際の打ち切りは容易 Commentz-Walter風アルゴリズム 深さ優先で実装可能 通ってきたノードを記憶する必要あり パスが縮退した際の打ち切り条件が複雑

40 DAGテキストの検索アルゴリズム 分岐と縮退によるパス数の爆発 縮退時の打ち切りは？ Aho-Corasick風アルゴリズム
初期状態に戻れば確実に打ち切れる Commentz-Walter風アルゴリズム 「その他」が起これば確実に打ち切れる

41 今後の課題 DAGテキスト検索アルゴリズムの高速化 パス数の爆発を抑えられるか？ 縮退時の打ち切り条件をtightにできるか？
もっと効率のよいアルゴリズムはないか？

42 テキスト検索は 文字列検索でも木検索でもない
京都大学人文科学研究所附属漢字情報研究センター 安岡孝一