2 개의 문자열 시퀀스 일치

Question

원래 문자열과 편집 된 문자열이있는 작은 응용 프로그램을 만들었습니다. 원래 문자열은 "one"이고 편집 된 문자열은 "two"라고합니다. 각 문자열을 살펴보고 문자열로 편집 한 내용을 원래 문자열에 편집 된 단어를 대문자로 추가하고 싶습니다. Original "This is original"edited "This is edited" 출력 ("This is original EDITED"). 문자열을 통과하여 일치하는 문자열을 찾고 중단하고 변경하기 위해 변경되면 원래의 문자열의 해당 위치에 단어를 추가합니다. 이것은 내가 문자열에서 편집 된 모든 단어를 찾기 위해 지금까지 가지고있는 것입니다. 내 문제는 문자열에 가입하는 것입니다.

string one = "This is a new value"; 
     string two = "This This is a new values"; 
     int index = 0; 
     var coll = two.Split(' ').Select(p => one.Contains(p) ? p : p.ToUpperInvariant()); 

     var col2 = two.Split(' '); 
     var col1 = one.Split(' '); 


     for (int i = 0; i < col1.Length; i++) 
     { 
      var a = two.IndexOf(col2[i].ToString(), index); 
      if (col2[index].ToString()==col1[i].ToString()) 
      { 
       Debug.WriteLine(col2[index]); 
      } 
      else 
      { 




       Debug.WriteLine(col2[index].ToUpper()); 
       two.Insert(index, col1[i].ToString().ToUpper()); 
       //Debug.WriteLine(col1[i]); 

       i--; 

      } 
      index++; 
      if (index==col2.Length) 
      { 
       break; 
      } 
     } 

     Console.WriteLine(string.Join(" ", two)); 
     Console.ReadKey(); 

Answer 1

당신은 Edit Distance 문제를 해결됩니다 휴한지로 출력 예상 "This This THIS is a new value VALUES"

내 코드입니다. 당신은 일련의 항목들 - 당신의 경우에 단어들 -을 가지고 있으며, 첫 번째 순서에 대한 최소한의 변경 횟수를 계산하여 두 번째 순서에 도달하려고합니다.

나는 위 링크 된 Wikipedia 기사의 알고리즘을 따르는 것이 좋겠다. 그러면 매우 좋은 구현에 도달 할 것이다. 이러한 알고리즘은 처음 엔 두려운 것처럼 보일 수 있지만 실제로 들어갈 때 매우 간단합니다.

다음은 C#의 전체 구현입니다. 동적 프로그래밍을 기반으로하고 원래 문자열에서 최종 문자열로 이어지는 단계를 재구성합니다. 내 솔루션은 대괄호 안에 삭제 된 단어를 쓰고 있습니다. 삭제 된 단어를 건너 뛰고 싶다면 문자를 ReconstructEdit() 방법으로 출력에 추가하지 마십시오.

private static string CalculateMinimumEdit(string[] original, string[] final) 
{ 
    int[,] costs = new int[original.Length + 1, final.Length + 1]; 

    // =, +, - or * for equal words, inserted, deleted or modified word 
    char[,] resultOf = new char[original.Length + 1, final.Length + 1]; 

    // Set all costs to invalid values (mark all positions not reached) 
    InitializeInvalidCosts(costs); 

    // Empty sequences are equal and their edit costs is 0 
    // This is setting the initial state for the following calculation 
    resultOf[0, 0] = '='; 
    costs[0, 0] = 0; 

    for (int originalIndex = 0; originalIndex < original.Length + 1; originalIndex++) 
    { 
     for (int finalIndex = 0; finalIndex < final.Length + 1; finalIndex++) 
     { 
      SetDeleteCost(costs, resultOf, originalIndex, finalIndex); 
      SetInsertCost(costs, resultOf, originalIndex, finalIndex); 
      SetModifiedCost(costs, resultOf, originalIndex, finalIndex); 
      SetEqualCost(costs, resultOf, originalIndex, finalIndex, original, final); 
     } 
    } 

    return ReconstructEdit(costs, resultOf, original, final); 
} 

private static void InitializeInvalidCosts(int[,] costs) 
{ 
    // Set all costs to negative values 
    // That will indicate that none of the positions 
    // in the costs matrix has been analyzed yet 
    for (int i = 0; i < costs.GetLength(0); i++) 
    { 
     for (int j = 0; j < costs.GetLength(1); j++) 
     { 
      costs[i, j] = -1; 
     } 
    } 
} 

private static void SetInsertCost(int[,] costs, char[,] resultOf, 
            int originalIndex, int finalIndex) 
{ 
    // You can always assume that the new word was inserted 
    // Position in original sequence remains the same 
    // Position in final sequence moves by one and that is the new word 
    // Cost of this change is 1 
    SetCostIfBetter(costs, resultOf, originalIndex, finalIndex + 1, 
        costs[originalIndex, finalIndex] + 1, '+'); 
} 

private static void SetDeleteCost(int[,] costs, char[,] resultOf, 
            int originalIndex, int finalIndex) 
{ 
    // You can always assume that one word was deleted from original sequence 
    // Position in original sequence moves by one and that is the deleted word 
    // Position in final sequence remains the same 
    // Cost of this change is 1 
    SetCostIfBetter(costs, resultOf, originalIndex + 1, finalIndex, 
        costs[originalIndex, finalIndex] + 1, '-'); 
} 

private static void SetModifiedCost(int[,] costs, char[,] resultOf, 
            int originalIndex, int finalIndex) 
{ 
    // You can always assume that one word was replaced with another 
    // Both positions in original and final sequences move by one 
    // That means that one word from input was consumed 
    // and it was replaced by a new word from the final sequence 
    // Cost of this change is 1 
    SetCostIfBetter(costs, resultOf, originalIndex + 1, finalIndex + 1, 
        costs[originalIndex, finalIndex] + 1, '*'); 
} 

private static void SetEqualCost(int[,] costs, char[,] resultOf, 
            int originalIndex, int finalIndex, 
            string[] original, string[] final) 
{ 
    // If incoming words in original and final sequence are the same 
    // then you can take advantage and move to the next position 
    // at no cost 
    // Position in original sequence moves by 1 
    // Position in final sequence moves by 1 
    // Cost of this change is 0 
    if (originalIndex < original.Length && 
     finalIndex < final.Length && 
     original[originalIndex] == final[finalIndex]) 
    { 
     // Attempt to set new cost only if incoming words are equal 
     SetCostIfBetter(costs, resultOf, originalIndex + 1, finalIndex + 1, 
         costs[originalIndex, finalIndex], '='); 
    } 
} 

private static void SetCostIfBetter(int[,] costs, char[,] resultOf, 
            int originalIndex, int finalIndex, 
            int cost, char operation) 
{ 
    // If destination cost is not set (i.e. it is negative) 
    // or destination cost is non-negative but new cost is lower than that 
    // then the cost can be set to new value and 
    // new operation which has caused the change can be indicated 
    if (IsBetterCost(costs, originalIndex, finalIndex, cost)) 
    { 
     costs[originalIndex, finalIndex] = cost; 
     resultOf[originalIndex, finalIndex] = operation; 
    } 
} 

private static bool IsBetterCost(int[,] costs, int originalIndex, 
            int finalIndex, int cost) 
{ 
    // New cost is better than existing cost if 
    // either existing cost is negative (not set), 
    // or new cost is lower 
    return 
     originalIndex < costs.GetLength(0) && 
     finalIndex < costs.GetLength(1) && 
     (costs[originalIndex, finalIndex] < 0 || 
      cost < costs[originalIndex, finalIndex]); 
} 

private static string ReconstructEdit(int[,] costs, char[,] resultOf, 
             string[] original, string[] final) 
{ 
    string edit = string.Empty; 

    int originalIndex = original.Length; 
    int finalIndex = final.Length; 

    string space = string.Empty; 

    while (originalIndex > 0 || finalIndex > 0) 
    { 
     edit = space + edit; 
     space = " "; 

     char operation = resultOf[originalIndex, finalIndex]; 

     switch (operation) 
     { 
      case '=': 
       originalIndex -= 1; 
       finalIndex -= 1; 
       edit = original[originalIndex] + edit; 
       break; 
      case '*': 
       originalIndex -= 1; 
       finalIndex -= 1; 
       edit = final[finalIndex].ToUpper() + edit; 
       break; 
      case '+': 
       finalIndex -= 1; 
       edit = final[finalIndex].ToUpper() + edit; 
       break; 
      case '-': 
       originalIndex -= 1; 
       edit = "[" + original[originalIndex] + "]" + edit; 
       break; 
     } 
    } 

    return edit; 
}