多列表最长公共子序列泛化实现CSV列有序合并

问题背景 #

需要合并多个CSV文件的列，要求尽可能保留每个文件的列顺序，且最终结果不依赖文件的合并顺序。例如：

• 文件1列：[A, B, D]
• 文件2列：[A, C, D]
• 文件3列：[B, C]
  期望得到合并列顺序：[A, B, C, D]，而非依赖合并顺序得到的[A, C, B, D]。

初始采用双序列LCS算法合并，但迭代合并多文件时结果依赖顺序，无法利用所有文件的顺序约束信息。

解决方案：基于约束图的拓扑排序 #

核心思路 #

1. 构建顺序约束图：把每个列名作为图的节点，对每个CSV文件的列序列，为每一对连续列(X, Y)添加一条有向边X→Y，并统计这条边的出现次数（支持度）。
2. 处理冲突与环：如果出现互斥约束（如X→Y和Y→X），保留支持度更高的边；若支持度相同，可按列名字典序或其他规则默认排序。若存在环（无法解决的循环约束），直接移除环内的边，避免拓扑排序失败。
3. 拓扑排序生成最终列顺序：对处理后的有向无环图（DAG）执行拓扑排序，得到的序列即为满足所有有效约束的合并列顺序。

TypeScript实现 #

// 定义图结构：key是节点，value是{ 后继节点: 支持度 }
type ConstraintGraph = Record<string, Record<string, number>>;

// 构建约束图
function buildConstraintGraph(columnLists: string[][]): ConstraintGraph {
    const graph: ConstraintGraph = {};

    for (const columns of columnLists) {
        for (let i = 0; i < columns.length - 1; i++) {
            const prev = columns[i];
            const next = columns[i + 1];

            // 初始化节点
            if (!graph[prev]) graph[prev] = {};
            if (!graph[next]) graph[next] = {};

            // 更新边的支持度
            graph[prev][next] = (graph[prev][next] || 0) + 1;
        }
    }

    // 处理互斥约束：保留支持度更高的边
    const nodes = Object.keys(graph);
    for (const x of nodes) {
        for (const y of nodes) {
            if (x === y) continue;
            const xToY = graph[x][y] || 0;
            const yToX = graph[y][x] || 0;

            if (xToY > 0 && yToX > 0) {
                if (xToY > yToX) {
                    delete graph[y][x];
                } else if (yToX > xToY) {
                    delete graph[x][y];
                } else {
                    // 支持度相同，按字典序保留X→Y（X字典序小于Y时）
                    if (x.localeCompare(y) > 0) {
                        delete graph[x][y];
                    } else {
                        delete graph[y][x];
                    }
                }
            }
        }
    }

    return graph;
}

// 拓扑排序（Kahn算法）
function topologicalSort(graph: ConstraintGraph): string[] {
    const inDegree: Record<string, number> = {};
    const queue: string[] = [];
    const result: string[] = [];

    // 初始化入度
    Object.keys(graph).forEach(node => {
        inDegree[node] = 0;
    });
    Object.values(graph).forEach(edges => {
        Object.keys(edges).forEach(node => {
            inDegree[node] = (inDegree[node] || 0) + 1;
        });
    });

    // 入度为0的节点入队
    Object.keys(inDegree).forEach(node => {
        if (inDegree[node] === 0) {
            queue.push(node);
        }
    });

    // 执行拓扑排序
    while (queue.length > 0) {
        const current = queue.shift()!;
        result.push(current);

        Object.keys(graph[current]).forEach(nextNode => {
            inDegree[nextNode]--;
            if (inDegree[nextNode] === 0) {
                queue.push(nextNode);
            }
        });
    }

    // 处理环（剩余入度不为0的节点）：按字典序追加
    const remainingNodes = Object.keys(inDegree).filter(node => inDegree[node] > 0);
    remainingNodes.sort();
    result.push(...remainingNodes);

    return result;
}

// 合并多文件列顺序的主函数
function mergeColumnOrders(columnLists: string[][]): string[] {
    const graph = buildConstraintGraph(columnLists);
    return topologicalSort(graph);
}

// 示例使用
const testColumns = [
    ['A', 'C', 'D'],
    ['A', 'B', 'D'],
    ['B', 'C']
];
console.log(mergeColumnOrders(testColumns)); // 输出: [ 'A', 'B', 'C', 'D' ]

性能分析 #

• 时间复杂度：构建图的时间是O(NM)（N是文件数，M是单文件列数），拓扑排序是O(V+E)（V是总列数，E是约束边数）。对于20个50列的文件，总边数最多为2049=980，总列数最多约75（多数列一致，少数差异50%），计算耗时远小于1秒，完全满足≤10秒的要求。
• 空间复杂度：主要存储约束图，空间占用极小，适合大规模文件处理。

关键特性说明 #

• 不依赖合并顺序：所有文件的顺序约束被统一收集到图中，最终排序由全局约束决定。
• 利用所有文件信息：通过统计边的支持度，优先保留出现次数多的顺序约束，解决冲突。
• 兼容列差异：自动包含所有文件的列，即使某列仅出现在单个文件中。

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