编辑距离矩阵

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 和 len2 时使用 sizeof是错的。您将处理一个 entire 100 的缓冲区，即使其中只有 10 个有效字符（即其余字符是 undefined/random）。

您[可能]想要的是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 只会将其填充到输入的输入大小 [如有必要，剪裁到第二个参数]。但是，它 not pad/fill 缓冲区的其余部分 anything （例如右边的空格）。它所做的是在从输入读取的最后一个字符[通常是换行符]之后添加一个EOS [字符串结尾]字符[这是一个二进制0x00]。

因此，如果输入字符串为：abcdef\n，长度[从strlen得到]为7，输入[7]将为0x00，而input1[8]通过input1[99] 将有 undefined/random/不可预测的值和没有空格。

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

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

正如我上面提到的，fgets 不会在结束处填充字符串，所以，不用担心。它会做你想做的事 want/expect.

strlen 只计算最多 [but not 的字符，包括 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 在长度计算中包括 [internal/embedded] 空格。那是因为它是计算词组编辑距离的完全有效。

malloc 有一个有效的用法：当数据量太大而无法放入堆栈时。大多数系统都有默认限制（例如，在 linux 下，它是 8 MB）。

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

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

以上是合适的，但 c 矩阵会导致堆栈溢出：

int c[50000][50000];

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

所以，为了容纳所有这些数据，我们需要在堆上分配它。虽然可以为 c 和执行 malloc 维护二维矩阵访问，但我们必须创建一个函数并将指针传递给 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;
}

编辑距离矩阵

Edit Distance Matrix

c

algorithm

edit-distance