c - 编辑距离矩阵

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;
}

Answer 1

坚持使用 fgets。

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

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

您 [可能] 想要的是 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;
}

---

更新:

Okay sweet I see what you mean! The reason I was trying to use malloc though was to avoid making the matrix that I had to print a size of 100x100 blank spaces.

使用固定大小的 input1 或 malloced 之一，fgets 只会将其填充到输入的输入大小 [clipped to the第二个参数，如有必要]。但是，它不会用任何东西填充/填充缓冲区的剩余部分(例如右边的空格)。它所做的是在从输入 [通常是换行符] 读取的最后一个字符后添加一个 EOS [字符串结尾] 字符 [这是一个二进制 0x00]。

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

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

Does using strlen() only count the number of chars inside the array, or does it include all the blank spaces too?

正如我上面提到的，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 在长度计算中包含[内部/嵌入] 空格。这是因为计算短语的编辑距离是完全有效的。

---

malloc 有一个有效的用法:当数据量太大而不适合堆栈时。大多数系统都有一个默认限制(例如，在 Linux 下，它是 8 MB)。

假设我们正在计算两本书章节的编辑距离 [从文件中读取]，我们将有(例如):

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;
}