0

我有以下任务：开发一个程序，其中有一块应该由用户输入的示例文本。用户在测试期间所做的任何拼写错误都会被注册。基本上我可以将每个输入的字符与基于插入符号索引的示例字符进行比较输入的位置。但是在这种“幼稚”的方法中有一个重要的流程——如果用户错误地输入了比整个字符串更多的字母，或者在字符串之间插入了比应有的更多的空格，在这种情况下，有其余的比较将是错误的，因为额外的错误插入添加了索引偏移量。我考虑过设计某种解析器，其中每个字符串（甚至是 char ）都被标记化并且比较是“按字符”而不是“索引明智”。但在我看来，对于这样的任务来说，这似乎是一种矫枉过正。我想获得对可能有助于解决此类问题的现有算法的参考。

另外，我不确定这个问题是否更符合“程序员”网站的精神，所以我也把它贴在那里。

更新

我忘记提及的另一个重要细节是，必须对每个输入进行评估，而不是在任务结束时进行评估，因为它包括打字时间记录等......

4

1 回答 1

0

如果用户正在重新键入现有文本，那么它应该像对简单文本（一个字符代表一个字母/数字等）进行基于索引的比较一样简单，或者您可以使用 StringInfo.GetTextElementEnumerator 作为下面的示例。

如果您要让用户先输入文本，然后检查犯了多少错误，您可以使用 Levenshtein 距离（请参阅此处的实现和解释： http: //www.dotnetperls.com/levenshtein）。Levenshtein 距离本质上是使一个字符串看起来像另一个字符串所需的编辑量。

请注意，如果您的任务是支持 unicode 与组合字符和代理对（其中需要 2 个或更多字符来表示一个字母），那么实现在技术上将是不完整的。在后一种情况下，您可以修改该实现以使用 StringInfo.GetTextElementEnumerator 来生成和比较文本元素，如下所示：

using System;
using System.Collections.Generic;
using System.Globalization;

/// <summary>
///     Contains approximate string matching
/// </summary>
internal static class LevenshteinDistance
{
    /// <summary>
    ///     Compute the distance between two strings using text elements.
    /// </summary>
    public static int ComputeByTextElements(string s, string t) {
        string[] strA = GetTextElements(s),
                 strB = GetTextElements(t);

        int n = strA.Length;
        int m = strB.Length;
        var d = new int[n + 1,m + 1];

        // Step 1
        if (n == 0) {
            return m;
        }

        if (m == 0) {
            return n;
        }

        // Step 2
        for (int i = 0; i <= n; d[i, 0] = i++) {}

        for (int j = 0; j <= m; d[0, j] = j++) {}

        // Step 3
        for (int i = 1; i <= n; i++) {
            //Step 4
            for (int j = 1; j <= m; j++) {
                // Step 5
                int cost = (strB[j - 1] == strA[i - 1]) ? 0 : 1;

                // Step 6
                d[i, j] = Math.Min(
                    Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                    d[i - 1, j - 1] + cost);
            }
        }
        // Step 7
        return d[n, m];
    }

    private static string[] GetTextElements(string str) {
        if (string.IsNullOrEmpty(str)) {
            return new string[] {};
        }

        var result = new List<string>();

        var enumerator = StringInfo.GetTextElementEnumerator(str);

        while (enumerator.MoveNext()) {
            result.Add(enumerator.Current.ToString());
        }

        return result.ToArray();
    }
}

另请注意，上述解决方案区分大小写，因此如果您需要不区分大小写的 Levenshtein 距离计算，您可能希望将输入全部设为大写或小写。

关于您的编辑

我不会满足于基于（字符）索引的比较，因为它没有考虑组合字符和代理对。我将建立一个文本元素数组，表示要输入的文本，然后每次击键创建一个数组（或子集，通过一些缓存实现进行比较以优化速度）并比较它们。

于 2013-03-02T18:21:46.233 回答