類似性検出

検出方法論

similarity-goは、コード類似性を検出するために多層アプローチを採用し、複数のアルゴリズムを組み合わせて包括的で正確な結果を提供します。この方法論により、フォーマット、変数名、または軽微な構造的変更の表面的な違いに関係なく、類似したコードが識別されることが保証されます。

アルゴリズムの概要

3層検出システム

1. 構文層 - AST構造解析
2. 字句層 - トークンシーケンス比較
3. 意味層 - 機能的動作分析

各層は最終的な類似性スコアに寄与し、異なる使用ケースに適応するために構成可能な重みを持ちます。

構文解析（ASTベース）

構文層は、Go関数のAbstract Syntax Tree構造を分析します。

主な特徴

• 構造比較: ツリートポロジーとノード関係を比較
• パターン認識: 一般的なプログラミングパターンを識別
• 制御フロー解析: 分岐とループ構造を検査

重み付け要因

要素	重み	根拠
制御構造	35%	プログラムロジックを定義
関数呼び出し	25%	操作を示す
変数操作	20%	データ操作を表示
式	15%	計算パターン
リテラル	5%	軽微な実装詳細

字句解析（トークンベース）

字句層は、ソースコードから抽出されたトークンのシーケンスを比較します。

類似性メトリクス

最長共通部分列（LCS）

同じ順序で現れる最長のトークンシーケンスを見つけます。

Similarity_LCS = 2 × LCS(tokens1, tokens2) / (len(tokens1) + len(tokens2))

Jaccard指数

トークンセット間の重複を測定します。

Jaccard = |tokens1 ∩ tokens2| / |tokens1 ∪ tokens2|

編集距離

1つのトークンシーケンスを別のシーケンスに変換するための最小操作数を計算します。

Similarity_Edit = 1 - (EditDistance / max(len(tokens1), len(tokens2)))

意味解析

意味層は、コードの機能的動作を理解しようとします。

データフロー解析

データが関数を通してどのように移動するかを追跡：

type DataFlowAnalyzer struct {
    cfg *ControlFlowGraph
}

func (d *DataFlowAnalyzer) AnalyzeDataFlow(fn *ast.FuncDecl) *DataFlowGraph {
    // データフローグラフを構築
    dfg := &DataFlowGraph{}

    // 変数の定義と使用を追跡
    ast.Inspect(fn, func(n ast.Node) bool {
        switch node := n.(type) {
        case *ast.AssignStmt:
            d.processAssignment(dfg, node)
        case *ast.CallExpr:
            d.processFunctionCall(dfg, node)
        }
        return true
    })

    return dfg
}

制御フロー解析

関数を通る実行パスを検査：

• 基本ブロック: 分岐のない命令シーケンス
• 分岐点: 条件文とループ
• 支配関係: ブロック間の制御依存関係

機能等価検出

同じ入力に対して同じ出力を生成する関数を識別：

func detectFunctionalEquivalence(f1, f2 *Function) float64 {
    // 入力/出力シグネチャを比較
    sigSimilarity := compareSignatures(f1.Signature, f2.Signature)

    // 副作用を比較
    effectSimilarity := compareSideEffects(f1.Effects, f2.Effects)

    // 計算複雑度を比較
    complexitySimilarity := compareComplexity(f1.Complexity, f2.Complexity)

    return weightedAverage(sigSimilarity, effectSimilarity, complexitySimilarity)
}