问题日志记录的算法解决方案

最近在思考一个需求，类似于知乎这种问答平台，或者各种支持 markdown 编辑贡献的平台，允许每个用户对问题进行修改做贡献，同时记录每个用户的修改日志，如何实现？

业务系统的交互形态

在问题界面，前端请求后端拿到题目的文本，然后在前端使用 markdown 编辑器修改，然后点击提交按钮，将修改的文本提交给后端，后端计算原文本和修改后文本的修改日志，存储日志和操作信息。

其他考虑：哪些用户可以修改问题？有没有权限限制？角色限制和属性限制？

技术方案

存储数据结构

关于问题文本的存储，目前考虑方案是 checkout + 修改日志计算出最新内容，比如每10个修改日志存储一个 checkout，两个方向的考虑：节省存储成本，可以根据 checkout 进行分页。

前端直接请求问题：后端计算生成后返回 + 缓存 checkout 优化

前端请求问题日志：后端直接返回 checkout + log

后续优化：对频繁访问的文本内容，可以记录热点数据然后再定时任务预热生成 checkout，弱一致。

文本修改日志

前端传回新文本，后端接收到之后，上锁，从数据库取得最新的文本，计算两者的最小编辑距离，生成修改日志。

为什么采用修改日志的方案：

1. 问题的修改操作不会修改太多的文本，也就是增量数据是比较少的，如果直接存储新文本，会存在大量的重复数据存储，浪费空间。
2. 一个问题的文本最高不会超过400个字符，按最小编辑距离算法 DP 的时间复杂度 O(nm) ，最多计算 16w 次，最多不过80ms，计算成本可以接收。

技术细节：最小编辑成本算法

编辑成本：DELETE（删除），INSERT（插入），SUBSTITUTE（替换）操作代价相等，计算操作代价最少的方案。

实现：

1. 动态规划表：
   • 使用一个二维数组 dp，其中 dp[i][j] 表示将字符串 str1 的前 i 个字符转换为字符串 str2 的前 j 个字符所需的最小编辑距离。
2. 初始化：
   • dp[i][0] = i：将 str1 的前 i 个字符转换为空字符串，需要 i 次删除操作。
   • dp[0][j] = j：将空字符串转换为 str2 的前 j 个字符，需要 j 次插入操作。
3. 填充动态规划表：
   • 如果 str1.charAt(i - 1) 等于 str2.charAt(j - 1)，则 cost = 0，否则 cost = 1。
   • dp[i][j] 的值取以下三种操作的最小值：
     • 删除操作：dp[i - 1][j] + 1
     • 插入操作：dp[i][j - 1] + 1
     • 替换操作：dp[i - 1][j - 1] + cost
4. 返回结果：
   • 最终结果存储在 dp[str1.length()][str2.length()] 中。

PS：这种只需加记录前一次代价的 DP 可以压缩到一维节省空间。

由于 dp 数组只记录代价，所以需要自己维护操作记录。

public class EditorUtils {

    /* 计算最短修改日志 */
    public static List<Operation> diff(String fromText, String toText) {
        int m = fromText.length();
        int n = toText.length();

        // dp arrays
        int[] previous = new int[n + 1];
        int[] current = new int[n + 1];
        List<CharOp[]> previousOps = new ArrayList<>(n + 1);
        List<CharOp[]> currentOps = new ArrayList<>(n + 1);

        for (int j = 0; j <= n; j++) {
            previous[j] = j;
            if (j == 0) {
                previousOps.add(null);
            } else {
                previousOps.add(copyAndAppend(previousOps.get(j - 1), CharOp.insert(0, toText.charAt(j - 1))));
            }
        }

        for (int i = 1; i <= m; i++) {
            current[0] = i;
            currentOps.add(copyAndAppend(previousOps.get(0), CharOp.delete(i - 1)));

            for (int j = 1; j <= n; j++) {
                int cost = (fromText.charAt(i - 1) == toText.charAt(j - 1)) ? 0 : 1;

                int substitution = previous[j - 1] + cost;
                int insertion = current[j - 1] + 1;
                int deletion = previous[j] + 1;

                current[j] = Math.min(Math.min(substitution, insertion), deletion);

                // Record the operation
                if (current[j] == substitution) {
                    if (cost == 1) {
                        // substitute copy&append dp[i-1][j-1] 的 CharOp[]
                        currentOps.add(copyAndAppend(
                                previousOps.get(j - 1),
                                CharOp.substitute(i - 1, toText.charAt(j - 1))
                        ));
                    } else {
                        // 无变化，直接引用 dp[i-1][j-1] 的 CharOp[] 避免频繁 copy 带来的 gc
                        currentOps.add(previousOps.get(j - 1));
                    }
                } else if (current[j] == insertion) {
                    // insertion copy&append dp[i][j-1] 的 CharOp[]
                    currentOps.add(copyAndAppend(
                            currentOps.get(j - 1),
                            CharOp.insert(i, toText.charAt(j - 1))
                    ));
                } else if (current[j] == deletion) {
                    // deletion copy&append dp[i-1][j] 的 CharOp[]
                    currentOps.add(copyAndAppend(previousOps.get(j), CharOp.delete(i - 1)));
                }
            }

            int[] temp = previous;
            previous = current;
            current = temp;

            List<CharOp[]> tmpOps = previousOps;
            previousOps = currentOps;
            currentOps = tmpOps;
            currentOps.clear();
        }

        return optimize(previousOps.get(previousOps.size() - 1));
    }

    private static CharOp[] copyAndAppend(CharOp[] ops, CharOp operation) {
        if (Objects.isNull(ops)) {
            return new CharOp[]{operation};
        }
        CharOp[] copy = Arrays.copyOf(ops, ops.length + 1);
        copy[ops.length] = operation;
        return copy;
    }

    private static List<Operation> optimize(CharOp[] ops) {
        if (Objects.isNull(ops)) {
            return new ArrayList<>(0);
        }
        List<Operation> result = new ArrayList<>(ops.length / 2);
        for (CharOp op : ops) {
            if (result.isEmpty()) {
                result.add(buildOperation(op));
                continue;
            }
            Operation operation = result.get(result.size() - 1);
            if (!op.type.equals(operation.getType())) {
                result.add(buildOperation(op));
                continue;
            }
            switch (op.type) {
                case INSERT:
                    if (op.position == operation.getBeginIdx()) {
                        operation.appendChange(op.change);
                    } else {
                        result.add(buildOperation(op));
                    }
                    break;
                case SUBSTITUTE:
                    if (op.position == operation.getEndIdx() + 1){
                        operation.setEndIdx(op.position);
                        operation.appendChange(op.change);
                    } else {
                        result.add(buildOperation(op));
                    }
                    break;
                case DELETE:
                    if (op.position == operation.getEndIdx() + 1){
                        operation.setEndIdx(op.position);
                    } else {
                        result.add(buildOperation(op));
                    }
                    break;
            }
        }
        return result;
    }

    private static Operation buildOperation(CharOp op) {
        Operation operation = new Operation();
        operation.setBeginIdx(op.position);
        operation.setEndIdx(op.position);
        operation.setType(op.type);
        if (OperationType.INSERT.equals(op.type) || OperationType.SUBSTITUTE.equals(op.type)) {
            operation.setChange(String.valueOf(op.change));
        }
        return operation;
    }

    private static class CharOp {

        public final int position;
        public final char change;
        public final OperationType type;

        public CharOp(int position, OperationType type, char change) {
            this.position = position;
            this.change = change;
            this.type = type;
        }

        public static CharOp delete(int position) {
            return new CharOp(position, OperationType.DELETE, '\0');
        }

        public static CharOp insert(int position, char insertion) {
            return new CharOp(position, OperationType.INSERT, insertion);
        }

        public static CharOp substitute(int position, char change) {
            return new CharOp(position, OperationType.SUBSTITUTE, change);
        }
    }
}

数据结构：

public class Operation {

    private int beginIdx;
    private int endIdx;
    private OperationType type;
    private StringBuilder change;

    public int getBeginIdx() {
        return beginIdx;
    }

    public void setBeginIdx(int beginIdx) {
        this.beginIdx = beginIdx;
    }

    public int getEndIdx() {
        return endIdx;
    }

    public void setEndIdx(int endIdx) {
        this.endIdx = endIdx;
    }

    public OperationType getType() {
        return type;
    }

    public void setType(OperationType type) {
        this.type = type;
    }

    public String getChange() {
        return change.toString();
    }

    public void setChange(String change) {
        this.change = new StringBuilder(change);
    }

    public void appendChange(char change) {
        this.change.append(change);
    }

    @Override
    public String toString() {
        switch (type){
            case DELETE:
                return String.format("%s %d~%d",type,beginIdx,endIdx);
            case INSERT:
                return String.format("%s %d `%s`",type,beginIdx,change);
            case SUBSTITUTE:
                return String.format("%s %d~%d `%s`",type,beginIdx,endIdx,change);
        }
        return null;
    }
}

public enum OperationType {
    INSERT,
    DELETE,
    SUBSTITUTE,
}

实验数据：

public class Main {

    public static void main(String[] args) {
        String str1 = "夜色如墨，笼罩着这座古老而繁华的城市。霓虹灯闪烁，似是无数星星坠入凡间，却也掩盖不了街角那家老式唱片店透出的微弱光晕。林悦站在店门前，手中紧紧攥着一张泛黄的信笺，那是她与他唯一的联系。\n" +
                "\n" +
                "信上只有寥寥数语：“悦，我在唱片店等你，最后一首歌。”熟悉的笔迹，却带着陌生的疏离。她的心跳得厉害，像是要冲破胸腔。三年了，三年的思念与等待，她以为他早已消失在她的世界里，可如今，这封信却又将她拉回那个未解的谜团。\n" +
                "\n" +
                "推开门，旧唱片机的旋律悠悠传来，是那首老得掉牙的《月亮代表我的心》。灯光昏黄，空气中弥漫着旧时光的味道。她缓缓走进，视线在店内扫过，却不见他的身影。正当她有些失落时，角落里传来一声轻笑：“你来了。”她猛地转身，只见他倚在唱片架旁，眉眼如初，只是多了几分沧桑。";
        String str2 = "夜色如墨，温柔地拥抱着这座古老而繁华的城市。霓虹闪烁，似是无数星辰坠入凡间，却也掩盖不了街角那家老式唱片店透出的微弱光晕。林悦站在店门前，手中紧紧攥着一张泛黄的信笺，那是她与他唯一的联系。\n" +
                "\n" +
                "信上只有寥寥数语：“悦，我在唱片店等你，最后一首歌。”熟悉的笔迹，带着淡淡的墨香，却也透着陌生的疏离。她的心跳得厉害，像是要冲破胸腔。三年了，三年的思念与等待，她以为他早已消失在她的世界里，可如今，这封信却又将她拉回那个未解的谜团。\n" +
                "\n" +
                "她深吸一口气，缓缓推开门。旧唱片机的旋律悠悠传来，是那首老得掉牙的《月亮代表我的心》，熟悉的旋律在空气中轻轻荡漾，仿佛时光从未走远。灯光昏黄，空气中弥漫着旧时光的味道，每一寸空间都似乎在诉说着过往的故事。\n" +
                "\n" +
                "她小心翼翼地走进，视线在店内扫过，却不见他的身影。失落感正要涌上心头时，角落里传来一声轻笑：“你来了。”她猛地转身，只见他倚在唱片架旁，眉眼如初，只是多了几分沧桑。他的眼神温柔而深邃，仿佛藏着无尽的星辰大海，瞬间将她的世界点亮。";

        long begin = System.currentTimeMillis();
        List<Operation> diff =EditorUtils.diff(str1, str2);
//        diff.forEach(System.out::println);
        long end = System.currentTimeMillis();
        System.out.println("cost(ms) = " + (end-begin));

        StringBuilder builder = new StringBuilder(str1);
        for (int i = diff.size() - 1; i >= 0; i--) {
            Operation op = diff.get(i);
            switch (op.getType()) {
                case SUBSTITUTE:
                    builder.replace(op.getBeginIdx(), op.getEndIdx() + 1, op.getChange());
                    break;
                case INSERT:
                    builder.insert(op.getBeginIdx(), op.getChange());
                    break;
                case DELETE:
                    builder.delete(op.getBeginIdx(), op.getEndIdx() + 1);
                    break;
            }
        }
        System.out.println("operations = "+ diff.size());
        System.out.println("compare = " + str2.equals(builder.toString()));
    }
}

结果：

cost(ms) = 48
operations = 17
compare = true