Diptarama Hendrian（ディプタラマ ヘンリアン）
東北大学 大学院 情報科学研究科

辞書照合（dictionary matching）とは，辞書（dictionary）と呼ばれるパターンの集合とテキストが入力として与えられたときに，テキスト中にすべてのパターンの出現位置を求める問題である．辞書照合は文字列処理やデータマイニングにおいて重要な基盤技術である．例えば，いくつかのキーワードを辞書に登録しておき，そのキーワードを含んだSNSの投稿をリアルタイムに検知することにも利用できる．1975年にAho&Corasickがオートマトン（ACオートマトンと呼ぶ）を用いた辞書照合を効率的に行ったアルゴリズムを開発した．

しかしながら，通常の辞書照合アルゴリズム用いると新たなパターンを追加するときに，データ構造を新たに構築し直さなければならないため，パターンの数が多い場合はこの再構築に長い時間がかかってしまう．そこで，データ構造をゼロから再構築するのではなく，必要最小限の手間でデータ構造更新するアルゴリズムが必要となる．

キーワードの追加に対応したACオートマトンを更新するアルゴリズムは1985年にMayerに示された．それ以降，様々な工夫がなされてきたが，既存のものは，最悪時には辞書をゼロから再構築する手間と変わらなかったり，逆に最悪時の再構築時間を短縮する代償として照合時間が遅くなったりという欠点を持っていた．本研究は，Aho-Corasickオートマトンの構造と，有向無閉路グラフ(DAWG)の構造の類似点や特徴を巧妙に利用して融合させることで，照合時間を高速に保ったままで，更新時間を必要最小限に抑えることに成功しており，その実行時間の解析も行っている．

この度，野口研究奨励賞の受賞者にお選びいただき，誠にありがとうございます．このような賞を受賞できて，とても光栄に思って言います．情報処理学会東北支部の皆様をはじめ，すべての関係者には深く感謝申し上げます．また本論の共著者でもあり，指導した頂いた篠原歩先生および吉仲亮先生に深く御礼申し上げます．今後も，情報科学・情報処理分野のますますの発展のために，研究を進んでいきたいと思います．今後ともどうぞよろしくお願い申し上げます。ありがとうございました。