(57)【要約】【課題】データ変換に用いる処理の探索時間を低減することを目的とする。【解決手段】データ変換プログラムは、コンピュータに、第１データと、第１データの変換後データである第２データを取得し、処理ごとに定義された処理時間を示す属性に基づいて、第１データを第２データに変換する際に用いられる複数の処理の組み合わせを探索し、探索した複数の処理の組み合わせを表示する処理を実行させる。【選択図】図９
2019049815.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
第１データと、前記第１データの変換後データである第２データを取得し、
処理ごとに定義された処理時間を示す属性に基づいて、前記第１データを前記第２データに変換する際に用いられる複数の処理の組み合わせを探索し、
探索した前記複数の処理の組み合わせを表示する
処理を実行させるデータ変換プログラム。
【請求項２】
前記コンピュータに、
前記複数の処理の組み合わせに基づいて、変換対象データを変換する
処理を実行させることを特徴とする請求項１記載のデータ変換プログラム。
【請求項３】
前記コンピュータに、
複数の処理の組み合わせに含まれる処理を、実行処理順に探索する際に、処理時間が所定値より長いことを示す属性が定義されたいずれかの処理が、直前に探索した処理から第１回数前までの処理に含まれておらず、かつ、探索対象データに前記第２データが含まれていない場合、前記探索対象データに適用する処理の候補に前記いずれかの処理を用いる
処理を実行させることを特徴とする請求項１または２記載のデータ変換プログラム。
【請求項４】
前記コンピュータに、
複数の処理の組み合わせに含まれる処理を、実行処理順に探索する際に、処理時間が所定値より長いことを示す属性が定義されたいずれかの処理が、直前に探索した処理から第１回数前までの処理に第２回数以上含まれておらず、かつ、探索対象データに前記第２データが含まれていない場合、前記探索対象データに適用する処理の候補に前記いずれかの処理を用いる
処理を実行させることを特徴とする請求項１または２記載のデータ変換プログラム。
【請求項５】
前記コンピュータに、
複数の処理の組み合わせに含まれる処理を、実行処理順に探索する際に、処理時間が所定値より長いことを示す属性が定義されたいずれかの処理が、探索済みの全処理に含まれておらず、かつ、探索対象データに前記第２データが含まれていない場合、前記探索対象データに適用する処理の候補に前記いずれかの処理を用いる
処理を実行させることを特徴とする請求項１または２記載のデータ変換プログラム。
【請求項６】
前記コンピュータに、
処理の種別毎に処理時間を計測し、前記処理時間に基づいて、前記属性を設定する
処理を実行させることを特徴とする請求項１乃至５記載のデータ変換プログラム。
【請求項７】
前記コンピュータに、
処理の種別毎に処理時間を計測し、処理の種別毎の処理時間の平均値を算出し、前記処理の種別と前記処理時間の平均値とを表示し、ユーザからの入力に基づいて、前記属性を設定する
処理を実行させることを特徴とする請求項１乃至５記載のデータ変換プログラム。
【請求項８】
コンピュータが、
第１データと、前記第１データの変換後データである第２データを取得し、
処理ごとに定義された処理時間を示す属性に基づいて、前記第１データを前記第２データに変換する際に用いられる複数の処理の組み合わせを探索し、
探索した前記複数の処理の組み合わせを表示する
処理を実行することを特徴とするデータ変換方法。
【請求項９】
第１データと、前記第１データの変換後データである第２データを取得する取得部と、
処理ごとに定義された処理時間を示す属性に基づいて、前記第１データを前記第２データに変換する際に用いられる複数の処理の組み合わせを探索する探索部と、
探索した前記複数の処理の組み合わせを表示する表示制御部と、
を備えることを特徴とするデータ変換装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ変換プログラム、データ変換方法、およびデータ変換装置に関する。
【背景技術】
【０００２】
企業が販売戦略を検討する際に、購買履歴等のデータ分析が行われる。例えば、支社や支部を多く持つ企業は、地域や顧客毎に、どのような商品が売れているのか分析し、販売戦略を練る。しかし、企業の営業拠点や購買部門によって、分析に用いるための購買履歴等のデータのファイルフォーマットや標記方法が異なる場合があるため、ファイルフォーマットとデータ表記の統一が行われる。また、気象データのような公開データと組み合わせて販売推移の分析を行う場合、自社のデータと公開データとの、ファイルフォーマットとデータ表記の統一が行われる。
【０００３】
関連する技術として、データ変換操作の空間を効率的に検索して、望ましい変換を実行するプログラムを生成するシステムが開示されている（例えば、非特許文献１を参照）。
【０００４】
また、関連する技術として、変換を発見するシステムであって、複数行、非機能、および間接変換を発見するためにＷｅｂテーブルを活用するシステムが開示されている（例えば、非特許文献２を参照）。
【０００５】
また、関連する技術として、グラフ上の２頂点間の最短経路を求めるアルゴリズムであるＤｉｊｋｓｔｒａ法が用いられている（例えば、非特許文献３を参照）。
【０００６】
また、関連する技術として、各頂点からゴールまでの距離の推定値を返すヒューリスティック関数を用いたグラフ探索アルゴリズムであるＡ＊法が用いられている（例えば、非特許文献４を参照）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許出願公開第２０１６／０２９９７４４号明細書
【特許文献２】米国特許出願公開第２０１７／００７５６６１号明細書
【特許文献３】米国特許出願公開第２０１７／０１６１０２７号明細書
【非特許文献】
【０００８】
【非特許文献１】Zhongjun Jin et. al., "Foofah: Transforming Data By Example," SIGMOD’17.
【非特許文献２】Z. Abedjan, et. al. "DataXFormer: A Robust Transformation Discovery System." ICDE 2016.
【非特許文献３】Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs". Numerische Mathematik. 1: 269-271.
【非特許文献４】Hart, P. E.; Nilsson, N. J.; Raphael, B. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" (1968),IEEE Transactions on Systems Science and Cybernetics SSC4. 4 (2): 100-107.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
変換前データに対して複数の処理を適用することにより変換後データが生成される場合、複数の処理を実行した際の処理の探索時間をより短くすることが好ましい。
【００１０】
例えば、データ変換の際に、変換前データ内に存在しない情報を用いる場合に、変換前データ以外のデータ（外部データ）を用いる場合がある。しかし、外部データを参照する処理は、外部データを参照しない処理と比べて処理時間が長い。よって、外部データを参照する処理数が増加するに応じて、データ変換に用いる処理の探索時間が増加する。
【００１１】
１つの側面として、本発明は、データ変換に用いる処理の探索時間を低減することを目的とする。
【課題を解決するための手段】
【００１２】
１つの態様では、データ変換プログラムは、コンピュータに、第１データと、前記第１データの変換後データである第２データを取得し、処理ごとに定義された処理時間を示す属性に基づいて、前記第１データを前記第２データに変換する際に用いられる複数の処理の組み合わせを探索し、探索した前記複数の処理の組み合わせを表示する処理を実行させる。
【発明の効果】
【００１３】
１つの側面によれば、データ変換に用いる処理の探索時間を低減することができる。
【図面の簡単な説明】
【００１４】
【図１】データ変換処理の比較例を示す図である。
【図２】データ変換システムの一例を示す図である。
【図３】処理種別テーブルの一例を示す図である。
【図４】処理の組み合わせの一例を示す図である。
【図５】データ変換処理手順を示す図である。
【図６】変換前の表示例を示す図である。
【図７】変換処理結果の表示例を示す図である。
【図８Ａ】実施形態の処理の流れの一例を示すフローチャート（その１）である。
【図８Ｂ】実施形態の処理の流れの一例を示すフローチャート（その２）である。
【図８Ｃ】実施形態の処理の流れの一例を示すフローチャート（その３）である。
【図８Ｄ】実施形態の処理の流れの一例を示すフローチャート（その４）である。
【図９】図８ＢのステップＳ１１３におけるneighborFunc関数の処理の流れの第１の例を示すフローチャートである。
【図１０】distbetween処理の流れの一例を示すフローチャートである。
【図１１】図９のステップＳ２０９におけるＦＩＦＯ処理の第１の例を示すフローチャートである。
【図１２】図８ＤのステップＳ１２５の処理の一例を示すフローチャートである。
【図１３】図８ＤのステップＳ１２６の処理の一例を示すフローチャートである。
【図１４】図８ＢのステップＳ１１３におけるneighborFunc関数の処理の流れの第２の例を示すフローチャートである。
【図１５】図９のステップＳ２０９におけるＦＩＦＯ処理の第２の例を示すフローチャートである。
【図１６】データ変換装置のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１５】
＜実施形態のシステムの全体構成の一例＞
以下、図面を参照して、実施形態について説明する。図１は、データ変換処理の比較例を示す。図１に示すように、比較例の処理を行う情報処理装置が、変換前データに対して、複数の処理を実行することにより変換後データを生成する。中間データは、変換前データから変換後データに変換する過程で生成されるデータであり、変換前に少なくとも一つの処理が適用されたデータである。
【００１６】
図１に示す変換前データは、電話番号であり、"Tel:"、"("、")"等の記号を含む。また、変換後データは、"XXX-XXX-XXXX"という形式の電話番号である。図１に示す矢印は、処理を示す。また、太い矢印は、重い処理を示し、細い矢印は、軽い処理を示す。重い処理は、例えば、処理にかかる時間が所定時間以上である処理である。また、軽い処理は、例えば、処理にかかる時間が所定時間未満である処理である。重い処理は、例えば、外部データを参照する処理である。
【００１７】
図１に示すように、変換前データに対して、複数の処理を実行して変換後データを作成する場合、実行される処理の組み合わせが多数になる可能性がある。特に、処理の組み合わせに重い処理を含む場合、処理の組み合わせの探索にかかる時間が長くなる。
【００１８】
＜データ変換システムの一例＞
図２は、データ変換システムの一例を示す図である。データ変換システムは、データ変換装置１と、表示装置２とを含む。データ変換装置１は、取得部１１と探索部１２とＦＩＦＯ処理部１３と変換部１４と変換前データ記憶部１５と変換後データ記憶部１６と処理情報記憶部１７と設定部１８と表示制御部１９とを含む。データ変換装置１は、コンピュータの一例である。
【００１９】
なお、変換部１４と変換前データ記憶部１５と変換後データ記憶部１６と処理情報記憶部１７は、データ変換装置１とは別の装置に含まれていてもよい。
【００２０】
取得部１１は、変換前データ記憶部１５に記憶される変換前データを取得する。また、取得部１１は、該変換前データを変換したデータであり、且つ変換後データ記憶部１６に記憶されている変換後データを取得する。取得部１１が取得する変換前データは、変換前データ記憶部１５に記憶される変換前データの一部であってよい。取得部１１が取得する変換後データは、取得した変換前データに対応する変換後のデータであり、データ変換装置１に対するユーザの入力操作により、予め記憶されているとする。変換前データは、第１データの一例である。変換後データは、第２データの一例である。
【００２１】
探索部１２は、処理ごとに定義された処理時間を示す属性に基づいて、変換前データを変換後データに変換する際に用いる複数の処理の組み合わせを探索する。探索部１２は、探索の際に、取得部１１が取得した変換前データおよび変換後データを用いる。
【００２２】
ＦＩＦＯ処理部１３は、属性を示す数値を処理順に格納するキューを用いて、ＦＩＦＯ処理を実行する。
【００２３】
変換部１４は、複数の処理の組み合わせに基づいて、変換対象データを変換する。変換対象データは、例えば、変換前データ記憶部１５に記憶される全データである。
【００２４】
変換前データ記憶部１５は、変換前データを記憶する。変換後データ記憶部１６は、変換後データを記憶する。変換後データの一部は、予めユーザから入力される。残りの変換後データは、変換部１４の変換により得られるデータである。
【００２５】
処理情報記憶部１７は、後述する処理種別テーブルを記憶する。設定部１８は、後述する処理種別テーブルに、処理毎の属性を設定する。また、処理情報記憶部１７は、探索部１２により探索された処理の組み合わせを記憶する
表示制御部１９は、探索した複数の処理の組み合わせを表示装置２に表示する。また、表示制御部１９は、変換部１４が変換前データを変換して得られた変換後データを表示する。
【００２６】
図３は、処理種別テーブルの一例を示す図である。図３に示すように、処理種別テーブルでは、処理種別毎に、重い処理か軽い処理かを示す属性が対応づけられている。図３に示す例では、重い処理に"１"が対応づけられ、軽い処理に"０"が対応づけられている。例えば、分割処理は、変換前データである文字列のうち「,」または「:」が存在する位置で分割を行う処理であり、比較的短時間で実行可能であるため、軽い処理に分類されている。
【００２７】
図３に示す例では、重い処理は、「外部データ参照」のみであるが、重い処理として他の処理が設定されていてもよい。例えば、重い処理として、表の縦と横を入れ換える転置処理が設定されていてもよい。図３に示す処理種別毎の属性は、例えば、ユーザによって予め定義される。
【００２８】
外部データは、例えば、変換前データ、または中間データに、変換後データが含まれていない場合に用いられる。例えば、"ABCLtd."を"ABCLimited"に変換する場合、"Ltd."が"Limited."の略であることを示す外部データが用いられる。外部データは、変換前データ、中間データおよび変換後データ以外のデータであり、データ変換装置１に記憶されていてもよく、他の情報処理装置から取得されたデータであってもよい。
【００２９】
また、設定部１８が、スタートノード（変換前データ）に対して処理を実行し、処理時間を計測することにより、処理時間に基づいて重い処理か軽い処理かを判定し、処理種別テーブルに"１"または"０"を設定してもよい。設定部１８は、例えば、処理種別毎に処理時間を測定し、全処理の処理時間の平均値μおよび標準偏差σを算出する。そして、設定部１８は、例えば、各処理種別の処理時間が、例えばμ＋２σ以上であれば処理が重い処理であると判定し、属性に"１"を設定する。また、設定部１８は、例えば、μ＋２σ未満であれば処理が軽い処理であると判定し、属性に"０"を設定する。
【００３０】
設定部１８は、各処理が重い処理であるか否かをユーザに問い合わせてもよい。例えば、表示制御部１９が、表示装置２に図３に示す処理種別テーブルを表示させ、ユーザに重い処理か否かの選択を促すメッセージを表示させる。そして、設定部１８は、ユーザからの入力に基づいて、属性を設定してもよい。
【００３１】
また、設定部１８は、処理種別毎の処理時間を計測し、処理の種別毎の処理時間の平均値を算出し、処理種別毎の処理時間の平均値（平均処理時間）を記録してもよい。そして、表示制御部１９は、図３に示すように、平均処理時間を表示してもよい。また、表示制御部１９は、平均処理時間が大きい順に処理種別を表示してもよい。そして、設定部１８は、ユーザからの入力に基づいて、属性を設定してもよい。
【００３２】
図４は、処理の組み合わせの例を示す図である。図４に示す処理の組み合わせは、処理番号と処理種別とパラメータとを含む。処理番号は、変換の際に実行される順序を示す。パラメータは、例えばJavaScript（登録商標） Object Notation（ＪＳＯＮ）形式で表記される。変換ロジックは、処理の系列として保持され、任意のシリアライズ機能を用いて保持される。
【００３３】
探索部１２は、探索処理を実行した後、処理の組み合わせを変換部１４に送るとともに、例えば、図４に示す形式で、処理情報記憶部１７に記憶する。
【００３４】
図５は、データ変換処理手順を示す図である。データ変換装置１は、変換前データに対して、複数の処理を実行することにより変換後データを出力する。中間データは、変換途中のデータを示す。図５に示すように、変換データおよび中間データの上部には、テーブル形式で示したデータと、ＦＩＦＯ処理で用いられるキューを示している。
【００３５】
探索部１２は、例えば、変換前データと変換後データの例を取得し、変換前データと変換後データに変換する際に用いる処理の組み合わせを探索する。探索部１２は、処理が重い処理である場合、キューに"1"を挿入し、処理が軽い処理である場合、ＦＩＦＯのキューに"0"を挿入する。
【００３６】
図５に示す例では重い処理が外部データ参照処理であるとする。外部データ参照処理を実行する場合、データに外部データが付加されるため、テーブルの列が増加する。
【００３７】
探索部１２は、処理を探索する際に、重い処理を示す"1"がＦＩＦＯに含まれておらず、かつ、探索中のデータに変換後データが含まれていない場合、重い処理を処理の候補に用いる。すなわち、重い処理が処理の候補から除外される可能性がある点で図１に示す比較例とは異なる。
【００３８】
図５に示す例では、中間データａ０１から中間データｂ０１に変換するための重い処理、および中間データｂ０４から中間データｃ０１に変換するための重い処理が、処理の候補から除外される。
【００３９】
実施形態のデータ変換装置１は、所定条件を満たす場合に、重い処理を処理の候補に用いるが、所定条件を満たさない場合、重い処理を処理の候補から除外するため、処理の探索にかかる時間を低減することができる。
【００４０】
図６は、変換前の表示例を示す図である。図６に示す例では、変換前データおよび変換後データが電話番号である。変換前データは、"Tel:"、"("、")"等の記号を含む電話番号である。また、変換後データは、"XXX-XXX-XXXX"という形式で示される電話番号である。
【００４１】
表示制御部１９は、例えば、全ての変換前データを表示し、ユーザに一定数の変換後データの入力を促すメッセージを表示する。そして、ユーザから、変換後データである電話番号が４つ入力されたとする。
【００４２】
そして、図６に示す例では、取得部１１は、変換前データである４つの電話番号と、変換前データに対応する変換後データである４つの電話番号を取得する。そして、探索部１２は、取得された変換前データと変換後データに基づいて、変換に用いる処理の組み合わせを探索する。
【００４３】
図７は、変換処理結果の表示例を示す図である。探索部１２は、取得した変換前データと変換後データに基づいて、変換に用いる変換ロジックを出力する。表示制御部１９は、探索部１２から出力された変換ロジックを表示装置２に表示する。
【００４４】
図７に示すように、変換ロジックは、複数の処理（関数）の組み合わせである。図７に示す変換ロジックは、処理ｆ１、ｆ２、およびｆ３の組み合わせである。
【００４５】
さらに、表示制御部１９は、変換部１４が変換して得られた変換後データを表示する。図７に示す例では、表示制御部１９は、変換前データに対応する全ての変換後データを表示する。
【００４６】
なお、変換前データまたは中間データの型は文字列だけでなく、数値型や日付型などが含まれていてもよい。本実施形態のデータ変換装置１は、全ての型を文字列型へ変換してから変換を実行することを想定している。
【００４７】
＜実施形態の処理の流れの一例＞
図８Ａ〜図８Ｄは、実施形態の処理の流れの一例を示すフローチャートである。本実施形態の処理では、スタートノードを変換前データとし、ゴールノードを変換後データとして、グラフ探索アルゴリズムとしてのＡ＊法を用いた探索を行う。該探索には、他の探索手法が適用されてもよい。
【００４８】
取得部１１は、変換前データ"start"、変換後データ"end"、ヒューリスティック関数h、および近傍ノード出力関数neighborFuncを取得する（ステップＳ１０１）。
【００４９】
探索部１２は、ＦＩＦＯに用いる空のキュー"F"にＭ個の０を挿入する（ステップＳ１０２）。探索部１２は、集合"openSet"を空にして、対("start",F)を挿入し、集合"closedSet"を空集合とする（ステップＳ１０３）。集合"openSet"は、計算中のノードを格納する。集合"closedSet"は、計算済みのノードを格納する。
【００５０】
探索部１２は、連想配列"cameFrom"と、連想配列"cameFromWithOp"とを空にする（ステップＳ１０４）。連想配列"cameFrom"は、スタートノードからゴールノードまでの経路中のノード（データ）を格納する。連想配列"cameFromWithOp"は、スタートノードからゴールノードに到達するまでに実施される処理の候補を格納する。
【００５１】
探索部１２は、連想配列"gScore"、および連想配列"fSrore"を空配列とし、gScore[("start",F)]に0を設定する（ステップＳ１０５）。探索部１２は、ヒューリスティック関数hを用いて、fScore[("start",F)]にh("start","end")を設定する（ステップＳ１０６）。
【００５２】
ヒューリスティック関数hは、取得したノード間の最小コストの推定値を返す関数である。例えば、h("start","end")は、"start"から"end"に到達するまでの最小コストの推定値を返す。ヒューリスティック関数hには、例えば、非特許文献１に開示されている"Algorithm4：Table Edit Distance Algorithm"を適用してもよい。
【００５３】
探索部１２は、openSetが空であるか判定する（ステップＳ１０７）。openSetが空である場合（ステップＳ１０７でＹＥＳ）、失敗フラグであるブール値Ｆａｌｓｅを出力し（ステップＳ１１１）、処理を終了する。また、表示制御部１９は、探索処理が失敗したことを表示装置２に表示してもよい。
【００５４】
openSetが空でない場合（ステップＳ１０７でＮＯ）、探索部１２は、openSetの中で、fScoreの値が最も小さい対(node,F)を探し、データ"current_node"をnodeとし、キュー"current_F"をFとする（ステップＳ１０８）。
【００５５】
探索部１２は、"current_node"が"end"と同じであるか判定する（ステップＳ１０９）。ステップＳ１０９でＹＥＳである場合、ゴールノードまで探索したこととなるため、探索部１２は、cameFromとcameFromWithOpとcurrent_Fとを処理情報記憶部１７に記憶する（ステップＳ１１０）。
【００５６】
ステップＳ１０９でＮＯである場合、処理は「Ｂ」からステップ１１２に移行する。探索部１２は、openSetから(current_node,current_F)を取り除き、closedSetに(current_node,current_F)を追加する（ステップＳ１１２）。探索部１２は、neighborFunc(current_node,current_F,"end")を計算し、出力された対NLを対のリスト"NL"とし、出力されたリストoperatorListを処理のリスト"operatorList"とする（ステップＳ１１３）。ステップＳ１１３の処理について、詳細は後述する。
【００５７】
探索部１２は、NLが空であるか判定する（ステップＳ１１４）。NLが空である場合（ステップＳ１１４でＹＥＳ）、処理は「Ａ」からステップＳ１０７に移行する。
【００５８】
NLが空でない場合（ステップＳ１１４でＮＯ）、探索部１２は、NLから取り出した対を(neighbor_node,neighbor_F)とし、operatorListから取り出した処理をoiとする（ステップＳ１１５）。
【００５９】
探索部１２は、(neighbor_node,neighbor_F)がclosedSetに存在するか判定する（ステップＳ１１６）。ステップＳ１１６でＹＥＳの場合、処理は、ステップＳ１１４に戻る。
【００６０】
ステップＳ１１６でＮＯの場合、処理は、「Ｄ」からステップＳ１１７に移行する。探索部１２は、(neighbor_node,neighbor_F)がopenSetに存在するか判定する（ステップＳ１１７）。ステップＳ１１７でＮＯの場合、探索部１２は、(neighbor_node, neighbor_F)をopenSetに追加する（ステップＳ１１８）。
【００６１】
ステップＳ１１７でＹＥＳの場合、またはステップＳ１１８の処理後、探索部１２は、スカラー値tentative_gScoreをgScore[(current_node,current_F)]+dist_between(current_node,neighbor_node)とする（ステップＳ１１９）。dist_between関数に関して、詳細は後述する。
【００６２】
探索部１２は、gScore[(neighbor_node, neighbor_F)]がtentative_gScore以下であるか判定する（ステップＳ１２０）。ステップＳ１２０でＹＥＳの場合、処理は「Ｃ」からステップＳ１１４に戻る。
【００６３】
ステップＳ１２０でＮＯの場合、探索部１２は、cameFrom[(neighbor_node,neighbor_F)]を(current_node,current_F)とする（ステップＳ１２１）。すなわち、ステップＳ１２１の処理は、(current_node,current_F)に処理を適用した結果、neighbor_node,neighbor_Fが得られることを示す。
【００６４】
探索部１２は、cameFromWithOp[(neighbor_node,neighbor_F)]をoiとする（ステップＳ１２２）。なお、cameFromWithOp[(neighbor_node,neighbor_F)]は、neighbor_nodeに適用された処理を示す。すなわち、ステップＳ１２２の処理は、あるノード、キューの対に処理oiを作用させた結果、(neighbor_node,neighbor_F)が得られることを示す。
【００６５】
探索部１２は、gScore[(neighbor_node, neighbor_F)]をtentative_gScoreとする（ステップＳ１２３）。
【００６６】
探索部１２は、fScore[(neighbor_node,neighbor_F)]をgScore[(neighbor_node,neighbor_F)]+h(neighbor_node,"end")とする（ステップＳ１２４）。ステップＳ１２４の処理後、処理は、「Ｃ」からステップＳ１１４に移行する。
【００６７】
図８Ａにおいて、ステップＳ１１０の処理後、処理は、「Ｅ」から、ステップＳ１２５に移行する。探索部１２は、cameFromとcameFromWithOpとcurrent_Fとに基づいて、変換対象データｄの変換に用いる処理の組み合わせを出力する（ステップＳ１２５）。ステップＳ１２５の処理について、詳細は後述する。
【００６８】
変換部１４は、変換対象データｄの変換に用いる処理の組み合わせを用いて、変換対象データｄを変換する（ステップＳ１２６）。
【００６９】
表示制御部１９は、変換対象データｄの変換に用いた処理の組み合わせ（変換ロジック）および変換後データを表示装置２に表示する（ステップＳ１２７）。表示制御部１９は、例えば、図７に示す形式で、変換ロジックおよび変換後データを表示装置２に表示する。
【００７０】
図９は、図８ＢのステップＳ１１３で用いられるneighborFunc関数の処理の流れの第１の例を示す。neighborFunc関数は、図８ＢのステップＳ１１３で呼び出される関数であり、探索部１２により実現される。
【００７１】
探索部１２は、neighborFunc関数にデータ"current_node"、キュー"current_F"、データ"end"を入力する（ステップＳ２０１）。探索部１２は、対のリスト"NL"と、処理のリスト"operatorList"を空にする（ステップＳ２０２）。探索部１２は、事前定義された処理のリストＬのコピーをtmp_Ｌとする（ステップＳ２０３）。
【００７２】
探索部１２は、current_Fに１が含まれるか判定する（ステップＳ２０４）。current_Fに１が含まれる場合、探索対象のノード（current_node）に適用される処理から所定回数（第１回数）前の処理までに、重い処理が含まれていることを意味する。所定回数は、キューに格納される数値の数に等しい。
【００７３】
ステップＳ２０４でＮＯの場合、current_nodeが"end"の要素を含むか判定する（ステップＳ２０５）。ステップＳ２０５でＮＯの場合、探索部１２は、tmp_Lに「外部データ参照」を追加する（ステップＳ２０６）。なお、図３に示す処理種別テーブルにおいて、「外部データ参照」以外の重い処理が存在する場合、ステップＳ２０６において、探索部１２は、tmp_Lに「外部データ参照」以外の重い処理も追加する。
【００７４】
すなわち、探索部１２は、重い処理が、直前に探索した処理から所定回数前までの処理に含まれておらず、かつ、探索対象データに変換後データが含まれていない場合、探索対象データに適用する処理の候補に重い処理を用いる。
【００７５】
探索部１２は、tmp_Lが空であるかを判定する（ステップＳ２０７）。tmp_Lが空でない場合（ステップＳ２０７でＮＯ）、探索部１２は、tmp_Lのうちのいずれかの処理oiを取り出す（ステップＳ２０８）。探索部１２は、処理oiとキューＦをＦＩＦＯ処理部１３に渡す。そして、ＦＩＦＯ処理部１３は、ＦＩＦＯ処理を実行する（ステップＳ２０９）。ＦＩＦＯ処理部１３は、ＦＩＦＯ処理を実行し、更新されたキューＦ２を出力する。ステップＳ２０９のＦＩＦＯ処理について、詳細は後述する。
【００７６】
探索部１２は、ＦＩＦＯ処理において更新されたキューＦ２を取得し、NLに、対（oi(current_node),F2）を追加する（ステップＳ２１０）。探索部１２は、operatorListにoiを追加する（ステップＳ２１１）。ステップＳ２１１の処理後、処理は、ステップＳ２０７に移行する。
【００７７】
tmp_Lが空である場合（ステップＳ２０７でＹＥＳ）、探索部１２は、neighborFunc関数の出力値をNL,operatorListとする（ステップＳ２１２）。
【００７８】
図９に示す処理において、ステップＳ２１０で処理oiが実行されるが、処理oiが重い処理であった場合、探索処理の時間が増加する。データ変換装置１は、ステップＳ２０４〜Ｓ２０６において、所定の条件を満たさない場合に外部データ参照処理（重い処理）を適用しないため、探索処理を高速化することができる。また、図９に示す例を用いた場合、ステップＳ２０４の条件により、重い処理の実行間隔を所定回数以上とすることができる。
【００７９】
図１０は、distbetween処理の流れの一例を示すフローチャートである。distbetween処理は、図８ＣのステップＳ１１９で呼び出される関数である。distbetween処理は、探索部１２により実現される。
【００８０】
探索部１２は、distbetween処理の出力値に１を設定する（ステップＳ３０１）。distbetween処理の出力値は、入力した２つノード間の距離（コスト）を示す。なお、本実施形態では、distbetween処理の出力値は１であるが入力したノードに応じて異なる値であってもよい。
【００８１】
図１１は、図９のステップＳ２０９におけるＦＩＦＯ処理の第１の例を示すフローチャートである。ＦＩＦＯ処理部１３は、処理oiとＦＩＦＯのキューＦを取得する（ステップＳ４０１）。ＦＩＦＯ処理部１３は、ＦのコピーをＦ２とする（ステップＳ４０２）。
【００８２】
ＦＩＦＯ処理部１３は、oiが外部データ参照処理であるか判定する（ステップＳ４０３）。なお、外部データ参照処理以外にも重い処理が存在する可能性がある。よって、ステップＳ４０３では、ＦＩＦＯ処理部１３は、例えば、図３の処理種別テーブルを参照して、oiが重い処理であるか判定してもよい。
【００８３】
oiが外部データ参照処理でない場合（ステップＳ４０３でＮＯ）、ＦＩＦＯ処理部１３は、Ｆ２から、最も先に入力された要素を一つ取り出し、Ｆ２に０を追加する（ステップＳ４０４）。oiが外部データ参照処理である場合（ステップＳ４０３でＹＥＳ）、Ｆ２から、最も先に入力された要素を一つ取り出し、Ｆ２に１を追加する（ステップＳ４０４）。
【００８４】
ＦＩＦＯ処理部１３は、更新されたＦ２を探索部１２に出力する（ステップＳ４０６）。
【００８５】
図１２は、図８ＤのステップＳ１２５の処理の一例を示すフローチャートである。探索部１２は、処理情報記憶部１７に記憶した連想配列cameFrom、cameFromWithOpを取得し、変換後データ記憶部１６から、変換後データdを取得する（ステップＳ５０１）。探索部１２は、リストtotal_opを空にする
探索部１２は、current_nodeをdとする（ステップＳ５０３）。探索部１２は、(current_node,current_F)がcameFromに含まれるか判定する（ステップＳ５０４）。
【００８６】
ステップＳ５０４でＹＥＳの場合、処理opをcameFromWithOp[(current_node,current_F)]とする（ステップＳ５０５）。探索部１２は、cameFrom[(current_node, current_F)]を(current_node2,current_F2)とする（ステップＳ５０６）。探索部１２は、current_node2をcurrent_nodeとし、current_F2をcurrent_Fとする（ステップＳ５０７）。探索部１２は、total_opの末尾にopを追加する（ステップＳ５０８）。
【００８７】
ステップＳ５０４でＮＯの場合、探索部１２は、total_opを変換部１４に出力する（ステップＳ５０９）。
【００８８】
以上の処理により、探索部１２は、変換後データdから変換前データまで逆向きに経路を辿ることにより、処理の組み合わせ（変換ロジック）を示すtotal_opを生成し、変換部１４に出力する。total_opには、変換処理の実行順とは逆の順序で処理が格納される。
【００８９】
図１３は、図８ＤのステップＳ１２６の処理の一例を示すフローチャートである。変換部１４は、探索部１２から処理のリストtotal_opを取得し、変換前データ記憶部１５から変換前データdを取得する（ステップＳ６０１）。変換部１４は、total_opが空であるか判定する（ステップＳ６０２）。
【００９０】
total_opが空でない場合（ステップＳ６０２でＮＯ）、変換部１４は、total_opの末尾から処理ｏｐを取り出す（ステップＳ６０３）。ステップＳ６０３において、変換部１４は、処理番号順に、処理ｏｐを取り出す。
【００９１】
変換部１４は、dにopを実行したデータをd2とする（ステップＳ６０４）。変換部１４は、d2をdとする（ステップＳ６０５）。total_opが空である場合（ステップＳ６０２でＹＥＳ）、変換部１４は、dを出力する（ステップＳ６０６）。ステップＳ６１６で、変換部１４が出力するデータｄは変換後データである。変換部１４は、変換後データを変換後データ記憶部１６に記憶するとともに、表示制御部１９に出力する。
【００９２】
図１４は、図８ＢのステップＳ１１３におけるneighborFunc関数の処理の流れの第２の例を示すフローチャートである。図１４において、ステップＳ２０４’の処理が図９に示す処理と異なる。図１４において、ステップＳ２０４’以外の処理は、図９と同様である。
【００９３】
ステップＳ２０４’では、探索部１２は、current_Fに１がｋ回（第２回数）以上含まれるか判定する。current_Fに１が含まれる場合、探索中のノードに適用される処理から所定回数（第１回数）前の処理までに、重い処理が含まれていることを意味する。所定回数は、キューに格納される数値の数に等しい。
【００９４】
ステップＳ２０４’でＮＯの場合、current_nodeが"end"の要素を含むか判定する（ステップＳ２０５）。ステップＳ２０５でＮＯの場合、探索部１２は、tmp_Lに「外部データ参照」を追加する（ステップＳ２０６）。
【００９５】
すなわち、探索部１２は、重い処理が、直前に探索した処理から所定回数前までの処理にｋ回以上含まれておらず、かつ、探索対象データに変換後データが含まれていない場合、探索対象データに適用する処理の候補に重い処理を用いる。
【００９６】
図１５は、図９のステップＳ２０９におけるＦＩＦＯ処理の第２の例を示すフローチャートである。図１５に示す処理は、ステップＳ４０４’およびステップＳ４０５’の処理が図９に示す処理と異なる。
【００９７】
ステップＳ４０４’において、探索部１２は、Ｆ２の格納要素数を１つ増加しＦ２に０を追加する。また、ステップＳ４０５’において、探索部１２は、Ｆ２の格納要素数を１つ増加しＦ２に１を追加する。ステップＳ４０４’およびＳ４０５’において、探索部１２は、キューＦ２から要素を取り出す処理を行わない。よって、Ｆ２には、すでに追加された要素が全て含まれている。
【００９８】
図１５の処理を用いた場合、探索部１２は、図９のステップＳ２０４〜２０６において、探索部１２は、重い処理が、探索済みの全処理に含まれておらず、かつ、探索対象データに変換後データが含まれていない場合、探索対象データの処理の候補に重い処理を用いることとなる。よって、データ変換装置１は、図１５の処理を用いた場合、データ探索に用いられる全処理における重い処理を低減することができる。
【００９９】
＜データ変換装置のハードウェア構成の一例＞
次に、図１６の例を参照して、データ変換装置１のハードウェア構成の一例を説明する。図１６の例に示すように、バス１００に対して、プロセッサ１１１とRandom Access Memory(RAM)１１２とRead Only Memory(ROM)１１３とが接続される。また、該バス１００に対して、補助記憶装置１１４と媒体接続部１１５と通信インタフェース１１６と入力インタフェース１１８とが接続される。
【０１００】
プロセッサ１１１は、ＲＡＭ１１２に展開されたプログラムを実行する。実行されるプログラムとしては、実施形態における処理を行うデータ変換プログラムが適用されてもよい。
【０１０１】
ＲＯＭ１１３は、ＲＡＭ１１２に展開されるプログラムを記憶する不揮発性の記憶装置である。補助記憶装置１１４は、種々の情報を記憶する記憶装置であり、例えばハードディスクドライブや半導体メモリ等が適用されてもよい。補助記憶装置１１４に実施形態の処理を行うデータ変換プログラムが記録されていてもよい。
【０１０２】
媒体接続部１１５は、可搬型記録媒体１１７と接続可能に設けられている。可搬型記録媒体１１７には、可搬型のメモリや光学式ディスク（例えば、Compact Disc(CD)やDigital Versatile Disc(DVD))、半導体メモリ等が適用されてもよい。可搬型記録媒体１１７に実施形態の処理を行うデータ変換プログラムが記録されていてもよい。
【０１０３】
図２に示す変換前データ記憶部１５、変換後データ記憶部１６および処理情報記憶部１７は、ＲＡＭ１１２や補助記憶装置１１４等により実現されてもよい。図２に示す取得部１１は、通信インタフェース１１６または入力インタフェース１１８により実現されてもよい。入力インタフェース１１８は、例えば、マウス、キーボード、またはタッチパネルディスプレイである。図２に示す探索部１２、ＦＩＦＯ処理部１３、変換部１４、設定部１８、および表示制御部１９は、ＲＡＭ１１２に展開されたデータ変換プログラムをプロセッサ１１１が実行することにより実現されてもよい。
【０１０４】
ＲＡＭ１１２、ＲＯＭ１１３、補助記憶装置１１４および可搬型記録媒体１１７は、何れもコンピュータ読み取り可能な有形の記憶媒体の一例である。これらの有形な記憶媒体は、信号搬送波のような一時的な媒体ではない。
【０１０５】
＜その他＞
本実施形態は、以上に述べた実施の形態に限定されるものではなく、本実施形態の要旨を逸脱しない範囲内で種々の構成または実施形態を取ることができる。
【符号の説明】
【０１０６】
１    データ変換装置
２    表示装置
１１    取得部
１２    探索部
１３    ＦＩＦＯ処理部
１４    変換部
１５    変換前データ記憶部
１６    変換後データ記憶部
１７    処理情報記憶部
１８    設定部
１９    表示制御部
１００    バス
１１１    プロセッサ
１１２    ＲＡＭ
１１３    ＲＯＭ
１１４    補助記憶装置
１１５    媒体接続部
１１６    通信インタフェース
１１７    可搬型記録媒体
１１８    入力インタフェース
【図１】
2019049815.tif 000003
【図２】
2019049815.tif 000004
【図３】
2019049815.tif 000005
【図４】
2019049815.tif 000006
【図５】
2019049815.tif 000007
【図６】
2019049815.tif 000008
【図７】
2019049815.tif 000009
【図８Ａ】
2019049815.tif 000010
【図８Ｂ】
2019049815.tif 000011
【図８Ｃ】
2019049815.tif 000012
【図８Ｄ】
2019049815.tif 000013
【図９】
2019049815.tif 000014
【図１０】
2019049815.tif 000015
【図１１】
2019049815.tif 000016
【図１２】
2019049815.tif 000017
【図１３】
2019049815.tif 000018
【図１４】
2019049815.tif 000019
【図１５】
2019049815.tif 000020
【図１６】
2019049815.tif 000021