順序木の類似度を評価する手法の提案－C言語プログラムの類似性検証への応用

摘要

本論文では，与えられた2つの順序木の類似度を効率的に評価する方法について論じる．順序木の類似度計算手法として，順序木を文字列に変換して文字列の編集距離を計算することによって木の編集距離を近似する方法が提案されている．それに対して，本研究では与えられた2つの順序木について，文字列に変換するのではなく，同じ深さのノードの最大マッチングを行って順序木の類似度を計算する．まずは，すべてのノードについて，根ノードからの距離を求め，同じ深さのノードに対応する2部グラフを作る．作られた2部グラフの最大マッチングを求め，マッチングが取れたノードの数に基づいて順序木の類似度を計算する．このように提案した．手法をC言語プログラムの類似性判定に応用し，提案手法の有効性を確認する．