Я хотел бы сделать какой-то алгоритм «поиска и замены», который будет, по возможности, эффективным образом идентифицировать подстроку строки, которая встречается более одного раза, и заменять все вхождения этой подстроки токеном.
Например, учитывая строку «AbcAdAefgAbijkAblmnAbAb», обратите внимание, что «A» повторяется, поэтому в первом проходе уменьшите ее до «#1bc#1d#1efg#1bijk#1blmn#1b#1b», где #_ — это индексированный шаблон (обратите внимание на шаблоны в индексированной таблице), затем обратите внимание, что "#1b" повторяется, поэтому уменьшите его до "#2c#1d#1efg#2ijk#2lmn#2#2". В строке больше нет шаблонов, поэтому мы закончили.
Я нашел некоторую информацию о «самых длинных общих подпоследовательностях» и алгоритмах сжатия, но, похоже, ничего подобного. Они предназначены либо для сравнения двух строк, либо для получения какого-то оптимального для хранения результата.
Моя цель, с другой стороны, состоит в том, чтобы свести геном к его «словам», а не к «буквам». т.е. вместо gatcatcgatc я хочу видеть 2c1c2c. После этого я мог бы сделать некоторое регулярное выражение, чтобы найти такие вещи, как «# 42 * # 42»; было бы здорово увидеть повторяющиеся скобки в ДНК.
Если бы я мог просто найти это в Интернете, я бы не стал делать это сам, но я не вижу ответа на этот вопрос раньше в терминах, которые я мог бы раскрыть. Всем, кто может указать мне в правильном направлении, большое спасибо.
