Сокращение строки путем обнаружения шаблонов

Учитывая строку, я хотел бы обнаружить повторяющиеся подстроки, а затем уменьшить абаб до (аб)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)²
ord(c)-ord('0') может быть просто int(c).
LeopardShark 15.05.2022 15:30
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
1
1
63
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Вы можете использовать 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

Спасибо! Я всегда упускаю из виду силу регулярных выражений.

padawan 15.05.2022 20:19

Однако это не дает правильного результата для строки abcdabcdabcdabcdabababab.

padawan 15.05.2022 20:30

@padawan немного улучшил ответ, теперь регулярное выражение должно соответствовать повторяющимся группам из 2-5 символов. Дарить (abcd)⁴(ab)⁴

Iain Shelvington 15.05.2022 20:40

Есть ли способ установить верхний предел длины входной строки вместо константы? Та же проблема возникает и при печати счетчика повторений. Для подстроки длины 5 это должно быть m.group(0)//5 и т. д.

padawan 15.05.2022 20:42

@padawan Я просто обновлял исправление длины. Вы можете опустить второе число в совпадении повторения, чтобы соответствовать повторению любой длины, хотя в некоторых обстоятельствах это может привести к нежелательным результатам - (\w{2,}?)(\1+)

Iain Shelvington 15.05.2022 20:43

Значит, нет возможности написать что-то вроде '(\w{' + i + '}?)(\1+)'? В конечном итоге я хочу уменьшить ввод до тех пор, пока не будет абсолютно никаких повторений. Например, (hd)⁴(cg)⁴(hd)⁴(cg)⁴ уменьшится до ((hd)⁴(cg)⁴)²

padawan 15.05.2022 20:52

@padawan Конечно, вот так rf'(\w{{2,{i}}}?)(\1+)' для повторений длины 2-i или rf'(\w{{{i}}})(\1+)' для повторений ровно i длины

Iain Shelvington 15.05.2022 20:56

Проблема в вашем коде возникает, когда вы составляете список повторяющихся шаблонов. Когда вы объединяете паттерны длины 2 и паттерны длины 3, вы используете паттерны, несовместимые друг с другом.

  • hdhdhdhd = (hd)4 начинается с индекса 0 и заканчивается индексом 7 (включительно).
  • (dcgcgcgcgcbfbfbfbfbaeaeaeaeaadhdhdhdh)5, который является правильным шаблоном в вашей строке, начинается с индекса 7 (включительно).

Это означает, что когда вы объединяете два шаблона, вы получаете неправильный конечный результат, потому что буква с индексом 7 является общей.

Эта проблема возникает из-за того, что один паттерн имеет четную длину, а другой нечетный, и их пределы не совпадают. Таким образом, они даже не перезаписывают друг друга в d, и вы получаете свой результат.

Я думаю, вы пытались решить эту проблему, используя словарь d с начальным индексом в качестве ключа и со списком processed, но есть еще пара проблем.

  1. for j in range(i, (i+k)*repeat_count + 1): должно быть for l in range(i, j), иначе вы пропускаете последний индекс шаблона (j). Кроме того, я изменил индекс цикла на l, потому что j уже использовался. Это решило проблему, которую я описал выше.
  2. Несмотря на то, что это исправлено, проблема все еще существует. Вы проверяете шаблоны, начиная с длины 2 (for k in range(2, len(signature))), поэтому отдельные буквы, не принадлежащие ни одному шаблону, например c в (hd)4(cg)4с(bf)4, никогда не попадут в словарь, и поэтому вы все равно будете имеют перекрывающиеся узоры разной длины в этих позициях.

Другие вопросы по теме