03-Knuth-Plass算法

Knuth-Plass 算法详解 (optimalLayout)

概述

optimalLayout() 是整个排版系统的核心，实现了经典的 Knuth-Plass 行break算法。与浏览器贪婪策略不同，它通过动态规划找到段落的最优断点组合，使整段文本的间距分布最均匀。

核心思想对比

浏览器贪婪算法（简单但质量差）

flowchart LR
    A[填满当前行] --> B[计算剩余空间]
    B --> C[均分到所有词间距]
    C --> D[换行]
    D --> A

问题： 每行独立优化，忽略后续影响，导致间距参差不齐。

Knuth-Plass 全局优化（复杂但质量高）

flowchart TD
    A[构建所有可行断点图] --> B[计算每条边的badness]
    B --> C[最短路径搜索]
    C --> D[回溯得到最优break序列]
    
    style A fill:#e3f2fd
    style C fill:#c8e6c9
    style D fill:#fff3e0

完整算法流程

graph TD
    subgraph 输入
        A["prepared<br/>segments + widths"] --> B["maxWidth 容器宽度"]
        A --> C["NORMAL_SPACE_W 正常空格宽度"]
        A --> D["HYPHEN_WIDTH 连字符宽度"]
    end

    subgraph 断点候选构建
        B --> E["初始化breakCandidates<br/>从segIndex 0开始"]
        E --> F{"遍历所有segments"}
        F -->|遇到软连字符| G["添加候选：下个seg<br/>isSoftHyphen=true"]
        F -->|遇到空格| H["添加候选：下个seg<br/>isSoftHyphen=false"]
        F -->|其他| I["继续"]
        G --> J
        H --> J
        I --> F
        J --> K["末尾添加end标记"]
    end

    subgraph DP计算
        K --> L["dp[0]=0, 其余=∞"]
        L --> M{"遍历j从1到numCandidates"}
        M --> N{"遍历i从j-1到0"}
        N --> O["计算info<br/>wordWidth + spaceCount"]
        O --> P{"total > maxWidth×2"}
        P -->|是| Q["break跳出内循环"]
        P -->|否| R["cost = dp[i] + lineBadness"]
        R --> S{"cost < dp[j]"}
        S -->|是| T["dp[j] = cost<br/>prev[j] = i"]
        S -->|否| U["保持"]
        T --> V["i--"]
        U --> V
        V --> N
        N -->|i<0| W["j++"]
        W --> M
        M -->|完成| X["开始回溯"]
    end

    subgraph 回溯构建lines
        X --> Y["cur = numCandidates-1"]
        Y --> Z{"prev[cur] !== -1"}
        Z -->|是| AA["breaks.push cur"]
        AA --> AB["cur = prev[cur]"]
        Z -->|否| AC["cur--"]
        AB --> Z
        AC --> Z
        Z -->|cur<=0| AD["breaks.reverse"]
        AD --> AE["构建lines数组<br/>segments + y + lineWidth"]
    end

    style M fill:#fff3e0
    style R fill:#ffcdd2
    style T fill:#c8e6c9
    style AD fill:#e8f5e9

代码逐段解析

第一阶段：构建断点候选

// 第289-305行
const segs = prepared.segments;
const widths = prepared.widths;
const n = segs.length;
if (n === 0) return [];

const breakCandidates = [{ segIndex: 0, isSoftHyphen: false }];
// 初始候选：段落开头

for (let i = 0; i < n; i++) {
  const text = segs[i];
  if (text === "") {
    // 软连字符：可断裂点，且行尾带连字符
    if (i + 1 < n)
      breakCandidates.push({ segIndex: i + 1, isSoftHyphen: true });
  } else if (text.trim().length === 0 && i + 1 < n) {
    // 空格：可断裂点，行尾不带连字符
    breakCandidates.push({ segIndex: i + 1, isSoftHyphen: false });
  }
}
breakCandidates.push({ segIndex: n, isSoftHyphen: false });
// 末尾添加段落结束标记

断点候选数据结构：

interface BreakCandidate {
  segIndex: number;    // 指向segments数组的索引
  isSoftHyphen: boolean; // 是否由软连字符触发
}

为什么空格后面才是断点？
英文排版约定：行尾不能是空格，所以断点应在下一个单词的起始位置。

第二阶段：计算行信息

// 第307-321行
const getLineInfo = (fromIdx: number, toIdx: number) => {
  const from = breakCandidates[fromIdx].segIndex;
  const to = breakCandidates[toIdx].segIndex;
  // 将候选索引转换为实际segment范围

  const endsWithHyphen = breakCandidates[toIdx].isSoftHyphen;
  let wordWidth = 0,
    spaceCount = 0;
    
  for (let si = from; si < to; si++) {
    const t = segs[si];
    if (t === "") continue;  // 软连字符不计入宽度
    t.trim().length === 0 
      ? spaceCount++          // 统计空格数量
      : (wordWidth += widths[si]); // 累加单词宽度
  }
  
  if (to > from && segs[to - 1].trim().length === 0) spaceCount--;
  // 减去行末尾的尾部空格
  
  if (endsWithHyphen) wordWidth += HYPHEN_WIDTH;
  // 软连字符断裂时需要加上连字符宽度
  
  return { wordWidth, spaceCount, endsWithHyphen };
};

关键细节：

场景	处理逻辑
软连字符	`continue` 不占宽度，但 `endsWithHyphen=true` 时加 HYPHEN_WIDTH
行末尾空格	`spaceCount--` 排除，不参与间距计算
空格数量	决定了行内有多少个"可拉伸"的间距位置

第三阶段：行质量评估（核心！）

// 第323-341行
const lineBadness = (info: any, isLastLine: boolean) => {
  if (isLastLine) 
    return info.wordWidth > maxWidth ? 1e8 : 0;
    // 最后一行：只惩罚超宽，其他不罚
  
  if (info.spaceCount <= 0) {
    // 无空格行：可能是URL或其他连续字符
    const slack = maxWidth - info.wordWidth;
    return slack < 0 ? 1e8 : slack * slack * 10;
    // 超宽严惩，不超宽给适度惩罚
  }
  
  // 计算实际间距 js (justification space)
  const js = (maxWidth - info.wordWidth) / info.spaceCount;
  // js = 可用空间 / 空格数量 = 每个间距应该有的宽度
  
  if (js < 0 || js < NORMAL_SPACE_W * 0.4) return 1e8;
  // 间距过紧或为负 → 严惩
  
  // ---- 以下是核心惩罚项 ----
  
  // 1. 基本不良度：间距偏离正常值越多，惩罚越大
  const ratio = (js - NORMAL_SPACE_W) / NORMAL_SPACE_W;
  const badness = Math.abs(ratio) ** 3 * 1000;
  
  // 2. 河流惩罚：间距 > 正常间距的1.5倍时触发
  //    这种情况会产生视觉上的"白河"
  const river = Math.max(0, js / NORMAL_SPACE_W - 1.5);
  
  // 3. 紧凑惩罚：间距 < 正常间距的0.65倍时触发
  const tight = Math.max(0, NORMAL_SPACE_W * 0.65 - js);
  
  // 4. 连字符惩罚：行尾带连字符不太优雅
  return (
    badness +
    (river ** 2 * 1e4 + 5000) +     // 河流惩罚权重最高
    (tight ** 2 * 1e4 + 3000) +
    (info.endsWithHyphen ? 50 : 0)   // 连字符惩罚最低
  );
};

Badness 公式图解：

flowchart LR
    subgraph 间距评估
        A[js = (maxWidth - wordWidth)<br/>/ spaceCount] --> B{js vs 阈值}
        B -->|过紧<br/>js < 0.4×normal| C[1e8 严惩]
        B -->|正常| D[计算badness<br/>ratio³×1000]
        B -->|过松| E[河流检测]
        
        E -->|有河流<br/>js > 1.5×normal| F[river惩罚<br/>river²×1e4+5000]
        E -->|无河流| G[基本badness]
        
        D --> H[总计惩罚值]
        F --> H
        G --> H
    end
    
    style C fill:#ffcdd2
    style F fill:#fff3e0
    style H fill:#c8e6c9

第四阶段：动态规划求解

// 第343-360行
const dp = new Array(numCandidates).fill(Infinity);
// dp[i] = 从起点到第i个候选的最小累计惩罚

const prev = new Array(numCandidates).fill(-1);
// prev[i] = 到达i的最优前驱节点

dp[0] = 0;  // 起点成本为0

for (let j = 1; j < numCandidates; j++) {
  const last = j === numCandidates - 1;
  // 最后一行使用不同的badness计算
  
  for (let i = j - 1; i >= 0; i--) {
    if (dp[i] === Infinity) continue;
    // 无法到达的节点跳过
    
    const info = getLineInfo(i, j);
    // 计算从i到j这一行的信息
    
    const total = info.wordWidth + info.spaceCount * NORMAL_SPACE_W;
    // 预估行总宽度
    
    if (total > maxWidth * 2) break;
    // 超过2倍最大宽度就不考虑了，大幅减少计算量
    
    const cost = dp[i] + lineBadness(info, last);
    // 累计成本 = 之前成本 + 当前行惩罚
    
    if (cost < dp[j]) {
      dp[j] = cost;
      prev[j] = i;  // 记录最优前驱
    }
  }
}

DP状态转移图：

flowchart LR
    subgraph DP过程
        A[dp[0]=0] --> B[计算dp[1]]
        B --> C[dp[1]=dp[0]+badness<br/>prev[1]=0]
        C --> D[计算dp[2]]
        D --> E[尝试dp[0]→dp[2]]
        D --> F[尝试dp[1]→dp[2]]
        E --> G[取最小者]
        F --> G
        G --> H[...]
    end

第五阶段：回溯构建结果

// 第362-371行
const breaks: number[] = [];
let cur = numCandidates - 1;  // 从末尾开始

while (cur > 0) {
  if (prev[cur] === -1) {
    cur--;  // 跳过无法到达的节点
    continue;
  }
  breaks.push(cur);  // 记录断点
  cur = prev[cur];   // 回溯到前驱
}
breaks.reverse();  // 翻转得到正序

回溯过程图解：

prev数组: [-1, 0, 0, 1, 2, 4, ...]
           0   1  2  3  4  5

回溯从 index 6 开始:
  6 → prev[6]=4 → breaks=[6]
  4 → prev[4]=2 → breaks=[6,4]
  2 → prev[2]=0 → breaks=[6,4,2]
  0 → 终止

reverse: [2, 4, 6]  ← 断点位置

与浏览器排版的关键差异

特性	浏览器贪婪	Knuth-Plass
考虑范围	单行	全段落
间距均匀度	差	优
河流抑制	无	有
连字符使用	少	多
计算复杂度	O(n)	O(n²)

性能优化技巧

1. 提前终止 (`total > maxWidth * 2`)

if (total > maxWidth * 2) break;

这行代码至关重要：

当行宽度超过容器2倍时，必然不是最优解
跳过对后续i的探索，将复杂度从 O(n³) 降至接近 O(n²)

2. Infinity 剪枝

if (dp[i] === Infinity) continue;

不可达状态直接跳过，避免无效计算。

3. 倒序遍历i

for (let i = j - 1; i >= 0; i--) { ... }

从右向左遍历可以在找到超宽行时立即 break。

扩展讨论：如何优化更多场景

1. 孤立词惩罚（Orphan control）

// 行首单词太短不优雅
if (firstWordWidth < threshold) badness += 1000;

2. Widow/Orphan 行数控制

// 确保段落最后至少2行不分离
if (linesRemaining <= 2) 
  preferredBreak = Math.min(...nearBreaks);

3. 多段落联合优化

当前实现按段落独立优化，可扩展为跨段落考虑，使页面整体更均衡。