Алгоритм для поиска наиболее повторяющейся (не самой общей) последовательности в строке (так называемые тандемные повторы)
Я ищу алгоритм (возможно, реализованный в Python), способный найти наиболее повторяющуюся последовательность в строке. Что касается REPETITIVE, я имею в виду любую комбинацию символов, которая повторяется снова и снова без перерыва (тандемное повторение).
Алгоритм, который я ищу, отличается от алгоритма "найди самое распространенное слово". Фактически, повторяющийся блок не должен быть самым распространенным словом (подстрокой) в строке.
Например:
s = 'asdfewfUBAUBAUBAUBAUBAasdkBAjnfBAenBAcs'
> f(s)
'UBAUBAUBAUBAUBA' #the "most common word" algo would return 'BA'
К сожалению, я не знаю, как с этим справиться. Любая помощь очень приветствуется.
ОБНОВИТЬ
Небольшой дополнительный пример, чтобы уточнить, что я хочу, чтобы мне возвращали последовательность с наибольшим количеством повторений, независимо от того, какой у нее базовый строительный блок.
g = 'some noisy spacer'
s = g + 'AB'*5 + g + '_ABCDEF'*2 + g + 'AB'*3
> f(s)
'ABABABABAB' #the one with the most repetitions, not the max len
Примеры от @rici:
s = 'aaabcabc'
> f(s)
'abcabc'
s = 'ababcababc'
> f(s)
'ababcababc' #'abab' would also be a solution here
# since it is repeated 2 times in a row as 'ababcababc'.
# The proper algorithm would return both solutions.
Ответы
Ответ 1
Вот решение, основанное на регулярном выражении ((\w+?)\2+)
, но с дополнительными улучшениями:
import re
from itertools import chain
def repetitive(sequence, rep_min_len=1):
"""Find the most repetitive sequence in a string.
:param str sequence: string for search
:param int rep_min_len: minimal length of repetitive substring
:return the most repetitive substring or None
"""
greedy, non_greedy = re.compile(r'((\w+)\2+)'), re.compile(r'((\w+?)\2+)')
all_rep_seach = lambda regex: \
(regex.search(sequence[shift:]) for shift in range(len(sequence)))
searched = list(
res.groups()
for res in chain(all_rep_seach(greedy), all_rep_seach(non_greedy))
if res)
if not sequence:
return None
cmp_key = lambda res: res[0].count(res[1]) if len(res[1]) >= rep_min_len else 0
return max(searched, key=cmp_key)[0]
Вы можете проверить его так:
def check(seq, expected, rep_min_len=1):
result = repetitive(seq, rep_min_len)
print('%s => %s' % (seq, result))
assert result == expected, expected
check('asdfewfUBAUBAUBAUBAUBAasdkBAjnfBAenBAcs', 'UBAUBAUBAUBAUBA')
check('some noisy spacerABABABABABsome noisy spacer_ABCDEF_ABCDEFsome noisy spacerABABAB', 'ABABABABAB')
check('aaabcabc', 'aaa')
check('aaabcabc', 'abcabc', rep_min_len=2)
check('ababcababc', 'ababcababc')
check('ababcababcababc', 'ababcababcababc')
Основные возможности:
- используется жадное
((\w+)\2+)
и неживое ((\w+)\2+?)
regex;
- поиск повторяющейся подстроки во всех подстроках со сдвигом от начала (например,'string '= > [' string ',' tring ',' ring ',' ing ',' ng ',' g ']);
- выбор основан на количестве повторений не на длине подпоследовательности (например, для результата "ABABABAB_ABCDEF_ABCDEF" будет "ABABABAB", а не "_ABCDEF_ABCDEF" );
- минимальная длина повторяющейся последовательности имеет значение (см. "aaabcabc" check).
Ответ 2
С комбинацией re.findall()
(с использованием специальных функций regex patten) и max()
:
import re
# extended sample string
s = 'asdfewfUBAUBAUBAUBAUBAasdkjnfencsADADADAD sometext'
def find_longest_rep(s):
result = max(re.findall(r'((\w+?)\2+)', s), key=lambda t: len(t[0]))
return result[0]
print(find_longest_rep(s))
Выход:
UBAUBAUBAUBAUBA
Важнейший шаблон:
-
((\w+?)\2+)
:
-
(....)
- самая удаленная захваченная группа, которая является первой захваченной группой.
-
(\w+?)
- любая последовательность символов без пробелов, заключенная во вторую захваченную группу; +?
- квантификатор, совпадающий между одним и неограниченным временем, как можно меньше, расширяя по мере необходимости
-
\2+
- совпадает с тем же самым текстом, который был недавно согласован второй группой захвата
Ответ 3
То, что вы ищете, - это алгоритм поиска "наибольшего" примитивного тандемного повтора в строке. Вот статья, описывающая линейный алгоритм времени, чтобы найти все тандемные повторы в строке и, наконец, все примитивные тандемные повторы. Гусфилд. Алгоритмы линейного времени для поиска и представления всех тандемных повторений в строке
Ответ 4
Вот алгоритм перебора, который я написал. Может быть, это будет полезно:
def find_most_repetitive_substring(string):
max_counter = 1
position, substring_length, times = 0, 0, 0
for i in range(len(string)):
for j in range(len(string) - i):
counter = 1
if j == 0:
continue
while True:
if string[i + counter * j: i + (counter + 1) * j] != string[i: i + j] or i + (counter + 1) * j > len(string):
if counter > max_counter:
max_counter = counter
position, substring_length, times = i, j, counter
break
else:
counter += 1
return string[position: position + substring_length * times]