基于约束的最优文本块组合Python实现方法咨询

问题背景 #

给定如下嵌套JSON结构：

{
  "id": 1,
  "parent_id": null,
  "text": "This is level 1, id 1",
  "blocks": [
    {
      "id": 2,
      "parent_id": 1,
      "text": "This is level 2, id 2",
      "blocks": [
        {
          "id": 3,
          "parent_id": 2,
          "text": "This is level 3, id 3"
        },
        {
          "id": 4,
          "parent_id": 2,
          "text": "This is level 3, id 4"
        }
      ]
    },
    {
      "id": 5,
      "parent_id": 1,
      "text": "This is level 2, id 5"
    }
  ]
}

需要按照以下约束将text字段组合成文本块：

• 仅当组合后文本块的总字符数小于阈值X（示例中为50）时，才可组合
• 从最深层嵌套元素开始组合
• 最小化生成的文本块数量
• 保留原有元素顺序

针对示例的预期输出：

chunks = [
  ["This is level 1, id 1", "This is level 2, id 2"],
  ["This is level 3, id 3", "This is level 3, id 4"],
  ["This is level 2, id 5"]
]

注：id=5的元素与id=2的元素虽处于同一深度，但因会破坏顺序无法组合，仅当元素2、3、4、5的字符总数少于50时才可合并。尝试通过递归从最深层到根节点遍历生成文本块，但未得到预期结果，寻求Python实现方案。

解决方案 #

实现思路 #

核心采用后序遍历（先处理所有子节点，再处理当前节点）确保从最深层开始组合；将当前节点文本作为单独块插入子块列表头部，再从左到右尝试合并相邻块，满足字符数限制则合并，最终得到符合所有约束的文本块列表。

Python代码实现 #

def combine_blocks(node, max_chars=50):
    # 递归处理所有子节点，拼接子块列表
    child_chunks = []
    if 'blocks' in node and node['blocks']:
        for child in node['blocks']:
            child_chunks.extend(combine_blocks(child, max_chars))
    
    # 将当前节点的text作为单独块（用列表包裹，方便合并）
    current_chunk = [node['text']]
    # 构建临时列表：当前块 + 子块列表
    temp_chunks = [current_chunk] + child_chunks
    
    # 合并相邻块，直到无法合并
    merged = []
    for chunk in temp_chunks:
        if not merged:
            merged.append(chunk)
        else:
            # 计算合并后的总字符数
            combined_length = len(''.join(merged[-1])) + len(''.join(chunk))
            if combined_length <= max_chars:
                # 合并两个块
                merged[-1] = merged[-1] + chunk
            else:
                merged.append(chunk)
    return merged

# 测试示例数据
data = {
  "id": 1,
  "parent_id": None,
  "text": "This is level 1, id 1",
  "blocks": [
    {
      "id": 2,
      "parent_id": 1,
      "text": "This is level 2, id 2",
      "blocks": [
        {
          "id": 3,
          "parent_id": 2,
          "text": "This is level 3, id 3"
        },
        {
          "id": 4,
          "parent_id": 2,
          "text": "This is level 3, id 4"
        }
      ]
    },
    {
      "id": 5,
      "parent_id": 1,
      "text": "This is level 2, id 5"
    }
  ]
}

chunks = combine_blocks(data)
print("chunks = [")
for chunk in chunks:
    print(f"  {chunk!r},")
print("]")

运行代码后输出与预期一致：

chunks = [
  ['This is level 1, id 1', 'This is level 2, id 2'],
  ['This is level 3, id 3', 'This is level 3, id 4'],
  ['This is level 2, id 5'],
]

代码说明 #

1. 递归处理子节点：优先完成最深层元素的合并，满足“从最深层开始组合”的约束。
2. 维护顺序：将当前节点文本插入子块列表头部，确保元素顺序与原结构一致。
3. 合并逻辑：从左到右尝试合并相邻块，仅在字符数阈值内合并，实现最小化块数量的目标。

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