如何基于起止偏移量递归分组数组元素并构建splits层级结构

问题背景 #

在文本位置计数中，空格计入位置（如单词Asteroid的A在0位，d在7位，后续空格为8位）。

需求描述 #

给定包含start_offset（起始偏移量）、end（结束偏移量）、text、entity_type的对象数组，需递归执行以下操作：

• 找出所有完全落在某元素start_offset与end范围内的子元素
• 将子元素归入该元素的splits数组中
• 重复此操作n次，最终构建出层级化的分组结构

现有尝试 #

已使用reduce方法实现近似效果，但仍需优化，代码如下：

const res = arr.reduce((pv, cv) => {
    const [{ start_offset, end }] = arr
      .filter((s) => (s.start_offset <= cv.start_offset) && (s.end >= cv.end))
      .sort((s1, s2) => (s2.end - s2.start_offset) - (s1.end - s1.start_offset));
    
    const hash = `${start_offset}-${end}`;
    pv[hash] = pv[hash]
      ? { ...pv[hash], splits: [...pv[hash].splits, cv] }
      : { start_offset, end, splits: [cv] };
    
    return pv;
}, {});
const result = Object.values(res);
console.log(result)

输入示例 #

let arr = [
    {
      "start_offset": 0,
      "end": 38,
      "text": "Asteroid is a rocky objects that orbit",
      "entity_type": "adjective",
    },
    {
      "start_offset": 12,
      "end": 19,
      "text": "a rocky",
      "entity_type": "adjective",
    },
    {
      "start_offset": 14,
      "end": 27,
      "text": "rocky objects",
      "entity_type": "adjective",
    },
    {
      "start_offset": 20,
      "end": 32,
      "text": "objects that",
      "entity_type": "adjective",
    },
    {
      "start_offset": 14,
      "end": 19,
      "text": "rocky",
      "entity_type": "adjective",
    },
    {
      "start_offset": 20,
      "end": 27,
      "text": "objects",
      "entity_type": "adjective",
    },
    {
      "start_offset": 33,
      "end": 47,
      "text": "orbit the Sun",
      "entity_type": "adjective",
    },
    {
      "start_offset": 43,
      "end": 47,
      "text": "Sun",
      "entity_type": "adjective",
    }
  ]

期望输出 #

构建出包含层级splits的数组结构，示例如下：

let output = [
    {
      "start_offset": 0,
      "end": 38,
      "text": "Asteroid is a rocky objects that orbit",
      "entity_type": "adjective",
      "splits": [
            {
              "start_offset": 12,
              "end": 19,
              "text": "a rocky",
              "entity_type": "adjective",
              "splits": [
                {
                  "start_offset": 14,
                  "end": 19,
                  "text": "rocky",
                  "entity_type": "adjective",
                },
              ]
            },
            {
              "start_offset": 14,
              "end": 27,
              "text": "rocky objects",
              "entity_type": "adjective",
              "splits": [
                {
                  "start_offset": 20,
                  "end": 27,
                  "text": "objects",
                  "entity_type": "adjective",
                },
              ]
            },
            {
              "start_offset": 20,
              "end": 32,
              "text": "objects that",
              "entity_type": "adjective",
            },
      ]
    },
    {
      "start_offset": 33,
      "end": 47,
      "text": "orbit the Sun",
      "entity_type": "adjective",
    },
    {
      "start_offset": 43,
      "end": 47,
      "text": "Sun",
      "entity_type": "adjective",
    }
 ]

优化方案 #

现有代码仅完成单层分组，未实现递归嵌套层级，且未排除元素自身作为父元素的情况。以下是优化后的实现：

function buildHierarchy(arr) {
    // 创建元素映射，避免重复创建对象，提升查找效率
    const elementMap = new Map(arr.map(item => [`${item.start_offset}-${item.end}`, {...item}]));
    const roots = [];

    // 遍历每个元素，找到其直接父元素（最小的包含自身的元素）
    for (const item of arr) {
        // 筛选所有包含当前元素的候选父元素，排除自身
        const parents = arr.filter(p => 
            p.start_offset <= item.start_offset && p.end >= item.end 
            && !(p.start_offset === item.start_offset && p.end === item.end)
        );

        if (parents.length > 0) {
            // 按范围大小升序排序，取第一个即为直接父级
            const directParent = parents.sort((a, b) => (a.end - a.start_offset) - (b.end - b.start_offset))[0];
            const parentKey = `${directParent.start_offset}-${directParent.end}`;
            
            // 给父元素初始化splits数组并添加当前元素
            if (!elementMap.get(parentKey).splits) {
                elementMap.get(parentKey).splits = [];
            }
            elementMap.get(parentKey).splits.push(elementMap.get(`${item.start_offset}-${item.end}`));
        } else {
            // 无父元素则作为根节点
            roots.push(elementMap.get(`${item.start_offset}-${item.end}`));
        }
    }

    return roots;
}

// 测试调用
const output = buildHierarchy(arr);
console.log(output);

优化说明 #

1. 元素映射：用Map存储每个元素，避免重复构造对象，提升查找效率
2. 直接父级筛选：通过筛选+排序找到范围最小的包含元素，确保是直接父级而非任意祖先
3. 嵌套层级构建：通过给父元素添加splits数组，自然形成递归嵌套结构
4. 根节点收集：无父元素的元素直接作为顶层节点

内容的提问来源于stack exchange，提问作者Vikas Acharya