如何将字符串分解为具有多个重叠的较小字符串

How to break up a string into smaller strings with multiple overlaps?

本文关键字：字符串 重叠 分解      更新时间：2023-09-26

我有一大块文本，需要以给定的偏移量+长度突出显示。

提供的字符串为：

By Lesley Wroughton WASHINGTON Feb 25 (Reuters) - As scientists warn that climate change will lead to stronger storms the World Bank is launching on Monday the first disaster insurance plan to offer emergency money to 18 Caribbean countries immediately after they are hit by hurricanes or earthquakes.

我提供的ranges是：

var ranges = [
  {offset: 53, length: 10, highlightClass: 'a'},
  {offset: 74, length: 14, highlightClass: 'b'},
  {offset: 10, length: 20, highlightClass: 'a'},
  {offset: 20, length: 14, highlightClass: 'b'},
  {offset: 24, length: 3, highlightClass: 'c'},
  {offset: 28, length: 2, highlightClass: 'd'},
];

在继续之前，我将根据它们的偏移量对提供的范围进行排序，因此上面会产生：

var ranges = [
  {offset: 10, length: 20, highlightClass: 'a'},
  {offset: 20, length: 14, highlightClass: 'b'},
  {offset: 24, length: 3, highlightClass: 'c'},
  {offset: 28, length: 2, highlightClass: 'd'},
  {offset: 53, length: 10, highlightClass: 'a'},
  {offset: 74, length: 14, highlightClass: 'b'},
];

我需要做的是用它们适当的类名来突出显示这里的各种范围（例如，一段文本被两个类a和b重叠，而字符串将应用两个类）。到目前为止，如果一个单词上只有一个重叠，那么我所做的工作非常好，但如果有多个重叠，就像本例中的单词WASHINGTON一样，我的代码会崩溃，因为我只检查"下一个范围"，而不是试着查看所有可用的范围以及它们是否与我现有的范围重叠。

我通过简单地查看下一个范围是否与当前范围重叠来进行检查，如果重叠，我会创建一个新范围，并将其推到下一个之前，修改当前范围的长度和下一个的偏移量。

有没有更好的方法将字符串分解为多个范围，以容纳所有可能重叠的范围？

用良好的嵌套生成必要标记的一种暴力方法是：

  1. 计算并存储每个范围的结束位置（在您的情况下为offset+length）
  2. 按范围的起始位置对其进行排序（正如您所做的）
  3. 创建一个数组（我们称之为character_classes），数组中的空数组数量与文本中的字符数量一样多。
    • 注意：我们将使用外部数组作为列表，使用内部数组作为堆栈。在JavaScript中，数组是两者都适合的数据结构，但如果您愿意，可以随意选择其他合适的类型
    • character_classes中的每个堆栈将跟踪适用于文本中相应字符的所有类（该字符在文本中的位置与该堆栈在character_classes中的位置相同）。当从头到尾阅读文本时，它将按照应用的顺序使用这些类
  4. 在您的范围内循环：
    • 将每个范围推送到character_classes中与该范围的起始位置或之后的任何字符相对应的堆栈中
  5. 新建空字符串result

  6. 循环文本中的字符：

    对于每个字符（以及最后一个字符之后的位置）

    • 从与字符相对应的堆栈中弹出范围，直到所有到此为止的范围（参见步骤1的计算结果）都已删除

      同时：

      • 记住没有结束的所有弹出范围，包括它们的顺序
      • 对于弹出的每个范围（无论是否结束），将结束相应类的标记附加到result，按弹出相应范围的顺序

    • 将记住的范围（而非结束于此的范围）按弹出的相反顺序推回堆栈。（因此，它们以原始顺序结束，只是没有在此结束的那些。）

      同时：

      • 按照将范围推送到堆栈上的顺序，将开始对应类的标记附加到result
    • 将文本中的字符附加到result
    • 从以下所有字符的堆栈中删除在此结束的范围，使堆栈中的其他范围保持当前顺序

完成后，result应该包含正确标记的文本。

相关文章：