树的偏移量

Question

所以我的数据结构如下所示：

{
  "text": "hello world!",
  "tags": [{"start": 0, "end": 4, "tag": "b"}, {"start": 1, "end": 5, "tag": "i"}]
}

我想把它变成这样的东西：

[["b", [
   ["#text", "h"],
   ["i", ["#text", "ello"]]]]
,["i", ["#text", " "]]
,["#text", "world!"]]

（是的，这是对 DOM 树的抽象表示。）

我不太确定开始处理这个问题的正确方法是什么。 . .有什么想法吗？

Answer 1

也许添加新标签的方法会通过类似于深度优先搜索的过程来完成。最初的数据结构只是一个叶节点：

[
    ["#text", "hello world!"]
]

添加第一个标签会将目前唯一的节点拆分为两个节点，其中一个节点具有标签 "b"。实际上，正在添加一个新元素，并且正在将唯一节点的字符串变成它原来的子字符串：

[
    ["b",
        ["#text", "hello"]
    ],
    ["#text", " world!"]
]

概括这个过程，叶节点包含原文的子串，非叶节点是标签。添加另一个标签时，将执行深度优先搜索，同时还保持到目前为止看到的子字符串的长度总和

当搜索在上述结构中输入"b"时，子串总长度为0。加上该节点的字符串长度("hello")后，子串长度将变为5。因为"i" 的范围重叠 0 - 5 "b" 节点必须临时拆分产生：

[
    ["b",
        ["#text", "h"],
        ["i",
            ["#text", "ello"]
        ]
    ],
    ["#text", " world!"]
]

然而，"i" 标签的深度优先搜索尚未完成，下一个节点（标记为“#text”）仍必须拆分。当前子字符串长度在进入该节点时为 5，在添加该节点的文本（“world！”）后变为 12。 "i" 在 5 - 12 的范围内，这是拆分节点的条件产生：

[
    ["b",
        ["#text", "h"],
        ["i",
            ["#text", "ello"]
        ]
    ],
    ["i",
        ["#text", " "]
    ],
    ["#text", "world!"]
]

请注意，括号与您在问题中发布的略有不同。我认为原来的括号问题（评论中提到）不是最后一个括号

树的偏移量

Offsets to tree

javascript

algorithm

dom

data-structures