研究目的

世界中のサーバには様々な情報や log が保管されている。 それら全体のデータサイズは TB 単位になると予想され、文字列処理をかけると膨大な時間がかかると予想される。
Cerium の例題にはファイルの読み込みと文字列処理を行う Word Count があり、先行研究では文字列処理の並列化によってプログラム全体の処理速度は向上している。
ファイルの読み込みを含むプログラムは読み込みがオーバーヘッドとなり並列度が下がる。
ファイルの読み込みから文字列処理までのオーバーヘッドが軽減されると、読み込みから文字列処理までの処理速度は向上する。
また、読み込むファイルによっては 数GB 単位の大きなファイルになる可能性もあるので、ファイル読み込みのオーバーヘッドは無視できない。
本研究ではファイルの読み込みまで含む文字列処理を考慮した並列処理を実装し、プログラム全体の処理速度を軽減する。

実装している正規表現エンジンの全体の要約

• 与えられた正規表現から正規表現木(Parser)を生成する。
• Parser に状態を割り振り、NFA を構成する。
• 構成した NFA を DFA に変換する。(Subset Construction)
• DFA に変換後、読み込んだファイルと照らし合わせてファイル内の文字列が正規表現にマッチするかどうか実行する。

正規表現にマッチさせる方法

• DFA変換後、状態遷移を C のコードで生成してコンパイル。その実行ファイルでファイルを読み込ませてマッチング。
• DFA変換後、状態遷移をオンデマンドに呼び実行し、状態遷移と読み込んだファイルがマッチするかどうかチェック。