高效的字符串重叠拼接算法

Question

我们需要通过连接将数据库中的3列组合起来。但是这3列可能包含重叠部分，这些部分不应重复。例如：

  "a" + "b" + "c" => "abc"
  "abcde" + "defgh" + "ghlmn" => "abcdefghlmn"
  "abcdede" + "dedefgh" + "" => "abcdedefgh"
  "abcde" + "d" + "ghlmn" => "abcdedghlmn"
  "abcdef" + "" + "defghl" => "abcdefghl"

我们目前的算法使用暴力方法来确定两个字符串之间的重叠部分，因此速度较慢。有没有人知道一种高效的算法来解决这个问题？

假设我们有两个字符串A和B。该算法需要找到最长的公共子串S，以便A以S结尾，B以S开头。

我们目前在Java中的暴力实现附在此供参考，

public static String concat(String s1, String s2) {
    if (s1 == null)
        return s2;
    if (s2 == null)
        return s1;
    int len = Math.min(s1.length(), s2.length());

    // Find the index for the end of overlapping part
    int index = -1;
    for (int i = len; i > 0; i--) {
        String substring = s2.substring(0, i);
        if (s1.endsWith(substring)) {
            index = i;
            break;
        }
    }
    StringBuilder sb = new StringBuilder(s1);
    if (index < 0) 
        sb.append(s2);
    else if (index <= s2.length())
        sb.append(s2.substring(index));
    return sb.toString();
}

- ZZ Coder

---

字符串的平均长度是多少？ - RBarryYoung

只有中间的字符串很长，平均约100个字符。前缀和后缀只有约20个字符，这并不重要。数据库转换只会发生一次。它将需要几天时间，但在最坏的情况下，只需花费几个小时来连接字符串。我正在尝试找到最优解，只是为了好玩和挑战。我想我找到了。谢谢！ - ZZ Coder

Answer 1

大多数其他答案都集中在常数因子优化上，但也有可能做到渐进更好。看看你的算法：它是O(N^2)。这似乎是一个可以比这快得多解决的问题！

考虑Knuth Morris Pratt。它跟踪我们到目前为止匹配的最大子字符串量。这意味着它知道已经匹配了S1的多少在S2的末尾，这就是我们要找的值！只需修改算法以在早期匹配子字符串时继续而不是返回，并使其在结尾返回匹配的数量而不是0。

这给您提供了一个O(n)算法。不错！

    int OverlappedStringLength(string s1, string s2) {
        //Trim s1 so it isn't longer than s2
        if (s1.Length > s2.Length) s1 = s1.Substring(s1.Length - s2.Length);

        int[] T = ComputeBackTrackTable(s2); //O(n)

        int m = 0;
        int i = 0;
        while (m + i < s1.Length) {
            if (s2[i] == s1[m + i]) {
                i += 1;
                //<-- removed the return case here, because |s1| <= |s2|
            } else {
                m += i - T[i];
                if (i > 0) i = T[i];
            }
        }

        return i; //<-- changed the return here to return characters matched
    }

    int[] ComputeBackTrackTable(string s) {
        var T = new int[s.Length];
        int cnd = 0;
        T[0] = -1;
        T[1] = 0;
        int pos = 2;
        while (pos < s.Length) {
            if (s[pos - 1] == s[cnd]) {
                T[pos] = cnd + 1;
                pos += 1;
                cnd += 1;
            } else if (cnd > 0) {
                cnd = T[cnd];
            } else {
                T[pos] = 0;
                pos += 1;
            }
        }

        return T;
    }

OverlappedStringLength("abcdef", "defghl") 返回 3

- Craig Gidney

---

对于我实现的代码，使用一百万个随机生成的字符串（来自字母表a-z，长度为8-23，对于两种实现使用相同的字符串集合）进行测试，你的代码运行时间是我的两倍。实际上哪种实现更好将取决于要连接的实际字符串中重叠的性质，因此像往常一样... ZZ Coder需要在自己的数据集上进行测试，以确定哪种方法实际上最好。 - jerryjvl

即使如此，+1 用了 Knuth ;) - jerryjvl

是的，这个实现看起来有很多常数时间。如果字符串的大小与 OP 中的相同，可能不值得。必须进行性能分析。 - FogleBird

我同意对于小的随机字符串，您的搜索速度会更快。实际上，如果输入是随机的，您可以通过逐步过滤可能的起始位置来检查越来越多的字符，从而实现预期的线性时间算法。但是依赖输入进行任何操作都是一个坏主意。如果您得到长字符串、重复字符串、只有0和1的字符串等，该怎么办？您的算法性能依赖于相当随机的输入，这在实践中可能适用或不适用（或将来可能不再适用）。例如，英文字符频率会稍微影响您的性能。 - Craig Gidney

我并不打算让我的测量或反驳变得普遍化；请记住，我们对 ZZ Coder 实际运行算法的数据知之甚少；在没有更多类似信息的情况下，我们无法说出哪种实现方式最好。正如我所说...他需要使用他的实际真实字符串进行测量，以便做出明智的决定。 - jerryjvl

我的目标是找到O(n)的解决方案，我认为这就是它。谢谢！ - ZZ Coder

Answer 2

您可以使用DFA。例如，字符串XYZ应该由正则表达式^((A)?B)?C读取。该正则表达式将匹配与字符串XYZ的后缀匹配的最长前缀。通过这样的正则表达式，您可以匹配并获得匹配结果，或生成一个DFA，该DFA可以使用状态指示“切割”的正确位置。

在Scala中，第一种实现方式--直接使用正则表达式--可能如下所示：

def toRegex(s1: String) = "^" + s1.map(_.toString).reduceLeft((a, b) => "("+a+")?"+b) r
def concatWithoutMatch(s1 : String, s2: String) = {
  val regex = toRegex(s1)
  val prefix = regex findFirstIn s2 getOrElse ""
  s1 + s2.drop(prefix length)
}

例如：

scala> concatWithoutMatch("abXabXabXac", "XabXacd")
res9: java.lang.String = abXabXabXacd

scala> concatWithoutMatch("abc", "def")
res10: java.lang.String = abcdef

scala> concatWithoutMatch(concatWithoutMatch("abcde", "defgh"), "ghlmn")
res11: java.lang.String = abcdefghlmn

- Daniel C. Sobral

---

不错 :) ... 但是，它错过了我实现中的（可能显著的）优化，即基于所考虑的重叠部分的第一个和最后一个字符丢弃大多数典型的不匹配。 - jerryjvl

不完全是这样。考虑我们正在与第二个字符串进行匹配。对于该第二个字符串的每个字符，匹配可以完成或不完成。一旦找到第一个不匹配的字符，您就知道最大可能的匹配是什么。这样做*永远不必比较一个字符多次。现在，创建和编译正则表达式的开销可能过高。 - Daniel C. Sobral

我可能漏掉了什么，但尽管它从未比较过's1'中的字符超过一次，但它可能不得不在's2'中检查相同的字符两次，对吧？例如，在您的第一个示例中，其中's1'包含'XabXabXac'？它将不得不至少两次检查's2'的前三个字符。 - jerryjvl

将NFA转换为DFA可能会导致状态呈指数级增长。你只是将复杂性从暴力扫描转移到了构建DFA状态上。 - Barry Kelly

是的，如果使用循环和替代，它可能导致状态呈指数增长。该正则表达式的状态数等于第一个字符串的大小加上初始状态和非接受终端状态。 - Daniel C. Sobral

@jerryjvl：不，我不会这样做。这就是为什么正则表达式如此受欢迎的原因。 - Daniel C. Sobral

Answer 3

以下是Python的解决方案。它应该更快，因为不需要一直在内存中构建子字符串。_concat函数完成了工作，它连接两个字符串。concat函数是一个帮助器，可以连接任意数量的字符串。

def concat(*args):
    result = ''
    for arg in args:
        result = _concat(result, arg)
    return result

def _concat(a, b):
    la = len(a)
    lb = len(b)
    for i in range(la):
        j = i
        k = 0
        while j < la and k < lb and a[j] == b[k]:
            j += 1
            k += 1
        if j == la:
            n = k
            break
    else:
        n = 0
    return a + b[n:]

if __name__ == '__main__':
    assert concat('a', 'b', 'c') == 'abc'
    assert concat('abcde', 'defgh', 'ghlmn') == 'abcdefghlmn'
    assert concat('abcdede', 'dedefgh', '') == 'abcdedefgh'
    assert concat('abcde', 'd', 'ghlmn') == 'abcdedghlmn'
    assert concat('abcdef', '', 'defghl') == 'abcdefghl'

- FogleBird

---

你是指这个：def _concat(a, b): la = len(a) for i in range(la): if a[i:] == b[:la-i]: return a + b[la-i:] return a + b def _concat(a, b): la = len(a) for i in range(la): if a[i:] == b[:la-i]: return a + b[la-i:] return a + b - hughdbrown

或者运行以下代码：print "\ndef _concat(a, b):\n\tla = len(a)\n\tfor i in range(la):\n\t\tif a[i:] == b[:la-i]:\n\t\t\treturn a + b[la-i:]\n\treturn a + b\n".replace(r'\n', '\n').replace(r'\t', '\t') - hughdbrown

是的，但那还不错吧？你运行它，它就会自动格式化。 - hughdbrown

无论如何，你的版本会创建子字符串，这可能需要更多时间。但由于很多操作都在 C 语言层面进行，所以它可能仍然运行得更快，我还没有检查过。但是当转移到 C# 时可能不会出现相同的情况。 - FogleBird

我这么做是为了清晰明了，而不是为了速度。_concat的主体代码：5行对比14行。 - hughdbrown

Answer 4

换句话说（抱歉使用C#）：

public static string OverlapConcat(string s1, string s2)
{
    // Handle nulls... never return a null
    if (string.IsNullOrEmpty(s1))
    {
        if (string.IsNullOrEmpty(s2))
            return string.Empty;
        else
            return s2;
    }
    if (string.IsNullOrEmpty(s2))
        return s1;

    // Checks above guarantee both strings have at least one character
    int len1 = s1.Length - 1;
    char last1 = s1[len1];
    char first2 = s2[0];

    // Find the first potential match, bounded by the length of s1
    int indexOfLast2 = s2.LastIndexOf(last1, Math.Min(len1, s2.Length - 1));
    while (indexOfLast2 != -1)
    {
        if (s1[len1 - indexOfLast2] == first2)
        {
            // After the quick check, do a full check
            int ix = indexOfLast2;
            while ((ix != -1) && (s1[len1 - indexOfLast2 + ix] == s2[ix]))
                ix--;
            if (ix == -1)
                return s1 + s2.Substring(indexOfLast2 + 1);
        }

        // Search for the next possible match
        indexOfLast2 = s2.LastIndexOf(last1, indexOfLast2 - 1);
    }

    // No match found, so concatenate the full strings
    return s1 + s2;
}

这个实现在确定需要复制的内容前不会进行任何字符串复制（部分或完整），这应该会很有助于性能。

另外，匹配检查首先测试潜在匹配区域的极端位置（2个单字符），在正常的英文文本中应该有很好的避免检查其他字符是否不匹配的机会。

只有在确立了它可以做出最长匹配或者根本无法匹配时，两个字符串才会被连接起来。我在这里使用了简单的 '+'，因为我认为算法的其余优化已经消除了原始代码中大部分的低效之处。试一试并让我知道它是否足够满足你的需求。

- jerryjvl

---

还要注意，由于“LastIndexOf”的存在，它甚至不考虑所有可能的重叠偏移量，只考虑可能匹配的那些偏移量，这意味着它可以比while循环的O(n)迭代次数少得多。 - jerryjvl

我认为使用内置函数（如LastIndexOf）并假设实现是超级高效的总是很危险的。重新编写代码，使其适用于任何语言（考虑到问题是与语言无关的），这意味着在实现中不使用String.LastIndexOf，这样做是值得的。话虽如此，该算法的基本前提看起来是可靠的。 - Phil

我希望答案保持相对简短 ;) ... 实现一个“LastIndexOf”，在这个实现中可以做出的假设前提下进行有效的字符扫描，应该不会很复杂（它不需要对第二个参数进行任何边界检查）。 - jerryjvl

还要注意，如果需要进一步提高性能，则通过反复使用“LastIndexOf”执行的对s2的字符扫描可能不是最优的，特别是当s2显着长于s1时，可以基于s1和s2的相对长度进行特殊处理；相反的版本显然需要使用“IndexOf”，等等。...这超出了问题的范围。 - jerryjvl

再思考一下...可以将单字符检查折叠到比较循环中，通过在相反方向迭代“ix”来快速消除不匹配。 - jerryjvl

Answer 5

或者您可以使用以下存储函数在mysql中完成：

DELIMITER //

DROP FUNCTION IF EXISTS concat_with_overlap //

CREATE FUNCTION concat_with_overlap(a VARCHAR(100), b VARCHAR(100))
  RETURNS VARCHAR(200) DETERMINISTIC
BEGIN 
  DECLARE i INT;
  DECLARE al INT;
  DECLARE bl INT;
  SET al = LENGTH(a);
  SET bl = LENGTH(a);
  IF al=0 THEN 
    RETURN b;
  END IF;
  IF bl=0 THEN 
    RETURN a;
  END IF;
  IF al < bl THEN
     SET i = al;
  ELSE
     SET i = bl;
  END IF;

  search: WHILE i > 0 DO
     IF RIGHT(a,i) = LEFT(b,i) THEN
    RETURN CONCAT(a, SUBSTR(b,i+1));
     END IF;
     SET i = i - 1;
  END WHILE search;

  RETURN CONCAT(a,b);
END//

我用了你的测试数据试了一下：

mysql> select a,b,c,
    -> concat_with_overlap( concat_with_overlap( a, b ), c ) as result 
    -> from testing //
+-------------+---------+--------+-------------+
| a           | b       | c      | result      |
+-------------+---------+--------+-------------+
| a           | b       | c      | abc         |
| abcde       | defgh   | ghlmn  | abcdefghlmn |
| abcdede     | dedefgh |        | abcdedefgh  |
| abcde       | d       | ghlmn  | abcdedghlmn |
| abcdef      |         | defghl | abcdefghl   |
| abXabXabXac | XabXac  |        | abXabXabXac |
+-------------+---------+--------+-------------+
6 rows in set (0.00 sec)

- bjelli

---

这是一个非常有趣的东西。如果我们使用同一个数据库，我肯定会使用它。但由于我们正在从Sybase转移到MySQL，所以不能使用了。 - ZZ Coder

所以，你到达后在MySQL中完成它吧;-) - bjelli

我们的新模式只有合并列。我必须创建一些临时列来完成这个操作。在MySQL中删除列需要很长时间（数天），因为数据库相当大，所以我们尽量避免这样做。 - ZZ Coder

Answer 6

我正在尝试让这个C#代码尽可能易读。

    public static string Concatenate(string s1, string s2)
    {
        if (string.IsNullOrEmpty(s1)) return s2;
        if (string.IsNullOrEmpty(s2)) return s1;
        if (s1.Contains(s2)) return s1;
        if (s2.Contains(s1)) return s2;

        char endChar = s1.ToCharArray().Last();
        char startChar = s2.ToCharArray().First();

        int s1FirstIndexOfStartChar = s1.IndexOf(startChar);
        int overlapLength = s1.Length - s1FirstIndexOfStartChar;

        while (overlapLength >= 0 && s1FirstIndexOfStartChar >=0)
        {
            if (CheckOverlap(s1, s2, overlapLength))
            {
                return s1 + s2.Substring(overlapLength);
            }

            s1FirstIndexOfStartChar = 
                s1.IndexOf(startChar, s1FirstIndexOfStartChar);
            overlapLength = s1.Length - s1FirstIndexOfStartChar;

        }

        return s1 + s2;
    }

    private static bool CheckOverlap(string s1, string s2, int overlapLength)
    {
        if (overlapLength <= 0)
            return false;

        if (s1.Substring(s1.Length - overlapLength) == 
            s2.Substring(0, overlapLength))
            return true;

        return false;            
    }

编辑：我看到这个解决方案与jerryjvl的解决方案几乎相同。唯一的区别是，这将适用于“abcde”，“d”情况。

- Kirk Broadhurst

---

这仍然会为CheckOverlap创建字符串副本，我建议至少使用原地比较循环重新实现此辅助方法。 - jerryjvl

我不确定我理解你的“唯一的区别是…”，我的算法为原始问题中的那个例子给出了正确的结果。 - jerryjvl

Answer 7

我认为这个问题很简单：

你有两个字符串，string1和string2。从右到左遍历string1，找到string2的第一个字符。一旦找到位置，确定是否存在重叠。如果没有，你需要继续搜索。如果有，你需要确定是否还有可能出现其他匹配。

为了做到这一点，只需在两个字符串中较短的那个字符串中探索重叠字符的重复。例如：如果在string1中的匹配位置留下了一个较短的string1，则从string1的新起始点重新开始搜索。相反，如果未匹配的string2部分较短，则在其中搜索重叠字符的重复。

根据需要重复此过程。

任务完成！

这不需要太多的内存分配（所有搜索都在原地完成，只需要分配结果字符串缓冲区），并且只需要（最多）对被重叠的字符串之一进行一次遍历。

- Phil

---

那么，这里有一些作业要交给你。实现这两个算法，对同一组几百万个随机生成的字符串运行它们，并测量每个算法的相对性能。 - Phil

好的...在尝试实现你的算法时：一旦找到初始重叠部分，匹配循环部分将需要同时查找string1和string2中的重叠部分...只有当它在两个字符串中都出现时才能找到更长的匹配。(此外，你的解决方案没有使用快速排除可能不匹配的简便方法)...我仍然很乐意进行基准测试，但你必须对如何高效处理“寻找更长匹配”的部分给出更明确的说明。 - jerryjvl

不太对。如果string2不是自相似的，那么您也不需要继续搜索字符串。如果它是自相似的，那么您就可以得到自相似性的长度，因此可以进行一次非常直接的比较以进行匹配 - 根本不需要搜索。在单个字符重叠（在这种情况下不要寻找自相似性）等方面可能存在优化。您似乎很聪明，你会想出来的。附注：在原始问题的上下文中还有一些全局优化可应用。例如：传递输出流。String op+很差。 - Phil

我们从右到左进行，假设重叠部分很小，并且自相似性不太可能存在于许多string2中。 - Phil

实际上（从左到右工作），“g”将匹配，“a”不会匹配，“g”将匹配，然后“gag”将匹配。在string2中没有自相似性意味着我们完成了。 - Phil

Answer 8

如果您是在数据库外进行编程，请尝试使用 Perl：

sub concat {
  my($x,$y) = @_;

  return $x if $y eq '';
  return $y if $x eq '';

  my($i) = length($x) < length($y) ?  length($x) : length($y);
  while($i > 0) {
      if( substr($x,-$i) eq substr($y,0,$i) )  {
          return $x . substr($y,$i);
      }
      $i--;
  }
  return $x . $y;
}

这些算法和你的完全一样，我只是好奇 Java 还是 Perl 更快 ;-)

- bjelli

Answer 9

这是一个 Perl 伪单行程序： $_ = s1.s2;

s/([\S]+)\1/\1/;

Perl 正则表达式非常高效，你可以查找它们使用的算法，但它们肯定实现了某种类型的 FSM 等，因此可以在相当不错的 O(..) 时间复杂度内得到结果。

- monis rahman

Answer 10

为什么不这样做呢？首先获取三列中的第一个字符或单词（它将表示重叠）。

然后，开始将第一个字符串逐个字符地添加到字符串缓冲区中。

每次查看是否已经到达与第二个或第三个字符串重叠的部分。

如果是，则开始连接也包含第一个字符串内容的字符串。

完成后，如果没有重叠，则从第二个字符串开始，然后是第三个字符串。

因此，在问题的第二个示例中，我将保留d和g在两个变量中。

然后，当我添加第一个字符串abc时，我发现d也在第二个字符串中，所以我转而从第二个字符串添加def，最后再添加第三个字符串。

如果您正在数据库中执行此操作，为什么不使用存储过程来执行此操作呢？

- James Black

---

我们的数据库管理员已经决定这个操作过于复杂，不能在存储过程中完成。此外，我们正在从Sybase迁移到MySQL。因此，这将由批处理作业完成，并可以使用任何语言编写。 - ZZ Coder