2

2 つの文字列間の編集距離を計算する必要がある宿題があります。初期機能は動作するようになりましたが、この部分で問題が発生しています

ここでカットオフを編集距離に追加します。これにより、生成される結果が変わることはありませんが、パフォーマンスが大幅に高速化されます。

ここに私の元の機能があります：

static unsigned int compute_edit_distance(const char *const a,
                                      const char *const b)
{
    if (strcmp(a, b) == 0) return 0;
    if (a[0] == '\0') return strlen(b);
    if (b[0] == '\0') return strlen(a);

    unsigned int remove_from_a =
        compute_edit_distance(a + 1, b) + 1;
    unsigned int remove_from_b =
        compute_edit_distance(a, b + 1) + 1;

    unsigned int remove_from_both =
        compute_edit_distance(a + 1, b + 1);
    if (tolower(a[0]) != tolower(b[0])) ++remove_from_both;

    return get_min(get_min(remove_from_a, remove_from_b),
               remove_from_both);
}

いくつか試してみましたが、どれもうまくいきません。私の最近の変化はこれです

if (depth == MAX_EDIT_DISTANCE_DEPTH)
{
    size_t a_length = strlen(a);
    size_t b_length = strlen(b);
    size_t max_length = (a_length > b_length) ? a_length : b_length;
    return MAX_EDIT_DISTANCE_DEPTH + max_length;
}

新しい関数シグネチャを使用

static unsigned int compute_edit_distance(const char *const a,
                                      const char *const b, unsigned int depth)

しかし、それもうまくいきません。

これを正しく行う方法についてヒントを得ることができますか? ありがとう！

4

1 に答える 1

2

最も簡単な方法は、「残りの深さ」をパラメーターとして渡すことです。つまり、最初の呼び出しにはカットオフ深度が渡され、すべての再帰呼び出しにはより小さい数が渡されます。これは、行われた編集の種類によって決定されます。

基本的な考え方は、最初のソリューションでは、分岐が再帰的に探索された後に深さが計算されるということです。つまり、呼び出しはすべてブランチを下って行われ、次にブランチを戻る途中で番号が加算されます。

深さを計算するためにこれを行うこともできますが、ブランチが行き過ぎないようにするために、ブランチを下る途中の呼び出しで既に使用した編集予算の現在の合計、または同等の編集予算を渡します。残ります。

番号が確実に拒否されるようにするには、失敗したブランチから番号を返すためのトリックが必要です。たとえば、大きすぎることがわかっている数値を返し、最後に結果を確認します。たとえば、MAX_DEPTH + 1 などを返します。

于 2012-07-15T07:05:55.797 に答える