博 士 （ 情 報 科 学 ） 金 田 悠 作 学 位 論 文 題 名
Efficient Regular Expression IVIatching Algorithms and Their Implementation on Reconfigurable Hardware
（効率良い正規表現照合アルゴリズムとその再構成可能ハードウェア上の実装）
学 位 論 文 内 容 の 要 旨
パ タ ー ン 照 合 間 題(pattem matching problem)と は ， あ る パタ ー ンPと ある テ キ ス ト 丁 が与 え ら れ た と き ．Pの ァ 中 の 出 現位 置 を す べ て出 カ す る 問 題で あ る ， 理 論計 算 機 科 学 分 野で は ， こ れ まで に文 字列 照合や ，正規 表現照 合， 木パタ ーン照 合等， さまざ ま顔 パター ン照合 問題が 研究 されている，
近 年 の セ ン サ ー 技 術 と ネ ッ ト ワ ー ク 技術 の 性 能 向 上に 伴 う 大 規 模教 デ ー タ ス ト リー ム の 増 加 によ り ． こ れら の デ ー タ か らの 効 率 的 顔 情報検 索と情 報発見 が重 要にな ってき た．本 研究で は， とくに ， 高 速 放 大規 模 デ ー タ ス トリ ー ム に 対 し，大 量かつ 複雑を パタ ーンを 照合す る問題 ，す教 わち ，大規 模 パ タ ー ン照 合 間 題(large‑scale pattem matching problem)に ついて 考察す る．大 規模 パター ン照合 は ， 大 規模 デ ー タ ス ト リー ム 処 理 の 基盤技 術であ り，理 論的 観点か らだけ でをく ，実用 的観 点から も 重要 であ る．
1992年 にWuとManber， お よ び ，Baeza‑YatesとGonnetが 提 案 し たShift‑And手 法 は ， 入 カ と して 与え られた パター ンを受 理す る非決 定性有 限オー トマト ン(nondeterministic finite automaton， NFA)の 状 態 集 合 をピ ッ ト 列 で 表現 し ， 論 理 演算 と ， シ フ ト演 算 ， 表 引 き 計算 の 計 算機ワ ード内 の並 列 性 を 利用 す る こ と で ，文 字 列 に 対 するパ ターン 照合問 題を 効率良 く解く 手法で ある． この ようを 計 算機 ワー ド内の 並列性 を用い たア ルゴリ ズムは ，ビッ ト並列 アル ゴリズ ム(bit‑parallel algorithm)と 呼ば れ， 文字列 処理分 野を中 心に 広く研 究され ている ． Shift‑And手法は ，正 規表現 照合問 題(regular expression matching problem)に拡 張 できる ，ここ で，正 規表 現とは ，文字 列パタ ーンの 集合 を表現 し ， 文 字と ， 連 結，和 ，繰 り返し から再 帰的に 定義 される ．一方 で，正 規表現 の場 合，NFAの空 遷移閉 包計 算の ために 大規模 を遷移 表を 用いる ため， 計算領 域が大 きい ．
本 研 究で は ．2001年 にNavarroとRaffinotが 提案 し た 拡 張Shift・And手 法の 考 え に 基 づ き， よ り 複 雑 な パタ ー ン の ク ラ スに 対 し て ， 算術 演 算 を 用 いる 効 率 良 い ビッ ト 並 列 パ タ ーン照 合ア ルゴリ ズ ム を 設 計す る ． ま た ， ビッ ト 並 列 ア ルゴ リ ズ ム は 計算 機 ワ ー ド に対 す る 論 理 演 算と算 術演 算のみ か ら 構 成 され る た め ， 条 件分 岐 や 主 記 憶領域 の間接 参照を 多用 するア ルゴリ ズムと 比較し て， 回路実 装 に 適 し てい る と 考 え ら れる ． そ こ で ，本研 究では ，ピッ ト並 列アル ゴリズ ムの再 構成可 能ハ ードウ ェ ア(reconfigurable hardware)上 の実 装につ いても 考察す る．
初 め に ， 第2章 で 基 本 的 を 概 念 と 定 義 を 準 備 し た 後 で ， 第3章 で は ， ネ ッ ト ワ ー ク 表現 と 正 規 表 現 の クラ ス に 対 す る パタ ー ン 照 合 問題 つ い て 考 察す る ． こ こ で， ネ ッ ト ワ ← ク表現 とは ，文字 列 と ， 連 結、 和 か ら 定 義 され る 正 規 表 現の部 分クラ スであ る． 本章で は，算 術演算 を用い たビ ット並 列 演 算scatterとgatherを 提 案 し， こ れ ら の 演算 を 拡 張Shift‑And手 法 で 用い ら れ る ピ ット 並 列 演 算 propagateと 組 み 合 わ せ る こ と で ， ネッ ト ワ ー ク 表現 照 合 間 題 を〇(ndm/w)時 間 と〇(dm/w)領 域 で 解 く ビ ッ ト 並 列 ア ル ゴ リ ズ ム を 与 え る ． こ こ で っmとnは パ タ ーン 長 と テ キ スト 長 で あ り ，dは パ タ ー ン に対 す る 構 文 木 の深 さ ，wは 計算 機 ワ ー ド 長で あ る ， また， ネット ワーク 表現に 対す るビッ ト
−705―
並 列 ア ル ゴ リズ ム とmonotone routing技 法を 組 み 合 わ せる こ と で ， 一 般の 正 規 表 現 のク ラ ス に対 す る パ タ ー ン 照 合 問 題 を 〇(ndmlog(m)/w)時 間と 〇(dm log(m)/w)領 域 で 解 く ピッ ト 並 列 ア ル ゴリ ズ ム を 与 え る ． こ こ で ，mとnは パ タ ー ン 長 と テ キ ス ト 長 で あ り ，dは パ タ ー ンに 対 す る 構 文木 の 深 さ ，wは 計 算機 ワ ー ド 長 であ る ． ま た ，ワ ー ド 上 の ピ ット 逆 転 を 定 数時 間 で実行 可能を ハード ウェ ア 上 で ， 上 記 の 計 算 量 が 〇(ndm/w)時 間 と 〇(dm/w)領 域 に 改 善 で き る こ と を 示 す ． 次 に ， 第4章 で は ，無 順 序 木 の クラ ス に 対 す るパ タ ー ン 照 合問 題 を 考 察 す る． 木 パ タ ー ン照 合 間 題 と は ， あ る パ タ ー ン 木Pと あ る テ キ ス ト 木 ア が 与 え ら れ た と き ，Pの 丁 中 の す べ て の 出 現 位 置 を 出 カ す る 問 題 で あ る ． こ こ で ，Pが 丁 中 の あ る 節 点vで 出 現 す る と は ， あ るPの 節 点 か ら 丁 の 節 点 へ の 写 像 が 存 在 し ，Pの す べ て の 節 点 が 丁 の 節 点 に 写 像 さ れ 、 か つPの 根 がvに 写 像 さ れ る こ と を い う ． 本 章 で は ， と く に ，Pの 節 点 か ら 丁 の 節 点 へ の 写 像 と し て 多 対 一写 像 を 許 し た木 パ タ ー ン 照 合 間題 で あ る ， 無順 序木 に対す る擬似 木パタ ーン 照合問 題(unordered pseudo‑tree matching problem)， およ び ， 無 順 序 木に 対 す る 木 同相 写 像 問題(unordered tree homeomorphism problem)を考 え る ． こ れ らの 問 題 は ，XPathの検 索 問 題 と 深 く関 連 す る ， 一方 で ． そ の実用 面で の重要 性にも かか わ ら ず ， ． 理論 計 算 機 科 学分 野 に お け る 従来 の 理 論的解 析は， 一対 一写像 に関す るもの がほと んど で あ っ た ． し たが っ て ， こ のよ う 教 多 対 一 写像 を 許 した木 パター ン照 合問題 を考察 するこ とは． 実用 的 観 点 と 理 論 的観 点 の 両 方 から 非 常 に 重 要 であ る ． 本 章 では ， は じ め に， 無 順 序 木 に対 す る パ ター ン 照 合 問 題 をO(nm)時 間 と 〇(hm)領 域 で 解 く ア ル ゴ リ ズ ム を 与 え る ． 次 に ， 算 術演 算 を 用 い た ビッ ト 並 列 演 算tree aggregationを 与 え ， この 演 算 を 上 述の ア ル ゴ リ ズ ム， お よ び ，Myersのモ ジ ュ ー ル 分 解 技 法 と 組 み 合 わ せる こ と で ， 無 順序 木 に 対 す るパ タ ー ン 照 合問 題 を 〇(nm log(w)/w)時 間 と O(hm/w十mlog(w)/w)領 域 で 解 く ビ ッ ト 並 列 ア ル ゴ リ ズ ム を 与 え る ． こ こ で ，mとnは パ タ ー ン 木 と テ キ ス ト 木 の サ イ ズ で あ り ， 轟 は テ キ ス ト 木 の 深 さ ．wは 計 算 機 ワ ← ド 長 で あ る ． 第5章 で は ， 正 規 表 現 の 部 分 ク ラ ス に 対 す る ビ ッ ト 並 列 ア ル ゴ リ ズ ム に 基づ ぃ た パ タ ーン 照 合 ハ ードウ ェア の実装 につい て考察 する ，本章 では， とくに ，FI）GA (field programmable gate array)と 呼 ぱ れ る 再 構 成 可 能 ハ ード ウ ェ ア を 用 いる ． FPGAを 用 い たパ タ ー ン 照 合ハ ー ド ウ ェ アは ，2001年 にSidhuとPrasannaがThompsonのNFAに 基 づ ぃ た 設 計 を 与 え て 以 来 ， 主 に 回 路 設 計 分 野 で 研 究 さ れ て き た ．一 方 で ， そ の多 く は パ タ ー ンを 回 路 構成時 に静的 に設 定する 手法で あり． パター ンを 回 路 構 成 後 に 動 的 に 設 定 でき る 手 法 は ほ とん ど 教 い ．2006年 にBakerら は ， 決 定 性有 限 オ ー ト マ トン と マ イ ク ロ コン ト ロ ー ラ に基 づ ぃ た 正 規 表現 照 合 ハ ー ドウ ェ ア を 提 案し た ， こ の 手法 は ， パ ター ン を 動 的に 設定 できる ．一方 で，そ の照合 性能 はテキ ストの 内容に 依存 する． そこで ，本章 では， ビッ ト 並 列 ア ル ゴ リズ ム に 基 づ ぃた パ タ ー ン 照 合ハ ー ド ウ ェ アの 基 本 設 計 を与 え る ． こ の手 法 は ， パタ ー ン を 動 的 に 設定 で き る だ けで 教 く ， 最 悪 時照 合 性 能の理 論的保 証を 与えて いる． また， ビット 並列 ア ル ゴ リ ズ ム を基 本 設 計 に 適用 す る こ と で ，さ ま ざ ま教パ ターン 照合 問題に 拡張可 能であ る．ま た， 拡 張 文 字 列 に 対す る ビ ッ ト 並列 ア ル ゴ リ ズ ムで あ る 拡 張Shift‑And手 法， お よ び ， 第3章 で 与 え たネッ ト ワ ー ク 表 現に 対 す る ピ ット 並 列 ア ル ゴ リズ ム に 基 づ ぃた パ タ ー ン 照合 ハ ー ド ウ ェア の 評 価 実験 の 結 果 を 示 す ． 提 案 手 法 は，2004年にBakerら が 提 案 した 文 字 列 に 対す る パ タ ー ン照 合 ハ ー ド ウ ェア と ，2006年 にYangら が 提 案 し た 文 字 列 に 対 す る パ タ ー ン 照 合 ハ ー ド ウ ェ ア ，2006年 にBakerら が 提 案 し た 正 規 表 現 に 対 す る パ タ ー ン 照 合 ハ ー ド ウェ ア と 同 等 のパ タ ー ン 照 合性 能 を 達 成 した ． 最後に ，第6章で 本論文 の結諭 と今後 の課 題を述 べる．
‑ 706―
学位論文審査の要旨 主査 副査
副査 副査
教授 教授 教授 准教授
有村 湊 宮永 喜田
学 位 論 文 題 名
博紀 真一 喜一 拓也
Efficient Regular Expression IN/Iatching Algorithms and Their 工 mplementation on Reconfigurable Hardware
（効率良い 正規表現照合アルゴ 1J ズムとその再構成可能ハードウェア上の実装）
本論 文では 、理論 情報科学における重要教問題のーつである正規表現照合アルゴリズムの開発 と、並列ハードウェアを用いたその高速な実装法について研究している。正規表現照合間題は、長 さmの 正規表 現（パ ターン)Pと長さ れの長 い文字列 （テキ スト)Tが 与えら れたとき、Pの丁中の 出現位置をすべて見っける問題であり、古典的かつ重要を計算問題として、古くから研究されてき た。 一方2000年 代に入 って、大規模ストリーム処理のための並列ハードウェア上での高速実装が 注目され、盛んに研究が行われている。
理論 的観点 からは 、正規表現パターン照合問題において、素朴な〇(mn)時間アルゴリズムの高 速 化が1970年代以 来の未 解決問 題であ った。 これに 対して 、1992年にMyersは、パ ターン を長 さ々 の断片 に分割 して計算 する方式を用いて、初めて〇(mn/k)時間でこの問題を解くアルゴリズ ムを与え、〇(mn)時間の壁を破った。しかし、この方式は使用領域が大きく、実装が難しい。これ に 対 して 、2001年 にNavarroとRaffinotは、 先 行 す るWuとManber（1992)お よびBaeza‑Yates とGonnet（1992)らの 文字列 照合に 関する 結果を 拡張し、ビット並列手法という技法を用いて、
ビッ ト幅がwのとき に、拡 張文字列 パター ンと呼 ばれる直線状の正規表現の部分クラスに対して
〇(mn/w)時間の照 合アル ゴリズムを与えた。この方式は、パターンをビットマスクにコンパイル し、 低レベ ルのブ ール演算 と算術 演算で 照合を 実行するため、実装上の効率が良く、FPGAやGPU 教どのハードウェアへの高速実装に適している。 一方で、分岐や繰り返しを含むよう教一般的を正 規 表 現 へ の 拡 張 は 難 し く 、 大 規 模 ス ト リ ー ム 処 理 等 へ の 応 用 に 限 界 が あ っ た 。 そこで本論文では、分岐を含むようを一般的改正規表現を扱えるようにビット並列手法を一般化 し、 さらに この手 法に基づ ぃてFPGAと呼ぱ れる並 列ハード ウェア 上の効 率よい実装方式を確立 することを目的として研究を行っている。
第2章 では、 正規表 現照合 問題を 導入し ている。 第3章で は、ネ ットワ ーク表現と呼ぱれる分 岐をもっが、繰り返しを含ま顔い正規表現の部分クラスを考察し、構文木の深さがdであるネット ワー ク表現 の照合 問題を〇(ndm/w)時間 と〇(dm/w)領域で解く効率よいアルゴリズムを与えてい る。これは深さの小さをネットワーク表現に対しては、現在、最も良い計算量の結果である。さら に、これを一般の正規表現のクラスに拡張し、〇(ndm log(m)/w)時間と〇(dm log(m)/w)領域のア ルゴリズムを与えている。
‑ 707―
次 に 、 第4章 で は 、 上 記 の 技 法 を 木 パ タ ー ン 照 合 間 題 に 適 用 し 、XMLデ ー タ 照 合 の 形 式 的モ デル で ある 多対 一写 像 を許 した無順序木パターン照 合問題を考察している。この 問題に対 して 、新 しいビット並列手法 を用いて、テキスト木の深さ 轟に対して、〇(nm log(w)/w)時間と
〇(hm/w十mlog(w)/w)領域で解 くアルゴリズムを与えてい る。また、枝の伸長を許した 問題の効 率 良 い 解 法 も 与 え 、 従 来 の ア ル ゴ リ ズ ム の 計 算 量 を 大 き く 改 善 し て い る 。 第5章 では 、第3章 の結 果 に基 づぃた大規模正規表現照 合システムのハードウェア実 装につい て議論する。初めに 、提案の拡張されたビット並 列アルゴリズムに基づぃて 、FPGA上での照合シ ステムのアーキテク チャを与え、次に拡張文字列パターンとネットワーク表現の両方に対して、具 体的なハードウェア アルゴリズムの高速実装法を与えている。評価実験では、従来手法に比べて、
提案手法は動的再構 成性と、パターンの表現力、 最悪時評価の計算時間の3点で優位教ことが示さ れている。
本論文の成果は、 次のようにまとめられる：
1．理論情報科学に おける正規表現照合問題に 対して、ピット並列手法に基づくアルゴリズムの 系統的教設計に取り 組み、種々の問題に対して効率よい照合アルゴリズムを与えた。これにより、
正規表現および木パ ターン照合における新しい結 果を示した。
2．ハードウェア設 計において、再構成可能ハ ードウェアにおける新しい高速パターン照合アー キテクチャを提案し 、さらに照合アルゴリズムのFPGA上の実装を与え、性能 評価を行うことで、
提案のアーキテクチ ャの有効性を実証した。
これを要するに、 著者は、大規模パターン照合のための照合アルゴリズムとハードウェア設計の 両者について、新し い方法論を提案し、種々の問題に対して効率よい解法が構成可能であるという 新知見を得たもので あり、理論情報科学とデータ工学において貢献するところ大なるものがある。
よ っ て 著 者 は 、 北 海 道 大 学 博 士 （ 情 報 科 学） の学 位 を授 与さ れる 資 格あ るも のと 認め る 。
