(57)【要約】【課題】テスト・スイート最小化を利用した方法、装置、およびコンピュータ・プログラム製品を提供する。【解決手段】方法、コンピューティング・システム、およびコンピュータ・プログラム製品が、本発明の実施形態を実装し、それらの実施形態は、第１の数のカテゴリを定義することであって、カテゴリの各々がそれぞれの第２の数の値を有する、定義することと、試験問題のセット内の各々の所与の試験問題に、それぞれの第３の数のカテゴリ、および、第３の数のカテゴリの各々に対する少なくとも１つの所与の値を割り当てることとを含む。要件のセットが検索され、各々の所与の要件が、それぞれの第４の数のカテゴリ要件、および、カテゴリ要件の各々に対するそれぞれの値要件を含み、テスト・スイート最小化アルゴリズムが、カテゴリ要件および値要件を含む、カテゴリおよびそれぞれの値を有する、試験問題の最小サブセットを選択するために実行される。【選択図】図１
2016212846.tif 000002
【特許請求の範囲】
【請求項１】
方法であって、
第１の数のカテゴリを定義するステップであって、前記カテゴリの各々がそれぞれの第２の数の値を有する、前記定義するステップと、
試験問題のセット内の各々の所与の試験問題に、それぞれの第３の数のカテゴリ、および、前記第３の数のカテゴリの各々に対する少なくとも１つの所与の値を割り当てるステップと、
要件のセットを検索するステップであって、各々の所与の要件が、それぞれの第４の数のカテゴリ要件、および、前記カテゴリ要件の各々に対するそれぞれの値要件を含む、前記検索するステップと、
テスト・スイート最小化アルゴリズムを実行して、前記カテゴリ要件および前記値要件を含む、カテゴリおよびそれぞれの値を有する、前記試験問題の最小サブセットを選択するステップと
を含む、方法。
【請求項２】
前記問題が医学試験問題を含む、請求項１に記載の方法。
【請求項３】
所与のカテゴリが、患者のデモグラフィック、病気の特性、および医学テスト結果からなる群から選択される、請求項２に記載の方法。
【請求項４】
所与の問題が画像を含み、前記画像に対する前記カテゴリの各々が、前記画像の特徴を含む、請求項１に記載の方法。
【請求項５】
前記要件が第１の要件を含み、前記方法が、所与の第１の要件の対象数を含む第２の要件を含む、請求項１に記載の方法。
【請求項６】
所与のカテゴリが複数の問題タイプを含み、所与の試験問題に対する所与のカテゴリが所与の問題タイプを含む、請求項１に記載の方法。
【請求項７】
所与の要件が、特定の問題タイプを含む、前記試験問題の対象数を含む、請求項６に記載の方法。
【請求項８】
装置であって、
試験問題のセットを記憶するように構成される記憶デバイスと、
プロセッサであって、
第１の数のカテゴリを定義することであって、前記カテゴリの各々がそれぞれの第２の数の値を有する、前記定義することと、
試験問題の前記セット内の各々の所与の試験問題に、それぞれの第３の数のカテゴリ、および、前記第３の数のカテゴリの各々に対する少なくとも１つの所与の値を割り当てることと、
要件のセットを検索することであって、各々の所与の要件が、それぞれの第４の数のカテゴリ要件、および、前記カテゴリ要件の各々に対するそれぞれの値要件を含む、前記検索することと、
テスト・スイート最小化アルゴリズムを実行して、前記カテゴリ要件および前記値要件を含む、カテゴリおよびそれぞれの値を有する、前記試験問題の最小サブセットを選択することと
を行うように構成される、前記プロセッサと
を備える、装置。
【請求項９】
前記問題が医学試験問題を含む、請求項８に記載の装置。
【請求項１０】
所与のカテゴリが、患者のデモグラフィック、病気の特性、および医学テスト結果からなる群から選択される、請求項９に記載の装置。
【請求項１１】
所与の問題が画像を含み、前記画像に対する前記カテゴリの各々が、前記画像の属性を含む、請求項８に記載の装置。
【請求項１２】
前記要件が第１の要件を含み、前記プロセッサが、所与の第１の要件の対象数を含む第２の要件を定義するように構成される、請求項８に記載の装置。
【請求項１３】
所与のカテゴリが複数の問題タイプを含み、所与の試験問題に対する所与のカテゴリが所与の問題タイプを含む、請求項８に記載の装置。
【請求項１４】
所与の要件が、特定の問題タイプを含む、前記試験問題の対象数を含む、請求項１３に記載の装置。
【請求項１５】
請求項１〜７の何れか１項に記載の方法の各ステップをコンピュータに実行させる、
コンピュータ・プログラム。
【請求項１６】
前記コンピュータ・プログラムをコンピュータ可読記憶媒体に記録した、コンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には試験設計に関し、詳細には、テスト・スイート最小化を使用して、試験のための問題を選択することに関する。
【背景技術】
【０００２】
組合せテストとしても知られている組合せテスト設計（ＣＴＤ：CombinatorialTest Design）は、テスト空間が、カテゴリ、それらのそれぞれの値、および、値組合せに関する制約のセットによりモデリングされる、効果的なソフトウェア・テスト計画立案技法である。このモデルにより表されるテスト空間は、制約に違反しない、各々のカテゴリへの１つの値の任意の割り当てである。空間のサブセットが、次いで、それが、あらゆるｔ個のカテゴリのすべての有効な値組合せ（相互作用としても知られている）を包含するように自動的に構築されるものであり、ただしｔは、通常はユーザ入力である。換言すれば、ｔ個のカテゴリのあらゆるセットに対して、それらに対するｔ個の値の任意の組合せが、（制約によって、それを内包する有効なテストが存在しないということでない限り）テスト計画で少なくとも１回出現することになる。
【０００３】
一般的に、異なるレベルの相互作用が、カテゴリの異なるサブセットに対して要求され得る。ＣＴＤの最も普通の用途は、ペアワイズ・テストとして知られており、カテゴリのあらゆるペアの相互作用が包含されなければならない。ＣＴＤの結果での各々のテストは、すべてのカテゴリへの値の割り当てであり、具体的な実行可能なテストに変換される必要がある、高レベル・テストまたはテスト・シナリオを表す。
【０００４】
上記の説明は、本分野での関係のある技術分野の一般的な概観として提示されるものであり、その説明が内包する情報のいずれかが、本特許出願に対する従来技術の構成物となるということの自認と解釈すべきではない。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の課題は、テスト・スイート最小化を利用した方法、装置、およびそのコンピュータ・プログラムを提供することである。
【課題を解決するための手段】
【０００６】
本発明の実施形態によって、方法が提供され、方法は、第１の数のカテゴリを定義するステップであって、カテゴリの各々がそれぞれの第２の数の値を有する、定義するステップと、試験問題のセット内の各々の所与の試験問題に、それぞれの第３の数のカテゴリ、および、第３の数のカテゴリの各々に対する少なくとも１つの所与の値を割り当てるステップと、要件のセットを検索するステップであって、各々の所与の要件が、それぞれの第４の数のカテゴリ要件、および、カテゴリ要件の各々に対するそれぞれの値要件を含む、検索するステップと、テスト・スイート最小化アルゴリズムを実行して、カテゴリ要件および値要件を含む、カテゴリおよびそれぞれの値を有する、試験問題の最小サブセットを選択するステップを含む。
【０００７】
本発明の実施形態によって、装置がさらに提供され、装置は、試験問題のセットを記憶するように構成される記憶デバイスと、プロセッサであって、第１の数のカテゴリを定義することであって、カテゴリの各々がそれぞれの第２の数の値を有する、定義することと、試験問題のセット内の各々の所与の試験問題に、それぞれの第３の数のカテゴリ、および、第３の数のカテゴリの各々に対する少なくとも１つの所与の値を割り当てることと、要件のセットを検索することであって、各々の所与の要件が、それぞれの第４の数のカテゴリ要件、および、カテゴリ要件の各々に対するそれぞれの値要件を含む、検索することと、テスト・スイート最小化アルゴリズムを実行して、カテゴリ要件および値要件を含む、カテゴリおよびそれぞれの値を有する、試験問題の最小サブセットを選択することとを行うように構成される、プロセッサとを含む。
【０００８】
本発明の実施形態によって、コンピュータ・プログラムがさらに提供され、コンピュータ・プログラムは、コンピュータ可読プログラム・コードが一体として具現化される非一時的コンピュータ可読記憶媒体に記録され、コンピュータ可読プログラム・コードが、第１の数のカテゴリを定義することであって、カテゴリの各々がそれぞれの第２の数の値を有する、定義することを行うように構成されるコンピュータ可読プログラム・コードと、試験問題のセット内の各々の所与の試験問題に、それぞれの第３の数のカテゴリ、および、第３の数のカテゴリの各々に対する少なくとも１つの所与の値を割り当てることを行うように構成されるコンピュータ可読プログラム・コードと、要件のセットを検索することであって、各々の所与の要件が、それぞれの第４の数のカテゴリ要件、および、カテゴリ要件の各々に対するそれぞれの値要件を含む、検索することを行うように構成されるコンピュータ可読プログラム・コードと、テスト・スイート最小化アルゴリズムを実行して、カテゴリ要件および値要件を含む、カテゴリおよびそれぞれの値を有する、試験問題の最小サブセットを選択することを行うように構成されるコンピュータ可読プログラム・コードを含む。
【０００９】
本開示を、本明細書では、単に例として、付随する図面を参照して説明する。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施形態による、テスト・スイート最小化アルゴリズムを使用して、試験のための問題を選択するように構成されるコンピュータ・システムを概略的に示すブロック図である。
【図２】本発明の実施形態による、テスト・スイート最小化アルゴリズムを使用して、試験のための問題を選択する方法を概略的に示すフロー図である。
【発明を実施するための形態】
【００１１】
健康管理システムの複雑度および精巧化が指数関数的に高まることに伴って、健康管理要員の技量を絶えず向上させることが、より不可欠になってきている。したがって健康管理開業医は、それらの開業医らの専門家としての人生の全体を通して数多くの講習に出席すること、および、それらの開業医らの専門家としての技量を証明するために数多くの専門家としてのテストを受けることが期待される。さらに、画像診断が広範にわたっていることを考えれば、臨床知識および医用画像理解の両方をテストすることは不可欠である。例えば、多くの国での放射線科医は、初期に上級の検定試験に合格し、その後、年１回の再検定試験に合格することが期待される。
【００１２】
患者の生命は医師の技量に左右されるので、一般の人々は、テストが包括的なだけでなく公正なものになるということを要望する。現在そのようなテストの運営管理を行う組織体は、圧倒的に手作業のテスト準備に依拠し、結果として、テスト準備のコストは非常に高い。これらの高いコストにもかかわらず、試験は多くの事例で、不公正であることに対して、および、問題が受験者に漏れることに対しての両方で批判される。実際、（受験者が、正しい答えがわからない場合に）問題構造を分析することにより、どのように好結果の見込みを高めるかに関する助言を提案する「処方箋本」を見つけ出すことが可能である。
【００１３】
本発明の実施形態は、相互作用ベースのテスト・スイート最小化（ＩＴＳＭ：interaction-basedtest suite minimization）アルゴリズムのテスト・スイート最小化アルゴリズムを使用して、試験問題のセットから、要件のセットを満足させる試験問題の最小サブセットを選択するための方法およびシステムを提供する。本明細書の下記で解説するように、ＩＴＳＭ（本明細書では、テスト・スイート最小化アルゴリズムとも称する）は、既存のテスト・スイートを低減し、一方で、その相互作用包含範囲を保持する。ＣＴＤと同様に、ＩＴＳＭは、テスト空間のカテゴリ、およびそれらの値を定義することを要するが、そのＩＴＳＭは、値間の制約を定義することを要さない。そのＩＴＳＭは次いで、各々のテストがカテゴリへの値の割り当ての形式でのものであるテスト・スイートを与えられ、そのｔワイズ値組合せを保持するテスト・スイートのサブセットを選択する。明らかに、他のテスト最小化技法のように、ＩＴＳＭは、一方では、省略されるものが重要なものではないように、十分に広範および代表的であり、他方では、完了まで走らせるには大きすぎるものであり、冗長なテスト・ケースを内包し得る、既存のテスト・スイートが存在するときにのみ適用可能である。
【００１４】
図１は、本発明の実施形態による、試験問題セット２２から、要件セット２６を満たす試験問題のセットのサブセット２４を選択するように構成されるコンピュータ２０を概略的に示すブロック図である。コンピュータ２０は、プロセッサ２８と、メモリ３０と、記憶デバイス３２とを備える。動作中は、プロセッサは、メモリ３０から、サブセット２４を要件セット２６に基づいて選択するテスト・スイート最小化アプリケーション３４を実行する。テスト・スイート最小化アプリケーション３４は、本明細書の下記で提示する付録で説明するＩＴＳＭアルゴリズムを実装する。
【００１５】
記憶デバイス３２は典型的には、問題セット２２、要件セット２６、選択されたサブセット２４、答えセット３６、画像セット３８、およびカテゴリ・テーブル４０を記憶する、ハード・ディスク・ドライブまたはソリッド・ステート・ディスク（ＳＳＤ）ドライブを備える。問題セット２２は、複数の試験問題４２を含み、答えセット３６は、各々の問題４２に対する複数の答え（示さない）を含む。
【００１６】
カテゴリ・テーブル４０は、複数のカテゴリ・レコード４４を含み、カテゴリ・レコードの各々は、それぞれのカテゴリ４６、および複数のそれぞれの値４８を含む。所与のカテゴリ４６の例は、民族性、性別、および年齢範囲などのデモグラフィック、症状場所および症状重症度などの病気特性、ならびに医学テスト結果を含むが、それらに限定されない。上で説明したように、各々のカテゴリ４６は、複数のそれぞれの値４８を有する。例えば、以下の通りである。
・「性別」カテゴリ４６に対する値は、「男性」および「女性」を含み得る。
・「年齢範囲」カテゴリ４６に対する値は、「０〜１０」、「１１〜２０」、「２１〜４０」、「４１〜６０」、および「６１＋」を含み得る。
・「病気特性」カテゴリ４６に対する値は、「心性」、「肺性」、「免疫学的」、「神経性」、その他を含み得る。
・「医学テスト結果」カテゴリ４６に対する値は、「白血球数」、「ナトリウム・レベル」、「グルコース・レベル」、その他を含み得る。
【００１７】
一部の実施形態では、所与のカテゴリ４６は、複数のサブ・カテゴリを有し得る。例えば、患者に対する所与のカテゴリ４６「病気」は、「１次病気特性」および「２次病気特性」サブ・カテゴリを有し得る。
【００１８】
画像セット３８は、複数の画像レコード５０を含み、画像レコードの各々は、画像５２、および複数の画像データ・エントリ５４を含む。画像５２は、Ｘ線および超音波などのデジタル画像を含み得るものであり、各々の画像データ・エントリは、特徴５６、確率スコア５８、および所与のカテゴリ４６を含む。本明細書の実施形態では、画像データ・エントリ５４、ならびに、それらのそれぞれの特徴５６、スコア５８、およびカテゴリ４６は、画像属性と称する場合もある。加えて一部の実施形態では、各々の特徴は、複数の画像値（示さない）を有し得る。例えば、以下の通りである。
・所与の特徴５６は、可能な画像値「悪性」、「良性」、および「不明」を伴う「病巣タイプ」を含み得る。
・所与の特徴５６は、可能な画像値「高」、「中」、および「低」を伴う「乳房密度」を含み得る。
・所与の特徴５６は、可能な画像値「平滑」、「不鮮明」、および「針骨状（Spiculated）」を伴う「境界」を含み得る。
・所与の特徴５６は、可能な画像値「腋窩」、「線維腺組織」、「脂肪組織」、および「皮膚」を伴う「場所」を含み得る。
・所与の特徴５６は、可能な画像値「ＣＣ」および「ＭＬＯ」を伴う「ビュー」を含み得る。
・所与の特徴５６は、可能な画像値「右」および「左」を伴う「側」を含み得る。
・所与の特徴５６は、可能な画像値「困難」、「中程度」、および「容易」を伴う「難易度」を含み得る。
【００１９】
一部の実施形態では、テスト・スイート最小化アプリケーション３４は、画像レコード５０を「画像ベースの」問題として扱い得る。換言すれば、要件セット２６に基づいて、選択されたサブセット２４は、１つまたは複数の画像レコード５０を参照し得る問題４２を含む。画像ベースの問題に対して、プロセッサ２８は、テスト・スイート最小化アプリケーション３４を適用して、各々の画像ベースの問題に対して、対応する意味表現、およびその関連する確率スコア５８を作成し得る。
【００２０】
例えば超音波の腫瘍画像に対して、コンピュータ２０は、関連性のある診断特徴５６（例えば、均質性、エコー輝度、境界定義、腫瘍形状、向き）の推定物を自動的に提供し得る。各々の特徴５６は、画像難易度の推定のために所与の確率を使用する必要がある場合がある。同様にこれらの特徴は、コンピュータにより、試験（すなわち、サブセット２４）が、画像特徴の包含範囲で、および、画像複雑度の見地での両方で良好にバランスがとれているということを確実にするために使用されることになる。
【００２１】
要件セット２６は、複数の要件６０を含み、要件の各々は、複数のカテゴリ要件６２、および、カテゴリ要件の各々に対するそれぞれの値要件を含む。要件６０は、医学試験に出るべきであるカテゴリ値の組合せを定義する。所与の要件６０は、カテゴリ要件６２および値要件６４の複数のペア（本明細書では、カテゴリ／値ペアとも称する）であり得る。カテゴリ／値ペアの例は、以下のものを含む。
・病巣タイプ＝悪性、ただし、「病巣タイプ」は所与のカテゴリ要件６２を構成し、「悪性」は所与の値要件６４を構成する。
・乳房密度＝中、ただし、「乳房密度」は所与のカテゴリ要件６２を構成し、「中」は所与の値要件６４を構成する。
・境界＝平滑、ただし、「境界」は所与のカテゴリ要件６２を構成し、「平滑」は所与の値要件６４を構成する。
【００２２】
一部の実施形態では要件６０は、「病巣タイプ、乳房密度、場所、およびビューからの任意の３つのカテゴリのすべての値組合せ」などの、カテゴリ／値ペアのタプルにより定義され得る。加えて、本明細書の上記で説明した２つのタイプの要件の組合せが可能である。
【００２３】
所与の要件６０の別の例は、臨床試験定義に対するものとなる。例えば要件は、試験が、１０個の主要な疾病の各々からの少なくとも１つの問題、および、２０個のより頻度の高くない疾病のセットからの少なくとも５つの問題を内包するということを指示し得る。換言すれば要件６０は、特定のカテゴリ４６（または、カテゴリ４６の組合せ）を包含する問題に対する対象数を含み得る。同様に要件６０は、患者年齢、症状、その他などのカテゴリ要件６２の選定を制御し得る。
【００２４】
一部の実施形態では、問題４２に対する所与のカテゴリは、問題タイプを指示し得るものであり、所与の要件は、所与の問題タイプに対する問題の対象数を指示し得る。例えば所与の要件６０は、サブセット２４内の選択された問題の１０％が陰性タイプのものであり、１０％がブール式を内包することになり、８０％が陽性タイプのものとなるということを指示し得る。
【００２５】
追加的な実施形態では、所与のカテゴリ４６は、所与の問題４２の難易度を指示し得るものであり、所与の要件６０は、画像難易度（画像カテゴリの１つ）、診断頻度、および、答えの間の類似度の関数として定義される試験難易度の意向を内包し得る。難易度尺度は、例えば１〜１００に正規化されることになる。したがって、所与の要件を変更することにより、試験監督者は、試験に対する難易度レベルをセットすることが可能である。
さらなる実施形態では問題４２は、既存の病院記録から作成され得る。動作中にプロセッサ２８は、患者のデータ・フォルダから、臨床情報および診断画像の両方を検索し得る。次いで、上記で説明した技法を使用して、プロセッサ２８は、１つまたは複数の特定の科目を包含する、他とは異なる試験を作成するために、実際の現場事例を分析し得る。
【００２６】
本発明の実施形態では、要件のセットを与えられると、プロセッサ２８は、問題または画像あるいはその両方のセットの内容を与えられる、要件の可能な限り多くのものを満足させるサブセット２４を含む試験を生成するために、テスト最小化アルゴリズム（本明細書の下記の付録で説明するものなど）を適用し得る。アルゴリズムはさらには、試験が可能な限り短いということを確実にし、そのアルゴリズムは、要件に関する最大の積載量を有する問題を選定する。
【００２７】
一部の実施形態では、問題および画像セットは、すべての要件を満足させるとは限らない場合がある。例えば、腋窩での悪性腫瘍を示す所与の画像５２に対する所与の要件６０が存在する場合があるが、そのような画像が画像セット内に存在しない場合がある。アプリケーション３４は、そのような事例を報告し得るものであり、組合せテスト設計が、これらの要件を満足させる試験を生成することを可能とすることになる、データベース（すなわち、問題および画像セット）に対する新しいエントリの最小限のセットを定義するために使用され得る。
【００２８】
プロセッサ２８は、本明細書で説明する機能を実行するようにソフトウェアまたはファームウェアでプログラムされる、汎用中央処理装置（ＣＰＵ）または専用埋め込み型プロセッサを備える。ソフトウェアは、例えば、コンピュータ２０に電子的な形式でネットワークを介してダウンロードされ得るものであり、またはそのソフトウェアは、光、磁気、もしくは電子のメモリ媒体などの非一時的有形媒体上で提供され得る。あるいは、プロセッサの機能の一部またはすべては、専用もしくはプログラマブルのデジタル・ハードウェア構成要素により、または、ハードウェアおよびソフトウェア要素の組合せを使用して実行され得る。
【００２９】
本発明は、システム、方法、またはコンピュータ・プログラム製品あるいはそれらの組合せであり得る。コンピュータ・プログラム製品は、プロセッサが本発明の態様を実行することを引き起こすための、コンピュータ可読プログラム命令を有する、コンピュータ可読記憶媒体（または、複数の媒体）を含み得る。
【００３０】
コンピュータ可読記憶媒体は、命令実行デバイスによる使用のために命令を保ち記憶することが可能である有形デバイスであり得る。コンピュータ可読記憶媒体は、例えば、電子記憶デバイス、磁気記憶デバイス、光記憶デバイス、電磁気記憶デバイス、半導体記憶デバイス、または、前述の任意の適した組合せであり得るが、それらに限定されない。コンピュータ可読記憶媒体のより具体的な例の非網羅的な列挙は、以下のもの：ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、消去可能プログラマブル読み出し専用メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、ポータブル・コンパクト・ディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）、デジタル・バーサタイル・ディスク（ＤＶＤ）、ｍｅｍｏｒｙ  ｓｔｉｃｋ（Ｒ）、フロッピー（Ｒ）・ディスク、命令が記録されたパンチ・カードまたは溝内の一段高い構造などの機械的に符号化されるデバイス、および、前述の任意の適した組合せを含む。コンピュータ可読記憶媒体を、本明細書では、電波もしくは他の自由伝搬する電磁波、導波管もしくは他の伝送媒体を介して伝搬する電磁波（例えば、光ファイバ・ケーブルを通過する光パルス）、または、電線を介して伝送される電気信号などの、本質的に一時的な信号であると解釈すべきではない。
【００３１】
本明細書で説明するコンピュータ可読プログラム命令は、それぞれのコンピューティング／処理デバイスにコンピュータ可読記憶媒体から、あるいは、外部コンピュータまたは外部記憶デバイスに、ネットワーク、例えば、インターネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、もしくはワイヤレス・ネットワークまたはそれらの組合せを介してダウンロードされ得る。ネットワークは、銅伝送ケーブル、光伝送ファイバ、ワイヤレス伝送、ルータ、ファイアウォール、スイッチ、ゲートウェイ・コンピュータ、またはエッジ・サーバあるいはそれらの組合せを備え得る。各々のコンピューティング／処理デバイス内のネットワーク・アダプタ・カードまたはネットワーク・インターフェイスが、コンピュータ可読プログラム命令をネットワークから受信し、コンピュータ可読プログラム命令を、それぞれのコンピューティング／処理デバイスの内部のコンピュータ可読記憶媒体での記憶のために転送する。
【００３２】
本発明の動作を実行するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令セット・アーキテクチャ（ＩＳＡ）命令、機械命令、機械依存命令、マイクロコード、ファームウェア命令、状態セッティング・データ、または、１つもしくは複数のプログラミング言語の任意の組合せで書き記される、ソース・コードもしくはオブジェクト・コードのいずれかであり得るものであり、それらのプログラミング言語は、Ｓｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋、または類するものなどのオブジェクト指向プログラミング言語、および、「Ｃ」プログラミング言語または同様のプログラミング言語などの従来型の手続き型プログラミング言語を含むものである。コンピュータ可読プログラム命令は、全体的にユーザのコンピュータ上で、部分的にユーザのコンピュータ上で、スタンド・アローン・ソフトウェア・パッケージとして、部分的にユーザのコンピュータ上、および部分的にリモート・コンピュータ上で、または、全体的にリモート・コンピュータもしくはサーバ上で実行し得る。後の方のシナリオではリモート・コンピュータは、ユーザのコンピュータに、ローカル・エリア・ネットワーク（ＬＡＮ）もしくはワイド・エリア・ネットワーク（ＷＡＮ）を含む任意のタイプのネットワークを介して接続され得るものであり、または接続は、外部コンピュータに対して（例えば、インターネット・サービス・プロバイダを使用して、インターネットを介して）行われ得る。一部の実施形態では、例えば、プログラマブル論理回路網、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、またはプログラマブル論理アレイ（ＰＬＡ）を含む電子回路網が、本発明の態様を実行するために、コンピュータ可読プログラム命令の状態情報を利用して、電子回路網を個人向け仕様にすることにより、コンピュータ可読プログラム命令を実行し得る。
【００３３】
本発明の態様を、本明細書で、本発明の実施形態による方法、装置（システム）、およびコンピュータ・プログラム製品の、フローチャート図またはブロック図あるいはその両方を参照して説明する。フローチャート図またはブロック図あるいはその両方の各々のブロック、および、フローチャート図またはブロック図あるいはその両方でのブロックの組合せが、コンピュータ可読プログラム命令により実装され得るということが理解されよう。
【００３４】
これらのコンピュータ可読プログラム命令は、コンピュータまたは他のプログラマブル・データ処理装置のプロセッサによって実行する命令が、フローチャートまたはブロック図あるいはその両方の、１つまたは複数のブロックで指定される機能／行為を実装するための手段を創出するように、汎用コンピュータ、専用コンピュータ、または他のプログラマブル・データ処理装置のプロセッサに提供されて、マシンを作り出すものであってよい。
【００３５】
これらのコンピュータ可読プログラム命令はさらには、命令が記憶されたコンピュータ可読記憶媒体が、フローチャートまたはブロック図あるいはその両方の、１つまたは複数のブロックで指定される機能／行為の態様を実装する命令を含む製造品を備えるように、コンピュータ可読記憶媒体に記憶され、コンピュータ、プログラマブル・データ処理装置、または他のデバイスあるいはそれらの組合せを、個別の様式で機能するように指示するものであってもよい。
【００３６】
コンピュータ可読プログラム命令はさらには、コンピュータ、他のプログラマブル装置、または他のデバイス上で実行する命令が、フローチャートまたはブロック図あるいはその両方の、１つまたは複数のブロックで指定される機能／行為を実装するように、コンピュータ実装プロセスを生み出すべく、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイスにロードされ、コンピュータ、他のプログラマブル装置、または他のデバイス上で一連の動作ステップを実行させるものであってもよい。
【００３７】
試験生成
図２は、本発明の実施形態による、テスト・スイート最小化アルゴリズムを使用して、試験のためのサブセット２４を選択する方法を概略的に示すフロー図である。定義ステップ７０でプロセッサ２８は、第１の数のカテゴリ４６を定義し、割り当てステップ７２でプロセッサは、それぞれの第２の数（すなわち、少なくとも１つ）の値４８をカテゴリの各々に割り当てる（すなわち、関連付ける）。一部の実施形態では、カテゴリ４６への値４８の割り当ては、手作業で実行され、カテゴリ・テーブル４０に記憶され得るものであり、プロセッサ２８は、定義ステップ７０および割り当てステップ７２を、カテゴリおよび値をカテゴリ・テーブルから検索することにより実行し得る。
【００３８】
第１の選択ステップ７４でプロセッサ２８は、問題セット２２または画像セット３８あるいはその両方を選択し、それらの問題セット２２または画像セット３８あるいはその両方の、それぞれの問題４２または画像５２あるいはその両方は、試験を作成するために使用されることになる。識別ステップ７６でプロセッサ２８は、各々の所与の問題４２に対して、それぞれの第３の数のカテゴリ４６を識別する。画像５２が試験に含まれることになる実施形態では、プロセッサ２８は、１つまたは複数のカテゴリ４６を、画像の各々に対して識別する。
【００３９】
検索ステップ７８でプロセッサ２８は、要件セット２６を検索するものであり、上で説明したように、要件セット内の各々の所与の要件６０は、それぞれの第４の数の要件６０を含み、第４の数の要件の各々は、所与のカテゴリ要件６２、および所与の値要件６４を含む。最終的に、第２の選択ステップ８０でプロセッサ２８は、（本明細書の下記で、付録で説明するような）アプリケーション３４内のテスト・スイート最小化アルゴリズムを実行し、そのアプリケーション３４は、要件６０の可能な限り多くのものを包含する、最小の数の問題４２または画像５２あるいはその両方を含むサブセット２４を選択し、方法は終了する。本発明の実施形態ではサブセット２４は、要件セット２６内のカテゴリ要件および値要件を含む（すなわち、包含する）、カテゴリ４６およびそれぞれの値４８を有する問題４２を含む。
【００４０】
図でのフローチャートおよびブロック図は、本発明の様々な実施形態によるシステム、方法、およびコンピュータ・プログラム製品の可能な実装形態の、アーキテクチャ、機能性、および動作を示す。この点に関して、フローチャートまたはブロック図での各々のブロックは、指定される論理機能を実装するための１つまたは複数の実行可能命令を含む、モジュール、セグメント、またはコードの小部分を表し得る。さらには、一部の代替的実装形態では、ブロックで記述される機能は、図で記述される順序とは無関係に行われ得るということに留意すべきである。例えば、連続して示される２つのブロックは、実際には、実質的に同時に実行される場合があり、または、ブロックは時には、含まれる機能性に応じて、逆の順序で実行される場合がある。さらには、ブロック図またはフローチャート図あるいはその両方の各々のブロック、および、ブロック図またはフローチャート図あるいはその両方でのブロックの組合せは、指定される機能もしくは行為を実行する専用ハードウェア・ベースのシステム、または、専用ハードウェアおよびコンピュータ命令の組合せにより実装され得るということが留意されよう。
【００４１】
上記で説明した実施形態は、例として記載されるということ、および、本発明は、本明細書の上記で特に示し説明したものに限定されないということが認識されよう。むしろ本発明の範囲は、本明細書の上記で説明した様々な特徴の、組合せおよび部分的組合せの両方、ならびに、前述の説明を読むことで当業者が想到することになる、および、従来技術で開示されない、それらの特徴の変形および変更を含む。
【００４２】
付録
相互作用ベースのテスト・スイート最小化（ＩＴＳＭ）アルゴリズム
この付録は、ＩＴＳＭアルゴリズムの実装形態を提示するものである。本発明の実施形態では、包含されることになる値組合せは、包含範囲対象と称する。包含範囲対象は、デカルト積（例えば、まさに標準的なＣＴＤでのような「サイズｔのあらゆる組合せ」）などの、または、包含されることになる値組合せの明示的なセットとしての、異なる形式で与えられ得る。本明細書で説明する実施形態では、テストｔは、包含範囲要件ｃを、ｃにより指定される値がｔで使用されるときに包含する。
【００４３】
テストのスイートＴ＝ｔｉ、ｉ＝１…ｎ、包含範囲対象のセットＣ＝ｃｊ、ｊ＝１…ｍ、および、Ｔ内の各々のテストにより包含される包含範囲対象を指定するマッピングＭ：Ｔ→２Ｃを与えられると、相互作用ベースのテスト・スイート最小化アルゴリズムの目的は、Ｓ＝ｓｉ、ｉ＝１…ｋ、すなわち、Ｔが包含するすべての対象を包含するＴのサブセットを見つけ出すことである。
Ｓ⊆Ｔ  ただし  ∪ｉ＝１…ｎＭ（ｔｉ）＝∪ｉ＝１…ｋＭ（ｓｉ）
【００４４】
本願では、低オーバヘッド・データ構造を使用する高速アルゴリズムを説明する。
【００４５】
最初に、以下の単純で貪欲なアルゴリズムを検討する。
・ｉ＝１…ｎに対して、ｔｉが、Ｓによりまだ包含されない対象を包含するとき、ｔｉをＳに追加する。
【００４６】
ループの終了で、Ｓが、Ｔが包含するすべての対象を包含するということを確かめることは容易である。しかしながら、Ｓが常に最良の解であるとは限らないということを確かめることもまた容易である。例えば、テスト・スイートが２つのテストを有し、それらのテストの第１のものが１つの対象を包含し、第２のものが、同じ対象および別のものを包含するとき、このアルゴリズムは両方のテストを選択することになるが、第２のテストで十分である。
【００４７】
このアルゴリズムは、Ｔ内の各々のテストに、多くても１回しか調査に寄らない。その時間複雑度は、Ｏ（｜Ｔ｜・｜Ｃ｜）である。
【００４８】
以下のアルゴリズムは、より貪欲ではなく、より良好な結果を生み出すが、よりハードな動きとなる。
・Ｓが、Ｔより少ないものを包含する間は、Ｔにより包含されるがＳによりまだ包含されない、最も多くの対象を包含するテストをＳに追加する。
【００４９】
このアルゴリズムもまた、正しい結果を計算し、すなわち、最終的にはＳは、Ｔが包含するのと同じ対象を包含する。その結果は最適ではないが、そのアルゴリズムは、上記の例に対して良好に動く。
【００５０】
このアルゴリズムは、ｎ−ｉ個のテストに、その第ｉの反復で調査に寄るものであり、ゆえに、その時間複雑度は、Ｏ（｜Ｔ｜・｜Ｃ｜・｜Ｓ｜）である。最悪の事例では｜Ｓ｜＝｜Ｔ｜であるが、実際問題として、｜Ｓ｜が｜Ｔ｜より数桁少ないということの頻度は高い。
【００５１】
本願では次に、このアルゴリズムを改善するための３つの方途を探求する。２つによって、このアルゴリズムのＯ（）複雑度式内の定数因子が低減し、１つによって、より小さな出力テスト・スイートが結果として生じる。
・不必要な算出を回避する。
・テスト優先順位付け。
・包含されない対象を計数する。
【００５２】
不必要な算出を回避する：本願では、包含されない対象が計数される回数の数を有意に低減する改善を導入する。
【００５３】
テストが単一の反復で、以て寄与し得る包含されない対象の数は、そのテストが前の反復で、以て寄与し得る数より決して高くないということに留意されたい。ゆえに、現在の反復がすでに、maxSoFar個の新しい対象を以て寄与するテストを見つけ出しているとき、前の反復でmaxSoFarより少ないものを以て寄与し得るいずれのテストに対しても、包含されない対象を計数することのＯ（｜Ｃ｜）プロセスはスキップされ得る。このことがアルゴリズム１で示されており、testi.prevCountは、testiに対する最新の計算された寄与である。この値が、必ずしもあらゆる反復で計算されないということに留意されたい。
【００５４】
【数１】
2016212846.tif 000003
【００５５】
テスト優先順位付け：テストを選択することの優先順位を変更することによって、より小さな出力テスト・スイートが結果として生じる。
【００５６】
ここまで本願では、１つのテストを別のものに対して選好する際に、包含されない対象の数を検討するのみであった。典型的にはこのことによって、アルゴリズムが、ただ１つの対象を以て寄与するテストを選択する多くの反復で終了するということが結果として生じる。本願では、より高い重みを、入力でより少なく現れる対象に与え、より高い重みのテストを、より低いものより選好する、いくつもの重み付け体系によって実験した。
【００５７】
この手法の背後にある直観的事実は、そのような重みが使用されるとき、最初の反復は、多くの見つけ出すのが困難な対象を包含するテストを選択し、最後の反復は、多くの見つけ出すのが容易な対象を容易に見つけ出すということである。
【００５８】
実際のところ、重みを使用することによって、選択されるスイートのサイズは、最高で１５％だけ低減し得る。
【００５９】
包含されない対象を計数する：最終的にＩＴＳＭは、いくつものビット演算を一時に実行することによりスピードアップされ得る。本願では、各々のテストから、そのテストが包含する対象へのマッピングを維持する。ＩＴＳＭを実装するために、包含される対象は、本願では要素と呼ぶ、整数変数でのビットにより表され得るものであり、ビットマップ内のセット・ビットの数を計数することは、要素に対するルックアップ・テーブルを使用して一時に行われる。有意なスピードアップは、１６ビット要素  −  Ｃ／Ｃ＋＋での「short int」、またはＪａｖａ（Ｒ）での「char」を使用することにより得られ得る。そのようなビットマップは、各々の入力テストに関連付けられて、各々のテストが包含する対象を表し、さらには、中間結果に対して使用されて、依然として包含されなければならない対象を表す。
【００６０】
アルゴリズム２は、testiが以て寄与する包含されない対象の数を計数することを示す。testi.coveredjは、testiにより包含される対象を説明するビットマップ内の第ｊの要素であり、bitCount[]は、あらゆる可能な要素でのセット・ビットの計数に初期化されるルックアップ・テーブルであり、countは、testiが以て寄与し得る包含されない対象の数である。
【００６１】
このスピードアップは、nElementsInBitmap個のbitCount[]テーブルを使用すること、すなわち、アルゴリズム２の４行目でbitCount[new]の代わりにbitCountj[new]を使用することにより、上記の優先順位判定基準と組み合わされ得る。
【００６２】
【数２】
2016212846.tif 000004
【符号の説明】
【００６３】
２０  コンピュータ
２２  問題セット
２４  サブセット
２６  要件セット
２８  プロセッサ
３０  メモリ
３２  記憶デバイス
３４  アプリケーション
３６  答えセット
３８  画像セット
４０  カテゴリ・テーブル
４２  問題
４４  カテゴリ・レコード
４６  カテゴリ
４８  値
５０  画像レコード
５２  画像
５４  画像データ・エントリ
５６  特徴
５８  スコア
６０  要件
６２  カテゴリ要件
６４  値要件
７０  定義ステップ
７２  割り当てステップ
７４  第１の選択ステップ
７６  識別ステップ
７８  検索ステップ
８０  第２の選択ステップ
【図１】
2016212846.tif 000005
【図２】
2016212846.tif 000006