Эффективный алгоритм для конкатенации строк с перекрытием

Question

Нам нужно объединить 3 столбца в базе данных путем конкатенации. Тем не менее, три столбца могут содержать перекрывающиеся части, и детали не должны дублироваться. Например,

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

Нашего текущий алгоритм является довольно медленным, поскольку он использует перебор для идентификации перекрывающихся частей между 2 строками. Кто-нибудь знает эффективный алгоритм для этого?

Скажем, у нас есть 2 строки A и B. Алгоритм должен найти самую длинную общую подстроку S, так что А заканчивается 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(); 
} 

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

Answer 2

Почему бы просто не сделать что-то подобное. Сначала получите первый символ или слово (которое будет обозначать перекрытие) в трех столбцах.

Затем начните добавлять первую строку в stringbuffer, по одному символу за раз.

Каждый раз посмотрите, достигли ли вы части, перекрытой второй или третьей строкой.

Если это так, начните конкатенировать строку, которая также содержит то, что находится в первой строке.

Когда все началось, если нет совпадений, начните со второй строки, а затем третьей строки.

Итак, во втором примере в вопросе я буду хранить d и g в двух переменных.

Тогда, как добавить первую строку аЬса приходит из первой строки, то я видеть, что д также во второй строке, так что я перейти к добавлению из второй строки четкости добавляется из строки 2, то я перейдите и закончите строку 3.

Если вы делаете это в базе данных, почему бы просто не использовать хранимую процедуру для этого?

Answer 3

Если вы делаете это за пределами базы данных, попробуйте 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 быстрее ;-)

Answer 4

Вы можете использовать DFA. Например, строка XYZ должна считываться с помощью регулярного выражения ^((A)?B)?C. Это регулярное выражение будет соответствовать самому длинному префиксу, который соответствует суффиксу строки XYZ. С таким регулярным выражением вы можете либо совместить, либо получить результат совпадения, либо создать 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 

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) 

Answer 6

Как насчет (простите 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 одиночных символа), которые в обычном английском тексте должны давать хорошие шансы избежать проверки любых других символов для несоответствий.

Только один раз, когда он устанавливает самое длинное совпадение, которое он может сделать, или что совпадение вообще невозможно, будут объединены две строки. Я использовал простой «+» здесь, потому что я думаю, что оптимизация остальной части алгоритма уже устранила большую часть неэффективности вашего оригинала. Попробуйте и дайте мне знать, достаточно ли это для ваших целей.

Answer 7

Вот решение в 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' 

Answer 8

Я думаю, что это будет довольно быстро:

У вас есть две строки string1 и string2. Посмотрите назад (справа налево) через строку1 для первого символа string2. Когда у вас есть это положение, определите, есть ли перекрытие. Если этого не происходит, вам нужно продолжать поиск. Если вам нужно определить, есть ли возможность для другого матча.

Для этого просто исследуйте более короткую из двух строк для повторения перекрывающихся символов. т.е.: если местоположение совпадения в строке1 оставляет оставшуюся короткую строку1, повторите начальный поиск из новой начальной точки в строке1. И наоборот, если несогласованная часть строки2 короче, найдите ее для повторения перекрывающихся символов.

Повторите при необходимости.

Работа выполнена!

Это не требует многого с точки зрения распределения памяти (все поиски выполняются на месте, просто нужно выделить результирующий буфер строк) и требует (не более) одного прохода одной из перекрывающихся строк.

Answer 9

Я пытаюсь сделать этот 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;    
    } 

EDIT: Я вижу, что это почти то же самое, что и решение jerryjvl.Единственное различие заключается в том, что это будет работать с операцией «abcde», «d».

Answer 10

Эта проблема, как представляется, как изменение самой длинной общей проблемы суб-последовательности, которая может быть решена с помощью динамического программирования.

http://www.algorithmist.com/index.php/Longest_Common_Subsequence

Answer 11

Heres Perl-Псевдо Oneliner:

$ _ = s1.s2;

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

perl regex's довольно эффективен, вы можете посмотреть, какой алгоритм они используют, но они определенно реализуют некоторый тип FSM и т. Д., Поэтому получат u результаты в довольно хорошем O (..).

Answer 12

Вот реализация Java, которая находит максимальное перекрытие между двумя строками с длиной N и M в чем-то вроде операций O (min (N, M)) ~ O (N).

У меня была та же идея, что и @ sepp2k: теперь удалили ответ и немного поработали над этим. Кажется, хорошо работает. Идея состоит в том, чтобы выполнить итерацию первой строки и начать отслеживание, как только вы найдете что-то, что соответствует началу второй строки. Выяснилось, что вам может потребоваться несколько одновременных отслеживаний, если совпадения ложных и истинных совпадений. В конце вы выбираете самый длинный трек.

Я havent разработал абсолютно худший случай, с максимальным совпадением между матчами, но я не ожидаю, что он вырвется из-под контроля, так как я думаю, что вы не можете совместить произвольное множество матчей. Обычно вы отслеживаете только одно или два матча за раз: кандидаты удаляются, как только происходит несоответствие.

static class Candidate { 
    int matchLen = 0; 
} 

private String overlapOnce(@NotNull final String a, @NotNull final String b) { 
    final int maxOverlap = Math.min(a.length(), b.length()); 
    final Collection<Candidate> candidates = new LinkedList<>(); 
    for (int i = a.length() - maxOverlap; i < a.length(); ++i) { 
     if (a.charAt(i) == b.charAt(0)) { 
      candidates.add(new Candidate()); 
     } 
     for (final Iterator<Candidate> it = candidates.iterator(); it.hasNext();) { 
      final Candidate candidate = it.next(); 
      if (a.charAt(i) == b.charAt(candidate.matchLen)) { 
       //advance 
       ++candidate.matchLen; 
      } else { 
       //not matching anymore, remove 
       it.remove(); 
      } 
     } 

    } 
    final int matchLen = candidates.isEmpty() ? 0 : 
      candidates.stream().map(c -> c.matchLen).max(Comparator.comparingInt(l -> l)).get(); 
    return a + b.substring(matchLen); 
} 

private String overlapOnce(@NotNull final String... strings) { 
    return Arrays.stream(strings).reduce("", this::overlapOnce); 
} 

И некоторые тесты:

@Test 
public void testOverlapOnce() throws Exception { 
    assertEquals("", overlapOnce("", "")); 
    assertEquals("ab", overlapOnce("a", "b")); 
    assertEquals("abc", overlapOnce("ab", "bc")); 
    assertEquals("abcdefghqabcdefghi", overlapOnce("abcdefgh", "efghqabcdefghi")); 
    assertEquals("aaaaaabaaaaaa", overlapOnce("aaaaaab", "baaaaaa")); 
    assertEquals("ccc", overlapOnce("ccc", "ccc")); 
    assertEquals("abcabc", overlapOnce("abcabc", "abcabc")); 

    /** 
    * "a" + "b" + "c" => "abc" 
    "abcde" + "defgh" + "ghlmn" => "abcdefghlmn" 
    "abcdede" + "dedefgh" + "" => "abcdedefgh" 
    "abcde" + "d" + "ghlmn" => "abcdedghlmn" 
    "abcdef" + "" + "defghl" => "abcdefghl" 
    */ 
    assertEquals("abc", overlapOnce("a", "b", "c")); 
    assertEquals("abcdefghlmn", overlapOnce("abcde", "defgh", "ghlmn")); 
    assertEquals("abcdedefgh", overlapOnce("abcdede", "dedefgh")); 
    assertEquals("abcdedghlmn", overlapOnce("abcde", "d", "ghlmn")); 
    assertEquals("abcdefghl", overlapOnce("abcdef", "", "defghl")); 


    // Consider str1=abXabXabXac and str2=XabXac. Your approach will output abXabXabXacXabXac because by 
    // resetting j=0, it goes to far back. 
    assertEquals("abXabXabXac", overlapOnce("abXabXabXac", "XabXac")); 

    // Try to trick algo with an earlier false match overlapping with the real match 
    // - match first "aba" and miss that the last "a" is the start of the 
    // real match 
    assertEquals("ababa--", overlapOnce("ababa", "aba--")); 
}