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 回答