Строковые повторяющиеся подпоследовательности и сжатие - PullRequest
Новая
       3

Строковые повторяющиеся подпоследовательности и сжатие

1 голос
/ 29 июня 2010

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

Например, если задана строка «AbcAdAefgAbijkAblmnAbAb», обратите внимание, что «A» повторяется, поэтому уменьшите на первом проходе «# 1bc # 1d # 1efg # 1bijk # 1blmn # 1b # 1b», где #_ - индексированный шаблон ( мы отмечаем шаблоны в индексированной таблице), затем замечаем, что «# 1b» повторяется, поэтому уменьшаем до «# 2c # 1d # 1efg # 2ijk # 2lmn # 2 # 2». В строке больше нет шаблонов, поэтому мы закончили.

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

Моя цель, с другой стороны, сводить геном к его «словам» вместо «букв». т.е. вместо gatcatcgatc я хочу видеть 2c1c2c. После этого я мог бы сделать регулярное выражение, чтобы найти такие вещи, как "# 42 * # 42"; было бы здорово увидеть повторяющиеся скобки в днк.

Если бы я мог просто найти это онлайн, я бы пропустил это сам, но я не вижу ответа на этот вопрос раньше в терминах, которые я мог бы раскрыть. Всем, кто может указать мне правильное направление, большое спасибо.

1 Ответ

1 голос
/ 18 июня 2011

Кодировка пары байтов делает что-то очень похожее на то, что вы хотите. Вместо того, чтобы искать непосредственно самую длинную повторяемую строку (сверху вниз), каждый проход кодирования пары байтов ищет повторяющиеся пары байтов (снизу вверх). Но в конце концов он обнаруживает самую длинную повторяющуюся строку (*).

  • gatcatcgatc
  • 1 = при g1c1cg1c
  • 2 = atc g22g2
  • 3 = GATC 2 = ATC 323

Как видите, он нашел самую длинную повторяющуюся строку "gatc".

(*) кодирование пары байтов либо в конечном итоге находит самую длинную повторяющуюся строку, или же он останавливается рано после выполнения (2 ^ 8 - uniquechars (источник)) замен. Я подозреваю, что может быть возможно настроить кодирование пары байтов так, чтобы условие раннего останова было немного смягчено - возможно (2 ^ 9 - uniquechars (источник)) или 2 ^ 12 или 2 ^ 16. Даже если это ухудшит производительность сжатия, возможно, оно даст интересные результаты для таких приложений, как ваше.

...