DEIM Forum 2019 J3-4

正規表現を DGL としたモックデータベース自動生成システムの開発
李

馨†

成

凱††

† 九州産業大学情報科学部 〒 813–8503 福岡県福岡市東区松香台 2–3–1†† 九州産業大学理工学部情報科学科 〒 813–8503 福岡県福岡市東区松香台 2–3–1
E-mail: ††chengk@is.kyusan-u.ac.jp
あらましソフトウェアを開発する際，プロトタイプの開発やシステムの動作確認には，システムの特徴に合った大量のテストデータが必要である．そのデータを一から作るとなると，時間やコストがかかる．さらに個人情報などのデータを処理するシステムでは，個人情報をそのまま使用できない．そのため，リアルな疑似的データを作成する必要がある．既存の研究では，ソフトウェアテスト用のテストデータはシステムの機能や負荷をテストすることを目的として，データにリアル性が欠けている．また，決められた種類のデータしか生成できない問題や確率分布に従う乱数の生成ができない問題がある．本研究では，正規表現を DGL として，リアルで多様なテストデータを簡単に生成できるシステムを開発した．正規表現に従うデータ生成の効率性を高める手法を考察し，実験による性能評価を行った．
キーワード 正規表現，モックデータベース，テストデータ，DGL (Data Generation Language)，自動生成

1 はじめにソフトウェア開発においてシステムの動作確認や性能評価を行うために，システムの特徴に合った大量のテストデータが必要である．そのデータを一から作るとなると，時間やコストがかかり，さらに個人情報などを扱うシステムでは，実データをそのまま利用できないため，疑似的データを自動的に生成するニーズが高まっている．

図 1 正規表現による疑似的データの定義と生成

データベースを中心とするシステムの性能を評価するためにシステムの負荷特徴に合わせてダミーデータを生成し，データベース化するようになっている．例えば，トランザクション処
理性能評議会 TPC が策定したベンチマーク [35] [36] [37] がよく知られている．また，ソフトウェアテストの一環として，テストデータ生成が必要であり，それに関する研究が存在している [1] [5] [7] [8] [9] [10] [11] [13] [18]．しかし，これらの研究は一定の目的に合わせて生成可能なデータの種類が限られており，汎用性やリアル性に欠けている．例えば，氏名，商品名，電話番号等がランダムな文字列になってしまい，疑似的データとして使えない．近年，氏名や住所等の疑似データを生成するツー
ル [30] [31] [32], [33] も複数存在しているが，用意された種類以外のデータが生成できない問題点がある．例えば，電話番号，
学籍番号などパターンを持つデータには対応していない．
テストデータはダミーデータと疑似データに大別される．ダ
ミーデータとは統計的に規則があるものの、人間にとって意味のないものでもよいデータであり，TPC 等性能テスト・負荷テ
ストを目的として、大量のテストデータが必要なときに使われる．疑似データとは実データに近似する架空データ（Realistic

Fake Data）．データベースへの初期データ投入，プロトタイ
プ開発における画面モックアップ等に使われる．また，テスト
データ自動生成については，専用データジェネレータと汎用
データジェネレータに開けられる．専用データジェネレータは

特定のシステムをテストするために開発されたデータ生成プロ
グラム。例えば、TPC の dbgen ツール．一方，汎用データジェ
ネレータはデータ生成言語 DGL (Data Generation Language)
でどのようなデータが必要なのかを定義し、定義に従い、テス
トデータを自動的に生成する汎用システムである．
本研究では我々は正規表現を DGL として，パターンを持つ
データを生成可能にする．また，通常の正規表現の \d（数字）,\w（英数文字）のような文字クラスに加え，苗字，男子名，女子名，
県名のようなユーザ定義クラスを導入することによって多様で疑似的データを生成することができるようにする．例えば，正規表現「16JK\d{3}, %1(%2 | %3), 0[7 − 9]0 − \d{4} − \d{4}」で学籍番号，氏名，電話番号を定義する．学籍番号と電話番号
は通常の正規表現であり，氏名は苗字（%1）に男子名（%2）
または女子名（%3）が続くと定義される．ここで%1〜%3 は
ユーザ定義クラスであり，詳しくは後で説明する．図 1 ではこの正規表現で定義されたテストデータ例を示している．
本稿では，我々は正規表現を拡張し DGL として利用することを提案する．提案手法を効率的に実現するために文字列生成，生成結果及びデータベースキャッシングの技術を開発し，実験による評価を行う．

2 正規表現によるモックデータベース定義
2. 1 モックデータベース
本研究では，実際のデータベースに近い疑似データベースを
モックデータベース（mock database）と呼ぶ．モックデータ
ベースは以下の特徴をもつものとする．
（ 1 ） リアリティー・現実味．氏名，住所等は架空のものであるが意味のないランダム文字列ではなく，実データに近い現
実味が感じられる．
図 2 拡張非決定性有限オートマトン（GNFA）（ 2 ） 等差数列．連番や等差数列のような規則をもつデータが生成できる．
（ 3 ） 確率分布．確率分布に従う乱数を生成できる．

字列は遷移（エッジ）に付記された正規表現に対応するもので（ 4 ） データ型サポート．RDBMS が提供する主なデータ型，ある．GNFA は正規表現に簡単に変換できる．その変換は中整数 Int, 小数 Double, 日時 DateTime, 文字列 String をサポー間的な遷移を正規表現に変換していき，最終的に開始状態から受容状態へというひとつの遷移になるようにするものである

トする．

（図 2）．同様に GNFA の各遷移に付記された正規表現を一文

2. 2 正 規 表 現

字ずつに分解するまで中間状態を追加していけば NFA に変換

正規表現（regular expression）とは，ある記号集合（アルファベット）上で定義される文字列のパターンを定義する言語である．文字列のパターンマッチングによく使われる．アルできる．

2. 3 DGL としての正規表現

ファベット A 上の正規表現は一部の特殊記号を除き，ほかの文

正規表現はパターンマッチングのために設計されているもの

字が自身とマッチする．表 1 は正規表現によく使われる特殊記が多い．正規表現を DGL としては次のような拡張や制限を導号であり，表 2 は正規表現によるパターン定義の例である．

入する必要がある．
（１）繰り返し回数の上限．
「*」「+」「{m,}」のような上限なし繰り返しは DGL ではシステム独自の上限を

表 1 正規表現の特殊記号
記号

説明

記号

説明

.

任意 1 文字

∗0 回以上繰り返し[][ ] 中任意 1 文字+

1 回以上繰り返し[^][ ] 外任意 1 文字?

0 回か 1 回出現\d

数字 1 文字{n}n 回繰り返し\w

英数 1 文字{m, n} m 回以上 n 回以下繰り返し設ける必要がある．
（２）文字クラス \d, \w などだけでは不十分であり，さまざまな文字クラスを使えるように拡張する必要がある．
（３）特定の確率分布に従う乱数や，数列のような一定の規則をもつデータを発生することが望まれる．
（４）パターン
マッチングでは文字列の一部にパターンにマッチすればよいた
め，行頭「ˆ
」，行末「$」を表す位置指定子が必要であったが，DGL としてはパターンに従って文字列を生成すればよく，行
表 2 正規表現によるパターン定義
項目名

正規表現

携帯番号

0[7-9]0-\d{4}-\d{4} 090-6043-4759

学籍番号

1[5-6]JK0\d{2}パスワード [0-9a-zA-Z]{5, 6}

マッチする文字列例

16JK066, 15JK023

頭，行末の位置指定の必要がなくなる．したがって，DGL として「ˆ」と「$」が特殊記号とせず，後で紹介するように本研究では，「$」が関数の出現を表す記号とする．この節では，正規表現を DGL として必要な拡張について述べる．

uHiNG,4w7Skv

正規表現のマッチングを行う方法として，非決定性オートマ
トン（NFA）と決定性オートマトン（DFA）を用いる方法がある．逐次計算による正規表現マッチングでは単純にマッチするかどうかを判断する場合には，多くの場合 DFA を用いる方が

図 3 連番や確率分布に従う乱数の生成

効率よく計算できる．しかし，DFA の状態数が同じ正規表現に対応する NFA の状態数の指数倍になることがあり，その場
合には NFA を用いる方が効率よく計算できる．
また，NFA，DFA では入力記号一文字に対して一つの遷移を行うことになっている．この制限を緩和した計算機モデルが
拡張非決定性有限オートマトン（GNFA）である [38]．GNFA
では，各状態遷移が任意の正規表現に対応する NFA である．

GNFA は入力からまとめて複数の文字を読み込むが，その文

図 4 日付型の定義と生成

2. 3. 1 ユーザ定義クラス
ユーザ定義クラスとは，データベースに登録されたソースをもとに定義されるクラスのことである．例えば，苗字，男子名，女子名，役職名，都道府県名，市町村名など，事前にデー
タベースに登録しておき，必要な時，そこからデータをランダムに抽出する．正規表現の拡張として，ユーザ定義クラスをパ
ラメータ%1〜%9 で指定する．パラメータに対応するユーザ定義クラスが指定されると，そのユーザ定義クラスからデータがランダムに抽出される．

2. 3. 2 Range 関数による数列・確率分布の生成
連番や等差数列，確率分布に従う乱数を発生するため，Range
関数を導入する．Range 関数が正規表現に$range(.)$もしくは関数名を省略して (.) と埋め込み，パラメータにより連番や等差数列，確率分布に従う乱数が発生される．各パラメータは次のように定義する．

〔出力例〕..........................................................

range(Start, Stop, Type=0, Step=1)=(Start, Stop, Type=0, Step=1)
Start：

区間開始

Stop：
Step：

区間終了
等差数列の公差．デフォルトは 1Type = 0 (default),

等差数列

1

Uniform2

Normal3

Poisson4

Exponential..........................................................
図 5 正規表現を DGL としてデータ生成

3. 1 正規表現に従うランダム文字列の生成
正規表現のマッチングで与えられた正規表現 R と文字列 Qに対して，Q が R で定義された言語の一部であるか判断する

Type=0 のとき, 等差数列が発生される．Step=1 のとき，連ことである．これと逆に，正規表現に従うデータ生成では，正番となる．Type=1 のとき，区間 [Strart, Stop] 上で一様分布

規表現 Q 及び生成件数 N が与えられたとき，R で定義されたの乱数が発生される．Type=2 のとき，µ=(Start+Stop)/2,

言語からランダムに要素を抽出することになる．これを実現2

δ = 1 の 正 規 分 布 の 乱 数 が 発 生 さ れ る ．Type=3 の と き ，するために，我々は Random Walk アルゴリズムと Random

λ =(Start+Stop)/2 の ポ ア ソ ン 分 布 の 乱 数 が 発 生 さ れ る ．

Sampling アルゴリズムを提案する．

Type=4 のとき，区間 [Strart, Stop] 上で指数分布の乱数が発生される．

3. 1. 1 Random Walk アルゴリズム
正規表現マッチングに対応する有限オートマトン上（DFA,Start，Stop のフォーマットは出力のフォーマットを示してNFA）で開始状態から終了状態までランダムウォークを行い，いる．図 3 では，学籍番号が 001〜160 の 3 桁の連番（001

移動ステップ（状態遷移）に伴い，記号を出力する．正規表現，002, · · · ），修得単位数が区間 [70,120] 上の一様分布（87，76

を NFA に変換する最もよく知られている方法は Thompson 法，110，· · · ），GPA が区間 [1.0, 4.0] 上の正規分布（2.3，3.1，· · · ）であり，その状態数が正規表現文字列の長さに等しい [4] [22]．

となるようなデータが定義する例を示している．

2. 3. 3 データ型の対応

状態の有限集合（S），入力文字の有限集合（Σ），遷移関数（δ：S × (Σ ∪ ϵ) → 2S ，Range 関数を使って様々なデータ型に対応するデータが発生

開始状態 s0 , 終了（受容）状態 A から構成される有限オートできる．整数（Int），小数（Double）の場合は Range 関数がマトン N F A = {S, Σ, δ, s0 , A} とする．状態 s ∈ S から可能

そのまま使える．日付，日時は正規表現によるパターンで対応な遷移を Τ (s) とする．図 6 は NFA 上の Random Walk によできる (図 4)．

る文字列生成アルゴリズムを示している．開始状態から始め，終了状態まで次の処理を繰り返す．状態 s において次の状態へ

3 モックデータベースの生成
上記の拡張を含む正規表現で必要なデータのパターンを定義できる．モックデータベースはこの定義に従い，データを生成する．正規表現 %1(%2 | %3), 0[789]0-\d{4}-\d{4} にパラ
メータ%1（苗字），%2（男子名），%3（女子名）が与えられたとき，図 5（下部）のようなデータが生成される．

遷移するとき，ランラムに選ばれた遷移 δ(s, a) = s を適用し，入力文字 a を集めるとともに，状態 s へと遷移する．この処理は終了状態に到着まで続ける．終了状態に到着すると，集められた文字を一つの文字列として出力される．

3. 1. 2 Random Sampling アルゴリズム
正規表現 R に対して字句解析を行い文字セット (\d, \w, [a-z]等) とその繰り返し (∗, +, ?, {n}, {n, }, {n, m}) を抽出し，文字セットをランダムサンプリングし，得られたデータを出力する．

の正規表現として扱う．逆に以下のいずれかの Range 函数と

図 7 は Random Sampling による文字列生成アルゴリズムを認識できたら，第３の引数で Type を判断し，その結果に応じてデータ生成する．

示している．正規表現解析により，文字セット・繰り返しの系
列を抽出する．系列の要素は < A, n, m > のように構成される．

•$range(Start, Stop [, Type, Step])$

ここでは，A は文字クラス，n は繰り返し最小回数，m は繰り•$(Start, Stop [, Type, Step])$

返し最大回数である．m は無限大のとき，設定された最大値 M

コンピュータで確率分布に従う擬似乱数を生成するために，様々とする．以下のケースは文字クラスの特例として扱う．(1) パな技術が開発された [24]．その多くは一様乱数に基づき，特定

ラメータ，通常文字は１文字だけの文字クラスとする．(2) ORの確率分布の乱数を導出する手法を取っている．一様分布の乱(|) クラスは OR で繋がる文字列を要素する集合とする．

数列を作る方法として，線形合同法，M 系列法，最もよく使わ
アルゴリズム RWれるルセンヌ・ツイスター (Mersenne Twister) 法 [12] がある．

 (1) 正規分布乱数の作り方 平均 µ, 標準偏差 σ の正規分布乱数を得るためには Box–Muller 法がよく用いられる．α，βを入力：[0, 1] の一様乱数としたとき，次の二つの数値，

1. R: 正規表現√

2. N : 必要なデータ件数
出力：
正規表現 R にマッチする N 件のランダムデータ√− ln α2 cos 2πβ,は平均値 0, 標準偏差 1 の正規分布に即した乱数になる．上記

処理：の二つの数値に相関はないため，二つの正規分布乱数が得られ

1 R に対応する N F A = {S, Σ, δ, s0 , A} を構築する− ln α2 sin 2πβ,2 FOR (i = 0; i < N ; i + +) DO:

る．また，上記の数値に σ をかけた後，µ を足せば，任意の正3s = s0 ; str = nill

規分布乱数が出来上がる．

4

WHILE (s! = A) DO:

5

ランダムに選ばれた状態 s′ = δ(s, a) へ遷移

6

a を str に加える

7

END WHILE8

str を出力する

9 END FOR(2) 指数乱数の作り方
区間 [0, 1) 上の一様乱数 u から逆関数法を用いて指数分布の乱数列を作ることができる．指数分布の分布函数 f (x) = αe−αxより∫ y F (y) =図 6 NFA 上の Random Walk による文字列生成∫ yf (x)dx =0αe−∝ x dx = 1 − e−αy0となる．u = F (y) = 1 − e−αy なる等式を解いて y を求めると，次のようになる．

3. 2 Range 関数の実現
正規表現を解析する際に，$二つで挟まれた部分を Range 函数であるかどうかを解析する．Range 函数でない場合は，通常

y ＝−1loge (1 − u)α

この等式で得られる乱数列を必要な乱数の範囲に変換するとよい．


アルゴリズム RS
入力：

1. R: 正規表現
2. N : 必要なデータ件数
出力：
正規表現 R にマッチする N 件のランダムデータ処理： (3) ポアソン分布乱数の作り方
ポアソン分布は離散型確率分布であり，その確率分布が以下のようになる．

P (X = k) = e−mmk, (k = 0, 1, 2, · · ·)k!

m の値が決まれば確率変数 X のとる値が 0, 1, 2, · · · である確率が決まってくる．区間 [0, 1] 上の一様乱数 u からポアソン分布

1 R を解析し文字セット・繰り返しの系列 U に分解する

乱数列を作ることができる．

2 FOR (i = 0; i < N ; i + +) DO:

3

str = nill

4

FOREACH (Ui =< A, n, m >∈ U ) DO:−m
Σx−1
k ＝ 0emk <mku < Σxk ＝ 0 e−m
=
k!
k!

5

[n, m] 中から乱数 t を発生するを満たす x を求めると，ポアソン分布乱数列を作ることがで

6

a = A の t 回ランダム抽出で得られた文字列

きる．

7

a を str に加える

8

END FOREACH

9

str を出力する

10 END FOR
図 7 Random Sampling による文字列生成

3. 3 ユーザ定義クラスの実現
これまでの処理で得られた文字列にパラメータ (%1〜%9) が含まれることがある．パラメータがユーザ定義クラスと対応しており，外部のリソースより獲得する必要がある．表 3 の左側

はパラメータを含む結果で，右側は外部リソースから苗字，名表 3 ユーザ定義クラスの実現 (パターン %1 (%2|%3))
中間結果 説

明

最終結果

%1 %2

苗字 男子名 西田 浩司%1 %2

苗字 男子名 水野 圭吾%1 %3

苗字 女子名 山本 彩

%1 %2

苗字 男子名 大澤 響

%1 %3

苗字 女子名 上田 安奈%1 %3

苗字 女子名 松岡 理恵

前のインスタンスを代入したものである．

RDBMS に格納された外部リソースから抽選した結果をそれ

図 8 キャッシュによる性能改善の評価結果

ぞれのパラメータと置き換えることによって実現している．

3. 4 データ生成の効率化
データ生成の効率化を図るために，キャッシング技術を使う

5 関連研究のが有効である．(1) サブオートマトン・部分正規表現キャッ佐々木ら [26] は企業における非公開データを用いた学術研究

シング，(2) DB キャッシングがデータ生成の効率化に期待できを可能にするために，非公開データの特徴量のみをデータ収集

る．(1) サブオートマトン・部分正規表現キャッシング正規表

企業から受取ることを想定して，特徴量の似た研究用データを現を解析（コンパイル）するコストを削減するため，一度コン

人工的に作成する方法を提案した．松崎ら [27] は正規表現マッ

パイルした内部形式をキャッシングした方が，時間的に効率がチングを並列化する手法について議論した．

よい．個々の正規表現はコンパイル済みの形式と結びつけておくことで，コンパイル処理のコストを節約できる．アルゴリズ

様々なテストデータを生成することを目的として，データ生
成言語 (DGL) を用いるアプローチがあった [2] [13] [14]．

ム RS では正規表現の内部表現，アルゴリズム RW で NFA の

N. Bruno ら [2] は様々な確率分布をもつデータを人工生成す内部表現をキャッシングすることができる．さらに，メモリにる手法を提案した．イテレータを中心にデータ生成言語 DGL

余裕があれば，正規表現と合わせて生成されたデータをキャッを定義した．主なイテレータは等差数列 Step, Constant，確

シュしておくと，さらに高速化が実現できる．(2) DB キャッシ

率分布 Uniform, UniformInt, Normal, Exponential, Zipfian,

ングユーザ定義文字クラスからサンプル抽出する操作にかかるPoisson，重複除去 dupFilter, dupFilterMem, dupFilterDB，コストは DB キャッシングによって抑えることが可能である．

また Top, Union, probUnion, tableApply, Duplicate 等があDBMS 標準のキャッシング技術が使えるが，キャッシュを利用る．また，RDBMS と連携する Query 関数と Persist 関数も提する際に，毎回同じ結果にならないようにキャッシュデータを案された．文字列以外のデータ作成に適性しているが，本研究シャフルする必要がある．

のように，疑似的文字列を生成することはできない．

4 実験評価6 終わりに二つのキャッシュによる効率化を評価するため，評価実験を

本稿では確率分布に従うランダムデータ，現実味のある擬似行った．評価対象は表 4 に示されている．正規表現の解析結果

データを生成できるモックデータベース生成システムを提案しキャッシュ（RegExp Cache）とデータベースキャッシュ（DBた．正規表現を DGL としてパターンを持つデータを定義でき，

Cache）が使用されるかどうかによって実行時間の変化を調

さらにユーザ定義文字クラスを導入することにより，様々擬似

べた．

テータの生成が可能になる．また，キャッシュによる性能改善を考察し，予備実験によって検証を行った．
表4 評価対象
評価対象

今後の課題としてデータベースの整合性制約への対応や，例

RegExp Cache DB Cache

示データによる正規表現の自動生成などが挙げられる．整合性

TT

有効

有効

FT

無効

無効

TF

有効

有効

付けを後処理として実現する必要がある．
，例示データによる

FF

無効

無効

正規表現の自動生成については，機械学習による有限オートマ

制約は正規表現の範囲では対応できないため，データ間の関連

トンの自動生成に関する研究を参考にすることができる [39]．
正規表現解析は PHP パッケージ ReverseRegex [29] を使用している．実行時間は 10 回繰り返した平均になる．実験結果
は図 8 で示されている．DB キャッシュが使われた場合は実行時間の短縮に効果が大きいことが分かった．

文

献[1] Adir , R. Levy , T. Salman, Dynamic test data generation
for data intensive applications, Proceedings of the 7th international Haifa Verification conference on Hardware andSoftware: verification and testing, December 06-08, 2011,

Haifa, Israel[2] N. Bruno and S. Chaudhuri. Flexible database generators.
In Proceedings of the 31st international conference on Verylarge data bases (VLDB), pages 1097-1107, 2005.
[3] T. S. Buda, T. Cerqueus , J. Murphy , M. Kristiansen,
VFDS: An Application to Generate Fast Sample Databases,
Proceedings of the 23rd ACM International Conference on
Conference on Information and Knowledge Management,
November 03-07, 2014, Shanghai, China[4] R. Cox, Regular Expression Matching Can Be Simple And
Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...),(January 2007) https://swtch.com/ rsc/regexp/regexp1.html[5] R.A. DeMillo, A.J. Oﬀutt. Constraint-based automatic test
data generation. IEEE Transactions on Software Engineering. 19: 640. September 1991
[6] M. Douglas McIlroy, Enumerating the strings of regular languages, Journal of Functional Programming 14 (2004), pp.
503-518[7] R. Ferguson, K. Bogdan. The Chaining Approach for Software Test Data Generation. ACM. (1996)[8] J. Edvardsson, A Survey on Automatic Test Data Generation. Proceedings of the Second Conference on Computer
Science and Engineering in Linkoping. October 1999.
[9] D. C. Ince, The automatic generation of test data, Comput.
J., 30, 63-69 (1987).
[10] Korel. A Dynamic Approach of Automated Test Data Generation. Conference on Software Maintenance. (1990)[11] B. Korel. Automated Software Test Data Generation. IEEE
Transactions on Software Engineering. 16: 870879. August
1990.
[12] M. Matsumoto and T. Nishimura, ”Mersenne Twister:A 623-Dimensionally Equidistributed Uniform PseudoRandom Number Generator,” ACM Transactions on Modeling and Computer Simulation, 8 (1998), 3-30
[13] P. M. Maurer, Generating test data with enhanced context
free grammars, IEEE Software, 7, (4),50-56 (1990).
[14] P. M. Maurer, The design and implementation of agrammar-based data generator. Softw: Pract. Exper., 22:
223-244 (1992). doi:10.1002/spe.4380220303[15] C. Olston, S. Chopra, and U. Srivastava. Generating example data for dataflow programs. In Proc. ACM International
Conference on Management of data(SIGMOD), pages 245256, 2009.
[16] K. Pan , X. Wu , T. Xie, Generating program inputs fordatabase application testing, Proceedings of the 2011 26th
IEEE/ACM International Conference on Automated Software Engineering, p.73-82, November 06-10, 2011[17] K. Pan, X. Wu, T. Xie, Automatic test generation for mutation testing on database applications, Proceedings of the 8thInternational Workshop on Automation of Software Test,
May 18-19, 2013, San Francisco, California[18] R. Pargas,M. Harrold, R. Peck. Test Data Generation using
Genetic Algorithms. Journal of Software Testing, Verification and Reliability. 9: 263282 (1999)[19] M. Rabin and Dana Scott, Finite automata and their decision problems, IBM Journal of Research and Development
3 (1959), pp. 114125.
[20] T. Rabl, M. Frank, H. M. Sergieh, and H. Kosch. A data
generator for cloud-scale benchmarking. In Proceedings of
the Second TPC technology conference on Performance
evaluation, measurement and characterization of complex
systems (TPCTC), pages 41-56, 2011.
[21] K. Taneja, Y. Zhang, and T. Xie. Moda: Automated test
generation for database applications via mock objects. In
Proc. IEEE/ACM International Conference on AutomatedSoftware Engineering (ASE 2010), short paper, 2010.
[22] K. Thompson, Regular expression search algorithm, Communications of the ACM 11(6) (June 1968), pp. 419422.

http://doi.acm.org/10.1145/363347.363387[23] X. Wu, Y. Wang, S. Guo, and Y. Zheng. Privacy preserving
database generation for database application testing. Fundam. Inf., 78(4):595-612, Dec. 2007.
[24] Jeﬀrey E.F. Friedl, 長尾 高弘 (翻訳)，詳説正規表現 第 3 版，
オライリージャパン，2008/4/26[25] 四辻 哲章，計算機シミュレーションのための確率分布乱数生成
法，プレアデス出版， 2010/6/1[26] 佐々木健太郎, 門田暁人, 松本健一, 大岩佐和子, 押野智樹, 非
公開データからの類似データ生成. 研究報告ソフトウェア工学(SE) 2015.7 (2015): 1-6[27] 松崎公紀, 江本健斗, 劉雨. 正規表現マッチングの並列化とそのHadoop での評価. 情報処理学会論文誌プログラミング (PRO),4(4), (2011):1-11[28] 増田優香, 篠原哲平, 望月久稔. flex における遷移関数と正規表現マッチングの高速化. 第 79 回全国大会講演論文集 2017.1(2017): 429-430.
[29] ReverseRegex：Use Regular Expressions to generate text
strings
https://github.com/icomefromthenet/ReverseRegex[30] 疑似個人情報データ生成サービス,
http://hogehoge.tk/personal/[31] テストデータ・ジェネレータ,
https://yamagata.int21h.jp/tool/testdata/[32] SmartData・テストデータ生成―roopidea,
http://roopidea.com/smartdata/index.php[33] テスト用ダミーデータの生成ツール,
https://webbibouroku.com/Blog/Article/test-data-generator[34] 李馨, 成凱, 正規表現に基づくテストデータ自動生成. http://www-db.is.kyusan-u.ac.jp/pbs/autodata/[35] TPC Benchmark D (Decision Support). Standard Specification 2.1, Transaction Processing Performance Council(TPC), February 1999.
[36] TPC–APP，TPC Transaction Processing Performance
Council. http://www.tpc.org/tpcw/default.asp[37] D. Menasce, TPC-W: A Benchmark for E-Commerce, IEEE
INTERNET COMPUTING，2002[38] M. Sipser. Introduction to the Theory of Computation (3rded.). Gengage Learning, 2013.
[39] M. J. Kearns, and U. Vazirani. An introduction to computational learning theory. MIT press, 1994.