algorithm - 关联文件内容以查找移动是否有效？

Question

我对检测文件更改(如文件夹同步程序)感到好奇。

如果文件的内容已更改但其路径和名称相同，则检测起来很简单。

如果内容相同，但文件已被移动，仍然可以通过类似逐个比较的方式检测到这一点。

如果文件的内容发生了轻微的变化并且它已经移动了怎么办？有没有可靠的方法来检测而不是将其视为单独的文件删除和创建事件？

编辑:在看到 Tobias 的回答后，我意识到我应该澄清一下，我说的是同步大量数据(100 GB，10,000 文件，许多它们是二进制文件)在合理的时间内(在普通个人计算机上为秒)。

Answer 1

您可以尝试将文件的内容与其 Levenshtein distance 进行比较.因此，您可以检测文件是否已被轻微更改和移动(如果您逐个比较)。

伪代码算法(来自维基百科)可能如下所示:

// len_s and len_t are the number of characters in string s and t respectively
int LevenshteinDistance(const char *s, int len_s, const char *t, int len_t)
{ 
  int cost;

  /* base case: empty strings */
  if (len_s == 0) return len_t;
  if (len_t == 0) return len_s;

  /* test if last characters of the strings match */
  if (s[len_s-1] == t[len_t-1])
      cost = 0;
  else
      cost = 1;

  /* return minimum of delete char from s, delete char from t, and delete char from both */
  return minimum(LevenshteinDistance(s, len_s - 1, t, len_t    ) + 1,
                 LevenshteinDistance(s, len_s    , t, len_t - 1) + 1,
                 LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost);
}

如果您只比较已删除的文件，则可以更快地完成，因此您不需要将新文件与文件系统中的每个文件进行比较。