c# Найти количество ошибок в веденном предложении

Question

Есть текст, который пользователь должен правильно переписать в текстбокс. Создал проверку точности, но если перед введённым предложением поставить пробел " предложение", то он неправильно посчитает количество неправильно введенных символомв, происходит как бы сдвиг на 1 символ из-за чего ошибок не 2, а больше десятка. Как пофиксить подобную проблему?

private void Tochnost()
        {
            mistakes[panagramCounter] = Math.Abs(txtPhrase.TextLength - txtWrite.TextLength);
            int loopCounter = txtPhrase.TextLength > txtWrite.TextLength ? txtWrite.TextLength : txtPhrase.TextLength;
        for (int i = 0; i < loopCounter; i++)
        {
            if (txtPhrase.Text.Substring(i, 1) != txtWrite.Text.Substring(i, 1))
                mistakes[panagramCounter] += 1;
        }
    }

Answer 1

Раз пошла такая тема, покажу альтернативный вариант. Вообще, для получения разницы строк есть алгоритмы, такие как расстояние Левенштейна. Такой алгоритм относительно легко позволяет найти разнницу между строками (да и между чем угодно другим, что можно сравнить). Вот простейший пример

private static int Diff (string original, string actual)
{
    var board = new int[original.Length + 1, actual.Length + 1];
    for (var i = 0; i < board.GetLength(0); i++) board[i, 0] = i;
    for (var i = 0; i < board.GetLength(1); i++) board[0, i] = i;
for (var i = 1; i &lt; board.GetLength(0); i++)
{
    for (var j = 1; j &lt; board.GetLength(1); j++)
    {
        var stringsEquals = original[i - 1] == actual[j - 1];
        var add = (stringsEquals ? 0 : 1);
        board[i, j] = Math.Min(board[i - 1, j - 1] + add * 2, Math.Min(board[i - 1, j] + 1, board[i, j - 1] + 1));
    }
}   
return board[original.Length, actual.Length];

}

Проверить можно легко, например вот так

Console.WriteLine(Diff("VASYA", "VASAYA")); // результат будет 1

Пробелы тоже учитываются, потому вот это

Console.WriteLine(Diff("VASYA", " VASYA")); // результат будет 1

Также покажет разницу в 1 символ. Можно усложнить тест, например

Console.WriteLine(Diff2("VASYA", "KAS1YA")); // результат 3

В примере выше мы видим 3 различия: убрана первая буква V, добавлена первая будква K, добавлена цифра 1. Если мы хоти замену первой буквы считать за 1 изменение, то надо немного подшаманить алгоритм (найдите 1 отличие :))

private static int Diff (string original, string actual)
{
    var board = new int[original.Length + 1, actual.Length + 1];
    for (var i = 0; i < board.GetLength(0); i++) board[i, 0] = i;
    for (var i = 0; i < board.GetLength(1); i++) board[0, i] = i;
for (var i = 1; i &lt; board.GetLength(0); i++)
{
    for (var j = 1; j &lt; board.GetLength(1); j++)
    {
        var stringsEquals = original[i - 1] == actual[j - 1];
        var add = (stringsEquals ? 0 : 1);
        board[i, j] = Math.Min(board[i - 1, j - 1] + add * 1, Math.Min(board[i - 1, j] + 1, board[i, j - 1] + 1));
    }
}           
return board[original.Length, actual.Length];

}

В таком виде замена буквы будет считаться 1 изменением, соответственно

Console.WriteLine(Diff2("VASYA", "KAS1YA")); // результат 2

---

Но было бы слишком скучно вот так просто узнать число, как точность. А что, если мы хотим прямо знать, что конкретно изменилось? Например, вот так мы можем представить изменение

public class CompareCharResult
{
    public enum ActionType { Deleted, Added, Changed, NotChanged };
public ActionType Action { get; }
public char? OldValue { get; }
public char? NewValue { get; }

public CompareCharResult(char? oldValue, char? newValue, ActionType action)
{
    OldValue = oldValue;
    NewValue = newValue;
    Action = action;
}

}

Теперь, если приглядеться на алгоритм Левенштейна, то можно учидеть, что он строит матрицу разниц строк. По сути в начале матрицы разница 0 (так как мы ещё не начали сравнивать строки), в конце (нижний правый угол) разница уже посчитана, так как в этой точке мы достигли конца обеих строк.

Зная это, и жная матрицу, можно начать с конца матрицы и построить наименьший путь к началу. Сам путь нам и укажет, какие операции были выполнены над текстом. Знаю, это вроде как сложно звучит, но оно только звучит так.

private static CompareCharResult[] Diff2(string original, string actual)
{
    var board = new int[original.Length + 1, actual.Length + 1];
    for (var i = 0; i < board.GetLength(0); i++) board[i, 0] = i;
    for (var i = 0; i < board.GetLength(1); i++) board[0, i] = i;
for (var i = 1; i &lt; board.GetLength(0); i++)
{
    for (var j = 1; j &lt; board.GetLength(1); j++)
    {
        var stringsEquals = original[i - 1] == actual[j - 1];
        var add = (stringsEquals ? 0 : 1);
        board[i, j] = Math.Min(board[i - 1, j - 1] + add * 2, Math.Min(board[i - 1, j] + 1, board[i, j - 1] + 1));
    }
}

Идея такая: раз нижний правый угол - наша конечная цель, то, чтобы найти кратчайший путь изменений, нам придется пройти от конца в начало. Стартуем в нижнем правом углу, заканчиваем в верхнем левом. Но, так как мы движемся в обратном направлении, то я использовал стек для реверса результата к прямому порядку в конце функции.

    var stack = new Stack<CompareCharResult>();
var ii = board.GetLength(0) - 1;
var jj = board.GetLength(1) - 1;

// прогулка из правого нижнего угла таблицы в верхний левый по пути с минимальной суммой
while (ii &gt; 0 &amp;&amp; jj &gt; 0)
{
    var max = board[ii, jj];

    // Очевидно, двигаться мы можем вверх, влево или вверх-влево. Смотрим где наименьший элемент, туда и идем.

    var min = Math.Min(board[ii - 1, jj - 1], Math.Min(board[ii - 1, jj], board[ii, jj - 1]));
    if (min == board[ii - 1, jj - 1])
    {
        if (min != max)
        {
            stack.Push(new CompareCharResult(original[ii - 1], actual[jj - 1], CompareCharResult.ActionType.Changed));
        }
        else
            stack.Push(new CompareCharResult(original[ii - 1], actual[jj - 1], CompareCharResult.ActionType.NotChanged));

        ii--;
        jj--;
    }
    else if (min == board[ii - 1, jj])
    {
        if (min != max)
            stack.Push(new CompareCharResult(original[ii - 1], null, CompareCharResult.ActionType.Deleted));
        else
            stack.Push(new CompareCharResult(original[ii - 1], actual[jj], CompareCharResult.ActionType.NotChanged));
        ii--;
    }
    else if (min == board[ii, jj - 1])
    {
        if (min != max)
            stack.Push(new CompareCharResult(null, actual[jj - 1], CompareCharResult.ActionType.Added));
        else
            stack.Push(new CompareCharResult(original[ii], actual[jj - 1], CompareCharResult.ActionType.NotChanged));
        jj--;
    }
}

// Если уперлись в левую стенку, но ещё не дошли до верха

while (ii &gt; 0)
{
    var max = board[ii, jj];
    var min = board[ii - 1, jj];

    if (min != max)
        stack.Push(new CompareCharResult(original[ii - 1], null, CompareCharResult.ActionType.Deleted));
    else
        stack.Push(new CompareCharResult(original[ii - 1], actual[jj], CompareCharResult.ActionType.NotChanged));
    ii--;

}

// Если уперлись в потолок, но ещё не в левом углу       

while (jj &gt; 0)
{
    var max = board[ii, jj];
    var min = board[ii, jj - 1];

    if (min != max)
        stack.Push(new CompareCharResult(null, actual[jj - 1], CompareCharResult.ActionType.Added));
    else
        stack.Push(new CompareCharResult(original[ii], actual[jj - 1], CompareCharResult.ActionType.NotChanged));
    jj--;

}

return stack.ToArray();

}

Полученный результат нам покажет для каждого смвола обеих строк, что было изменено/добавлено/удалено. Посмотрим на наш пример выше

var changes = Diff2("VASYA", "KAS1YA");
foreach (var change in changes) 
    Console.WriteLine($"{change.OldValue ?? ' '} | {change.NewValue ?? ' '} | {change.Action}");

Вывод предсказуем

V | K | Changed
A | A | NotChanged
S | S | NotChanged
  | 1 | Added
Y | Y | NotChanged
A | A | NotChanged

Конечно, так как такой алгоритм расзодует M*N памяти и времени, он не годится для больших текстов. Но для небольших вполне подойдет.

Answer 2

Используйте метод String.Trim чтобы обрезать пробельные символы по краям перед тем, как делать проверку.

Учитывая что строка это массив символов, можно избавиться от двойного вызова Substring в цикле.

Еще можно сделать метод универсальным, избавившись от использования внешних переменных.

static int Tochnost(string txtPhrase, string txtWrite) {
    txtPhrase = txtPhrase.Trim();
    txtWrite = txtWrite.Trim();
    int result = Math.Abs(txtPhrase.Length - txtWrite.Length);
    int loopCounter = Math.Min(txtWrite.Length, txtPhrase.Length);
for(int i = 0; i < loopCounter; i++) {
    if(txtPhrase[i] != txtWrite[i])
        result++;
}
return result;

}