如何实现带格式标记文本拼接为优化HTML的高效算法？

核心思路 #

要实现格式合并与合理嵌套，核心是先确定格式的优先级（覆盖范围越广优先级越高，越外层嵌套），再基于格式栈管理标签的开启/关闭，减少重复标签，实现连续相同格式的合并。

具体分四步：

1. 解析文本块：将每个带格式标记的文本解析为「文本内容 + 格式集合」的结构
2. 计算格式覆盖范围：统计每个格式覆盖的连续文本块区间（从首次出现到末次出现的块数量），覆盖范围越长的格式，嵌套层级越靠外
3. 排序格式优先级：按覆盖范围从大到小排序格式，确保外层标签对应覆盖更广的格式
4. 栈式生成HTML：用栈维护当前激活的格式，遍历每个文本块时，对比当前块格式与栈内格式，动态开启/关闭标签（按优先级顺序），同时输出文本内容

伪代码实现 #

# 1. 解析输入文本块
function parse_blocks(input_lines):
    blocks = []
    for line in input_lines:
        split_idx = line.find('[')
        text = line[:split_idx].strip()
        format_str = line[split_idx+1 : line.find(']')].strip()
        formats = set(format_str.split(',')) if format_str else set()
        blocks.append({ "text": text, "formats": formats })
    return blocks

# 2. 计算每个格式的覆盖范围（覆盖的块数）
function calculate_format_ranges(blocks):
    format_ranges = {}
    # 记录每个格式的首次和末次出现位置
    first_occur = {}
    last_occur = {}
    for idx, block in enumerate(blocks):
        for fmt in block["formats"]:
            if fmt not in first_occur:
                first_occur[fmt] = idx
            last_occur[fmt] = idx
    # 计算覆盖长度（末次-首次+1）
    for fmt in first_occur:
        format_ranges[fmt] = last_occur[fmt] - first_occur[fmt] + 1
    return format_ranges

# 3. 按覆盖范围降序排序格式
function sort_formats_by_range(format_ranges):
    return sorted(format_ranges.keys(), key=lambda x: -format_ranges[x])

# 4. 栈式生成HTML
function generate_html(blocks, sorted_formats):
    current_stack = []
    html = []
    indent = 0  # 用于美化缩进，可选
    
    for block in blocks:
        current_formats = block["formats"]
        
        # 第一步：关闭不再需要的格式（从栈顶到栈底，即内层先关）
        while current_stack:
            fmt = current_stack[-1]
            if fmt not in current_formats:
                current_stack.pop()
                indent -= 1
                html.append(f"{'  '*indent}</{fmt_to_tag(fmt)}>")
            else:
                break
        
        # 第二步：开启需要的新格式（按优先级顺序，外层先开）
        for fmt in sorted_formats:
            if fmt in current_formats and fmt not in current_stack:
                html.append(f"{'  '*indent}<{fmt_to_tag(fmt)}>")
                current_stack.append(fmt)
                indent += 1
        
        # 第三步：添加文本内容，带缩进
        html.append(f"{'  '*indent}{block['text']}")
    
    # 最后关闭所有剩余的格式
    while current_stack:
        fmt = current_stack.pop()
        indent -= 1
        html.append(f"{'  '*indent}</{fmt_to_tag(fmt)}>")
    
    return '\n'.join(html)

# 辅助函数：格式名转HTML标签（可扩展）
function fmt_to_tag(fmt):
    tag_map = {
        "bold": "b",
        "italic": "i",
        # 可添加更多格式，如underline->u等
    }
    return tag_map.get(fmt, fmt)

Python 示例实现 #

def parse_blocks(input_lines):
    blocks = []
    for line in input_lines:
        split_idx = line.find('[')
        text = line[:split_idx].strip()
        format_part = line[split_idx+1 : line.find(']')].strip()
        formats = set(format_part.split(',')) if format_part else set()
        blocks.append({"text": text, "formats": formats})
    return blocks

def calculate_format_ranges(blocks):
    first_occur = {}
    last_occur = {}
    for idx, block in enumerate(blocks):
        for fmt in block["formats"]:
            if fmt not in first_occur:
                first_occur[fmt] = idx
            last_occur[fmt] = idx
    format_ranges = {fmt: last_occur[fmt] - first_occur[fmt] + 1 for fmt in first_occur}
    return format_ranges

def sort_formats_by_range(format_ranges):
    return sorted(format_ranges.keys(), key=lambda x: -format_ranges[x])

def fmt_to_tag(fmt):
    tag_map = {"bold": "b", "italic": "i"}
    return tag_map.get(fmt, fmt)

def generate_html(blocks, sorted_formats):
    current_stack = []
    html = []
    indent = 0

    for block in blocks:
        current_formats = block["formats"]

        # 关闭不需要的格式
        while current_stack:
            fmt = current_stack[-1]
            if fmt not in current_formats:
                current_stack.pop()
                indent -= 1
                html.append(f"{'  '*indent}</{fmt_to_tag(fmt)}>")
            else:
                break

        # 开启新的格式
        for fmt in sorted_formats:
            if fmt in current_formats and fmt not in current_stack:
                html.append(f"{'  '*indent}<{fmt_to_tag(fmt)}>")
                current_stack.append(fmt)
                indent += 1

        # 添加文本
        html.append(f"{'  '*indent}{block['text']}")

    # 关闭剩余格式
    while current_stack:
        fmt = current_stack.pop()
        indent -= 1
        html.append(f"{'  '*indent}</{fmt_to_tag(fmt)}>")

    return '\n'.join(html)

# 测试示例
if __name__ == "__main__":
    test_input = [
        "text1[bold,italic]",
        "text2[italic]",
        "text3[]"
    ]
    blocks = parse_blocks(test_input)
    format_ranges = calculate_format_ranges(blocks)
    sorted_formats = sort_formats_by_range(format_ranges)
    result = generate_html(blocks, sorted_formats)
    print(result)

运行上述代码，输出与需求一致：

<i>
  <b>text1</b>
  text2
</i>
text3

关键说明 #

1. 格式优先级排序：通过计算每个格式的覆盖块数，确保覆盖范围广的格式先被开启，从而嵌套在最外层
2. 栈式管理：通过栈维护当前激活的格式，每次处理块时只调整差异部分，避免重复生成标签，实现格式合并
3. 可扩展性：fmt_to_tag函数可轻松扩展更多格式（如underline转<u>），排序逻辑也可根据需求调整（如覆盖范围相同时按格式名称排序）

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