寻找相似公式的算法
Algorithm for finding similar formulas
我正在寻找一些算法来以定量的方式找到 similar 公式。
例如，给定以下三个公式：
1. test = a + 4 - b
2. test = a - 16 + 2 * b
3. test = a + 5
我可以通过某种方式计算它们之间的相似度，比如说：
Similarity(1,2) = 0.5
Similairty(2,3) = 0.1
有什么标准的方法吗？基本上我想我需要从每个公式中提取一些数字向量，代表它们的特征，但我不知道该怎么做..
谁能帮帮我？谢谢
我将采用的方法是为表达式生成解析树，然后应用树差异度量。有很多可供选择（在网络上搜索 "tree distance metric"、"parse tree distance" 或 "parse tree similarity") 甚至更多，如果你限制自己使用二叉树（没有三元运算符，如 ?:）。通常的做法是使用tree edit distance。您需要解决几个问题：
- 变量名称更改会影响相似性吗？
- 交换运算符的操作数重新排序会影响相似性吗？ （例如，
a + b*c 与 b*c + a。）
P.S。可以找到一篇关于测量树结构之间相似性的不错 survey-type 文章 here。
我假设您正在寻找这些公式的 compare/check 相似度的度量标准。如果它们中的每一个都只包含三个变量 test、a 和 b，那么一个非常简单的度量是取 a、b 和常量的值。
然后你可以用这样的公式来判断相似度：
similarity = (ratio of constants) * X^2 + 2 * (ratio of coefficients of a) * X + (ratio of coefficients of b)。 X中的这个二次方程的根越接近-1，相似度越高。
我们可以将每个多项式表示为单项式的总和。然后假设我们可以比较单项式，我们比较每对来自第一个多项式的单项式和来自第二个多项式的单项式，然后我们使用匹配算法找到使我们在对中的差异总和最小的匹配。如果一个多项式的单项式比另一个多项式多，我们只需添加所需的 0 个单项式 (A+0+0+0+0....)。然后剩下的就是找到 2 个单项式之间的区别，我建议按照 Ted Hopp 建议的方式进行。这样你应该得到比直接比较原始多项式更准确的结果。
我正在寻找一些算法来以定量的方式找到 similar 公式。
例如，给定以下三个公式：
1. test = a + 4 - b
2. test = a - 16 + 2 * b
3. test = a + 5
我可以通过某种方式计算它们之间的相似度，比如说：
Similarity(1,2) = 0.5
Similairty(2,3) = 0.1
有什么标准的方法吗？基本上我想我需要从每个公式中提取一些数字向量，代表它们的特征，但我不知道该怎么做..
谁能帮帮我？谢谢
我将采用的方法是为表达式生成解析树，然后应用树差异度量。有很多可供选择（在网络上搜索 "tree distance metric"、"parse tree distance" 或 "parse tree similarity") 甚至更多，如果你限制自己使用二叉树（没有三元运算符，如 ?:）。通常的做法是使用tree edit distance。您需要解决几个问题：
- 变量名称更改会影响相似性吗？
- 交换运算符的操作数重新排序会影响相似性吗？ （例如，
a + b*c与b*c + a。）
P.S。可以找到一篇关于测量树结构之间相似性的不错 survey-type 文章 here。
我假设您正在寻找这些公式的 compare/check 相似度的度量标准。如果它们中的每一个都只包含三个变量 test、a 和 b，那么一个非常简单的度量是取 a、b 和常量的值。
然后你可以用这样的公式来判断相似度：
similarity = (ratio of constants) * X^2 + 2 * (ratio of coefficients of a) * X + (ratio of coefficients of b)。 X中的这个二次方程的根越接近-1，相似度越高。
我们可以将每个多项式表示为单项式的总和。然后假设我们可以比较单项式，我们比较每对来自第一个多项式的单项式和来自第二个多项式的单项式，然后我们使用匹配算法找到使我们在对中的差异总和最小的匹配。如果一个多项式的单项式比另一个多项式多，我们只需添加所需的 0 个单项式 (A+0+0+0+0....)。然后剩下的就是找到 2 个单项式之间的区别，我建议按照 Ted Hopp 建议的方式进行。这样你应该得到比直接比较原始多项式更准确的结果。