(57)【要約】      （修正有）【課題】２つのコールグラフを比較し、エッジの差異を検出するとき、エッジの差分を効率的に抽出する。【解決手段】情報処理装置１０は、起点となる第１ノード１ａからの距離により、第１コールグラフ１内の複数の第１エッジ１ｅ〜１ｇを距離ごとのカテゴリに分類し、起点となる第２ノード２ａからの距離により、第２コールグラフ２内の複数の第２エッジ２ｆ〜２ｉを分類する。呼び出し関係が共通の同じカテゴリの第２エッジが存在しない差分候補第１エッジと、呼び出し関係が共通の同じカテゴリの第１エッジが存在しない差分候補第２エッジとを特定し、差分候補第１エッジのうち、呼び出し関係が共通となる差分候補第２エッジが存在しない差分第１エッジと、差分候補第２エッジのうち、呼び出し関係が共通となる差分候補第１エッジが存在しない差分第２エッジとを抽出する。【選択図】図１
2017142712.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータが、
起点プログラムモジュールが指定されると、前記起点プログラムモジュールを含む第１ソフトウェア内の複数の第１プログラムモジュール間での呼び出し関係を、前記複数の第１プログラムモジュールを示す複数の第１ノード間を接続する複数の第１エッジによって表した第１コールグラフに基づいて、前記起点プログラムモジュールに対応する第１ノードから呼び出し関係を辿って前記複数の第１エッジそれぞれに到達するまでの距離により、前記複数の第１エッジを距離ごとのカテゴリに分類し、
前記起点プログラムモジュールを含む第２ソフトウェア内の複数の第２プログラムモジュール間での呼び出し関係を、前記複数の第２プログラムモジュールを示す複数の第２ノード間を接続する複数の第２エッジによって表した第２コールグラフに基づいて、前記起点プログラムモジュールに対応する第２ノードから呼び出し関係を辿って前記複数の第２エッジそれぞれに到達するまでの距離により、前記複数の第２エッジを距離ごとのカテゴリに分類し、
前記複数の第１エッジそれぞれを対象とし、対象第１エッジと同じカテゴリに属する第２エッジのなかに、呼び出し元と呼び出し先とのプログラムモジュールの組が該対象第１エッジと共通の第２エッジが存在しない場合、該対象第１エッジを差分候補第１エッジとして特定し、
前記複数の第２エッジそれぞれを対象とし、対象第２エッジと同じカテゴリに属する第１エッジのなかに、呼び出し元と呼び出し先とのプログラムモジュールの組が該対象第２エッジと共通の第１エッジが存在しない場合、該対象第２エッジを差分候補第２エッジとして特定し、
前記差分候補第１エッジのうち、呼び出し元と呼び出し先とのプログラムモジュールの組が共通となる前記差分候補第２エッジが存在しない差分第１エッジを抽出し、
前記差分候補第２エッジのうち、呼び出し元と呼び出し先とのプログラムモジュールの組が共通となる前記差分候補第１エッジが存在しない差分第２エッジを抽出する、
コールグラフ差分抽出方法。
【請求項２】
前記コンピュータが、さらに、
前記差分候補第１エッジのハッシュ値が登録された第１存在エッジリストと、前記差分候補第２エッジのハッシュ値が登録された第２存在エッジリストとを生成し、
前記差分第１エッジの抽出では、前記第２存在エッジリストに登録されているハッシュ値とは異なるハッシュ値が得られる前記差分候補第１エッジを、前記差分第１エッジとして抽出し、
前記差分第２エッジの抽出では、前記第１存在エッジリストに登録されているハッシュ値とは異なるハッシュ値が得られる前記差分候補第２エッジを、前記差分第２エッジとして抽出する、
請求項１記載のコールグラフ差分抽出方法。
【請求項３】
前記差分候補第１エッジと前記差分候補第２エッジとの特定では、分類されたカテゴリごとに第１エッジと第２エッジとを所定の基準でソートし、同じ距離のカテゴリに分類された第１エッジ群と第２エッジ群とを比較対象とし、前記第１エッジ群の上位から順に前記対象第１エッジを選択し、前記第２エッジ群の上位から順に前記対象第２エッジを選択し、前記対象第１エッジと前記対象第２エッジとにおける呼び出し元と呼び出し先とのプログラムモジュールの組が共通ではないとき、前記対象第１エッジと前記対象第２エッジとのうち、前記所定の基準でソートしたときに上位となる方を、前記差分候補第１エッジまたは前記差分候補第２エッジとして特定する、
請求項１または２記載のコールグラフ差分抽出方法。
【請求項４】
コンピュータに、
起点プログラムモジュールが指定されると、前記起点プログラムモジュールを含む第１ソフトウェア内の複数の第１プログラムモジュール間での呼び出し関係を、前記複数の第１プログラムモジュールを示す複数の第１ノード間を接続する複数の第１エッジによって表した第１コールグラフに基づいて、前記起点プログラムモジュールに対応する第１ノードから呼び出し関係を辿って前記複数の第１エッジそれぞれに到達するまでの距離により、前記複数の第１エッジを距離ごとのカテゴリに分類し、
前記起点プログラムモジュールを含む第２ソフトウェア内の複数の第２プログラムモジュール間での呼び出し関係を、前記複数の第２プログラムモジュールを示す複数の第２ノード間を接続する複数の第２エッジによって表した第２コールグラフに基づいて、前記起点プログラムモジュールに対応する第２ノードから呼び出し関係を辿って前記複数の第２エッジそれぞれに到達するまでの距離により、前記複数の第２エッジを距離ごとのカテゴリに分類し、
前記複数の第１エッジそれぞれを対象とし、対象第１エッジと同じカテゴリに属する第２エッジのなかに、呼び出し元と呼び出し先とのプログラムモジュールの組が該対象第１エッジと共通の第２エッジが存在しない場合、該対象第１エッジを差分候補第１エッジとして特定し、
前記複数の第２エッジそれぞれを対象とし、対象第２エッジと同じカテゴリに属する第１エッジのなかに、呼び出し元と呼び出し先とのプログラムモジュールの組が該対象第２エッジと共通の第１エッジが存在しない場合、該対象第２エッジを差分候補第２エッジとして特定し、
前記差分候補第１エッジのうち、呼び出し元と呼び出し先とのプログラムモジュールの組が共通となる前記差分候補第２エッジが存在しない差分第１エッジを抽出し、
前記差分候補第２エッジのうち、呼び出し元と呼び出し先とのプログラムモジュールの組が共通となる前記差分候補第１エッジが存在しない差分第２エッジを抽出する、
処理を実行させるコールグラフ差分抽出プログラム。
【請求項５】
第１ソフトウェア内の複数の第１プログラムモジュール間での呼び出し関係を、前記複数の第１プログラムモジュールを示す複数の第１ノード間を接続する複数の第１エッジによって表した第１コールグラフと、第２ソフトウェア内の複数の第２プログラムモジュール間での呼び出し関係を、前記複数の第２プログラムモジュールを示す複数の第２ノード間を接続する複数の第２エッジによって表した第２コールグラフとを記憶する記憶部と、
前記第１ソフトウェアと前記第２ソフトウェアとの両方に含まれる起点プログラムモジュールが指定されると、前記第１コールグラフに基づいて、前記起点プログラムモジュールに対応する第１ノードから呼び出し関係を辿って前記複数の第１エッジそれぞれに到達するまでの距離により、前記複数の第１エッジを距離ごとのカテゴリに分類し、前記第２コールグラフに基づいて、前記起点プログラムモジュールに対応する第２ノードから呼び出し関係を辿って前記複数の第２エッジそれぞれに到達するまでの距離により、前記複数の第２エッジを距離ごとのカテゴリに分類する分類部と、
前記複数の第１エッジそれぞれを対象とし、対象第１エッジと同じカテゴリに属する第２エッジのなかに、呼び出し元と呼び出し先とのプログラムモジュールの組が該対象第１エッジと共通の第２エッジが存在しない場合、該対象第１エッジを差分候補第１エッジとして特定し、前記複数の第２エッジそれぞれを対象とし、対象第２エッジと同じカテゴリに属する第１エッジのなかに、呼び出し元と呼び出し先とのプログラムモジュールの組が該対象第２エッジと共通の第１エッジが存在しない場合、該対象第２エッジを差分候補第２エッジとして特定する特定部と、
前記差分候補第１エッジのうち、呼び出し元と呼び出し先とのプログラムモジュールの組が共通となる前記差分候補第２エッジが存在しない差分第１エッジを抽出し、前記差分候補第２エッジのうち、呼び出し元と呼び出し先とのプログラムモジュールの組が共通となる前記差分候補第１エッジが存在しない差分第２エッジを抽出する抽出部と、
を有する情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コールグラフ差分抽出方法、コールグラフ差分抽出プログラム、および情報処理装置に関する。
【背景技術】
【０００２】
コンピュータに実行させるプログラムでは、サブルーチンとしての別のプログラムの呼び出しが定義されていることがある。大規模なソフトウェアでは、このようなプログラム間の呼び出し関係が複雑に絡み合う。そこで、ソフトウェアに含まれるプログラム間の呼び出し関係が視覚的に把握できるように、プログラム間の呼び出し関係をグラフで表すことがある。このようなプログラム間の呼び出し関係を表すグラフは、コールグラフと呼ばれる。
【０００３】
コールグラフは、プログラムを表すノードの集合と、プログラム間の呼び出し関係を表すエッジの集合とで構成される有向グラフである。コールグラフにおいて、エッジは、呼び出し元のプログラムに対応するノードから呼び出し先のプログラムに対応するノードへの方向性を有する線で表される。
【０００４】
このようなコールグラフは、ソフトウェアの一部のプログラムが修正されたことによる、他のプログラムの影響の有無の把握に利用できる。例えば、修正前のソフトウェアの呼び出し関係を示すコールグラフと、修正後のソフトウェアの呼び出し関係を示すコールグラフとを比較すれば、サブルーチンの呼び出し元が変更されたことなどを把握できる。このとき、サブルーチンが呼び出し元に依存する処理を含んでいる場合、そのサブルーチンのプログラムについても修正を要することが分かる。
【０００５】
グラフを用いてプログラムの構造を把握する技術としては、例えば、コンピュータ・プログラムの構造を、有向グラフで簡潔に表示する階層的グラフ解析方法がある。またアプリケーションに障害が発生した際、障害の根本的な原因となる処理を行っている箇所を特定するためにコールグラフを利用した、アプリケーションの障害原因の特定作業支援システムも考えられている。さらに、ソースコードの等価性を検証する際に、ソースコードを解析した構造グラフによる構造比較を行うソースコード等価性検証装置も考えられている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平６−１８７１３８号公報
【特許文献２】特開２００７−２４１４２６号公報
【特許文献３】特開２０１４−１２６９８５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、２つのコールグラフを比較し、エッジの差異を検出するとき、２つのコールグラフがどちらにも多数のエッジがある場合、実用的な時間内で比較処理を完了させることが困難となる。例えば、一方のコールグラフ内の各エッジを他方のコールグラフ内の全エッジと総当たりで比較した場合、それぞれのコールグラフのエッジ数同士を乗算した回数分のエッジの同一性判定処理が行われる。ＯＳ（Operating System）のような規模の大きなソフトウェアでは、コールグラフに含まれるエッジ数が百万個に及ぶ場合もあり、エッジの同一性判定処理の繰り返し回数が膨大になる。その結果、２つのコールグラフの比較に時間がかかっている。
【０００８】
１つの側面では、本件は、エッジの差分を効率的に抽出できるようにすることを目的とする。
【課題を解決するための手段】
【０００９】
１つの案では、コンピュータが以下の処理を実行するコールグラフ差分抽出方法が提供される。
このコールグラフ差分抽出方法では、コンピュータは、起点プログラムモジュールが指定されると、起点プログラムモジュールを含む第１ソフトウェア内の複数の第１プログラムモジュール間での呼び出し関係を、複数の第１プログラムモジュールを示す複数の第１ノード間を接続する複数の第１エッジによって表した第１コールグラフに基づいて、起点プログラムモジュールに対応する第１ノードから呼び出し関係を辿って複数の第１エッジそれぞれに到達するまでの距離により、第１コールグラフ内の複数の第１エッジを距離ごとのカテゴリに分類する。またコンピュータは、起点プログラムモジュールを含む第２ソフトウェア内の複数の第２プログラムモジュール間での呼び出し関係を、複数の第２プログラムモジュールを示す複数の第２ノード間を接続する複数の第２エッジによって表した第２コールグラフに基づいて、起点プログラムモジュールに対応する第２ノードから呼び出し関係を辿って複数の第２エッジそれぞれに到達するまでの距離により、複数の第２エッジを距離ごとのカテゴリに分類する。次にコンピュータは、複数の第１エッジそれぞれを対象とし、対象第１エッジと同じカテゴリに属する第２エッジのなかに、呼び出し元と呼び出し先とのプログラムモジュールの組が該対象第１エッジと共通の第２エッジが存在しない場合、該対象第１エッジを差分候補第１エッジとして特定する。またコンピュータは、複数の第２エッジそれぞれを対象とし、対象第２エッジと同じカテゴリに属する第１エッジのなかに、呼び出し元と呼び出し先とのプログラムモジュールの組が該対象第２エッジと共通の第１エッジが存在しない場合、該対象第２エッジを差分候補第２エッジとして特定する。さらにコンピュータは、差分候補第１エッジのうち、呼び出し元と呼び出し先とのプログラムモジュールの組が共通となる差分候補第２エッジが存在しない差分第１エッジを抽出する。またコンピュータは、差分候補第２エッジのうち、呼び出し元と呼び出し先とのプログラムモジュールの組が共通となる差分候補第１エッジが存在しない差分第２エッジを抽出する。
【発明の効果】
【００１０】
１態様によれば、エッジの差分を効率的に抽出できるようになる。
【図面の簡単な説明】
【００１１】
【図１】第１の実施の形態に係る情報処理装置の構成例を示す図である。
【図２】コールグラフの生成例を示す図である。
【図３】コールグラフのエッジのデータ構造の一例を示す図である。
【図４】コールグラフ上のエッジの距離の例を示す図である。
【図５】更新後のソースコードのコールグラフの例を示す図である。
【図６】第２の実施の形態に用いるコンピュータのハードウェアの一構成例を示す図である。
【図７】コールグラフ比較のためのコンピュータの機能を示すブロック図である。
【図８】第１・第２コールグラフ記憶部内のデータの例を示す図である。
【図９】第１・第２距離別エッジリスト記憶部内のデータの例を示す図である。
【図１０】第１・第２差分エッジ記憶部内のデータの例を示す図である。
【図１１】第１・第２存在エッジ記憶部内のデータの例を示す図である。
【図１２】差分抽出結果記憶部内のデータの例を示す図である。
【図１３】差分エッジ抽出処理の手順を示すフローチャートである。
【図１４】距離別エッジ分類処理の手順の一例を示すフローチャートである。
【図１５】同一距離間エッジ比較処理の手順の一例を示すフローチャートである。
【図１６】距離違いエッジ存在確認処理の手順の一例を示すフローチャートである。
【図１７】第１参考手法と第２の実施の形態に係る手法との比較例を示す図である。
【図１８】第２参考手法と第２の実施の形態に係る手法との比較例を示す図である。
【発明を実施するための形態】
【００１２】
以下、本実施の形態について図面を参照して説明する。なお各実施の形態は、矛盾のない範囲で複数の実施の形態を組み合わせて実施することができる。
〔第１の実施の形態〕
まず、第１の実施の形態について説明する。
【００１３】
図１は、第１の実施の形態に係る情報処理装置の構成例を示す図である。情報処理装置１０は、記憶部１１と演算部１２とを有する。
記憶部１１は、第１コールグラフ１と第２コールグラフ２とを記憶する。第１コールグラフ１は、第１ソフトウェア内の複数の第１プログラムモジュール間での呼び出し関係を、複数の第１プログラムモジュールを示す複数の第１ノード１ａ〜１ｄ間を接続する複数の第１エッジ１ｅ〜１ｇによって表した有向グラフである。第２コールグラフ２は、第２ソフトウェア内の複数の第２プログラムモジュール間での呼び出し関係を、複数の第２プログラムモジュールを示す複数の第２ノード２ａ〜２ｅ間を接続する複数の第２エッジ２ｆ〜２ｉによって表した有向グラフである。なお、第１ソフトウェアの識別子は「１」、第２ソフトウェアの識別子は「２」であるものとする。
【００１４】
演算部１２は、分類部１２ａ、特定部１２ｂ、および抽出部１２ｃを有する。
分類部１２ａは、第１ソフトウェアと第２ソフトウェアとの両方に含まれる起点プログラムモジュールが指定されると、第１コールグラフ１と第２コールグラフ２とのそれぞれに含まれる第１エッジ１ｅ〜１ｇと第２エッジ２ｆ〜２ｉとを複数のカテゴリに分類する。例えば分類部１２ａは、第１コールグラフ１に基づいて、起点プログラムモジュールに対応する第１ノード１ａを特定する。そして分類部１２ａは、特定した第１ノード１ａから呼び出し関係を辿って複数の第１エッジ１ｅ〜１ｇそれぞれに到達するまでの距離により、複数の第１エッジ１ｅ〜１ｇを距離ごとのカテゴリに分類する。例えば分類部１２ａは、複数の第１エッジ１ｅ〜１ｇをカテゴリごとに分けて、第１距離別エッジリスト３に格納する。なお、第１距離別エッジリスト３に登録されているエッジは、対応する呼び出し関係における呼び出し元のプログラムモジュールの名称と呼び出し先のプログラムモジュールの名称との組（プログラム名対）で表されている。
【００１５】
また分類部１２ａは、第２コールグラフ２に基づいて、起点プログラムモジュールに対応する第２ノード２ａを特定する。そして分類部１２ａは、特定した第２ノード２ａから呼び出し関係を辿って複数の第２エッジ２ｆ〜２ｉそれぞれに到達するまでの距離により、複数の第２エッジ２ｆ〜２ｉを距離ごとのカテゴリに分類する。例えば分類部１２ａは、複数の第２エッジ２ｆ〜２ｉをカテゴリごとに分けて、第２距離別エッジリスト４に格納する。なお、第２距離別エッジリスト４に登録されているエッジは、対応する呼び出し関係における呼び出し元のプログラムモジュールの名称と呼び出し先のプログラムモジュールの名称との組（プログラム名対）で表されている。
【００１６】
特定部１２ｂは、複数の第１エッジ１ｅ〜１ｇそれぞれを対象とする。そして特定部１２ｂは、対象第１エッジと同じカテゴリに属する第２エッジのなかに、呼び出し元と呼び出し先とのプログラムモジュールの組が該対象第１エッジと共通の第２エッジが存在しない場合、その対象第１エッジを差分候補第１エッジとして特定する。
【００１７】
また特定部１２ｂは、複数の第２エッジ２ｆ〜２ｉそれぞれを対象とする。そして特定部１２ｂは、対象第２エッジと同じカテゴリに属する第１エッジのなかに、呼び出し元と呼び出し先とのプログラムモジュールの組が該対象第２エッジと共通の第１エッジが存在しない場合、その対象第２エッジを差分候補第２エッジとして特定する。
【００１８】
例えば特定部１２ｂは、第１距離別エッジリスト３と第２距離別エッジリスト４との、同一カテゴリ内の第１エッジと第２エッジを比較する。そして特定部１２ｂは、同一カテゴリのなかに、同じプログラム名対で表されている第２エッジが存在しない第１エッジを、差分候補第１エッジとして第１差分エッジリスト５に格納する。また、特定部１２ｂは、同一カテゴリのなかに、同じプログラム名対で表されている第１エッジが存在しない第２エッジを、差分候補第２エッジとして第２差分エッジリスト６に格納する。
【００１９】
抽出部１２ｃは、差分候補第１エッジのうち、呼び出し元と呼び出し先とのプログラムモジュールの組が共通となる差分候補第２エッジが存在しない差分第１エッジを抽出する。また抽出部１２ｃは、差分候補第２エッジのうち、呼び出し元と呼び出し先とのプログラムモジュールの組が共通となる差分候補第１エッジが存在しない差分第２エッジを抽出する。
【００２０】
例えば抽出部１２ｃは、第１差分エッジリスト５内の差分候補第１エッジと第２差分エッジリスト６内の差分候補第２エッジとを、総当たりで比較する。そして抽出部１２ｃは、比較相手のいずれともプログラム名対が異なる差分候補第１エッジを、第１ソフトウェアの識別子に対応付けて、最終差分エッジリスト７に格納する。またそして抽出部１２ｃは、比較相手のいずれともプログラム名対が異なる差分候補第１エッジを、第２ソフトウェアの識別子に対応付けて、最終差分エッジリスト７に格納する。
【００２１】
このような情報処理装置１０によれば、起点プログラムモジュールが指定されると、第１コールグラフ１と第２コールグラフ２とのエッジが、起点ノード１ａ，２ａからの距離に応じたカテゴリに分類される。次に分類部１２ａによって、同じカテゴリの第１エッジと第２エッジとの比較により、差分候補第１エッジと差分候補第２エッジとが特定される。そして、抽出部１２ｃにより、差分候補第１エッジと差分候補第２エッジとのなかから、第１コールグラフ１と第２コールグラフ２との一方にのみ存在する差分第１エッジおよび差分第２エッジが抽出される。
【００２２】
第１の実施の形態では、特定部１２ｂによって抽出するエッジの候補を絞り込み、候補となったエッジから差分第１エッジおよび差分第２エッジを抽出するため、効率的に差分エッジを抽出できる。その結果、コールグラフ間の差分抽出に要する時間が短縮される。
【００２３】
なお演算部１２は、差分候補第１エッジと差分候補第２エッジとのハッシュ値を用いて、抽出部１２ｃによる抽出処理の効率化を図ることもできる。その場合、特定部１２ｂは、差分候補第１エッジのハッシュ値が登録された第１存在エッジリストと、差分候補第２エッジのハッシュ値が登録された第２存在エッジリストとを生成する。ハッシュ値は、差分候補第１エッジまたは差分候補第２エッジのプログラム名対を、所定のハッシュ関数で演算して求めることができる。抽出部１２ｃは、第２存在エッジリストに登録されているハッシュ値とは異なるハッシュ値が得られる差分候補第１エッジを、差分第１エッジとして抽出する。また抽出部１２ｃは、第１存在エッジリストに登録されているハッシュ値とは異なるハッシュ値が得られる差分候補第２エッジを、差分第２エッジとして抽出する。
【００２４】
このようにハッシュ値を用いることで、非常に長いプログラム名対を短いデータに圧縮することができ、少ない量のメモリ使用による効率的な処理が可能となる。
また演算部１２は、分類されたカテゴリ内で第１エッジおよび第２エッジをソート（並べ替え）することで、差分候補第１エッジと差分候補第２エッジとの特定処理をさらに効率化することができる。その場合、特定部１２ｂは、分類されたカテゴリにごとに第１エッジと第２エッジとを所定の基準でソートする。次に特定部１２ｂは、同じ距離のカテゴリに分類された第１エッジ群と第２エッジ群とを比較対象とする。さらに特定部１２ｂは、第１エッジ群の上位から順に対象第１エッジを選択し、第２エッジ群の上位から順に対象第２エッジを選択する。そして特定部１２ｂは、対象第１エッジと対象第２エッジとにおける呼び出し元と呼び出し先とのプログラムモジュールの組が共通か否かを判断する。共通ではないとき、特定部１２ｂは、対象第１エッジと対象第２エッジとのうち、所定の基準でソートしたときに上位となる方を、差分候補第１エッジまたは差分候補第２エッジとして特定する。
【００２５】
特定部１２ｂは、差分候補第１エッジを特定した場合、対象第１エッジを、第１エッジ群内の次の第１エッジに変更する。また特定部１２ｂは、差分候補第２エッジを特定した場合、対象第２エッジを、第２エッジ群内の次の第２エッジに変更する。呼び出し元と呼び出し先とのプログラムモジュールの組が共通と判断した場合、特定部１２ｂは、対象第１エッジを、第１エッジ群内の次の第１エッジに変更すると共に、対象第２エッジを、第２エッジ群内の次の第２エッジに変更する。
【００２６】
このように、カテゴリ内で第１エッジおよび第２エッジをソートした上で同一性の比較を行うことで、総当たりで比較する場合に比べ比較処理の回数を削減できる。その結果、処理の効率化が図れる。
【００２７】
なお、演算部１２は、例えば情報処理装置１０が有するプロセッサにより実現することができる。また、記憶部１１は、例えば情報処理装置１０が有するメモリまたはストレージ装置により実現することができる。演算部１２内の分類部１２ａ、特定部１２ｂ、および抽出部１２ｃは、例えば演算部１２にプログラムを実行させることで実現できる。その際、第１距離別エッジリスト３、第２距離別エッジリスト４、第１差分エッジリスト５、第２差分エッジリスト６、および最終差分エッジリスト７は、例えば情報処理装置１０が有するメモリまたはストレージ装置に一時的に格納される。
【００２８】
以上が第１の実施の形態についての説明である。
〔第２の実施の形態〕
次に第２の実施の形態について説明する。第２の実施の形態では、オブジェクト指向プログラミングにより作成された２つのソフトウェアそれぞれから作成されたコールグラフのエッジの差分の抽出を、コンピュータを用いて効率的に実施するものである。なお、オブジェクト指向プログラミングにより作成された２つのソフトウェアのコールグラフでは、ソフトウェアを構成する複数のメソッドがノードで表され、メソッド間の呼び出し関係が、エッジで表される。すなわちメソッドは、第１の実施の形態に示すプログラムモジュールの一例である。
【００２９】
図２は、コールグラフの生成例を示す図である。図２に示すように、ソースコード３１を解析することで、メソッド間の呼び出し関係を示すコールグラフ３２が得られる。
例えば、ソースコード３１を解析すると、「Tranceiver.transmit()」・「Transformer.encode()」・「Protocol.makeHeader()」・「Tranceiver.send()」というメソッドが存在していることが分かる。そこで、コールグラフ３２内に、各メソッドに対応するノード３２ａ〜３２ｄが生成される。また、ソースコード３１を解析すると、メソッド「Tranceiver.transmit()」が、他の３つのメソッド「Transformer.encode()」・「Protocol.makeHeader()」・「Tranceiver.send()」を呼び出していることが分かる。そこで、メソッド「Tranceiver.transmit()」に対応するノード３２ａと他の３つのノード３２ｂ〜３２ｄとを接続するエッジ３２ｅ〜３２ｇが生成される。エッジ３２ｅ〜３２ｇは、呼び出し元のメソッドに対応するノード３２ａから、呼び出し先のメソッドに対応するノード３２ｂ〜３２ｄを指し示す矢印である。
【００３０】
このようにして、ノード３２ａ〜３２ｄによりメソッドを表し、エッジ３２ｅ〜３２ｇによりメソッド間の呼び出し関係を表すコールグラフ３２が生成される。コールグラフ３２の各エッジ３２ｅ〜３２ｇは、文字列の２つ組で表現できる。
【００３１】
図３は、コールグラフのエッジのデータ構造の一例を示す図である。各エッジ３２ｅ〜３２ｇは、呼び出し元メソッドの完全修飾名文字列と、呼び出し先メソッドの完全修飾名文字列とを含んでいる。左側の文字列が呼び出し元メソッドの完全修飾名であり、右側の文字列が呼び出し先メソッドの完全修飾名である。このような文字列の２つ組によって、エッジが特定される。換言すると、文字列の２つ組が同じエッジは、同一の呼び出し関係を示すエッジであると判断できる。
【００３２】
なお、エッジ３２ｅ〜３２ｇを表す文字列としてノード３２ａ〜３２ｄを示すメソッドの完全修飾名が含まれている。そのため、エッジ３２ｅ〜３２ｇの情報があれば、ノード３２ａ〜３２ｄを含め、コールグラフ３２の全体を生成できる。
【００３３】
また、複数のエッジは、データ構造に含まれる文字列により、同一、および大小を比較することができる。例えば、図３に示すように呼び出し元メソッドを示す文字列と、呼び出し先メソッドを示す文字列との組で表される２つのエッジ（Ｎ１，Ｎ２），（Ｎ３，Ｎ４）があるものとする。ここで、Ｎ１，Ｎ２，Ｎ３，Ｎ４は、文字列である。このとき、各エッジそれらが同一であるかは以下の条件で判定できる。
（Ｎ１，Ｎ２）＝（Ｎ３，Ｎ４）⇔Ｎ１＝Ｎ３かつＮ２＝Ｎ４
さらに２つのエッジは次のように大小比較できる。
（Ｎ１，Ｎ２）＜（Ｎ３，Ｎ４）⇔Ｎ１＜Ｎ３または｛Ｎ１＝Ｎ３かつＮ２＜Ｎ４｝
（Ｎ１，Ｎ２）≦（Ｎ３，Ｎ４）⇔Ｎ１≦Ｎ３または｛Ｎ１＝Ｎ３かつＮ２≦Ｎ４｝
なお、文字列同士の大小関係は、例えばアルファベット順とする。その場合、「Ａ」が最も小さい値となり、「Ｚ」が最も大きな値となる。この比較方法を使って一意の順序にエッジをソートできる。
【００３４】
このようなコールグラフ３２は、ソフトウェア開発時に利用される。例えばソフトウェア開発過程での版数の異なる複数のソースコードそれぞれから生成した複数のコールグラフにおけるエッジの差分抽出を行うことがある。コールグラフ間のエッジの差分抽出は、大規模なソフトウェアの一部を修正した場合における、その修正の影響範囲の把握に有用である。例えば、ソフトウェアの開発にあたり、ＯＳＳ（Open Source Software）など第三者が作成したソースコードセットの呼び出しを含むソフトウェアが作成されることがある。または第三者が作成したソースコードセットを改変したり、機能を追加したりして、ソフトウェアを完成させることもある。
【００３５】
このようにして作成されたソフトウェアにおいて、呼び出されるソースコードセットが更新された場合、開発者は過去の版で呼び出したり改変したりしたメソッド（開発者が着目しているメソッド）が更新の影響を受けているか確認する。以下、開発者が着目しているメソッドに対応するノードを、起点ノードと呼ぶ。２つのコールグラフそれぞれから、起点ノードを起点として呼び出し関係を追跡し、追跡された呼び出し関係を比較して差分を抽出することにより、例えば更新の影響が起点メソッドに及ぶか否かを判断できる。また、その他に精査するメソッドを特定することもできる。
【００３６】
第２の実施の形態では、このような呼び出し関係の差分抽出をコンピュータ処理によって高速に実施できるようにする。そのため第２の実施の形態では、コールグラフ内のエッジが、起点ノードからの距離で分類される。
【００３７】
図４は、コールグラフ上のエッジの距離の例を示す図である。図４に示すコールグラフ４０は、ノード４１ａ〜４１ｋとエッジ４２ａ〜４２ｋを含んでいる。コールグラフ４０上の起点ノードからｄ個（ｄは０以上の整数）のエッジを同一方向に辿って別のあるノードに到達できるとき、２のノードの距離をｄと定義する。このときのエッジを辿る方向（探索方向）は、呼び出し元から呼び出し先へ向かう方向（呼び出し先方向）の場合と、逆に、呼び出し先から呼び出し元へ向かう方向（呼び出し元方向）の場合とがある。なお、起点ノードから、その起点ノードまでの距離は０と定義する。
【００３８】
そしてノード間の距離を用いて、起点ノードに対するエッジの距離を定義できる。例えば、起点ノードからみて距離（ｄ−１）の位置にあるノードと距離ｄの位置にあるノードを結ぶエッジは、起点ノードからの距離をｄと定義する。
【００３９】
図４の例では、「メソッドｇ」に対応するノード４１ｇが起点ノードである。起点ノードから「メソッドｄ」に対応するノード４１ｄまでの距離は「１」である。そして、起点ノードであるノード４１ｇとノード「メソッドｄ」に対応するノード４１ｄとを接続するエッジ４２ｈの距離は「１」である。
【００４０】
起点ノードから「メソッドｆ」に対応するノード４１ｆまでの距離は「２」である。そして、起点ノードから距離「１」にあるノード４１ｄとノード「メソッドｆ」に対応するノード４１ｆとを接続するエッジ４２ｄの距離は「２」である。
【００４１】
ここで、図４に示したコールグラフ４０の生成元となったソースコードが更新された場合を想定する。この場合、更新後のソースコードについてもコールグラフを生成することで、そのコールグラフにより、更新後のソースコードにおけるメソッド間の呼び出し関係が表される。
【００４２】
図５は、更新後のソースコードのコールグラフの例を示す図である。図５の例では、更新後のソースコードのコールグラフ４０ａを、図４に示す更新前のコールグラフ４０と比較すると、ノード４１ｋが削除され、ノード４１ｌが追加されている。ノード４１ｄとノード４１ｆとを接続するエッジ４２ｄは削除され、ノード４１ｄとノード４１ｌを接続するエッジ４２ｌおよびノード４１ｌとノード４１ｆを接続するエッジ４２ｍが追加されている。
【００４３】
以下、図４、図５に示した２つのコールグラフ４０，４０ａ間のエッジの差分抽出処理を高速に行うコンピュータについて、詳細に説明する。
＜ハードウェア構成＞
図６は、第２の実施の形態に用いるコンピュータのハードウェアの一構成例を示す図である。コンピュータ１００は、プロセッサ１０１によって装置全体が制御されている。プロセッサ１０１には、バス１０９を介してメモリ１０２と複数の周辺機器が接続されている。プロセッサ１０１は、マルチプロセッサであってもよい。プロセッサ１０１は、例えばＣＰＵ（Central Processing Unit）、ＭＰＵ（Micro Processing Unit）、またはＤＳＰ（Digital Signal Processor）である。プロセッサ１０１がプログラムを実行することで実現する機能の少なくとも一部を、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現してもよい。
【００４４】
メモリ１０２は、コンピュータ１００の主記憶装置として使用される。メモリ１０２には、プロセッサ１０１に実行させるＯＳのプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、メモリ１０２には、プロセッサ１０１による処理に必要な各種データが格納される。メモリ１０２としては、例えばＲＡＭ（Random Access Memory）などの揮発性の半導体記憶装置が使用される。
【００４５】
バス１０９に接続されている周辺機器としては、ストレージ装置１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、機器接続インタフェース１０７およびネットワークインタフェース１０８がある。
【００４６】
ストレージ装置１０３は、内蔵した記憶媒体に対して、電気的または磁気的にデータの書き込みおよび読み出しを行う。ストレージ装置１０３は、コンピュータの補助記憶装置として使用される。ストレージ装置１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、ストレージ装置１０３としては、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）を使用することができる。
【００４７】
グラフィック処理装置１０４には、モニタ２１が接続されている。グラフィック処理装置１０４は、プロセッサ１０１からの命令に従って、画像をモニタ２１の画面に表示させる。モニタ２１としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。
【００４８】
入力インタフェース１０５には、キーボード２２とマウス２３とが接続されている。入力インタフェース１０５は、キーボード２２やマウス２３から送られてくる信号をプロセッサ１０１に送信する。なお、マウス２３は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。
【００４９】
光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク２４に記録されたデータの読み取りを行う。光ディスク２４は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク２４には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。
【００５０】
機器接続インタフェース１０７は、コンピュータ１００に周辺機器を接続するための通信インタフェースである。例えば機器接続インタフェース１０７には、メモリ装置２５やメモリリーダライタ２６を接続することができる。メモリ装置２５は、機器接続インタフェース１０７との通信機能を搭載した記録媒体である。メモリリーダライタ２６は、メモリカード２７へのデータの書き込み、またはメモリカード２７からのデータの読み出しを行う装置である。メモリカード２７は、カード型の記録媒体である。
【００５１】
ネットワークインタフェース１０８は、ネットワーク２０に接続されている。ネットワークインタフェース１０８は、ネットワーク２０を介して、他のコンピュータまたは通信機器との間でデータの送受信を行う。
【００５２】
以上のようなハードウェア構成によって、第２の実施の形態の処理機能を実現することができる。なお、第１の実施の形態に示した情報処理装置１０も、図６に示したコンピュータ１００と同様のハードウェアにより実現することができる。
【００５３】
コンピュータ１００は、例えばコンピュータ読み取り可能な記録媒体に記録されたプログラムを実行することにより、第２の実施の形態の処理機能を実現する。コンピュータ１００に実行させる処理内容を記述したプログラムは、様々な記録媒体に記録しておくことができる。例えば、コンピュータ１００に実行させるプログラムをストレージ装置１０３に格納しておくことができる。プロセッサ１０１は、ストレージ装置１０３内のプログラムの少なくとも一部をメモリ１０２にロードし、プログラムを実行する。またコンピュータ１００に実行させるプログラムを、光ディスク２４、メモリ装置２５、メモリカード２７などの可搬型記録媒体に記録しておくこともできる。可搬型記録媒体に格納されたプログラムは、例えばプロセッサ１０１からの制御により、ストレージ装置１０３にインストールされた後、実行可能となる。またプロセッサ１０１が、可搬型記録媒体から直接プログラムを読み出して実行することもできる。
【００５４】
＜処理機能＞
コンピュータ１００は、２つのソースコードセットそれぞれから作成されたコールグラフを比較し、エッジの差分を検出する。コールグラフ比較処理のためにコンピュータ１００が有する機能を図７に示す。
【００５５】
図７は、コールグラフ比較のためのコンピュータの機能を示すブロック図である。コンピュータ１００は、第１コールグラフ記憶部１１１、第２コールグラフ記憶部１１２、要求受付部１２０、距離別エッジ分類部１３０、第１距離別エッジリスト記憶部１４１、第２距離別エッジリスト記憶部１４２、同一距離間エッジ比較部１５０、第１差分エッジ記憶部１６１、第２差分エッジ記憶部１６２、第１存在エッジ記憶部１６３、第２存在エッジ記憶部１６４、差分エッジ抽出部１７０、差分抽出結果記憶部１８０、および結果返答部１９０を有する。このうち距離別エッジ分類部１３０は、第１の実施の形態における分類部１２ａの一例である。また同一距離間エッジ比較部１５０は、第１の実施の形態における特定部１２ｂの一例である。さらに差分エッジ抽出部１７０は、第１の実施の形態における抽出部１２ｃの一例である。
【００５６】
第１コールグラフ記憶部１１１は、比較対象の２つのコールグラフのうちの一つを記憶する。例えば第１コールグラフ記憶部１１１は、改変前の版数のソフトウェアにおけるメソッド間の呼び出し関係を示すコールグラフを記憶する。
【００５７】
第２コールグラフ記憶部１１２は、比較対象の２つのコールグラフのうちの他の一つを記憶する。例えば第２コールグラフ記憶部１１２は、改変後の版数のソフトウェアにおけるメソッド間の呼び出し関係を示すコールグラフを記憶する。
【００５８】
要求受付部１２０は、開発者による差分抽出要求の入力を受け付ける。差分抽出要求には、着目するメソッドを指定する情報と、探索方向を指定する情報とが含まれる。要求受付部１２０は、受け付けた差分抽出要求を、距離別エッジ分類部１３０に送信する。
【００５９】
距離別エッジ分類部１３０は、第１コールグラフ記憶部１１１と第２コールグラフ記憶部１１２とに記憶されている２つのコールグラフそれぞれのエッジを、着目するメソッドに対応するノードからの距離により分類する。具体的には、距離別エッジ分類部１３０は、着目するメソッドからの距離ごとのカテゴリを生成する。そして距離別エッジ分類部１３０は、第１コールグラフ記憶部１１１に記憶されているコールグラフを読み出し、そのコールグラフ内のエッジが属するカテゴリを判断し、各エッジをカテゴリごとに第１距離別エッジリスト記憶部１４１に格納する。同様に、距離別エッジ分類部１３０は、第２コールグラフ記憶部１１２に記憶されているコールグラフを読み出し、そのコールグラフ内のエッジが属するカテゴリを判断し、各エッジをカテゴリごとに第２距離別エッジリスト記憶部１４２に格納する。
【００６０】
第１距離別エッジリスト記憶部１４１は、第１コールグラフ記憶部１１１内のコールグラフに含まれるエッジを、着目するメソッドからの距離に応じたカテゴリに分類して記憶する。
【００６１】
第２距離別エッジリスト記憶部１４２は、第２コールグラフ記憶部１１２内のコールグラフに含まれるエッジを、着目するメソッドからの距離に応じたカテゴリに分類して記憶する。
【００６２】
同一距離間エッジ比較部１５０は、第１距離別エッジリスト記憶部１４１と第２距離別エッジリスト記憶部１４２との同じカテゴリに分類されたエッジ同士を比較し、同じエッジの有無を判断する。そして同一距離間エッジ比較部１５０は、第１距離別エッジリスト記憶部１４１内のあるカテゴリに記憶されているが、第２距離別エッジリスト記憶部１４２内の同一カテゴリに記憶されていないエッジを、第１差分エッジ記憶部１６１に格納する。また同一距離間エッジ比較部１５０は、第２距離別エッジリスト記憶部１４２内のあるカテゴリに記憶されているが、第１距離別エッジリスト記憶部１４１内の同一カテゴリに記憶されていないエッジを、第２差分エッジ記憶部１６２に格納する。
【００６３】
さらに同一距離間エッジ比較部１５０は、第１差分エッジ記憶部１６１に格納したエッジのハッシュ値を算出し、得られたハッシュ値を第１存在エッジ記憶部１６３に格納する。また同一距離間エッジ比較部１５０は、第２差分エッジ記憶部１６２に格納したエッジのハッシュ値を算出し、得られたハッシュ値を第２存在エッジ記憶部１６４に格納する。
【００６４】
第１差分エッジ記憶部１６１は、第１距離別エッジリスト記憶部１４１内のあるカテゴリに記憶されているが、第２距離別エッジリスト記憶部１４２内の同一カテゴリに記憶されていないエッジを記憶する。
【００６５】
第２差分エッジ記憶部１６２は、第２距離別エッジリスト記憶部１４２内のあるカテゴリに記憶されているが、第１距離別エッジリスト記憶部１４１内の同一カテゴリに記憶されていないエッジを記憶する。
【００６６】
第１存在エッジ記憶部１６３は、第１差分エッジ記憶部１６１に格納されたエッジのハッシュ値を記憶する。
第２存在エッジ記憶部１６４は、第２差分エッジ記憶部１６２に格納されたエッジのハッシュ値を記憶する。
【００６７】
差分エッジ抽出部１７０は、第１差分エッジ記憶部１６１と第２差分エッジ記憶部１６２とから、比較対象の２つのコールグラフの一方にのみ含まれるエッジを抽出する。具体的には、差分エッジ抽出部１７０は、第１差分エッジ記憶部１６１に記憶されているエッジのハッシュ値と同一のハッシュ値が、第２存在エッジ記憶部１６４に格納されているか否かを判断する。差分エッジ抽出部１７０は、該当するハッシュ値が格納されていなければ、ハッシュ値の生成元であるエッジを第１差分エッジ記憶部１６１から抽出し、差分抽出結果記憶部１８０に格納する。また差分エッジ抽出部１７０は、第２差分エッジ記憶部１６２に記憶されているエッジのハッシュ値と同一のハッシュ値が、第１存在エッジ記憶部１６３に格納されているか否かを判断する。差分エッジ抽出部１７０は、該当するハッシュ値が格納されていなければ、ハッシュ値の生成元であるエッジを第２差分エッジ記憶部１６２から抽出し、差分抽出結果記憶部１８０に格納する。
【００６８】
差分抽出結果記憶部１８０は、第１コールグラフ記憶部１１１と第２コールグラフ記憶部１１２とのいずれか一方に格納されているコールグラフにのみ含まれるエッジの抽出結果を記憶する。
【００６９】
結果返答部１９０は、差分抽出要求に対する応答として、差分抽出結果記憶部１８０に記憶されているエッジの情報を出力する。
なお、図７に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。また、図７に示した各要素の機能は、例えば、その要素に対応するプログラムモジュールをコンピュータに実行させることで実現することができる。
【００７０】
＜データ構造＞
次に、図８〜図１２を参照し、コンピュータ１００内の各記憶部に格納されるデータについて具体的に説明する。
【００７１】
図８は、第１・第２コールグラフ記憶部内のデータの例を示す図である。第１コールグラフ記憶部１１１には、コールグラフ４０を示すコールグラフデータ１１１ａが格納されている。コールグラフデータ１１１ａには、コールグラフ４０に含まれる複数のエッジ４２ａ〜４２ｋそれぞれを示す文字列の２つ組が含まれる。第２コールグラフ記憶部１１２には、コールグラフ４０ａを示すコールグラフデータ１１２ａが格納されている。コールグラフデータ１１２ａには、コールグラフ４０ａに含まれる複数のエッジ４２ａ〜４２ｃ，４２ｅ〜４２ｋ，４２ｌ，４２ｍそれぞれを示す文字列の２つ組が含まれる。
【００７２】
図９は、第１・第２距離別エッジリスト記憶部内のデータの例を示す図である。第１距離別エッジリスト記憶部１４１には、起点ノードからの距離による、コールグラフ４０内のエッジの分類結果を示す第１距離別エッジリスト１４１ａが格納されている。第２距離別エッジリスト記憶部１４２には、起点ノードからの距離による、コールグラフ４０ａ内のエッジの分類結果を示す第２距離別エッジリスト１４２ａが格納されている。
【００７３】
第１距離別エッジリスト１４１ａおよび第２距離別エッジリスト１４２ａは、記憶領域が、距離によってカテゴライズされたブロックに分けられている。各ブロックには、起点ノードからの距離が、そのブロックに設定された距離と同じであるエッジが登録される。例えば「距離１」の欄には、起点ノードからの距離が「１」であるエッジが登録される。
【００７４】
図１０は、第１・第２差分エッジ記憶部内のデータの例を示す図である。第１差分エッジ記憶部１６１には、第１差分エッジリスト１６１ａが格納されている。第１差分エッジリスト１６１ａは、第１距離別エッジリスト１４１ａ内のある距離の欄には登録されているが、第２距離別エッジリスト１４２ａ内の同一距離の欄には登録されていないエッジの集合を示す。第２差分エッジ記憶部１６２には、第２差分エッジリスト１６２ａが格納されている。第２差分エッジリスト１６２ａは、第２距離別エッジリスト１４２ａ内のある距離の欄には登録されているが、第１距離別エッジリスト１４１ａ内の同一距離の欄には登録されていないエッジの集合を示す。
【００７５】
図１１は、第１・第２存在エッジ記憶部内のデータの例を示す図である。第１存在エッジ記憶部１６３には、第１存在エッジリスト１６３ａが格納されている。第１存在エッジリスト１６３ａは、第１差分エッジリスト１６１ａ内の複数のエッジそれぞれのハッシュ値を示すデータである。第２存在エッジ記憶部１６４には、第２存在エッジリスト１６４ａが格納されている。第２存在エッジリスト１６４ａは、第２差分エッジリスト１６２ａ内の複数のエッジそれぞれのハッシュ値を示すデータである。
【００７６】
図１２は、差分抽出結果記憶部内のデータの例を示す図である。差分抽出結果記憶部１８０には、２つのコールグラフ４０，４０ａの一方にのみ含まれるエッジの集合を示す最終差分エッジリスト１８１が格納されている。最終差分エッジリスト１８１には、エッジごとに、エッジを表す文字列の２つ組と、そのエッジが含まれていたコールグラフの識別番号とが設定されている。例えばコールグラフ４０の識別番号を「１」、コールグラフ４０ａの識別番号を「２」とする。この場合、コールグラフ４０に存在し、コールグラフ４０ａに存在しないエッジ４２ｋ（文字列の２つ組（“ｇ”，“ｋ”）には、コールグラフ４０の識別番号「１」が付与される。
【００７７】
＜処理手順＞
コンピュータ１００は、以上のようなデータを用いて、２つのコールグラフ４０，４０ａの差分エッジ抽出処理を行う。以下、差分エッジ抽出処理について詳細に説明する。
【００７８】
図１３は、差分エッジ抽出処理の手順を示すフローチャートである。以下、図１３に示す処理をステップ番号に沿って説明する。なお差分エッジ抽出処理は、差分抽出要求が入力されたときに実行される。
【００７９】
［ステップＳ１０１］差分抽出要求を受け付けた要求受付部１２０は、その差分抽出要求を、距離別エッジ分類部１３０に送信する。その後、ステップＳ１０２とステップＳ１０３の処理が並列に実行される。
【００８０】
［ステップＳ１０２］距離別エッジ分類部１３０は、差分抽出要求を取得すると、２つのスレッドを立ち上げる。そして距離別エッジ分類部１３０は、１つ目のスレッドにより、第１コールグラフ記憶部１１１内のコールグラフデータ１１１ａに対する距離別エッジ分類処理を実行する。これにより、第１距離別エッジリスト記憶部１４１に、第１距離別エッジリスト１４１ａが記憶される。
【００８１】
［ステップＳ１０３］距離別エッジ分類部１３０は、２つ目のスレッドにより、第２コールグラフ記憶部１１２内のコールグラフデータ１１２ａに対する距離別エッジ分類処理を実行する。これにより、第２距離別エッジリスト記憶部１４２に、第２距離別エッジリスト１４２ａが記憶される。
【００８２】
ステップＳ１０２，Ｓ１０３の距離別エッジ分類処理は、コールグラフ内のエッジを、起点ノードからの距離で分類する処理である。距離別エッジ分類処理の詳細は後述する（図１４参照）。ステップＳ１０２とステップＳ１０３の両方の処理が終了すると、処理がステップＳ１０４に進められる。
【００８３】
［ステップＳ１０４］距離別エッジ分類部１３０は、同一距離間エッジ比較処理を実行する。同一距離間エッジ比較処理では、第１距離別エッジリスト１４１ａと第２距離別エッジリスト１４２ａそれぞれにおける、起点ノードからの距離が同じカテゴリ内のエッジ集合同士が比較され、同一のエッジの有無が判断される。同一距離間エッジ比較処理により、第１差分エッジ記憶部１６１に第１差分エッジリスト１６１ａが格納され、第２差分エッジ記憶部１６２に第２差分エッジリスト１６２ａが格納される。また同一距離間エッジ比較処理により、第１存在エッジ記憶部１６３に第１存在エッジリスト１６３ａが格納され、第２存在エッジ記憶部１６４に第２存在エッジリスト１６４ａが格納される。同一距離間エッジ比較処理の詳細は後述する（図１５参照）。同一距離間エッジ比較処理が終了すると、ステップＳ１０５とステップＳ１０６との処理が並列で実行される。
【００８４】
［ステップＳ１０５］差分エッジ抽出部１７０は、２つのスレッドを立ち上げる。そして差分エッジ抽出部１７０は、１つ目のスレッドにより、第１差分エッジリスト１６１ａを対象として、距離違いエッジ存在確認処理を実行する。この距離違いエッジ存在確認処理では、第１差分エッジリスト１６１ａに含まれているが第２差分エッジリスト１６２ａには含まれていないエッジが特定される。
【００８５】
［ステップＳ１０６］差分エッジ抽出部１７０は、２つ目のスレッドにより、第２差分エッジリスト１６２ａを対象として、距離違いエッジ存在確認処理を実行する。この距離違いエッジ存在確認処理では、第２差分エッジリスト１６２ａに含まれているが第１差分エッジリスト１６１ａには含まれていないエッジが特定される。
【００８６】
ステップＳ１０５，Ｓ１０６の距離違いエッジ存在確認処理の詳細は後述する（図１６参照）。ステップＳ１０５，Ｓ１０６の距離違いエッジ存在確認処理により、差分抽出結果記憶部１８０内に最終差分エッジリスト１８１が格納される。ステップＳ１０５とステップＳ１０６の両方の処理が終了すると、処理がステップＳ１０７に進められる。
【００８７】
［ステップＳ１０７］結果返答部１９０は、差分抽出処理の結果を示す最終差分エッジリスト１８１を、差分抽出要求への応答として出力する。
以上のような手順で、２つのコールグラフ４０，４０ａ間の差分エッジを抽出することができる。以下、距離別エッジ分類処理（ステップＳ１０２，Ｓ１０３）、同一距離間エッジ比較処理（ステップＳ１０４）、および距離違いエッジ存在確認処理（ステップＳ１０５，Ｓ１０６）について、図１４〜図１６を参照して詳細に説明する。
【００８８】
図１４は、距離別エッジ分類処理の手順の一例を示すフローチャートである。以下、第１コールグラフ記憶部１１１内のコールグラフデータ１１１ａを処理対象とする場合を例に取り、図１４に示す処理をステップ番号に沿って説明する。
【００８９】
［ステップＳ１１１］距離別エッジ分類部１３０は、差分抽出要求で指定された、着目するメソッドに対応するノードを起点ノードとし、起点ノードの識別子のみが要素として登録された現ノードリストを生成する。現ノードリストに登録されるノードの識別子は、例えばそのノードに対応するメソッドのメソッド名である。生成された現ノードリストは、例えばメモリ１０２内に格納される。
【００９０】
［ステップＳ１１２］距離別エッジ分類部１３０は、比較対象の距離ｄに「１」を設定する。
［ステップＳ１１３］距離別エッジ分類部１３０は、内容が空の次ノードリストを生成する。生成された次ノードリストは、例えばメモリ１０２内に格納される。
【００９１】
［ステップＳ１１４］距離別エッジ分類部１３０は、コールグラフデータ１１１ａに含まれるすべてのエッジを、未探索の状態に設定する。例えば、距離別エッジ分類部１３０は、コールグラフデータ１１１ａ内のエッジに「探索済」を示すフラグが設定されていた場合、そのフラグを削除する。
【００９２】
［ステップＳ１１５］距離別エッジ分類部１３０は、現ノードリストに登録されている要素を、現在ノードとして１つ選択する。
［ステップＳ１１６］距離別エッジ分類部１３０は、現在ノードから探索方向に接続された、「探索済」のフラフが付与されていないエッジの１つを、探索対象として選択する。なお、探索方向は差分抽出要求において指定されている。探索方向が、呼び出し先方向であれば、距離別エッジ分類部１３０は、コールグラフデータ１１１ａから、現在ノードを呼び出し元とするエッジを１つ選択する。探索方向が、呼び出し元方向であれば、距離別エッジ分類部１３０は、コールグラフデータ１１１ａから、現在ノードを呼び出し先とするエッジを１つ選択する。
【００９３】
［ステップＳ１１７］距離別エッジ分類部１３０は、選択したエッジを、第１距離別エッジリスト１４１ａの距離ｄのブロックに格納する。そして距離別エッジ分類部１３０は、コールグラフデータ１１１ａの選択したエッジに「探索済」のフラグを設定する。
【００９４】
［ステップＳ１１８］距離別エッジ分類部１３０は、次ノードリストに、選択したエッジで接続される２つのノードのうち、現在ノード以外のノードを、次ノードリストに追加する。探索方向が呼び出し先方向であれば、選択したエッジの呼び出し先のノードが、次ノードリストに追加される。探索方向が呼び出し元方向であれば、選択したエッジの呼び出し元のノードが、次ノードリストに追加される。
【００９５】
［ステップＳ１１９］距離別エッジ分類部１３０は、現在ノードから探索方向に接続されたすべてのエッジを探索対象としたか否かを判断する。すべてのエッジを探索対象とした場合、処理がステップＳ１２０に進められる。探索対象としてないエッジがある場合、処理がステップＳ１１６に進められる。
【００９６】
［ステップＳ１２０］距離別エッジ分類部１３０は、現ノードリスト内のすべてのノードを処理したか否かを判断する。すべてのノードの処理が完了していれば、距離別エッジ分類処理が終了する。未処理のノードがあれば、処理がステップＳ１２１に進められる。
【００９７】
［ステップＳ１２１］距離別エッジ分類部１３０は、現ノードリストの内容を、次ノードリストの内容と一致させる。例えば距離別エッジ分類部１３０は、現ノードリストの内容をすべて削除した後、次ノードリストに登録されているすべてのノードを、現ノードリストに登録する。
【００９８】
［ステップＳ１２２］距離別エッジ分類部１３０は、次ノードリスト内の全ノードを削除し、次ノードリストを空にする。その後、処理がステップＳ１１５に進められる。
このようにして、コールグラフ４０に含まれるエッジ４２ａ〜４２ｋが、距離によってカテゴライズされ、第１距離別エッジリスト１４１ａに登録される。同様に、第２コールグラフ記憶部１１２内のコールグラフデータ１１２ａを処理対象として、図１４の距離別エッジ分類処理を実行すれば、コールグラフ４０ａに含まれるエッジ４２ａ〜４２ｃ，４２ｅ〜４２ｊ，４２ｌ，４２ｍが、距離によって分類される。そして各エッジ４２ａ〜４２ｃ，４２ｅ〜４２ｊ，４２ｌ，４２ｍが、距離ごとのカテゴリに分けて第２距離別エッジリスト１４２ａに登録される。その後、同一距離間エッジ比較部１５０により、同一距離間エッジ比較処理が実行される。
【００９９】
図１５は、同一距離間エッジ比較処理の手順の一例を示すフローチャートである。以下、図１５に示す処理をステップ番号に沿って説明する。
［ステップＳ１３１］同一距離間エッジ比較部１５０は、距離ｄに１を設定する。
【０１００】
［ステップＳ１３２］同一距離間エッジ比較部１５０は、第１距離別エッジリスト１４１ａの距離ｄのブロックに格納されたエッジを、所定の基準でソートする。例えば同一距離間エッジ比較部１５０は、エッジを表す２つ組の文字列に基づいて、アルファベット順で、同一の距離にカテゴライズされたエッジをソートする。そして同一距離間エッジ比較部１５０は、ソート後のエッジの配列を、第１リストとする。
【０１０１】
［ステップＳ１３３］同一距離間エッジ比較部１５０は、第２距離別エッジリスト１４２ａの距離ｄのブロックに格納されたエッジを、ステップＳ１３２と同様の基準でソートする。そして同一距離間エッジ比較部１５０は、ソート後のエッジの配列を、第２リストとする。
【０１０２】
［ステップＳ１３４］同一距離間エッジ比較部１５０は、第１リストの先頭エッジを、第１リストの着目点とする。同様に同一距離間エッジ比較部１５０は、第２リストの先頭エッジを、第２リストの着目点とする。
【０１０３】
［ステップＳ１３５］同一距離間エッジ比較部１５０は、第１リストの着目点のエッジと、第２リストの着目点のエッジとが同一か否かを判断する。エッジが同一であれば、処理がステップＳ１３６に進められる。エッジが同一でなければ、処理がステップＳ１３７に進められる。
【０１０４】
［ステップＳ１３６］同一距離間エッジ比較部１５０は、第１リストの着目点を、第１リストの現在の着目点のエッジの次のエッジに移動する。また同一距離間エッジ比較部１５０は、第２リストの着目点を、第２リストの現在の着目点のエッジの次のエッジに移動する。その後、処理がステップＳ１４４に進められる。
【０１０５】
［ステップＳ１３７］同一距離間エッジ比較部１５０は、第１リストの着目点のエッジと第２リストの着目点のエッジとについて、ステップＳ１３２，Ｓ１３３のソート条件に基づく大小を比較する。例えば同一距離間エッジ比較部１５０は、ソート条件において上位になるエッジほど、小さいエッジであると判断する。第１リストの着目点のエッジの方が小さければ、処理がステップＳ１３８に進められる。第２リストの着目点のエッジの方が小さければ、処理がステップＳ１４１に進められる。
【０１０６】
［ステップＳ１３８］同一距離間エッジ比較部１５０は、第１差分エッジリスト１６１ａに、第１リストの着目点のエッジを追加する。
［ステップＳ１３９］同一距離間エッジ比較部１５０は、第１存在エッジリスト１６３ａに、第１リストの着目点のエッジのハッシュ値を追加する。
【０１０７】
［ステップＳ１４０］同一距離間エッジ比較部１５０は、第１リストの着目点を、第１リストの現在の着目点のエッジの次のエッジに移動する。その後、処理がステップＳ１４４に進められる。
【０１０８】
［ステップＳ１４１］同一距離間エッジ比較部１５０は、第２差分エッジリスト１６２ａに、第２リストの着目点のエッジを追加する。
［ステップＳ１４２］同一距離間エッジ比較部１５０は、第２存在エッジリスト１６４ａに、第２リストの着目点のエッジのハッシュ値を追加する。
【０１０９】
［ステップＳ１４３］同一距離間エッジ比較部１５０は、第２リストの着目点を、第２リストの現在の着目点のエッジの次のエッジに移動する。
［ステップＳ１４４］同一距離間エッジ比較部１５０は、第１リストと第２リストとの両方において、すべてのエッジを比較済みか否かを判断する。すべてのエッジを比較済みであれば、処理がステップＳ１４５に進められる。第１リストと第２リストとの少なくとも一方に、比較していないエッジ（着目点になっていないエッジ）があれば、処理がステップＳ１３５に進められる。
【０１１０】
なお、第１リストと第２リストの一方において、すべてのエッジが比較済みとなっている場合、比較対象として残存しているエッジは、同一または大小の比較の相手が存在しない。その場合、比較対象として残存しているエッジについて、ステップＳ１３５の同一性判定では「ＮＯ」と判断される。またステップＳ１３７の大小判定では、比較対象として残存しているエッジの方が小さいと判定される。
【０１１１】
［ステップＳ１４５］同一距離間エッジ比較部１５０は、カテゴリとして存在するすべての距離ｄについて処理を実施したか否かを判断する。すべての距離ｄについて処理が完了した場合、同一距離間エッジ比較処理が終了する。未処理の距離があれば、処理がステップＳ１４６に進められる。
【０１１２】
［ステップＳ１４６］同一距離間エッジ比較部１５０は、距離ｄの値に１を加算し、処理をステップＳ１３２に進める。
このようにして、第１差分エッジリスト１６１ａ、第２差分エッジリスト１６２ａ、第１存在エッジリスト１６３ａ、および第２存在エッジリスト１６４ａが生成される。その後、差分エッジ抽出部１７０により、距離違いエッジ存在確認処理（ステップＳ１０５，Ｓ１０６）が実行される。
【０１１３】
図１６は、距離違いエッジ存在確認処理の手順の一例を示すフローチャートである。以下、第１差分エッジ記憶部１６１内の第１差分エッジリスト１６１ａを、エッジの抽出元として処理を実行する場合を例に取り、図１６に示す処理をステップ番号に沿って説明する。
【０１１４】
［ステップＳ１５１］差分エッジ抽出部１７０は、第１差分エッジリスト１６１ａから未処理のエッジを１つ選択する。
［ステップＳ１５２］差分エッジ抽出部１７０は、選択したエッジのハッシュ値を計算し、そのハッシュ値が第２存在エッジリスト１６４ａ内に存在するか否かを判断する。ハッシュ値が存在する場合、処理がステップＳ１５４に進められる。ハッシュ値が存在しなければ、処理がステップＳ１５３に進められる。
【０１１５】
［ステップＳ１５３］差分エッジ抽出部１７０は、選択したエッジに、そのエッジの抽出元のソースコードの識別子を付与し、差分抽出結果記憶部１８０内の最終差分エッジリスト１８１に追加する。
【０１１６】
［ステップＳ１５４］差分エッジ抽出部１７０は、第１差分エッジリスト１６１ａ内のすべてのエッジを処理したか否かを判断する。すべてのエッジの処理が完了した場合、距離違いエッジ存在確認処理が終了する。未処理のエッジがあれば、処理がステップＳ１５１に進められる。
【０１１７】
このようにして、起点ノードからの距離違いエッジ間で、同一エッジが他方のコールグラフに存在しているかどうかが確認され、存在していないエッジのみが、最終差分エッジリスト１８１に格納される。そして、最終差分エッジリスト１８１内のエッジが、差分抽出要求に対する応答として出力される。
【０１１８】
＜第２の実施の形態の効果＞
以上説明したように、第２の実施の形態によれば、起点ノードから距離で分類し、最初に同一距離のエッジ間で差分を抽出するようにしたことで、各エッジについての同一エッジの存否確認が容易となる。その結果、処理が高速化される。
【０１１９】
ここで、第２の実施の形態に示した差分抽出処理の処理時間を、他の差分抽出処理による処理時間と比較する。比較対象の差分抽出方法として、以下の２つの参考手法を想定する。
【０１２０】
［第１参考手法］一方のコールグラフ内の各エッジを他方のコールグラフ内の全エッジと総当たりで比較する手法である。この手法では、一致したエッジは双方のコールグラフにあり、一致しなかったエッジは一方のコールグラフのみにあることが検出される。
【０１２１】
［第２参考手法］それぞれのコールグラフ内のエッジ群をソートし、ソート後のエッジのリスト同士を比較し、相違するエッジを抽出する方法である。この手法では、コールグラフごとにエッジをソートした後、２つのソート済みエッジリストを先頭から順に着目点を移動させながら比較するものである。一致した場合は，双方のリストで着目点が次エッジに移され、不一致の場合、比較して小さい方のエッジがあるリストのみ次のエッジに着目点が移される。一致したエッジは双方のコールグラフにあり、一致しないエッジは比較して小さい方のエッジが一方のコールグラフのみにあると判定される。この第２参考手法は、第２の実施の形態の手法から、距離別エッジ分類処理を除外したものである。
【０１２２】
以下、図１７、図１８を参照し、第１・第２参考手法それぞれと、第２の実施の形態に係る手法との差分抽出処理の時間を比較する。なお以下の説明では、変数Ｍ、Ｎ、ｋ、ｒ、ｎを用いて、所要時間を計算する。各変数の意味は、以下の通りである。
Ｍ，Ｎ：それぞれのコールグラフに含まれるエッジの数
ｋ：対象範囲の半径（起点メソッドから呼び出し元・先のメソッドの距離の最大値）
ｒ：２つのコールグラフの元となった２つのソースコードセットの間の違いのある割合（違いのある箇所数／（違いのある箇所数＋違いのない箇所数））
ｎ：１つのメソッドを呼び出す（または呼び出される）メソッドの数
＜＜第１参考手法との比較＞＞
第１参考手法では、エッジ間の一致判定が総当たりで行われる。ここで、２つのエッジの比較１回当たりの所要時間を単位時間として、その単位時間の何倍の時間で差分抽出処理が完了するのかを計算する。第１参考手法の場合、差分抽出に要する時間ｒｔ０は、以下の式で表される。
ｒｔ０＝ＭＮ  ・・・（１）
一方、第２の実施の形態に示す手法で差分抽出処理を行う場合の所要時間ｒｔ２は、以下の式で表すことができる。
ｒｔ２＝Ｍｌｏｇ2（Ｍ／ｋ）＋Ｎｌｏｇ2（Ｎ／ｋ）＋Ｍ＋Ｎ＋ｒＭ＋ｒＮ
・・・（２）
式（２）の右辺の第１項「Ｍｌｏｇ2（Ｍ／ｋ）」は、２つのコールグラフのうちの一方のコールグラフの１つのカテゴリ（距離）に属するエッジのソートに要する時間を示している。１つのカテゴリのソートに「（Ｍ／ｋ）ｌｏｇ2（Ｍ／ｋ）」の時間を要し、その時間にカテゴリ数ｋを乗算することで「Ｍｌｏｇ2（Ｍ／ｋ）」が得られる。第２項「Ｎｌｏｇ2（Ｎ／ｋ）」は、他方のコールグラフの１つのカテゴリに属するエッジのソートに要する時間を示している。
【０１２３】
第３項「Ｍ」と第４項「Ｎ」とは、同一カテゴリのエッジ間での比較に要する時間である。１つのカテゴリについての比較に要する時間は「（Ｍ／ｋ）＋（Ｎ／ｋ）」であり、その時間にカテゴリ数ｋを乗算することで「Ｍ＋Ｎ」が得られる。
【０１２４】
第５項「ｒＭ」と第６項「ｒＮ」とは、同一カテゴリのエッジ間の比較で、同じエッジが見つからなかった差分エッジについて、異なるカテゴリのエッジとの比較に要する時間である。
【０１２５】
ここで、２つのコールグラフの元となった２つのソースコードセットの間に、微小な違いしかない場合、１つのメソッドを呼び出す（または呼び出される）メソッドの数ｎを用いて、以下の近似が可能である（以下の「〜」は近似記号）。
【０１２６】
【数１】
2017142712.tif 000003
【０１２７】
この場合、ｒｔ０とｒｔ２は、以下のようになる。
ｒｔ０〜Ｍ2〜ｎ2k    ・・・（４）
ｒｔ２〜２Ｍ（ｌｏｇ2（Ｍ／ｋ）＋１＋ｒ）〜２ｎk（ｋｌｏｇ2ｄ−ｌｏｇ2ｋ＋１＋ｒ）    ・・・（５）
多くの場合ｎ〜５となる。また様々なシステムのＯＳのマイナーバージョンアップでは、ｒ〜０．０１程度である。このような条件で改善率を計算すると、図１７に示すようになる。
【０１２８】
図１７は、第１参考手法と第２の実施の形態に係る手法との比較例を示す図である。図１７には、起点ノードからの距離の最大値に応じた、差分抽出時間の改善率を示している。改善率は以下の式で計算される。
改善率＝（ｒｔ０−ｒｔ２）／ｒｔ０）    ・・・（６）
なお図１７では、改善率をパーセントで表記している（式（６）の値×１００）。この例では、ｋ＝２以上の場合、４９％以上の高速化が図れることが分かる。
【０１２９】
＜＜第２参考手法との比較＞＞
第２参考手法の場合、差分抽出に要する時間ｒｔ１は、以下の式で表すことができきる。
ｒｔ１＝Ｍｌｏｇ2Ｍ＋Ｎｌｏｇ2Ｎ＋Ｍ＋Ｎ    ・・・（７）
式（７）の右辺の第１項「Ｍｌｏｇ2Ｍ」は、一方のコールグラフのエッジのソートに要する時間を表している。第２項「Ｎｌｏｇ2Ｎ」は、他方のコールグラフのエッジのソートに要する時間を表している。第３項「Ｍ」と第４項「Ｎ」は、ソート済みのリスト内のエッジ同士を比較する時間である。
【０１３０】
式（３）に示した近似を行うと、ｒｔ１は以下のようになる。
ｒｔ１〜２Ｍ（ｌｏｇ2Ｍ＋１）〜２ｎk（ｋｌｏｇ2ｄ＋１）    ・・・（８）
ここで、ｎ〜５、ｒ〜０．０１という条件で改善率を計算すると、図１８に示すようになる。
【０１３１】
図１８は、第２参考手法と第２の実施の形態に係る手法との比較例を示す図である。図１８には、起点ノードからの距離の最大値に応じた、差分抽出時間の改善率を示している。改善率は以下の式で計算される。
改善率＝（ｒｔ１−ｒｔ２）／ｒｔ１）    ・・・（９）
なお図１８では、改善率をパーセントで表記している（式（９）の値×１００）。この例では、ｋ＝２以上の場合、２０％程度の高速化が図れることが分かる。
【０１３２】
このように、第２の実施の形態では、起点ノードからの距離に応じたエッジの分類と、同一距離に属するエッジをソートした上での比較とを行うことで、高速な差分抽出処理が可能となっている。
【０１３３】
＜＜その他の効果＞＞
第２の実施の形態では、コンピュータ１００は、同一距離間エッジ比較の結果差分として抽出されたエッジのハッシュ値を計算し、第１存在エッジリスト１６３ａと第２存在エッジリスト１６４ａとを生成している。そして第１存在エッジリスト１６３ａと第２存在エッジリスト１６４ａとを、距離違いエッジ存在確認時の検索対象としている。このように、ハッシュ値によってエッジ存在確認を行うことで、処理が効率化される。例えば、エッジを示す、メソッドの完全修飾名を表す２つの文字列の組の比較をすると、比較対象の文字列が長いことから、メモリ消費量が多くなるとともに、比較にも時間がかかる。ＭＤ５（Message Digest 5）などのハッシュ値に変換して比較をすれば、比較対象の文字列が短くなり、メモリ容量が少なくて済むと共に、処理時間も短縮される。
【０１３４】
例えば、スマートフォンやタブレット端末などの携帯情報端末機器用のＯＳでは、メソッドの完全修飾名として、以下のような名前が用いられている。なお、以下に示す名前に使用されている文字は、半角文字であるものとする。
・google.protobuf.compiler.StaticDescriptorInitializer＿google＿2fprotobuf＿2fcompiler＿2fplugin＿2eproto.StaticDescriptorInitializer＿google＿2fprotobuf＿2fcompiler＿2fplugin＿2eproto （１７２文字）
・＿＿gnu＿pbds.detail.left＿child＿next＿sibling＿heap＿node＿point＿const＿iterator＿.left＿child＿next＿sibling＿heap＿node＿point＿const＿iterator＿ （１２９文字）
・extensions.FileBrowserPrivateLogoutUserForReauthenticationFunction.FileBrowserPrivateLogoutUserForReauthenticationFunction  （１２２文字）
・line＿map.tree＿base.tree＿decl＿common.tree＿decl＿with＿vis.tree＿function＿decl.VEC＿call＿site＿record＿base＿unordered＿remove （１１６文字）
当該ＯＳでは約６０万のメソッドがあり、完全修飾名の最長が２７９文字、最短が５文字、平均が４６．２文字、標準偏差は１５．６文字である。エッジのデータ構造には、このような長いメソッド名の２つ組が含まれる。
【０１３５】
エッジを示す文字列を例えばＭＤ５のハッシュ値に変換すると１２８ビット長となる。１２８ビットは、ＡＳＣＩＩコード（７ビット）でエンコードした文字だと約１８文字相当である。すると、上記平均長の完全修飾名の２つ組の長さ（約９３文字）方が（標準偏差を考慮しても）、ハッシュ値よりも十分長い。
【０１３６】
従って、エッジのハッシュ値を用いて同一距離間エッジ比較処理を行うことで、少ないデータ量による効率的な処理が可能となる。
以上が第２の実施の形態についての説明である。
【０１３７】
〔その他の実施の形態〕
第２の実施の形態では、第１存在エッジリスト１６３ａと第２存在エッジリスト１６４ａとを用いて距離違いエッジ存在確認を行っているが、第１存在エッジリスト１６３ａと第２存在エッジリスト１６４ａとを用いずに距離違いエッジ存在確認を行ってもよい。その場合、第１差分エッジリスト１６１ａ内のエッジのうち、第２差分エッジリスト１６２ａに同一エッジが存在しないエッジが抽出され、最終差分エッジリスト１８１に登録される。同様に第２差分エッジリスト１６２ａ内のエッジのうち、第１差分エッジリスト１６１ａに同一エッジが存在しないエッジが抽出され、最終差分エッジリスト１８１に登録される。
【０１３８】
このように、第１差分エッジリスト１６１ａと第２差分エッジリスト１６２ａとを検索対象とする場合、エッジを、各エッジの文字列の２つ組をキー（配列の添え字）とした連想配列で保持してもよい。このとき、キーに応じた連想配列の値（value）は、空欄あるいは「０」などの所定値でよい。すなわち、処理対象のエッジの２つ組の文字列をキーとして連想配列を読み出したとき、対応する値が読み出されれば、そのエッジと同一のエッジが存在することとなり、エラーとなれば、そのエッジと同一のエッジが存在しないこととなる。このように、エッジを示す２つ組の文字列を連想配列に格納することで、第１差分エッジリスト１６１ａと第２差分エッジリスト１６２ａとの一方に存在するエッジが、他方に存在するか否かの検索を効率的に実施することができる。
【０１３９】
また各エッジのハッシュ値を配列のキーとして、第１存在エッジリスト１６３ａと第２存在エッジリスト１６４ａとを保持することも可能である。これにより、第１存在エッジリスト１６３ａと第２存在エッジリスト１６４ａに基づくエッジの存在確認を高速に行うことができる。
【０１４０】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。
【符号の説明】
【０１４１】
１  第１コールグラフ
１ａ〜１ｄ  第１ノード
１ｅ〜１ｇ  第１エッジ
２  第２コールグラフ
２ａ〜２ｅ  第２ノード
２ｆ〜２ｉ  第２エッジ
３  第１距離別エッジリスト
４  第２距離別エッジリスト
５  第１差分エッジリスト
６  第２差分エッジリスト
７  最終差分エッジリスト
１０  情報処理装置
１１  記憶部
１２  演算部
１２ａ  分類部
１２ｂ  特定部
１２ｃ  抽出部
【図１】
2017142712.tif 000004
【図２】
2017142712.tif 000005
【図３】
2017142712.tif 000006
【図４】
2017142712.tif 000007
【図５】
2017142712.tif 000008
【図６】
2017142712.tif 000009
【図７】
2017142712.tif 000010
【図８】
2017142712.tif 000011
【図９】
2017142712.tif 000012
【図１０】
2017142712.tif 000013
【図１１】
2017142712.tif 000014
【図１２】
2017142712.tif 000015
【図１３】
2017142712.tif 000016
【図１４】
2017142712.tif 000017
【図１５】
2017142712.tif 000018
【図１６】
2017142712.tif 000019
【図１７】
2017142712.tif 000020
【図１８】
2017142712.tif 000021