如何计算含特殊字符的文档或代码的最小编辑距离（MED）？

问题背景 #

已掌握短字符串（如abcde和abfde）的最小编辑距离（MED）计算方法，但无法处理包含空格、制表符、换行符的长文档、文章或代码段。曾尝试删除所有空白字符并合并为单字符串，但存在字符串过长导致的内存/性能问题，寻求更优方案。

示例文本 #

text1:
The computer learns from a huge database of four million videos from volunteers and paid-for market
researchers in various emotional states and the algorithms are constantly updated and tested against real-world
scenarios.
The next stage is to integrate voice analysis and other measures of physical wellbeing such as heart rate and
hand gestures.

text2:
A computer model has been developed that can predict what word you are thinking of. The model may help to
resolve questions about how the brain processes words and language, and might even lead to techniques for
decoding people’s thoughts.
Researchers led by Tom Mitchell of Carnegie Mellon University in Pittsburgh, Pennsylvania, 'trained' a computer
model to recognize the patterns of brain activity associated with 60 images, each of which represented a
different noun, such as 'celery' or 'aeroplane'.

现有短字符串MED代码 #

int med_lev(char S[], char T[]) {
    int dis_lev[20][20];
    int n = strlen(S);
    int m = strlen(T);

    for (int i = 0; i <= n; i++) {
        dis_lev[i][0] = i;
    }
    for (int j = 0; j <= m; j++) {
        dis_lev[0][j] = j;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (S[i - 1] == T[j - 1]) {
                dis_lev[i][j] = dis_lev[i - 1][j - 1];
            }
            else {
                dis_lev[i][j] = min(dis_lev[i - 1][j - 1] + 2, min(dis_lev[i - 1][j] + 1, dis_lev[i][j - 1] + 1));
            }
        }
    }
    return dis_lev[n][m];
}

解决方案 #

1. 优化动态规划的空间复杂度 #

原代码使用二维数组存储所有中间状态，处理长文本时（比如长度10000的字符串）会占用大量内存（如10000*10000=1e8个int，约400MB），极易内存溢出。实际上，计算当前行的编辑距离只需要上一行的结果，可将空间复杂度从O(n*m)优化为O(min(n,m))，具体实现如下：

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

// 辅助函数：取三个整数的最小值
int min3(int a, int b, int c) {
    int temp = a < b ? a : b;
    return temp < c ? temp : c;
}

int med_lev_long(char *S, char *T) {
    int n = strlen(S);
    int m = strlen(T);

    // 始终以较短字符串作为列，进一步压缩内存占用
    if (n < m) {
        char *temp = S;
        S = T;
        T = temp;
        int tmp = n;
        n = m;
        m = tmp;
    }

    // 仅分配两行内存：上一行状态、当前行状态
    int *prev = (int*)malloc((m + 1) * sizeof(int));
    int *curr = (int*)malloc((m + 1) * sizeof(int));
    if (!prev || !curr) {
        free(prev);
        free(curr);
        return -1; // 内存分配失败返回错误标记
    }

    // 初始化第一行（空字符串到T前j个字符的编辑距离）
    for (int j = 0; j <= m; j++) {
        prev[j] = j;
    }

    for (int i = 1; i <= n; i++) {
        curr[0] = i; // 初始化当前行第一个元素（S前i个字符到空字符串的编辑距离）
        for (int j = 1; j <= m; j++) {
            int cost = (S[i-1] == T[j-1]) ? 0 : 2;
            curr[j] = min3(
                prev[j-1] + cost, // 匹配/替换操作
                prev[j] + 1,      // 删除操作
                curr[j-1] + 1     // 插入操作
            );
        }
        // 交换两行指针，准备下一轮迭代
        int *temp = prev;
        prev = curr;
        curr = temp;
    }

    int result = prev[m];
    free(prev);
    free(curr);
    return result;
}

2. 保留空白字符的必要性 #

不要直接删除空格、换行、制表符：这些字符在文本（段落分隔、排版逻辑）和代码（缩进、语法结构）中具有语义价值，删除会破坏原始内容的结构，导致计算出的MED无法准确反映两段内容的真实差异。优化空间后的方案可直接处理包含空白字符的长文本，无需预处理删除。

3. 超大规模文本的可选方案 #

如果文本规模达到数十MB级别，可考虑分块计算：将文本分割为若干语义独立的块（比如按段落、代码函数），分别计算每个块的MED后加权求和。但这种方法需要根据文本类型调整分割逻辑，且会损失全局最优性，仅在极端场景下使用。

内容的提问来源于stack exchange，提问作者Rou2001