编辑距离矩阵

Question

我正在尝试构建一个程序，该程序接收两个字符串并为它们填充编辑距离矩阵。让我困惑的是，对于第二个字符串输入，它跳过了第二个输入。我尝试使用getch()清除缓冲区，但没有起作用。我还尝试切换到scanf()，但也导致了一些崩溃。请帮忙解决！代码如下：

#include <stdio.h>
#include <stdlib.h>

int min(int a, int b, int c){
    if(a > b && a > c)
        return a;
    else if(b > a && b > c)
        return b;
    else
        return c;
}

int main(){

    // allocate size for strings
    int i, j;
    char *input1 = (char*)malloc(sizeof(char)*100);
    char *input2 = (char*)malloc(sizeof(char)*100);

    // ask for input
    printf("Enter the first string: ");
    fgets(input1, sizeof(input1), stdin);
    printf("\nEnter the second string: ");
    fgets(input2, sizeof(input2), stdin);

    // make matrix
    int len1 = sizeof(input1), len2 = sizeof(input2);
    int c[len1 + 1][len2 + 1];

    // set up input 2 length
    for(i = 0; i < len2 + 1; i++){
        c[0][i] = i;
    }

    // set up input 1 length
    for(i = 0; i < len1 + 1; i++){
        c[i][0] = i;
    }

    // fill in the rest of the matrix
    for(i = 1; i < len1; i++){
        for(j = 1; j < len2; j++){
            if(input1[i] == input2[j]) // if the first letters are equal make the diagonal equal to the last
                c[i][j] = c[i - 1][j - 1];
            else
                c[i][j] = 1 + min(c[i - 1][j - 1], c[i - 1][j], c[i][j - 1]);
        }
    }

    // print the matrix
    printf("\n");
    for(j = 0; j < len2; j++){
        for(i = 0; i < len1; i++){
            printf("|  %d", c[i][j]);
        }
        printf("\n");
    }

    return 1;
}

- Dylan Forsyth

---

“\n”仍然留在缓冲区中，这就是为什么您的第二个fgets无法获取第二行输入的原因。 - Mox

你尝试过使用 char input1[100] 吗？ - brijs

使用 sizeof(input1) 是错误的，它不会给你 100，而只会给你一个大小为 1 的尺寸。 - Mox

不要在 C 语言中对 malloc 的结果进行类型转换。 - phuclv

Answer 1

坚持使用 fgets。

正如其他人所指出的，使用 char input1[100] 而不是 char *input1 = malloc(...)

但是，即使进行了这个更改，使得 fgets 中的 sizeof 正确，使用 sizeof 设置 len1 和 len2 是错误的。即使其中只有 10 个有效字符（即其余字符是未定义/随机的），您也将处理整个大小为 100 的缓冲区。

您 [可能] 想要使用 strlen [和一个换行符剥离函数] 来获取实际有效长度。

这是修改后的代码 [请原谅过度的样式清理]:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int
min(int a, int b, int c)
{
    if (a > b && a > c)
        return a;
    if (b > a && b > c)
        return b;
    return c;
}

int
main(void)
{

    // allocate size for strings
    int i;
    int j;
    char input1[100];
    char input2[100];

    // ask for input
    printf("Enter the first string: ");
    fgets(input1, sizeof(input1), stdin);
    int len1 = strlen(input1);
    if (input1[len1 - 1] == '\n') {
        input1[len1 - 1] = 0;
        --len1;
    }

    printf("\nEnter the second string: ");
    fgets(input2, sizeof(input2), stdin);
    int len2 = strlen(input2);
    if (input2[len2 - 1] == '\n') {
        input2[len2 - 1] = 0;
        --len2;
    }

    // make matrix
    int c[len1 + 1][len2 + 1];

    // set up input 2 length
    for (i = 0; i < len2 + 1; i++) {
        c[0][i] = i;
    }

    // set up input 1 length
    for (i = 0; i < len1 + 1; i++) {
        c[i][0] = i;
    }

    // fill in the rest of the matrix
    for (i = 1; i < len1; i++) {
        for (j = 1; j < len2; j++) {
            // if the 1st letters are equal make the diagonal equal to the last
            if (input1[i] == input2[j])
                c[i][j] = c[i - 1][j - 1];
            else
                c[i][j] = 1 + min(c[i - 1][j - 1], c[i - 1][j], c[i][j - 1]);
        }
    }

    // print the matrix
    printf("\n");
    for (j = 0; j < len2; j++) {
        for (i = 0; i < len1; i++) {
            printf("|  %d", c[i][j]);
        }
        printf("\n");
    }

    return 1;
}

---

更新：

好的，我明白你的意思了！但是我尝试使用malloc的原因是为了避免让我要打印的矩阵大小为100x100个空格。

无论是固定大小的input1还是malloc的大小，fgets只会填充输入的大小[如果需要，剪裁到第二个参数]。但是，它不会用任何东西[例如右侧的空格]填充/填充缓冲区的其余部分。它所做的是在从输入读取的最后一个字符之后添加一个EOS [字符串结尾]字符[通常是换行符]。

因此，如果输入字符串是：abcdef\n，长度[可从strlen中获取]为7，input[7]将为0x00，而input1 [8]到input1 [99]将具有未定义/随机/不可预测的值，而不是空格。

由于换行符并不是非常有用，因此通常在进一步处理之前会将其删除。例如，在计算小短语的编辑距离时，它并不是非常相关。

使用 strlen() 仅计算数组中字符的数量，还是包括所有空格?

如我上面所提到的，fgets 不会在字符串 末尾 填充，所以不用担心。它将会做你想要/期望的事情。

strlen 仅计算字符直到 [但 不 包括 EOS 终止字符（即零）]。如果其中一些字符恰好是空格，则它们将被 strlen 计算--这正是我们想要的。

考虑计算以下任意两个 短语 之间的编辑距离:

quick brown fox jumped over the lazy dogs
the quick brown fox jumped over lazy dogs
quick brown fox jumps over the lazy dog

在每种情况下，我们希望strlen包括[内部/嵌入式]空格在长度计算中。这是因为计算短语的编辑距离是完全有效的。请注意保留HTML标签。

---

当数据量太大无法放在栈内时，malloc 有其有效用途。大多数系统都有默认限制（例如，在 Linux 下，它是 8MB）。

假设我们正在计算两个书籍章节的编辑距离 [从文件中读取]，我们可能会有以下情况：

char input1[50000];
char input2[50000];

上述方法可行，但 c 矩阵会导致堆栈溢出：

int c[50000][50000];

因为它的大小将是50000 * 50000 * 4，大约为9.3 GB。

因此，为了容纳所有这些数据，我们需要在堆上分配它。虽然可能会对c进行malloc并维护2D矩阵访问，但我们必须创建一个函数并将指向c的指针传递给它。

因此，这里有一个修改后的版本，可以输入任意大小的输入：

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>

#define sysfault(_fmt...) \
    do { \
        fprintf(stderr,_fmt); \
        exit(1); \
    } while (0)

#define C(y,x)      c[((y) * (len2 + 1)) + (x)]

long
min(long a, long b, long c)
{
    if (a > b && a > c)
        return a;
    if (b > a && b > c)
        return b;
    return c;
}

char *
input(const char *prompt,long *lenp,const char *file)
{
    FILE *fp;
    char *lhs;
    int chr;
    long siz;
    long len;

    if (file != NULL)
        fp = fopen(file,"r");
    else {
        fp = stdin;
        printf("Enter %s string: ",prompt);
        fflush(stdout);
    }

    lhs = NULL;
    siz = 0;
    len = 0;

    while (1) {
        chr = fgetc(fp);
        if (chr == EOF)
            break;

        if ((chr == '\n') && (file == NULL))
            break;

        // grow the character array
        if ((len + 1) >= siz) {
            siz += 100;
            lhs = realloc(lhs,siz);
            if (lhs == NULL)
                sysfault("input: realloc failure -- %s\n",strerror(errno));
        }

        lhs[len] = chr;
        len += 1;
    }

    if (file != NULL)
        fclose(fp);

    if (lhs == NULL)
        sysfault("input: premature EOF\n");

    // add the EOS
    lhs[len] = 0;

    // return the length to the caller
    *lenp = len;

    return lhs;
}

int
main(int argc,char **argv)
{
    long i;
    long j;
    char *input1;
    long len1;
    char *input2;
    long len2;
    long *c;

    --argc;
    ++argv;

    switch (argc) {
    case 2:
        input1 = input("first",&len1,argv[0]);
        input2 = input("second",&len2,argv[1]);
        break;
    default:
        input1 = input("first",&len1,NULL);
        input2 = input("second",&len2,NULL);
        break;
    }

    // make matrix
    c = malloc(sizeof(*c) * (len1 + 1) * (len2 + 1));
    if (c == NULL)
        sysfault("main: malloc failure -- %s\n",strerror(errno));

    // set up input 2 length
    for (i = 0; i < len2 + 1; i++) {
        C(0,i) = i;
    }

    // set up input 1 length
    for (i = 0; i < len1 + 1; i++) {
        C(i,0) = i;
    }

    // fill in the rest of the matrix
    for (i = 1; i < len1; i++) {
        for (j = 1; j < len2; j++) {
            // if the 1st letters are equal make the diagonal equal to the last
            if (input1[i] == input2[j])
                C(i,j) = C(i - 1,j - 1);
            else
                C(i,j) = 1 + min(C(i - 1,j - 1), C(i - 1,j), C(i,j - 1));
        }
    }

    // print the matrix
    printf("\n");
    for (j = 0; j < len2; j++) {
        for (i = 0; i < len1; i++) {
            printf("|  %ld", C(i,j));
        }
        printf("\n");
    }

    return 1;
}

- Craig Estey