Алгоритм разбиения строк

Question

Я ищу эффективный алгоритм для разбиения строк . По сути, вам предоставляется список строк, скажем BCD, CDE, ABC, A и результирующая строка tiled должна быть ABCDE, потому что BCD выравнивается с CDE, давая BCDE, который затем выравнивается с ABC, получая окончательный ABCDE.

В настоящее время я использую слегка наивный алгоритм, который работает следующим образом. Начиная со случайной пары строк, скажем, BCD и CDE, я использую следующее (на Java):

public static String tile(String first, String second) {
  for (int i = 0; i < first.length() || i < second.length(); i++) {
    // "right" tile (e.g., "BCD" and "CDE")
    String firstTile = first.substring(i);
    // "left" tile (e.g., "CDE" and "BCD")  
    String secondTile = second.substring(i);
    if (second.contains(firstTile)) {
      return first.substring(0, i) + second;
    } else if (first.contains(secondTile)) {
      return second.substring(0, i) + first;
    }
  }
  return EMPTY;
}

System.out.println(tile("CDE", "ABCDEF")); // ABCDEF
System.out.println(tile("BCD", "CDE")); // BCDE
System.out.println(tile("CDE", "ABC")); // ABCDE
System.out.println(tile("ABC", tile("BCX", "XYZ"))); // ABCXYZ

Несмотря на то, что это работает, это не очень эффективно, поскольку оно повторяет одни и те же символы снова и снова.

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

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

Заранее спасибо.

---

Для ситуаций, где есть неоднозначность - например, {ABC, CBA}, которая может привести к ABCBA или CBABC -, любой тайлинг может быть возвращен. Однако такая ситуация встречается редко, потому что я выкладываю слова, например {This is, is me} => {This is me}, которыми манипулируют так, чтобы вышеупомянутый алгоритм работал.

Аналогичный вопрос: Эффективный алгоритм объединения строк с перекрытием

Answer 1

Упорядочить строки по первому символу, затем по длине (от наименьшего к наибольшему), а затем применить адаптацию к KMP, найденную в этом вопросе о конкатенации перекрывающихся строк.

Answer 2

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

Я не думал ни о чем, чтобы улучшить временную сложность разбиения более чем на две строки. В качестве небольшого примечания для нескольких строк, этот алгоритм, приведенный ниже, легко расширяется до проверки мозаики одиночной «левой» строки с несколькими «правыми» строками одновременно, что может помешать дополнительной зацикливанию строк, если вы пытаетесь выясните, нужно ли делать («ABC», «BCX», «XYZ») или («ABC», «XYZ», BCX »), просто испробовав все возможности. Немного.

string Tile(string a, string b)
{
    // Try both orderings of a and b,
    // since TileLeftToRight is not commutative.

    string ab = TileLeftToRight(a, b);

    if (ab != "")
        return ab;

    return TileLeftToRight(b, a);

    // Alternatively you could return whichever
    // of the two results is longest, for cases
    // like ("ABC" "BCABC").
}

string TileLeftToRight(string left, string right)
{
    int i = 0;
    int j = 0;

    while (true)
    {
        if (left[i] != right[j])
        {
            i++;

            if (i >= left.Length)
                return "";
        }
        else
        {
            i++;
            j++;

            if (i >= left.Length)
                return left + right.Substring(j);

            if (j >= right.Length)
                return left;
        }
    }
}

Answer 3

Если открытый исходный код приемлем, то вам следует проверить геном тестов в наборе тестов STAMP Стэнфорда: он в значительной степени соответствует тому, что вы ищете. Начиная с набора строк («генов»), он ищет самую короткую строку, которая включает все гены. Так, например, если у вас есть ATGC и GCAA, он найдет ATGCAA. В алгоритме нет ничего, что ограничивало бы его 4-символьным алфавитом, поэтому он может вам помочь.

Answer 4

Интересная проблема. Вам нужен какой-то возврат. Например, если у вас есть:

ABC, BCD, DBC 

Объединение DBC с BCD приводит к:

ABC, DBCD

Что не решаемо. Но объединение ABC с BCD приводит к:

ABCD, DBC

Который может быть объединен с:

ABCDBC.

Answer 5

Первое, что нужно спросить, хотите ли вы найти обработку {CDB, CDA}? Там нет одного пахать.