(57)【要約】【課題】半構造電文内の制約の検証を多数のコアを用いて高速に処理する。【解決手段】半構造電文の受信前に、シーケンス処理に優れた第１の演算装置が、半構造電文のスキーマからタグ名を取得して文字列マッチングのためのタグ名の有限オートマトンを生成する。また、並列処理に優れた第２の演算装置を使用して半構造電文の検証を並列的に実行するためのプログラムを、制約を記述した検証ファイルに基づいて生成する。次に、半構造電文の受信時、第１の演算装置が、前処理として、半構造電文内のタグ位置を特定する配列と共にそのタグ構造を特定する配列を生成する。その後、第２の演算装置を構成する各コアが、前記プログラムを並列実行を通じ、有限オートマトンに基づいてタグ名を特定し、事前に作成されたタグ構造を特定する配列を利用してタグ及び／又はコンテンツ間の相互関係に関する制約の検証対象となるタグ及び／又はコンテンツを取得し、検証する。【選択図】図６
2014063244.tif 000002
【特許請求の範囲】
【請求項１】
シーケンス処理に優れる第１の演算装置が、半構造電文のスキーマからタグ名を取得し、文字列マッチングのためのタグ名の有限オートマトンを生成する第１の処理と、
並列処理に優れる第２の演算装置に半構造電文の検証処理を並列的に実行させるためのプログラムを、前記第１の演算装置が、タグ及び／又はコンテンツ間の相互関係に関する制約を記述した検証ファイルに基づいて生成する第２の処理と、
半構造電文を受信した前記第１の演算装置が、前処理として、半構造電文内のタグ位置を特定する配列及び半構造電文のタグ構造を特定する配列を生成する第３の処理と、
前記第２の演算装置を構成する各コアプロセッサが前記プログラムの並列実行を通じ、前記有限オートマトンに基づいてタグ名を特定し、前記タグ構造を特定する配列を利用してタグ及び／又はコンテンツ間の相互関係に関する制約の検証対象となるタグ及び／又はコンテンツを半構造電文から取得し、取得されたタグ及び／又はコンテンツに基づいて半構造電文を検証する第４の処理と、
前記第１の演算装置が、前記検証の結果を出力する第５の処理と
を有する半構造電文の並列検証方法。
【請求項２】
請求項１に記載の半構造電文の並列検証方法において、
前記第１の処理で生成された前記有限オートマトン及び前記第３の処理で生成されたタグ構造を特定する配列を、前記第１の演算装置が簡潔データ表現を利用して圧縮し、前記コアプロセッサに隣接するローカルメモリ上に格納する
ことを特徴とする半構造電文の並列検証方法。
【請求項３】
請求項１に記載の半構造電文の並列検証方法において、
前記検証ファイルは、検証対象のタグ及び／又はコンテンツを指定するＬｅｔ句と、対象となるタグ及び／又はコンテンツが全て条件を満たすか／条件を満たすものがあるかを指定するＥｖｅｒｙ/Ｓｏｍｅ句と、満たすべき条件を指定するＳａｔｉｓｆｙ句とを有する
ことを特徴とする半構造電文の並列検証方法。
【請求項４】
コンピュータを構成する、シーケンス処理に優れる第１の演算装置に、
半構造電文のスキーマからタグ名を取得し、文字列マッチングのためのタグ名の有限オートマトンを生成させる第１の処理と、
コンピュータを構成する、並列処理に優れる第２の演算装置に半構造電文の検証処理を並列的に実行させるためのプログラムを、タグ及び／又はコンテンツ間の相互関係に関する制約を記述した検証ファイルに基づいて生成させる第２の処理と、
半構造電文を受信した場合に、前処理として、半構造電文内のタグ位置を特定する配列及び半構造電文のタグ構造を特定する配列を生成させる第３の処理とを実行させ、
前記第２の演算装置を構成する各コアプロセッサに、
前記プログラムの並列実行を通じ、前記有限オートマトンに基づいてタグ名を特定させる処理、前記タグ構造を特定する配列を利用してタグ及び／又はコンテンツ間の相互関係に関する制約の検証対象となるタグ及び／又はコンテンツを半構造電文から取得する処理、取得されたタグ及び／又はコンテンツに基づいて半構造電文を検証させる第４の処理を実行させ、
前記第１の演算装置に、
前記検証の結果を出力させる第５の処理を実行させる
プログラム。
【請求項５】
シーケンス処理に優れる第１の演算装置が、半構造電文のスキーマからタグ名を取得し、文字列マッチングのためのタグ名の有限オートマトンを生成する第１の処理部と、
並列処理に優れる第２の演算装置に半構造電文の検証処理を並列的に実行させるためのプログラムを、前記第１の演算装置が、タグ及び／又はコンテンツ間の相互関係に関する制約を記述した検証ファイルに基づいて生成する第２の処理部と、
半構造電文を受信した前記第１の演算装置が、前処理として、半構造電文内のタグ位置を特定する配列及び半構造電文のタグ構造を特定する配列を生成する第３の処理部と、
前記第２の演算装置を構成する各コアプロセッサが前記プログラムの並列実行を通じ、前記有限オートマトンに基づいてタグ名を特定し、前記タグ構造を特定する配列を利用してタグ及び／又はコンテンツ間の相互関係に関する制約の検証対象となるタグ及び／又はコンテンツを半構造電文から取得し、取得されたタグ及び／又はコンテンツに基づいて半構造電文を検証する第４の処理部と、
前記第１の演算装置が、前記検証の結果を出力する第５の処理部と
を有する半構造電文の並列検証装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＸＭＬやＪＳＯＮ（java script object notation）等の形式で記述された半構造電文内のタグ及び／又はコンテンツ間の相互関係に関する制約の成立／不成立を、多数のコアを有する演算装置を用いて並列に検証する方法、装置及びプログラムに関する。
【背景技術】
【０００２】
企業間の電子取引やシステム間の連携等には固定長電文が用いられてきたが、昨今では、ＸＭＬやＪＳＯＮ等の形式で記述された半構造電文が普及してきている。半構造電文は、タグにより意味や構造を記述することができるため、固定長電文と比較して可読性や拡張性に優れている。一方で、半構造電文はサイズが大きく構造が複雑である。このため、制約に対する半構造電文の検証は、コンピュータにとって大きな負担になっている。
【０００３】
ＸＭＬ電文に対する検証内容の記述には、例えばＸＭＬ Ｓｃｈｅｍａ（非特許文献１）が利用されている。ＸＭＬ Ｓｃｈｅｍａでは、ＸＭＬ電文内で利用されるタグ名やコンテンツに対する制約（変数型や正規表現）を記述することができる。
【０００４】
このような背景から、半構造電文のタグ構造の解析や制約の検証を、ＣＰＵやＧＰＵの持つ多数のコアプロセッサ（演算ユニット）（以下、単に「コア」ともいう）を利用し、並列に処理する試みがなされている。例えば非特許文献３では、複数のＸＰａｔｈで指定されたタグやコンテンツの特定を、個々のＸＰａｔｈを各コアに割り当てることにより並列に処理している。また、非特許文献４は、各コアに一つのタグ名のみを割り当てることにより、並列に探索又はタグ検索するためのインデックスを作成している。更に、非特許文献５には、半構造電文内のコンテンツの書式の検証に必要な正規表現のマッチングの並列処理方法が記述されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】H. S. Thompson, D. Beech, M. Maloney, and N.  Mendelsohn, “XML Schema Part 1: Structures Second Edition”, W3C Recommendation 28 October 2004
【非特許文献２】ISO 20022, Payments Initiation - Maintenance 2012, Message Definition Report, Edition June 2012
【非特許文献３】R. Moussalli, R. Halstead, M. Salloum, W. Najjar, and V. J. Tsotras, “Efficient XML Path Filtering Using GPUs”, In Proceeding of ADMS, 2011
【非特許文献４】武藤教宏，廣田雅春，横山昌平，福田直樹，石川博：GPUとCPUの並列処理に適したXMLインデクス生成と検索手法，第4回データ工学と情報マネジメントに関するフォーラム, 2012
【非特許文献５】L. David and S. Sagi, “30x faster regular expression on a GPU”,Nvidia GPU Technology Conference, 2012
【非特許文献６】J. I. Munro and V. Raman, “Succinct Representation of Balanced Parentheses and Static Trees”, SIAMJournal on Computing, 31(3):762-776, 2001
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、特定の業界では、ＸＭＬ電文に対してＸＭＬ Ｓｃｈｅｍａでは記述できない制約を規定する場合がある。例えば金融決済電文を規定するＩＳＯ２００２２では、決済方法に応じて様々な制約を規定している（非特許文献２参照）。
【０００７】
図１に、ＩＳＯ２００２２で規定している送金指示のためのCusutomerCreditTransferInitiationのＸＭＬ電文の例を示す。ただし、説明を簡略化するために、図１では、電文の一部を省略している。図１の例では、ABC Corporationが、DEF Electronicsに10000000円、GHI Semiconductorsに500000ユーロ送金することを指示している。
【０００８】
このCustomerCreditTransferInitiationの電文に対し、ＩＳＯ２００２２は、次の様なルール（制約）を規定している。
【０００９】
R4 PaymentTypeInformationRule
If PaymentTypeInformation is present, then CreditTransferTransactionInformation/PaymentTypeInformation is not allowed.
On Condition
/PaymentTypeInformation is present
Following Must be True
/CreditTransferTransactionInformation[*]/PaymentTypeInformation Must be absent
【００１０】
このR4 PyamentTypeInformationRuleは、規定されているルール（制約）の一例であり、図１のＸＭＬ電文において、<CstmrCdtTrfInitn><Pmtiinf>（<PmtInf>はPaymentTypeInformationに対応するタグ名）が存在した場合、<CstmrCdtTrfInitn><CdtTrfTxInf><PmtInf>（<CdtTrfTxInf>は、CreditTransferTransactionInformationに対応するタグ名）が存在してはいけないことを規定している。このようなタグ間の相互関係に関する制約は、ＸＭＬ Ｓｃｈｅｍａによっては記述することができない。
【００１１】
このようなタグ及び／又はコンテンツ間の相互関係に関する制約を、多数のコアを用いて効率的に検証するには、次に示す技術課題がある。
（１）制約の記述方法について
そもそも、ＸＭＬ Ｓｃｈｅｍａでは記述できないタグ及び／又はコンテンツ間の相互関係に関する制約を、どのように記述したら良いかという課題がある。
（２）タグ構造の高速な特定について
非特許文献３に記載された手法では、指定されたＸＰａｔｈの個数までしか、非特許文献４に記載された手法では、スキーマに記述されたタグ名の数までしか、処理を並列化できない。現在市販のＧＰＵは数千個のコアを有しているが、従来技術では数十から数百程度の並列性しか実現できず、ＧＰＵの性能を十分に引き出していない。
（３）制約の検証に用いるタグの高速な検索について
従来の手法では、２つのタグが、タグ間の相対的な位置（Ｐａｒｅｎｔ/Ｃｈｉｌｄｒｅｎ，Ａｎｃｅｓｓｔｏｒ等）が指定された場合、２つのタグを効率的に取得することができない。
【００１２】
このように、従来の多数のコアを用いた半構造電文検証技術には、タグ及び／又はコンテンツ間の相互関係に関する制約の成立／不成立を効率的に検証できないという技術課題がある。
【課題を解決するための手段】
【００１３】
そこで、本発明者は、半構造電文内のタグ及び／又はコンテンツ間の相互関係に関する制約の検証処理を、可能な限り多数のコアを用いて並列的に実行するための仕組みを提供する。
【００１４】
具体的には、検証対象とする半構造電文を受信する前に、シーケンス処理に優れた第１の演算装置（例えばＣＰＵ）が、(i)半構造電文のスキーマからタグ名を取得して文字列マッチングのためのタグ名の有限オートマトンを生成すると共に、(ii)並列処理に優れた第２の演算装置（例えばＧＰＵ）を使用して半構造電文の検証を並列的に実行するためのプログラムを、制約を記述した検証ファイルに基づいて生成する。
【００１５】
次に、半構造電文が受信されると、第１の演算装置が、前処理として、半構造電文内のタグ位置を特定する配列と共にそのタグ構造の木構造を生成する。
【００１６】
その後、前述の第２の演算装置を構成する各コアプロセッサが、事前に作成されたプログラムの並列実行を通じ、有限オートマトンに基づいてタグ名を特定し、事前に作成されたタグ構造の木構造を利用してタグ及び／又はコンテンツ間の相互関係に関する制約の検証対象となるタグ及び／又はコンテンツを取得し、取得されたタグ及び／又はコンテンツに基づいて半構造電文を検証する仕組みを提供する。
【００１７】
ここで、検証ファイルは、検証対象となるタグ及び／又はコンテンツを指定するＬｅｔ句、全ての検証対象となるタグ及び／又はコンテンツが制約を満たすのかを指定するＥｖｅｒｙ句、制約を満たすタグ及び／又はコンテンツが存在するかを指定するＳｏｍｅ句、満たすべき制約を指定するＳａｔｉｓｆｙ句で記述したものであることが望ましい。
【発明の効果】
【００１８】
本発明によれば、例えば以下に示す効果の少なくとも１つを実現することができる。
（１）ＸＭＬ Ｓｃｈｅｍａでは記述できないタグ及び／又はコンテンツ間の相互関係に関する制約を記述した検証ファイルを提供することにより、結果として、相関のある制約を記述することができる。
（２）第１の演算装置による前処理において、半構造電文のタグ位置を予め特定しておくことにより、第２の演算装置を構成する各コアは、タグの位置からタグ名の文字列マッチングを行うことができる。このため、タグの数だけ処理を並列化できる。この結果、従来手法よりも高速な半構造電文の解析が可能となる。
（３）第１の演算装置による前処理において、半構造電文のタグ位置を特定する配列とタグ構造の木構造を生成し簡潔データ構造を用いて圧縮することにより、半構造電文のタグ構造の情報を、第２の演算装置を構成する多数のコアのローカルメモリに格納することができる。これにより、第２の演算装置は、半構造電文の制約を検証するために必要なタグ及び／又はコンテンツを高速に取得することができる。
【００１９】
このように、本発明によれば、タグ及び／又はコンテンツ間の相互関係に関する制約を、多数のコアを利用して、効率的に検証することができる。上記した以外の課題、構成及び効果は、以下の実施形態の説明により明らかにされる。
【図面の簡単な説明】
【００２０】
【図１】半構造電文例を示す図。
【図２】半構造電文検証システムのシステム構成を示す図。
【図３】半構造電文検証コンピュータの構成例を示す図。
【図４】検証ファイルの例を示す図。
【図５】ＧＰＵ内のＲＡＭに確保されるデータ例。
【図６】半構造電文検証の全体概要を示すフローチャート。
【図７】半構造電文検証の初期化処理のフローチャート。
【図８】タグ名の有限オートマトンのデータ構造生成処理を説明する図。
【図９】半構造電文検証の前処理のフローチャート。
【図１０】半構造電文のタグ構造の生成処理を説明する図。
【図１１】半構造電文検証処理のフローチャート。
【発明を実施するための形態】
【００２１】
以下、図面に基づいて、本発明の実施の形態を説明する。なお、後述する装置構成や処理動作の内容は発明を説明するための一例である。本発明は、後述する装置構成同士や処理動作同士の任意の組み合わせ、後述する装置構成や処理動作に既知の技術を追加する組み合わせ、後述する装置構成や処理動作の一部を既知の技術で置換する組み合わせも包含する。
【実施例】
【００２２】
（１）半構造電文検証システムの構成
図２に、半構造電文検証コンピュータ１２０を実装する半構造電文検証システムの構成例を示す。図２に示す半構造電文検証システムは、(1)決済等の半構造電文１４０を生成するクライアントコンピュータ１００、(2)生成された半構造電文１４０を転送するインターネット１１０、(3)多数のコアを持つＣＰＵやＧＰＵを備え、受信した半構造電文１４０をＣＰＵやＧＰＵを用いて検証する半構造電文検証コンピュータ１２０、(4)半構造電文１４０の検証結果を受信する半構造電文管理コンピュータ１３０とで構成される。本実施例における半構造電文１４０は、ＩＳＯ２００２２が規定している送金指示のCusutomerCreditTransferInitiationのＸＭＬ電文（図１）であるものとする。
【００２３】
図３に、半構造電文検証コンピュータ１２０の構成例を示す。半構造電文検証コンピュータ１２０は、コンピュータ本体３００と、入力装置３３０と、表示装置３３１と、通信装置３３２とから構成される。なお、通信装置３３２は、半構造電文管理コンピュータ１３０とは直接通信し、クライアントコンピュータ１００とはインターネット１１０を介して通信する。
【００２４】
コンピュータ本体３００は、ＣＰＵ３０１、ＲＯＭ３０２、ＣＰＵ＿ＲＡＭ３１０、ハードディスク駆動装置３２０、多数のコアプロセッサ（ＰＵ３４１）を有するＧＰＵ３４０、これらデバイス間のデータ転送を実現するＣＰＵバス３０８、これらデバイスとＣＰＵバス３０８とを結合するインターフェース３０３〜３０７で構成される。
【００２５】
ここで、ＣＰＵ３０１は、動作周波数とコアの処理能力が共に高い、シーケンス処理に優れた演算装置である。一方、ＧＰＵ３４０は、動作周波数とコアの処理能力がＣＰＵ３０１よりも低いものの多数のコアを有し、並列処理に優れた演算装置である。
【００２６】
ＣＰＵ＿ＲＡＭ３１０には、ＣＰＵ３０１で実行される半構造電文検証プログラム３１１の実行領域と、演算時に一時的に生成されるデータを格納する作業領域３１２が少なくとも確保される。
【００２７】
ハードディスク駆動装置３２０の記憶領域には、プログラム格納部３２１とデータ格納部３２２が少なくとも確保される。このうち、プログラム格納部３２１には、ＣＰＵ３０１で実行される半構造電文検証プログラム３１１と、ＧＰＵ３４０で実行される並列半構造電文検証プログラム３５１が格納される。データ格納部３２２には、検証する半構造電文のＸＭＬ Ｓｃｈｅｍａ等のスキーマ、タグ及び／又はコンテンツ間の相互関係に関する制約を記述した検証ファイル、クライアントコンピュータ１００から受信した半構造電文１４０が一時的に格納される。スキーマや検証ファイルは、例えば不図示の外部コンピュータから与えられる。
【００２８】
図４に、前述のPaymentTypeInformationRuleを記述した検証ファイルの例を示す。検証ファイルは、検証対象となるタグ及び／又はコンテンツをＸＰａｔｈ等により指定するＬｅｔ句４０１と、Ｌｅｔ句４０１で指定されたタグ及び／又はコンテンツの全てが条件を満たすのか（Ｅｖｅｒｙ）、条件を満たすものが存在するのか（Ｓｏｍｅ）を指定するＥｖｅｒｙ/Ｓｏｍｅ句４０２と、満たすべき条件を指定するＳａｔｉｓｆｙ句４０３から構成される。
【００２９】
この検証ファイルの例では、Ｌｅｔ句４０１で指定されたPmtInfタグとCdtTrfTxInf/PmtInfタグを取得し、PmtInfタグが存在するならばCdTrfIxInf/PmtInfタグが一つも存在しないという条件を満たすか否かを検証することを意味している。
【００３０】
ＧＰＵ３４０は、データ演算を実行させる数十から数千個の演算ユニットＰＵ３４１と、全てのＰＵ３４１からアクセス可能なＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭ３５０と、近接するＰＵ３４１からのみアクセス可能なＧＰＵ＿ＬＯＣＡＬ＿ＲＡＭ３６０、これらのデバイス間のデータ転送を実現するＧＰＵバス３４２で構成される。ここで、ＰＵ３４１とＧＰＵ＿ＬＯＣＡＬ＿ＲＡＭ３６０との間のデータ転送速度は、ＰＵ３４１とＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭ３５０との間のデータ転送速度に比べて非常に高速である。ただし、ＧＰＵ＿ＬＯＣＡＬ＿ＲＡＭ３６０のサイズは数十ＫＢ程度であり、ＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭ３５０のサイズ（数ＧＢ）と比べて非常に小さい。
【００３１】
ＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭ３５０には、ＰＵ３４１に演算処理させる並列半構造電文検証プログラム３５１と、演算時に一時的に生成されるデータを格納する作業領域３５２が確保される。ＧＰＵ＿ＬＯＣＡＬ＿ＲＡＭ３６０には、ＰＵ３４１の演算時に一時的に生成されるデータを格納する作業領域３６１が確保される。
【００３２】
図５は、ＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭ３５０及びＧＰＵ＿ＬＯＣＡＬ＿ＲＡＭ３６０の作業領域に少なくとも作成されるデータ領域の例を示している。ＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭ３５０の作業領域３５２には、半構造電文のタグ名を文字列マッチングにより特定するためにタグ名の有限オートマトンの各ノードに対応した文字配列５０１、タグ名の有限オートマトンに対応したタグＩＤ配列５０２、半構造電文１４０の構造を保持しつつ不要文字を削除した半構造電文５０３、半構造電文内のタグ位置の配列５０４、半構造電文内のタグＩＤの配列５０５、さらに個々の検証結果を保持するための検証結果の配列５０６を確保する。
【００３３】
ＧＰＵ＿ＬＯＣＡＬ＿ＲＡＭ３６０の作業領域３６１には、タグ名の文字列マッチングのための有限オートマトン及び半構造電文１４０の構造が簡潔データ構造を用いて、タグ名の有限オートマトンのＢＰ表現５１１と半構造電文内のタグ構造のＢＰ表現５１２を保持する。ここで、簡潔データ構造を利用しているのは、ＧＰＵ＿ＬＯＣＡＬ＿ＲＡＭ３６０の小さいメモリ容量で大量の構造を保持するためである。また、本実施形態では、簡潔データ構造としてＢＰ表現（非特許文献６参照）を利用しているが、これ以外の簡潔データ構造を利用してもよい。
【００３４】
（２）半構造電文の検証動作
図６に、半構造電文検証システム全体において実行される半構造電文検証プロセスの概略を示す。
【００３５】
（ステップ６００）
半構造電文検証コンピュータ１２０は、電源が入れられると、半構造電文検証プログラム３１１を実行する。
【００３６】
（ステップ６０１）
半構造電文検証コンピュータ１２０は、ＣＰＵ３０１を使用し、ハードディスク駆動装置３２０のデータ格納部３２２に格納されている半構造電文のスキーマ及び検証ファイルを取得し、ＣＰＵ＿ＲＡＭ３１０の作業領域３１２に格納する。
【００３７】
ここで、ＣＰＵ３０１は、タグ名の文字列マッチングのための有限オートマトンをスキーマから生成すると共に、ＧＰＵ３４０で検証処理を並列実行させるための並列半構造電文検証プログラムを検証ファイルから生成する。生成された有限オートマトンは、ＧＰＵ３４０のＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭの作業領域３５２とＧＰＵ＿ＬＯＣＡＬ＿ＲＡＭの作業領域３６１に転送される。また、生成された並列半構造電文検証プログラムは、ＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭ３５０の並列半構造電文検証プログラム３５１に転送される。このプログラムの処理内容の詳細は後述する。
【００３８】
（ステップ６０２）
半構造電文検証コンピュータ１２０は、クライアントコンピュータ１００から送信された半構造電文１４０を通信装置３３２を介して受信すると、これをＣＰＵ＿ＲＡＭ３１０の作業領域３１２に格納する。
【００３９】
（ステップ６０３）
半構造電文検証コンピュータ１２０は、通信装置３３２を介して受信した半構造電文１４０に対し、不要文字の削除やタグ構造の生成等の検証に必要な前処理を実行する。このとき、半構造電文検証コンピュータ１２０は、前処理で生成された不要文字を削除した半構造電文やタグ構造のデータを、ＧＰＵ３４０内のＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭの作業領域３５２及びＧＰＵ＿ＬＯＣＡＬ＿ＲＡＭの作業領域３６１に転送する。これら前処理の詳細についても後述する。
【００４０】
（ステップ６０４）
半構造電文検証コンピュータ１２０は、ＧＰＵ３４０の多数のＰＵ３４１を利用して並列半構造電文検証プログラム３５１を実行し、検証ファイルに記述された内容の検証を半構造電文に対して行う。この並列検証処理の詳細については後述する。
【００４１】
（ステップ６０５）
半構造電文検証コンピュータ１２０は、ステップ６０４で得られた検証結果を、通信装置３３２を介して半構造電文管理コンピュータ１３０に通知する。
【００４２】
（３）初期化プロセスの詳細
図６の初期化プロセス６０１の詳細内容を、図７を用いて説明する。
【００４３】
（ステップ７０１）
半構造電文検証コンピュータ１２０は、ハードディスク駆動装置３２０のデータ格納部３２２から半構造電文１４０のスキーマを取得し、ＣＰＵ３０１を介して、タグ名を文字列マッチングするための有限オートマトンを作成する。
【００４４】
図８は、ＧＰＵ３４０における処理に適したデータ構造を持つ有限オートマトンを、スキーマから生成する手順を説明する図である。まず、ＣＰＵ３０１は、スキーマからタグ名８０１を抽出する。ここでは、３つのタグ名「ＡＢ、ＢＣ、ＡＣＤ」が得られる。次に、ＣＰＵ３０１は、この３つのタグ名から有限オートマトン８０２を作成する。有限オートマトン８０２のリーフＥｎｄはアルファベット以外の文字が来ることを意味している。
【００４５】
このタグ名の文字列マッチングのための有限オートマトン８０２の木構造をＢＰ表現で表すと８０３のようになる。ＢＰ表現８０３において、「（」をビット０、「）」をビット１に置換したビット列を「タグ名の有限オートマトンのＢＰ表現５１１」とする。このとき、タグ名の有限オートマトンのＢＰ表現５１１のビット列の対応するノードの順番に従い作成した、有限オートマトン８０２の各ノードの文字の配列を「タグ名の有限オートマトンに対応した文字配列５０１」とする。さらに、タグ名の有限オートマトンのＢＰ表現５１１のビット列の対応するノードの順番に従い、（Ｅｎｄ）ノードの順番の位置にそのタグのＩＤを格納した「タグ名の有限オートマトンに対応したタグＩＤ配列５０２」を生成する。
【００４６】
このように、タグ名の有限オートマトン８０２の構造をＢＰ表現で表したことで、半構造電文をメモリ容量の小さいＧＰＵ＿ＬＯＣＡＬ＿ＲＡＭ３６０の作業領域３６１にも格納できるようになり、各ＰＵ３４１が高速にタグ名の文字列マッチングが行えるようになる。
【００４７】
（ステップ７０２）
半構造電文検証コンピュータ１２０は、ハードディスク駆動装置３２０のデータ格納部３２２に格納された検証ファイルを取得し、ＣＰＵ３０１を介して、ＧＰＵ３４０の多数のＰＵ３４１で並列に検証するための並列半構造電文検証プログラムを作成する。この並列半構造電文検証プログラムの内容については後述する。
【００４８】
（ステップ７０３）
半構造電文検証コンピュータ１２０は、ＣＰＵ３０１を通じ、ステップ７０１で作成したタグ名の有限オートマトンのデータを、図５に従いＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭ３５０及びＧＰＵ＿ＬＯＣＡＬ＿ＲＡＭ３６０の作業領域に格納する。また、半構造電文検証コンピュータ１２０は、ＣＰＵ３０１を通じ、ステップ７０２で作成した並列半構造電文検証プログラム３５１を、ＧＰＵ_ＧＬＯＢＡＬ＿ＲＡＭ３５０のデータ領域に格納する。
【００４９】
（４）半構造電文検証前処理プロセスの詳細
図６の半構造電文検証前処理プロセス６０３の詳細について、図９を用いて説明する。
【００５０】
（ステップ９０１）
半構造電文検証コンピュータ１２０は、ＣＰＵ３０１を用い、ＣＰＵ＿ＲＡＭの作業領域３１２に格納されている受信した半構造電文１４０から、タブやスペースや改行等の不要文字を削除する。これは、後述の処理においてタグ名の文字列マッチングを実行する際に誤ったマッチングを回避するためと、後述するステップ９０３において、ＣＰＵ＿ＲＡＭの作業領域３１２にある半構造電文１４０をＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭの作業領域３５２に転送する際に、転送量を削減し、転送時間及びＧＰＵ_ＧＬＯＢＡＬ＿ＲＡＭの作業領域３５２で使用するメモリサイズを削減するためである。
【００５１】
図１０に不要文字を削除した例を示す。受信した半構造電文１４０からタブ、スペース、改行文字が削除され、不要文字を削除した半構造電文５０３が生成されている。
【００５２】
（ステップ９０２）
半構造電文検証コンピュータ１２０は、ＣＰＵ３０１を用い、ステップ９０１で作成した不要文字を削除した半構造電文５０３からタグ構造を生成する。
【００５３】
図１０に、タグ構造を生成する具体例を示す。半構造電文検証コンピュータ１２０は、不要文字を削除した半構造電文５０３において、「<」をビット０に、「</」及び「/>」をビット１に置き換え、それ以外の文字は無視したビット列（半構造電文内のタグ構造のＢＰ表現５１２）を生成する。また、半構造電文検証コンピュータ１２０は、「<」、「</」、「/>」に対応したタグ名の位置の配列（半構造電文内のタグ位置の配列５０４）も同時に生成する。ただし、あくまで「<」、「</」、「/>」をビットに置換えただけで、タグ名自身は特定していない。
【００５４】
このように、前処理として逐次処理を得意とするＣＰＵ３０１を介してタグの構造と位置を特定しておくことで、後の処理で多数のＰＵ３４１を介して並列検証を効率的に行うことができる。タグ名の位置を特定しておくことで、各ＰＵ３４１がタグ名と関係無い位置から文字列マッチングを開始することを回避できる。並列処理では構築が困難なタグ構造を特定しておくことで、検証に必要な親ノードや子ノードを容易に見つけることができる。特にタグ構造は簡潔データ構造を利用して、ＧＰＵ＿ＬＯＣＡＬ＿ＲＡＭ３６０のメモリ容量の小さい領域に格納することで高速な親ノードや子ノードの検索が可能となる。
【００５５】
（ステップ９０３）
半構造電文検証コンピュータ１２０は、ステップ９０１で生成した不要文字を削除した半構造電文５０３をＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭの作業領域３５２に転送する。さらに、半構造電文検証コンピュータ１２０は、ステップ９０２で生成した半構造電文内のタグ構造のＢＰ表現５１２をＧＰＵ＿ＬＯＣＡＬ＿ＲＡＭの作業領域３６１に、半構造電文内のタグ位置の配列５０４を、ＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭの作業領域３５２に格納する。
【００５６】
（５）半構造電文検証プロセスの詳細
図６の半構造電文検証プロセス６０４の詳細を、図１１を用いて説明する。まず、半構造電文検証コンピュータ１２０は、ＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭ３５０の並列半構造電文検証プログラム３５１を各ＰＵ３４１で実行させる。以下、各ＰＵ３４１の処理について説明する。
【００５７】
（ステップ１１０１）
半構造電文検証コンピュータ１２０は、各ＰＵ３４１が順番に一意に自身に割り当てられたスレッドＩＤを取得する。
【００５８】
（ステップ１１０２）
半構造電文検証コンピュータ１２０は、各ＰＵ３４１が、ＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭの作業領域３５２に格納された半構造電文内のタグ位置の配列５０４から、ステップ１１０１で取得したスレッドＩＤに対応するタグ位置を取得する。
【００５９】
（ステップ１１０３）
半構造電文検証コンピュータ１２０は、各ＰＵ３４１にタグの文字列マッチングを行わせる。各ＰＵ３４１は、ステップ１１０２で取得したタグ位置を始点として、タグ名の有限オートマトンのＢＰ表現５１１とタグ名の有限オートマトンに対応した文字配列５０１を参照してタグ名の文字列マッチングを行い、タグ名を特定する。さらに、半構造電文検証コンピュータ１２０は、有限オートマトンにより特定したタグ名に基づいて、タグ名の有限オートマトンの対応したタグＩＤ配列５０２からタグＩＤを取得する。また、半構造電文検証コンピュータ１２０は、半構造電文内のタグ構造のＢＰ表現５１２を参照し、スレッドＩＤの番号に対応するビットが０の場合は取得したタグＩＤの符号を「＋」に、ビットが１の場合はタグＩＤの符号を「−」にして、半構造電文内のタグＩＤの配列５０５においてスレッドＩＤの番号に対応する位置に、この符号付きタグＩＤを格納する。
【００６０】
（ステップ１１０４）
半構造電文検証コンピュータ１２０は、各ＰＵ３４１間の同期をとる。
【００６１】
（ステップ１１０５）
半構造電文検証コンピュータ１２０は、ＰＵ３４１を利用して、半構造電文内のタグＩＤの配列５０５の総和を求める。もし総和が０になっていれば、開始タグと終了タグが対応していることがわかる。
【００６２】
（ステップ１１０６）
半構造電文検証コンピュータ１２０は、各ＰＵ３４１が検証ファイルのＬｅｔ句４０１で指定されたタグ及び／又はコンテンツを、不要文字を削除した半構造電文５０３から取得する。
【００６３】
ここでは、図４に例示した検証ファイルの場合を考える。各ＰＵ３４１は、半構造電文内のタグＩＤの配列５０５から自身のスレッドＩＤの番号の値を取得する。各ＰＵ３４１は、この取得した値がPmtInfのタグＩＤと一致している場合は、半構造電文内のタグ構造のＢＰ表現５１２を利用して、親ノードのタグＩＤを取得する。この親ノードのタグＩＤが「document」のタグＩＤと一致するならば、各ＰＵ３４１は、ＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭの作業領域３５２に確保した変数＄ａの配列内のスレッドＩＤに対応する番号の位置に存在することを意味するビット１を設定する。親ノードのタグＩＤが「CdtTrfTxInf」のタグＩＤと一致するならば、各ＰＵ３４１は、ＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭの作業領域３５２に確保した変数＄ｂの配列内のＰＵ３４１のスレッドＩＤに対応する番号の位置に存在することを意味するビット１を設定する。
【００６４】
（ステップ１１０７）
半構造電文検証コンピュータ１２０は、各ＰＵ３４１間の同期をとる。
【００６５】
（ステップ１１０８）
半構造電文検証コンピュータ１２０は、各ＰＵ３４１が、ステップ１１０６で取得した結果を用いて検証ファイルのＳａｔｉｓｆｙ句４０３を評価する。半構造電文検証コンピュータ１２０は、評価結果がＴｒｕｅの場合はビット１を、Ｆａｌｓｅの場合はビット０を、検証結果の配列５０６のスレッドＩＤの番号の位置に格納する。
【００６６】
（ステップ１１０９）
半構造電文検証コンピュータ１２０は、各ＰＵ３４１間の同期をとる。
【００６７】
（ステップ１１１０）
半構造電文検証コンピュータ１２０は、ＰＵ３４１を利用して検証結果の配列５０６を集計し、その後、検証結果をまとめて結果をＣＰＵ＿ＲＡＭの作業領域３１２に転送する。検証ファイルのＥｖｅｒｙ/Ｓｏｍｅ句４０２において、Ｅｖｅｒｙが指定されている場合は、検証結果の配列５０６が全てビット１（Ｔｒｕｅ）であること、Ｓｏｍｅが指定されている場合は、検証結果の配列５０６にビット１（Ｔｒｕｅ）が存在しているならば、検証ファイルで指定された制約を半構造電文１４０は満たしていることになる。
【００６８】
（６）実施例の効果
(i)本実施例によれば、検証対象となるタグ及び／又はコンテンツを指定するＬｅｔ句４０１、全ての検証対象となるタグ及び／又はコンテンツが制約を満たすのかを指定するＥｖｅｒｙ句／制約を満たすタグ及び／又はコンテンツが存在するかを指定するＳｏｍｅ句４０２、満たすべき制約を指定するＳａｔｉｓｆｙ句４０３を記述可能な検証ファイルを提供することができる。これにより、タグ及び／又はコンテンツ間の相互関係に関する制約を記述することができる。
(ii)本実施例に係る半構造電文検証コンピュータ１２０では、ＣＰＵ３０１による前処理において、半構造電文のタグ位置を予め特定しておくことにより、ＧＰＵ３４０を構成する各ＰＵ３４１は、タグの位置からタグ名の文字列マッチングを行うことができる。このため、タグの数だけ処理を並列化できる。この結果、従来手法よりも高速な半構造電文の解析が可能となる。
(iii)本実施例に係る半構造電文検証コンピュータ１２０では、ＣＰＵ３０１による前処理において、半構造電文のタグ構造を予め特定し、更に簡潔データ構造を利用してタグ構造を圧縮し、ＧＰＵ３４０を構成する多数のＰＵ３４１のローカルメモリに格納しておくことにより、相互関係に関する制約を検証するためのタグ及び／又はコンテンツを高速に取得することができる。
【００６９】
このように、本実施例に係る半構造電文検証コンピュータ１２０によれば、タグ及び／又はコンテンツ間の相互関係に関する制約を、多数のＰＵ３４１を利用して、効率的に検証することができる。
【００７０】
なお、本発明は上述した実施例に限定されるものでなく、様々な変形例が含まれる。例えば、上述した実施例は、本発明を分かりやすく説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、実施例の一部を他の構成を追加、削除又は置換することも可能である。例えば半構造電文検証コンピュータ１２０と半構造電文管理コンピュータ１３０は同一のコンピュータ上に形成しても良い。
【００７１】
また、上述した各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路その他のハードウェアとして実現しても良い。また、上記の各構成、機能等は、プロセッサがそれぞれの機能を実現するプログラムを解釈し、実行することにより実現しても良い。すなわち、ソフトウェアとして実現しても良い。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリやハードディスク、SSD（Solid State Drive）等の記憶装置、ICカード、SDカード、DVD等の記憶媒体に格納することができる。
【００７２】
また、制御線や情報線は、説明上必要と考えられるものを示すものであり、製品上必要な全ての制御線や情報線を表すものでない。実際にはほとんど全ての構成が相互に接続されていると考えて良い。
【符号の説明】
【００７３】
１００…クライアントコンピュータ
１１０…インターネット
１２０…半構造電文検証コンピュータ
１３０…半構造電文管理コンピュータ
３０１…ＣＰＵ
３４０…ＧＰＵ
３５０…ＧＰＵ＿ＧＬＯＢＡＬ＿ＲＡＭ
３６０…ＧＰＵ＿ＬＯＣＡＬ＿ＲＡＭ
【図１】
2014063244.tif 000003
【図２】
2014063244.tif 000004
【図３】
2014063244.tif 000005
【図４】
2014063244.tif 000006
【図５】
2014063244.tif 000007
【図６】
2014063244.tif 000008
【図７】
2014063244.tif 000009
【図８】
2014063244.tif 000010
【図９】
2014063244.tif 000011
【図１０】
2014063244.tif 000012
【図１１】
2014063244.tif 000013