提出算法相似性度量框架EMOC，可量化不同算法间的差异。
Towards a Measure of Algorithm Similarity
- 构建EMOC框架，将算法实现映射到特征空间
- 在三个问题上验证了算法聚类与近似重复检测能力
- 适合用于程序克隆检测和大模型生成代码的多样性分析
针对同一问题的两个算法是否具有实质性差异，这一问题在理论上不可计算，实践中又受多种相似性定义干扰。为应对程序克隆检测与程序合成等应用需求，本文回顾现有等价性与相似性概念，提出EMOC：一种基于评估、记忆、操作与复杂度的算法特征嵌入框架，将算法实现映射至适合下游任务的特征空间。我们构建了PACD数据集，包含三个问题下经验证的Python实现，并证明EMOC特征可支持算法类型分类、聚类、近似重复检测，以及对大语言模型生成代码多样性的量化。相关代码、数据与工具已开源，以促进可复现性与后续研究。
原文摘要 · Abstract (English)
Given two algorithms for the same problem, can we determine whether they are meaningfully different? In full generality, the question is uncomputable, and empirically it is muddied by competing notions of similarity. Yet, in many applications (such as clone detection or program synthesis) a pragmatic and consistent similarity metric is necessary. We review existing equivalence and similarity notions and introduce EMOC: An Evaluation-Memory-Operations-Complexity framework that embeds algorithm implementations into a feature space suitable for downstream tasks. We compile PACD, a curated dataset of verified Python implementations across three problems, and show that EMOC features support clustering and classification of algorithm types, detection of near-duplicates, and quantification of diversity in LLM-generated programs. Code, data, and utilities for computing EMOC embeddings are released to facilitate reproducibility and future work on algorithm similarity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。