Учитывая строку, я хотел бы обнаружить повторяющиеся подстроки, а затем уменьшить абаб до (аб)2.
Например, абабабакдекдеабабаб уменьшится до (ab)4a(cde)3(ab)3. Строка не содержит один и тот же символ дважды подряд. Итак, аааб — недопустимая строка.
Вот Python, который я написал:
def superscript(n):
return "".join(["⁰¹²³⁴⁵⁶⁷⁸⁹"[ord(c)-ord('0')] for c in str(n)])
signature = 'hdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfb'
d = {}
processed = []
for k in range(2, len(signature)):
i = 0
j = i + k
while j <= len(signature):
repeat_count = 0
while signature[i:i+k] == signature[j:j+k]:
repeat_count += 1
j += k
if repeat_count > 0 and i not in processed:
d[i] = [i+k, repeat_count + 1]
for j in range(i, (i+k)*repeat_count + 1):
processed.append(j)
i = j
j = i + k
else:
i += 1
j = i + k
od = collections.OrderedDict(sorted(d.items()))
output = ''
for k,v in od.items():
print(k, v)
output += '(' + signature[k:v[0]] + ')' + superscript(v[1])
Который направлен на обнаружение повторяющихся подстрок длины 2, 3, 4 и т. д. Я отмечаю начало и конец повторяющейся подстроки с помощью dict
. Я также помечаю индекс обработанных символов, сохраняя список, чтобы избежать замены (аб)4 на (абаб)2 (поскольку последний перезапишет начальный индекс в dict).
Строка примера, с которой я работаю, — это hdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfb, которая должна выводить (hd)4(cg)4c(bf)4b(ae)4a(dh)4d(cg)4c(bf)4b(ae)4a(dh)4d(cg)4c( бф)4b(ae)4a(dh)4d(cg)4cbfb.
Тем не менее, я получаю этот вывод: (hd)4(dcgcgcgcgcbfbfbfbfbaeaeaeaeaadhdhdhdh)5(cg)4(ea)2(dh)4(hd)2(cg)4
Я не знаю, является ли это известной проблемой, но я не смог найти никаких ресурсов. Меня не смущает временная сложность алгоритма. Где я сделал ошибку?
Алгоритм, который я пытаюсь описать, выглядит так:
Сначала найдите повторяющиеся подстроки длины 2, затем 3, затем 4, ..., вплоть до длины входной строки.
Затем проделайте ту же операцию до тех пор, пока повторений не будет вообще.
Пошаговый пример выглядит так:
abcabcefefefghabcdabcdefefefghabcabcefefefghabcdabcdefefefgh
abcabc(ef)²ghabcdabcd(ef)²ghabcabc(ef)²ghabcdabcd(ef)²gh
(abc)³(ef)²ghabcdabcd(ef)²gh(abc)³(ef)²ghabcdabcd(ef)²gh
(abc)³(ef)²gh(abcd)²(ef)²gh(abc)³(ef)²gh(abcd)²(ef)²gh
((abc)³(ef)²gh(abcd)²(ef)²gh)²
Вы можете использовать re.sub
для соответствия любым повторяющимся двум символам, а затем передать функцию замены, которая форматирует желаемый шаблон.
import re
def superscript(n):
return "".join(["⁰¹²³⁴⁵⁶⁷⁸⁹"[ord(c)-ord('0')] for c in str(n)])
s = 'hdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfbfbfbfbaeaeaeaeadhdhdhdhdcgcgcgcgcbfb'
max_length = 5
result = re.sub(
rf'(\w{{2,{max_length}}}?)(\1+)', # Omit the second number in the repetition to match any number of repeating chars (\w{2,}?)(\1+)
lambda m: f'({m.group(1)}){superscript(len(m.group(0))//len(m.group(1)))}',
s
)
print(result) # (hd)⁴(cg)⁴c(bf)⁴b(ae)⁴a(dh)⁴d(cg)⁴c(bf)⁴b(ae)⁴a(dh)⁴d(cg)⁴c(bf)⁴b(ae)⁴a(dh)⁴d(cg)⁴c(bf)⁴b(ae)⁴a(dh)⁴d(cg)⁴c(bf)⁴b(ae)⁴a(dh)⁴d(cg)⁴cbfb
Спасибо! Я всегда упускаю из виду силу регулярных выражений.
Однако это не дает правильного результата для строки abcdabcdabcdabcdabababab.
@padawan немного улучшил ответ, теперь регулярное выражение должно соответствовать повторяющимся группам из 2-5 символов. Дарить (abcd)⁴(ab)⁴
Есть ли способ установить верхний предел длины входной строки вместо константы? Та же проблема возникает и при печати счетчика повторений. Для подстроки длины 5 это должно быть m.group(0)//5
и т. д.
@padawan Я просто обновлял исправление длины. Вы можете опустить второе число в совпадении повторения, чтобы соответствовать повторению любой длины, хотя в некоторых обстоятельствах это может привести к нежелательным результатам - (\w{2,}?)(\1+)
Значит, нет возможности написать что-то вроде '(\w{' + i + '}?)(\1+)'
? В конечном итоге я хочу уменьшить ввод до тех пор, пока не будет абсолютно никаких повторений. Например, (hd)⁴(cg)⁴(hd)⁴(cg)⁴
уменьшится до ((hd)⁴(cg)⁴)²
@padawan Конечно, вот так rf'(\w{{2,{i}}}?)(\1+)'
для повторений длины 2-i или rf'(\w{{{i}}})(\1+)'
для повторений ровно i длины
Проблема в вашем коде возникает, когда вы составляете список повторяющихся шаблонов. Когда вы объединяете паттерны длины 2 и паттерны длины 3, вы используете паттерны, несовместимые друг с другом.
Это означает, что когда вы объединяете два шаблона, вы получаете неправильный конечный результат, потому что буква с индексом 7 является общей.
Эта проблема возникает из-за того, что один паттерн имеет четную длину, а другой нечетный, и их пределы не совпадают. Таким образом, они даже не перезаписывают друг друга в d
, и вы получаете свой результат.
Я думаю, вы пытались решить эту проблему, используя словарь d
с начальным индексом в качестве ключа и со списком processed
, но есть еще пара проблем.
for j in range(i, (i+k)*repeat_count + 1):
должно быть for l in range(i, j)
, иначе вы пропускаете последний индекс шаблона (j
). Кроме того, я изменил индекс цикла на l
, потому что j
уже использовался. Это решило проблему, которую я описал выше.for k in range(2, len(signature))
), поэтому отдельные буквы, не принадлежащие ни одному шаблону, например c
в (hd)4(cg)4с(bf)4, никогда не попадут в словарь, и поэтому вы все равно будете имеют перекрывающиеся узоры разной длины в этих позициях.
ord(c)-ord('0')
может быть простоint(c)
.