需要一种算法来检测两个文件之间的差异以进行添加和重新排序
Need an algorithm that detects diffs between two files for additions and reorders
我想弄清楚是否有现有算法可以检测两个文件之间在添加和重新排序方面的变化。我在下面有一个例子：
1 - 用户 1 提交
processes = 1
a = 0
allactive = []
2 - 用户 2 提交
processes = 2
a = 0
allrecords = range(10)
allactive = []
3 - 用户 3 提交
a = 0
allrecords = range(10)
allactive = []
processes = 2
我需要能够说明，例如 user1 代码是代码的前三行，用户 2 添加了 "allrecords = range(10)" 部分（以及数字更改），而用户 3 没有更改自从 he/she 刚刚重新排序代码以来的任何事情。
理想情况下，在提交 3 时，我希望能够查看代码并说明从字符 0 到 20（这是用户 1 的代码）、21-25 用户 2 的代码、26-30 用户 1 的代码等
我知道有两种流行的算法，最长公共子序列和最长公共子串，但我不确定哪一种可以正确计算新代码的添加，但也能够识别重新排序。
当然，这仍然排除了同一子字符串在文本中出现两次的问题。还有其他算法更适合这个问题吗？
每个 "diff" 算法都定义了一组可能的代码更改编辑类型，然后（通常）尝试找到最小的此类更改集来解释新文件是如何从旧文件产生的。通常这样的算法是纯粹从句法上定义的；不考虑语义。
因此，根据您的示例，您想要的是一种允许 "change line"、"insert line"、"move line"（并且大概 "delete line" [不在您的示例中）的算法但对于一组实际的编辑是必要的]）。鉴于此，您应该能够定义一个动态编程算法来找到最小的编辑集来解释一个文件与另一个文件的不同之处。请注意，这个集合是根据对整行的编辑来定义的，而不是像经典的 "diff"；当然经典 diff 没有 "change line" 或 "move line" 这就是为什么你要找别的东西。
您可以选择不同类型的增量。您的示例明确指出 "number change"；如果狭义地解释，这不是行内编辑，而是行内编辑。一旦开始允许部分行编辑，您需要定义允许部分行编辑的范围 ("unit of change")。 （您的编辑集允许 "change of digit" 吗？）
我们的 Smart Differencer 系列工具定义了对目标语言明确定义的子短语的编辑集；我们使用形式语言文法（非）终结符作为变化的单位。 [这使得家族中的每个成员都特定于某种语言的语法]Delta 包括以程序员为中心的概念，例如 "replace phrase by phrase"、"delete listmember"、"move listmember"、"copy listmember"、"rename identifier"；该算法通过根据这些操作计算最小的树差异来运行。为此，SmartDifferencer 需要（并且拥有）该语言的完整解析器（生成 AST）。
您没有为示例指定语言。但一般来说，对于看起来像这样的语言，SmartDifferencer 通常会报告 User2 提交更改是：
- 将第 1 行第 13 列中的（数字文字）“1”替换为“2”
- 在第 2 行
之后插入（语句）"allrecords = range(10)"
并且 User3 提交的更改是：
- 在第 4 行之后的第 1 行移动（语句）
如果您知道谁贡献了原始代码，通过编辑您可以直接确定谁贡献了最终答案的哪一部分。你必须决定报告的单位；例如，如果您想逐行报告此类贡献以便于阅读，或者如果您真的想跟踪 Mary 编写的代码，但 Joe 修改了数字。
检测 User3 的更改语义 null 无法使用任何类型的纯语法驱动的差异工具来完成。为此，该工具必须能够以某种方式计算语法增量，然后计算所有语句的副作用（好吧，"phrases"），需要一个完整的语言静态分析器来解释增量以查看如果他们有这样的无效效果。这样的静态分析器无论如何都需要一个解析器，所以做一个基于树的差异器是有意义的，但它需要的不仅仅是解析器[我们有这样的语言前端，并考虑过构建这样的工具，但还没有做到这一点].
底线：没有用于确定 "that user3 did not change anything" 的简单算法。有理由希望可以构建这样的工具。
我想弄清楚是否有现有算法可以检测两个文件之间在添加和重新排序方面的变化。我在下面有一个例子：
1 - 用户 1 提交
processes = 1
a = 0
allactive = []
2 - 用户 2 提交
processes = 2
a = 0
allrecords = range(10)
allactive = []
3 - 用户 3 提交
a = 0
allrecords = range(10)
allactive = []
processes = 2
我需要能够说明，例如 user1 代码是代码的前三行，用户 2 添加了 "allrecords = range(10)" 部分（以及数字更改），而用户 3 没有更改自从 he/she 刚刚重新排序代码以来的任何事情。
理想情况下，在提交 3 时，我希望能够查看代码并说明从字符 0 到 20（这是用户 1 的代码）、21-25 用户 2 的代码、26-30 用户 1 的代码等
我知道有两种流行的算法，最长公共子序列和最长公共子串，但我不确定哪一种可以正确计算新代码的添加，但也能够识别重新排序。
当然，这仍然排除了同一子字符串在文本中出现两次的问题。还有其他算法更适合这个问题吗？
每个 "diff" 算法都定义了一组可能的代码更改编辑类型，然后（通常）尝试找到最小的此类更改集来解释新文件是如何从旧文件产生的。通常这样的算法是纯粹从句法上定义的；不考虑语义。
因此，根据您的示例，您想要的是一种允许 "change line"、"insert line"、"move line"（并且大概 "delete line" [不在您的示例中）的算法但对于一组实际的编辑是必要的]）。鉴于此，您应该能够定义一个动态编程算法来找到最小的编辑集来解释一个文件与另一个文件的不同之处。请注意，这个集合是根据对整行的编辑来定义的，而不是像经典的 "diff"；当然经典 diff 没有 "change line" 或 "move line" 这就是为什么你要找别的东西。
您可以选择不同类型的增量。您的示例明确指出 "number change"；如果狭义地解释，这不是行内编辑，而是行内编辑。一旦开始允许部分行编辑，您需要定义允许部分行编辑的范围 ("unit of change")。 （您的编辑集允许 "change of digit" 吗？）
我们的 Smart Differencer 系列工具定义了对目标语言明确定义的子短语的编辑集；我们使用形式语言文法（非）终结符作为变化的单位。 [这使得家族中的每个成员都特定于某种语言的语法]Delta 包括以程序员为中心的概念，例如 "replace phrase by phrase"、"delete listmember"、"move listmember"、"copy listmember"、"rename identifier"；该算法通过根据这些操作计算最小的树差异来运行。为此，SmartDifferencer 需要（并且拥有）该语言的完整解析器（生成 AST）。
您没有为示例指定语言。但一般来说，对于看起来像这样的语言，SmartDifferencer 通常会报告 User2 提交更改是：
- 将第 1 行第 13 列中的（数字文字）“1”替换为“2”
- 在第 2 行 之后插入（语句）"allrecords = range(10)"
并且 User3 提交的更改是：
- 在第 4 行之后的第 1 行移动（语句）
如果您知道谁贡献了原始代码，通过编辑您可以直接确定谁贡献了最终答案的哪一部分。你必须决定报告的单位；例如，如果您想逐行报告此类贡献以便于阅读，或者如果您真的想跟踪 Mary 编写的代码，但 Joe 修改了数字。
检测 User3 的更改语义 null 无法使用任何类型的纯语法驱动的差异工具来完成。为此，该工具必须能够以某种方式计算语法增量，然后计算所有语句的副作用（好吧，"phrases"），需要一个完整的语言静态分析器来解释增量以查看如果他们有这样的无效效果。这样的静态分析器无论如何都需要一个解析器，所以做一个基于树的差异器是有意义的，但它需要的不仅仅是解析器[我们有这样的语言前端，并考虑过构建这样的工具，但还没有做到这一点].
底线：没有用于确定 "that user3 did not change anything" 的简单算法。有理由希望可以构建这样的工具。