SCE: Structural Cross Entropy for Code Similarity

Compute Structural Cross Entropy (SCE) and Jensen–Shannon-divergence-based similarity between two code snippets, using Tree-sitter abstract syntax trees.

Each snippet is parsed into an AST, and subtrees (a node type plus its child types, optionally with leaf token values) are counted up to max_depth. The two subtree frequency distributions are then compared with cross entropy or Jensen–Shannon divergence.

Installation

Available on PyPI:

pip install code-sce

Requires Python 3.9+.

Quick Start

from code_sce import (
    compute_cte_jsd_struct,
    compute_cte_jsd_value,
    compute_sce_norm_struct,
    compute_sce_norm_value,
)

code1 = """
if x >= 0:
    sign = "non-negative"
else:
    sign = "negative"
print(sign)
"""

code2 = """
if x >= 0:
    sign = "non-negative"
    print(sign)
else:
    sign = "negative"
    print(sign)
"""

lang = "python"
max_depth = 10

print(f"JSD Struct:      {compute_cte_jsd_struct(lang, code1, code2, max_depth):.6f}")
print(f"SCE-Norm Struct: {compute_sce_norm_struct(lang, code1, code2, max_depth):.6f}")
print(f"JSD Value:       {compute_cte_jsd_value(lang, code1, code2, max_depth):.6f}")
print(f"SCE-Norm Value:  {compute_sce_norm_value(lang, code1, code2, max_depth):.6f}")

Output:

JSD Struct:      0.933744
SCE-Norm Struct: 0.607837
JSD Value:       0.932699
SCE-Norm Value:  0.626398

Metrics

All four have the signature metric(lang, code_a, code_b, max_depth=30, eps=1e-10) and return 1.0 for identical code. The *_struct variants ignore identifier names and literals; the *_value variants take them into account.

Configuration Options

• lang: a language name supported by tree-sitter-language-pack (e.g. "python", "sql", "javascript", "java").
• max_depth: how deep the AST traversal goes (root is depth 1). Increase for more detailed subtree extraction; decrease to speed up comparisons.
• eps: smoothing constant (default 1e-10) that prevents zero-probability issues when computing entropy/divergence.

Notes

• The JSD-based functions compute

  JS Divergence = 0.5 * [KL(P || M) + KL(Q || M)],  where M = (P + Q)/2
  

  and return 1 - JSD as a similarity score.

• If a divergence calculation yields NaN, the functions print a warning and use JSD = 1.0 (similarity 0.0).

Development

git clone https://github.com/Etamin/SCE
cd SCE
pip install -e ".[test]"
pytest