0

次のタスクがあります:ユーザーが入力する必要があるサンプルテキストのブロックがあるプログラムを開発する.テスト中にユーザーが入力したタイプミスはすべて登録されます.基本的に、入力された各文字をキャレットインデックスに基づいてサンプル文字と比較できます入力の位置.しかし、そのような「素朴な」アプローチには重要な流れが1つあります.ユーザーが文字列全体よりも多くの文字を誤って入力した場合、または文字列の間に必要以上の空白を挿入した場合、そのような場合、そこに追加の間違った挿入によってインデックスオフセットが追加されるため、残りの比較は間違っています。私は、各文字列 (または char でさえ) がトークン化され、比較が「文字単位」ではなく行われるパーサーを設計することを考えました。 「インデックスごと」。しかし、それはそのようなタスクのやり過ぎのように思えます。この種の問題を解決するのに役立つ可能性のある既存のアルゴリズムへの参照を取得したいと思います。

また、この質問が「プログラマー」サイトの精神に合っているかどうかはわかりませんので、そこにも投稿しました。

アップデート

忘れていたもう 1 つの重要な詳細は、入力時間の記録などが含まれるため、タスクの最後ではなく、入力ごとに評価を行う必要があるということです...

4

1 に答える 1

0

ユーザーが既存のテキストを再入力する場合は、単純なテキスト（1つの文字/数字を表す1つの文字など）のインデックスベースの比較を行うのと同じくらい簡単である必要があります。または、以下の例のようにStringInfo.GetTextElementEnumeratorを使用できます。

最初にテキストを入力してからエラーの数を確認するようにユーザーに依頼する場合は、レーベンシュタイン距離を使用できます（実装と説明については、http：//www.dotnetperls.com/levenshteinを参照してください）。レーベンシュタイン距離は、基本的に、ある文字列を別の文字列のように見せるために必要な編集の量です。

1文字を表すために2文字以上が必要な、文字とサロゲートペアを組み合わせたUnicodeをサポートするように指示された場合、実装は技術的に不完全になることに注意してください。後者の場合、次のように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();
    }
}

また、上記のソリューションでは大文字と小文字が区別されるため、大文字と小文字を区別しないレーベンシュタイン距離の計算が必要な場合は、入力をすべて大文字または小文字にすることをお勧めします。

あなたの編集について

文字とサロゲートペアの組み合わせを考慮していないため、（文字）インデックスベースの比較には同意しません。入力するテキストを表すテキスト要素の配列を作成し、キーストロークごとに、入力した入力のテキスト要素の配列（または速度を最適化するためのキャッシュ実装による比較用のサブセット）を作成して比較します。

于 2013-03-02T18:21:46.233 に答える