Подтвердить что ты не робот

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

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

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

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

Скажем, у нас есть 2 строки 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();
}
4b9b3361

ОТВЕТЫ

Ответ 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

Ответ 2

Вы можете использовать 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

Ответ 3

Как насчет (простите С#):

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

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

Ответ 4

Вот решение в Python. Это должно быть быстрее, просто не нужно постоянно создавать подстроки в памяти. Работа выполняется в функции _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'

Ответ 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)

Ответ 6

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

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

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

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

Задание выполнено!

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

Ответ 7

Я пытаюсь сделать этот С# максимально приятным для чтения.

    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".

Ответ 8

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

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

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

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

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

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

Затем, когда я добавляю первую строку abc исходит из первой строки, тогда я вижу, что d также во второй строке, поэтому я перехожу к добавлению из второй строки def добавляются из строки 2, затем я перемещаюсь и заканчиваю строкой 3.

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

Ответ 9

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

Ответ 10

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

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

Ответ 11

Вот что такое: perl-pseudo oneliner:

$_ = s1.s2;

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

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

Ответ 12

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

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

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

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--"));
}