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

我有2个字符串

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 CalculateDifferences(string left, string right)
{
    int count = 0;
    List result = new List();
    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

您正在寻找(最小)编辑距离/(最小)编辑序列.你可以在这里找到这个过程的理论:

https://web.stanford.edu/class/cs124/lec/med.pdf

让我们实现(最简单的)Levenstein距离/序列算法(详见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 "???";
      }
    }
  }

据我所知,我们没有任何编辑操作,但添加+删除 ; 这就是为什么我放的editCost = 2时候insertCost = 1,int removeCost = 1(如果是平局:insert + remove与edit我们放的话insert + remove).现在我们准备实施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 result = 
    new List(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();
}

演示:

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

我会在这里提出一个并不是最有效的算法,但很容易推理.

我们首先介绍一些基础:

1)订单很重要

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

即使"bar"和"foo"出现在两个字符串中,"bar"也需要删除并稍后再添加.这也告诉我们,after字符串给了我们感兴趣的字符顺序,我们首先想要"foo".

2)订单超过计数

另一种看待它的方式是,一些角色可能永远不会轮到他们.

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

只有" bar b a r" 的大胆字符才能在"a b r a cadab ra "中发表意见.即使我们在两个字符串中都有两个b,但只有第一个才算数.当我们到达"ba r b ar"中的第二个b时,"abracada br a"中的第二个b 已经通过,当我们正在寻找第一次出现'r'时.

3)障碍

障碍是两个字符串中存在的字符,需要考虑顺序和计数.这已经暗示一个集合可能不是最合适的数据结构,因为我们会失去数量.

输入

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

我们得到(伪代码)

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

"pin ata "

" 一个 cciden ta l"

让我们按照执行流程:

'a'是第一个障碍,它也是第一个焦点,after因此before可以删除第一个'a'之前的所有内容."pin a ta" - >" a ta"

第二个障碍是't',它不在我们的after字符串中的下一个位置,所以我们可以在它们之间插入所有内容."一吨一个" - >"acciden 吨一个"

第三个障碍'a'已经处于下一个位置,因此我们可以在不做任何实际工作的情况下进入下一个障碍.

没有更多的障碍,但我们的字符串长度仍然小于after,所以会有一些后期处理."accidenta" - >"accidenta l "

注意'我'和'n'不再玩,再次,订单超过计数.

履行

我们已经确定了这个订单和数量,我Queue想到了.

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

    #region Preprocessing
    int index = 0;
    for (int i = 0; i  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  result)
{
    result.Add(new Difference()
    {
        c = barrier,
        op = Operation.Equal
    });
}

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

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