本文介绍一种基于贪心策略的html文本格式合并算法，通过分析相邻文本段的格式链长度与覆盖范围，智能合并冗余标签，显著减少html输出体积并保持语义正确性。
本文介绍一种基于贪心策略的html文本格式合并算法，通过分析相邻文本段的格式链长度与覆盖范围，智能合并冗余标签，显著减少html输出体积并保持语义正确性。
在将带格式的文本片段（如 text1[bold,italic]）拼接为结构化HTML时，关键挑战在于：避免为每个片段单独包裹标签，而是按格式作用域最大化合并，同时确保外层标签对应“最长持续格式”。例如，[bold,italic] → [bold] → [] 应生成 <b><i>text1</i>text2</b>text3，而非 <b><i>text1</i></b><b>text2</b>text3——后者多出1个 <b></b> 开闭对。
核心思想：格式链的“生命周期”建模
将每个格式（如 bold, italic）视为一个可开启/关闭的通道。对每个文本片段 t_i，定义其格式列表 F_i = [f₁, f₂, ..., fₖ]，其中顺序隐含嵌套关系（f₁ 最外层，fₖ 最内层）。关键观察是：
- 某格式
f的覆盖长度 = 从首个含f的片段起，连续包含f的片段数量； - 合并目标：让覆盖长度更长的格式处于更外层 DOM 位置，从而减少嵌套切换次数。
贪心算法步骤（伪代码）
def format_to_html(texts: List[Tuple[str, List[str]]]) -> str:
if not texts: return ""
# Step 1: 预计算每种格式的覆盖区间（起始索引、结束索引）
all_formats = set(f for _, fs in texts for f in fs)
coverage = {f: [len(texts), -1] for f in all_formats} # [first, last]
for i, (_, fs) in enumerate(texts):
for f in fs:
coverage[f][0] = min(coverage[f][0], i)
coverage[f][1] = max(coverage[f][1], i)
# Step 2: 按覆盖长度降序排序格式（长度 = last - first + 1），长度相同时按原始嵌套深度降序（保语义）
sorted_formats = sorted(
coverage.keys(),
key=lambda f: (coverage[f][1] - coverage[f][0], -len([i for i, (_, fs) in enumerate(texts) if f in fs and i == coverage[f][0]])),
reverse=True
)
# Step 3: 贪心生成标签流
html_parts = []
stack = [] # 当前打开的格式栈（按嵌套顺序）
for i, (content, current_fs) in enumerate(texts):
# 关闭不再需要的格式（从栈顶向下匹配）
while stack and stack[-1] not in current_fs:
html_parts.append(f"</{stack.pop()}>")
# 开启新格式：按 sorted_formats 顺序，只添加当前缺失且仍需开启的
for f in sorted_formats:
if f in current_fs and f not in stack:
html_parts.append(f"<{f}>")
stack.append(f)
# 插入文本内容（注意：不加换行符，由调用方控制可读性）
html_parts.append(content)
# 关闭剩余格式
while stack:
html_parts.append(f"</{stack.pop()}>")
return "".join(html_parts)实际示例验证
输入：
立即学习“前端免费学习笔记（深入）”；
生成可在 deepbi 沙箱 iframe 内运行或作为独立文件运行的交互式 HTML 页面，使用 `window.deepbi` JS SDK 实现数据查询、空间管理、文件浏览及用户操作。当用户提出以下需求时启用该能力： - 创建 KPI 仪表盘、数据表格、文件浏览器、成员列表、管理页面； - 明确要求“转成 dhtml”、“转译成 HTML”、“把 XX 页面转成……”、“控制台页面”、“管理后台”、“DeepBI 页面迁移”； - 提及位于 `apps/console/src/featur
texts = [
("text1", ["bold", "italic"]),
("text2", ["bold"]),
("text3", [])
]-
italic: 覆盖[0,0]→ 长度 1 -
bold: 覆盖[0,1]→ 长度 2
→bold优先外层 → 输出<b><i>text1</i>text2</b>text3✅
输入：
立即学习“前端免费学习笔记（深入）”；
texts = [
("text1", ["bold", "italic"]),
("text2", ["italic"]),
("text3", [])
]-
italic:[0,1]→ 长度 2 -
bold:[0,0]→ 长度 1
→italic外层 → 输出<i><b>text1</b>text2</i>text3✅
注意事项与进阶建议
-
格式冲突处理：若格式间存在语义互斥（如
code与bold），需在sorted_formats排序中加入业务规则权重； -
性能优化：对超长文本流（>10k 片段），可将
coverage计算改为单次遍历； -
HTML 安全性：实际部署时务必对
content做 HTML 实体转义（如html.escape(content)）； -
扩展性：支持 CSS 类名替代标签（如
["class:highlight", "bold"]），只需修改标签生成逻辑。
该算法时间复杂度为 O(n·m)（n=片段数，m=格式种类），空间复杂度 O(m)，在保证最优标签数的前提下兼具简洁性与工程实用性。
