检测两个字符串之间的差异

Question

我有两个字符串

string a = "foo bar";
string b = "bar foo";

我希望检测从a到b的变化。为了从a到b，我需要更改哪些字符呢？

我认为必须遍历每个字符，并检测它是添加、删除还是保持不变。因此，这是我的预期结果。

'f' Remove
'o' Remove
'o' Remove
' ' Remove
'b' Equal
'a' Equal
'r' Equal
' ' Add
'f' Add
'o' Add
'o' Add

结果的类和枚举：

public enum Operation { Add,Equal,Remove };
public class Difference
{
    public Operation op { get; set; }
    public char c { get; set; }
}

这是我的解决方案，但“删除”情况对我来说不太清楚代码应该是什么样子的。

public static List<Difference> CalculateDifferences(string left, string right)
{
    int count = 0;
    List<Difference> result = new List<Difference>();
    foreach (char ch in left)
    {
        int index = right.IndexOf(ch, count);
        if (index == count)
        {
            count++;
            result.Add(new Difference() { c = ch, op = Operation.Equal });
        }
        else if (index > count)
        {
            string add = right.Substring(count, index - count);
            result.AddRange(add.Select(x => new Difference() { c = x, op = Operation.Add }));
            count += add.Length;
        }
        else
        {
            //Remove?
        }
    }
    return result;
}

代码在删除字符时应该是什么样子的？

---

更新 - 添加了更多示例

示例1：

string a = "foobar";
string b = "fooar";

期望结果：

'f' Equal
'o' Equal
'o' Equal
'b' Remove
'a' Equal
'r' Equal

例子2：

string a = "asdfghjk";
string b = "wsedrftr";

预期结果：

'a' Remove
'w' Add
's' Equal
'e' Add
'd' Equal
'r' Add
'f' Equal
'g' Remove
'h' Remove
'j' Remove
'k' Remove
't' Add
'r' Add

---

更新：

这里是Dmitry和ingen答案的比较：https://dotnetfiddle.net/MJQDAO

- Impostor

---

莱文斯坦距离是指在两个字符串之间，将一个字符串转换为另一个字符串所需的最小单字符编辑操作数。这些操作包括插入、删除和替换字符。莱文斯坦距离用于比较两个序列的相似度或计算自动拼写更正算法中的编辑距离。 - Dmitry Bychenko

编辑距离可以轻松更新为编辑序列（添加回溯），例如 https://web.stanford.edu/class/cs124/lec/med.pdf - Dmitry Bychenko

这两个字符串的情况是什么：string A = "foobar", string B = "fooar"？索引3被删除了，还是索引3从“b”变成了“a”，4从“a”变成了“r”，并且索引5被删除了？除非您定义一些规则来评估这种情况，否则我们无法帮助您。 - JMadelaine

尝试实现Hirschberg算法。 - wilx

这是一个有趣的问题。根据使用情况，我可能会使用现有的应用程序（为二进制文件创建补丁文件）。或者当现有解决方案不适用时，我可能会使用修改后的LZ77 - 修改为使用一个（源）文件作为字典创建和第二个（目标）文件作为压缩值。 （我将压缩作为我的爱好进行了研究，但不幸的是，我目前没有真正的补丁压缩示例。） - Julo

Answer 1

你正在寻找“最小编辑距离” / “最小编辑序列”。你可以在这里找到该过程的“理论”：https://web.stanford.edu/class/cs124/lec/med.pdf。

让我们实现（最简单）的Levenstein Distance / Sequence算法（详情请参见https://en.wikipedia.org/wiki/Levenshtein_distance）。让我们从“辅助类”开始（我稍微改变了你对它们的实现）。

  public enum EditOperationKind : byte {
    None,    // Nothing to do
    Add,     // Add new character
    Edit,    // Edit character into character (including char into itself)
    Remove,  // Delete existing character
  };

  public struct EditOperation {
    public EditOperation(char valueFrom, char valueTo, EditOperationKind operation) {
      ValueFrom = valueFrom;
      ValueTo = valueTo;

      Operation = valueFrom == valueTo ? EditOperationKind.None : operation;
    }

    public char ValueFrom { get; }
    public char ValueTo {get ;}
    public EditOperationKind Operation { get; }

    public override string ToString() {
      switch (Operation) {
        case EditOperationKind.None:
          return $"'{ValueTo}' Equal";
        case EditOperationKind.Add:
          return $"'{ValueTo}' Add";
        case EditOperationKind.Remove:
          return $"'{ValueFrom}' Remove";
        case EditOperationKind.Edit:
          return $"'{ValueFrom}' to '{ValueTo}' Edit";
        default:
          return "???";
      }
    }
  }

据我所见，从提供的例子中来看，我们没有任何“编辑”操作，只有“添加+删除”操作；这就是为什么当insertCost = 1、int removeCost = 1（在tie的情况下：insert + remove vs. edit）时，我将editCost = 2。现在我们准备实现Levenstein算法：

public static EditOperation[] EditSequence(
  string source, string target, 
  int insertCost = 1, int removeCost = 1, int editCost = 2) {

  if (null == source)
    throw new ArgumentNullException("source");
  else if (null == target)
    throw new ArgumentNullException("target");

  // Forward: building score matrix

  // Best operation (among insert, update, delete) to perform 
  EditOperationKind[][] M = Enumerable
    .Range(0, source.Length + 1)
    .Select(line => new EditOperationKind[target.Length + 1])
    .ToArray();

  // Minimum cost so far
  int[][] D = Enumerable
    .Range(0, source.Length + 1)
    .Select(line => new int[target.Length + 1])
    .ToArray();

  // Edge: all removes
  for (int i = 1; i <= source.Length; ++i) {
    M[i][0] = EditOperationKind.Remove;
    D[i][0] = removeCost * i;
  }

  // Edge: all inserts 
  for (int i = 1; i <= target.Length; ++i) {
    M[0][i] = EditOperationKind.Add;
    D[0][i] = insertCost * i;
  }

  // Having fit N - 1, K - 1 characters let's fit N, K
  for (int i = 1; i <= source.Length; ++i)
    for (int j = 1; j <= target.Length; ++j) {
      // here we choose the operation with the least cost
      int insert = D[i][j - 1] + insertCost;
      int delete = D[i - 1][j] + removeCost;
      int edit = D[i - 1][j - 1] + (source[i - 1] == target[j - 1] ? 0 : editCost);

      int min = Math.Min(Math.Min(insert, delete), edit);

      if (min == insert) 
        M[i][j] = EditOperationKind.Add;
      else if (min == delete)
        M[i][j] = EditOperationKind.Remove;
      else if (min == edit)
        M[i][j] = EditOperationKind.Edit;

      D[i][j] = min;
    }

  // Backward: knowing scores (D) and actions (M) let's building edit sequence
  List<EditOperation> result = 
    new List<EditOperation>(source.Length + target.Length);

  for (int x = target.Length, y = source.Length; (x > 0) || (y > 0);) {
    EditOperationKind op = M[y][x];

    if (op == EditOperationKind.Add) {
      x -= 1;
      result.Add(new EditOperation('\0', target[x], op));
    }
    else if (op == EditOperationKind.Remove) {
      y -= 1;
      result.Add(new EditOperation(source[y], '\0', op));
    }
    else if (op == EditOperationKind.Edit) {
      x -= 1;
      y -= 1;
      result.Add(new EditOperation(source[y], target[x], op));
    }
    else // Start of the matching (EditOperationKind.None)
      break;
  }

  result.Reverse();

  return result.ToArray();
}

Demo:

演示：

var sequence = EditSequence("asdfghjk", "wsedrftr"); 

Console.Write(string.Join(Environment.NewLine, sequence));

结果：

'a' Remove
'w' Add
's' Equal
'e' Add
'd' Equal
'r' Add
'f' Equal
'g' Remove
'h' Remove
'j' Remove
'k' Remove
't' Add
'r' Add

- Dmitry Bychenko

---

首先感谢您，这似乎是目前为止最好的方法，所有测试都已成功完成（在将您的类结构转换为我的之后）。 - Impostor

@Dr. Snail：如果你坚持要摆脱编辑（Edit）操作（“在将你的类结构转换成我的之后”），完全由你决定 ;) - Dmitry Bychenko

如果你用你的方法运行“abc” -> “axc”，结果不会被编辑，这就是我试图解释的。 - Impostor

@Dr. Snail：因为编辑的价格太高了（路由器更喜欢使用“插入+删除”组合）。将其放置为var sequence = Levenshtein.EditSequence("abc", "axc", 1, 1, 1);。请注意，最后一个数字是1而不是2。 - Dmitry Bychenko

我想添加一个图形比较来展示这个问题背后的目的。 - Impostor

Answer 2

我会提供一个算法，虽然不是最高效的，但更易于理解。

首先，让我们简单介绍一下：

1）顺序很重要。

string before = "bar foo"
string after = "foo bar"

尽管“bar”和“foo”在两个字符串中都出现了，但“bar”将需要稍后删除并再次添加。这也告诉我们是“after”字符串给出了我们感兴趣的字符顺序，我们想要先出现“foo”。

2）按顺序而非数量排序

另一种看待它的方式是，有些字符可能永远不会轮到它们。

string before = "abracadabra"
string after = "bar bar"

只有 "bar bar" 中的粗体字符才在 "abracadabra" 中生效。尽管这两个字符串都有两个 b，但只有第一个被计数。当我们到达 "bar bar" 中的第二个 b 时，在寻找第一个 'r' 的过程中，"abracadabra" 中的第二个 b 已经被跳过了。

3) 障碍物

障碍物是同时存在于两个字符串中的字符，考虑顺序和数量。这已经暗示了一个 集合 可能不是最合适的数据结构，因为我们会丢失计数。

对于输入：

string before = "pinata"
string after = "accidental"

我们得到一个（伪代码）

var barriers = { 'a', 't', 'a' }

"pinata"

"accidental"

让我们跟随执行流程：

• 'a'是第一个屏障，也是after中的第一个字符，因此可以删除before中第一个'a'之前的所有内容。 "pinata" -> "ata"
• 第二个屏障是't'，在after字符串中不是下一个位置，因此我们可以插入中间的所有内容。 "ata" -> "accidenta"
• 第三个屏障 'a' 已经在下一个位置，所以我们可以继续到下一个屏障而不需要做任何实际的工作。
• 没有更多屏障了，但我们的字符串长度仍然少于after，因此将进行一些后处理。 "accidenta" -> "accidental"

请注意，'i'和'n'没有参与，重要的是顺序而非数量。

---

实现

我们已经确定顺序和数量很重要，那么 Queue 就出现在脑海中。

static public List<Difference> CalculateDifferences(string before, string after)
{
    List<Difference> result = new List<Difference>();
    Queue<char> barriers = new Queue<char>();

    #region Preprocessing
    int index = 0;
    for (int i = 0; i < after.Length; i++)
    {
        // Look for the first match starting at index
        int match = before.IndexOf(after[i], index);
        if (match != -1)
        {
            barriers.Enqueue(after[i]);
            index = match + 1;
        }
    }
    #endregion

    #region Queue Processing
    index = 0;
    while (barriers.Any())
    {
        char barrier = barriers.Dequeue();
        // Get the offset to the barrier in both strings, 
        // ignoring the part that's already been handled
        int offsetBefore = before.IndexOf(barrier, index) - index;
        int offsetAfter = after.IndexOf(barrier, index) - index;
        // Remove prefix from 'before' string
        if (offsetBefore > 0)
        {
            RemoveChars(before.Substring(index, offsetBefore), result);
            before = before.Substring(offsetBefore);
        }
        // Insert prefix from 'after' string
        if (offsetAfter > 0)
        {
            string substring = after.Substring(index, offsetAfter);
            AddChars(substring, result);
            before = before.Insert(index, substring);
            index += substring.Length;
        }
        // Jump over the barrier
        KeepChar(barrier, result);
        index++;
    }
    #endregion

    #region Post Queue processing
    if (index < before.Length)
    {
        RemoveChars(before.Substring(index), result);
    }
    if (index < after.Length)
    {
        AddChars(after.Substring(index), result);
    }
    #endregion

    return result;
}

static private void KeepChar(char barrier, List<Difference> result)
{
    result.Add(new Difference()
    {
        c = barrier,
        op = Operation.Equal
    });
}

static private void AddChars(string substring, List<Difference> result)
{
    result.AddRange(substring.Select(x => new Difference()
    {
        c = x,
        op = Operation.Add
    }));
}

static private void RemoveChars(string substring, List<Difference> result)
{
    result.AddRange(substring.Select(x => new Difference()
    {
        c = x,
        op = Operation.Remove
    }));
}

- ingen

Answer 3

我测试了上述三个例子，它们都可以正确地返回预期的结果。

        int flag = 0;
        int flag_2 = 0;

        string a = "asdfghjk";
        string b = "wsedrftr";

        char[] array_a = a.ToCharArray();
        char[] array_b = b.ToCharArray();

        for (int i = 0,j = 0, n= 0; i < array_b.Count(); i++)
        {   
            //Execute 1 time until reach first equal character   
            if(i == 0 && a.Contains(array_b[0]))
            {
                while (array_a[n] != array_b[0])
                {
                    Console.WriteLine(String.Concat(array_a[n], " : Remove"));
                    n++;
                }
                Console.WriteLine(String.Concat(array_a[n], " : Equal"));
                n++;
            }
            else if(i == 0 && !a.Contains(array_b[0]))
            {
                Console.WriteLine(String.Concat(array_a[n], " : Remove"));
                n++;
                Console.WriteLine(String.Concat(array_b[0], " : Add"));
            }


            else
            {
                if(n < array_a.Count())
                {
                    if (array_a[n] == array_b[i])
                    {
                        Console.WriteLine(String.Concat(array_a[n], " : Equal"));
                        n++;
                    }
                    else
                    {
                        flag = 0;
                        for (int z = n; z < array_a.Count(); z++)
                        {                              
                            if (array_a[z] == array_b[i])
                            {
                                flag = 1;
                                break;
                            }                                                              
                        }

                        if (flag == 0)
                        {
                            flag_2 = 0;
                            for (int aa = i; aa < array_b.Count(); aa++)
                            {
                                for(int bb = n; bb < array_a.Count(); bb++)
                                {
                                    if (array_b[aa] == array_a[bb])
                                    {
                                        flag_2 = 1;
                                        break;
                                    }
                                }
                            }

                            if(flag_2 == 1)
                            {
                                Console.WriteLine(String.Concat(array_b[i], " : Add"));
                            }
                            else
                            {
                                for (int z = n; z < array_a.Count(); z++)
                                {
                                    Console.WriteLine(String.Concat(array_a[z], " : Remove"));
                                    n++;
                                }
                                 Console.WriteLine(String.Concat(array_b[i], " : Add"));
                            }

                        }
                        else
                        {
                            Console.WriteLine(String.Concat(array_a[n], " : Remove"));
                            i--;
                            n++;
                        }

                    }
                }
                else
                {
                    Console.WriteLine(String.Concat(array_b[i], " : Add"));
                }

            }

        }//end for


        MessageBox.Show("Done");


    //OUTPUT CONSOLE:
    /*
    a : Remove
    w : Add
    s : Equal
    e : Add
    d : Equal
    r : Add
    f : Equal
    g : Remove
    h : Remove
    j : Remove
    k : Remove
    t : Add
    r : Add
    */  

- Nguyen Thanh Binh

---

它们可以相等，但长度也可能不同。 - Impostor

好的，我认为示例2的预期结果应该是：'a' 删除 'w' 添加 's' 等于 'd' 删除 'e' 添加。 - Nguyen Thanh Binh

你错过了：'d'。删除它，我说得对吗？这导致了所有剩余字符的预期结果出现错误。 - Nguyen Thanh Binh

我认为在你的代码中，在 Add 之后不能再有 Equal 或 Remove，因为在那之后你就结束了。 - Impostor

您的规范存在一些冲突，例如“foo bar”和“bar foo”；您需要删除所有字符，直到两个字符串中的字符相等。但是对于“asdfghjk”和“wsedrftr”，您需要同时删除和添加字符（如果字符串a中的下一个字符与字符串b中的当前字符不相等）。 - Nguyen Thanh Binh

Answer 4

这里可能有另一个解决方案，提供完整的代码和注释。不过，你第一个原始示例的结果是反转的：

class Program
{
    enum CharState
    {
        Add,
        Equal,
        Remove
    }

    struct CharResult
    {
        public char c;
        public CharState state;
    }

    static void Main(string[] args)
    {
        string a = "asdfghjk";
        string b = "wsedrftr";
        while (true)
        {
            Console.WriteLine("Enter string a (enter to quit) :");
            a = Console.ReadLine();
            if (a == string.Empty)
                break;
            Console.WriteLine("Enter string b :");
            b = Console.ReadLine();

            List<CharResult> result = calculate(a, b);
            DisplayResults(result);
        }
        Console.WriteLine("Press a key to exit");
        Console.ReadLine();
    }

    static List<CharResult> calculate(string a, string b)
    {
        List<CharResult> res = new List<CharResult>();
        int i = 0, j = 0;

        char[] array_a = a.ToCharArray();
        char[] array_b = b.ToCharArray();

        while (i < array_a.Length && j < array_b.Length)
        {
            //For the current char in a, we check for the equal in b
            int index = b.IndexOf(array_a[i], j);
            if (index < 0) //not found, this char should be removed
            {
                res.Add(new CharResult() { c = array_a[i], state = CharState.Remove });
                i++;
            }
            else
            {
                //we add all the chars between B's current index and the index
                while (j < index)
                {
                    res.Add(new CharResult() { c = array_b[j], state = CharState.Add });
                    j++;
                }
                //then we say the current is the same
                res.Add(new CharResult() { c = array_a[i], state = CharState.Equal });
                i++;
                j++;
            }
        }

        while (i < array_a.Length)
        {
            //b is now empty, we remove the remains
            res.Add(new CharResult() { c = array_a[i], state = CharState.Remove });
            i++;
        }
        while (j < array_b.Length)
        {
            //a has been treated, we add the remains
            res.Add(new CharResult() { c = array_b[j], state = CharState.Add });
            j++;
        }

        return res;
    }

    static void DisplayResults(List<CharResult> results)
    {
        foreach (CharResult r in results)
        {
            Console.WriteLine($"'{r.c}' - {r.state}");
        }
    }
}

- Martin Verjans

---

这不识别常见的 a，例如 string a = "fxiafer"; string b = "gkawvgf";。https://dotnetfiddle.net/YmNrCx - Impostor

@Dr.Snail 我明白了。实际上我只检查了一个方向的存在性。今天下午我会更新代码，检查两个方向的相等性。 - Martin Verjans

Answer 5

如果你想要对比两个字符串，你必须阅读并理解 Levenshtein Distance。使用这个算法，你可以精确地计算两个字符串的相似度，并且你可以回溯该算法以获取第二个字符串上变更的链。该算法也是自然语言处理中的重要指标。

还有一些其他的好处，但需要时间学习。

在这个链接中，有一个 Levenshtein Distance 的 C# 版本：

https://www.dotnetperls.com/levenshtein

- RezaNoei

---

这个算法可以告诉你（例如）你的字符串相似度为80％。这两个字符串的长度不重要，旋转和移位也不会影响结果。 - RezaNoei

这会对我的方法产生什么影响？我只是想修复Remove部分。 - Impostor

对不起，请问您的程序目标是什么呢？实际上，“错误纠正”是文本处理中的一个领域。如果您想跟踪删除的部分，可以使用Levenshtein Backtrack算法。请阅读来自https://web.stanford.edu/~jurafsky/NLPCourseraSlides.html的“最小编辑距离”PDF文件。在Coursera上有一位名叫Dan Jurafsky教授的讲师提供了很好的教程。 - RezaNoei