Удалить смежные дубликаты подстрок

Question

Я пытаюсь удалить дубликаты смежных подстрок длиной k, где k относится к числу слов.Код должен работать рекурсивно, начиная с

k = 1 слово до k = количество слов в строке

Например,

я селнаписать статью, статью этим утром, но обнаружил, что ii не может добиться прогресса

становится

я селнаписать статью этим утром, но обнаружил, что i не может добиться прогресса

Как мне этого добиться?Я могу добиться удаления 1 смежной подстроки:

str.chunk{|n| n}.map(&:first)

Answer 1

Я предположил, что строка не содержит пробелов, кроме пробелов (без табуляции, новых строк, переносов строк, переносов форм и т. Д.), И что слова разделяются одним пробелом, или, если они разделены несколькими пробелами, строкавозвращаемый может содержать только один пробел между словами.(Существует обходной путь для последнего, но он не является центральным для вопроса.)

def remove_repeats(str)
  s = str.squeeze(' ')
  s.insert(0, ' ')
  change = ''
  until change.nil?
    change = s.gsub!(/(?:((?: \S+)+))\1/, '\1')
  end
  s[1..-1]
end

remove_repeats 'a a b a a b'              #=> "a b"
remove_repeats 'a a b c a a b c d'        #=> "a b c d"
remove_repeats ' c a a b a a b d a a b e' #=> " c a b d a b e"
remove_repeats 'aa a bb bb b'             #=> "aa a bb b"
remove_repeats 'a b c d e f'              #=> "a b c d e f"
remove_repeats ''                         #=> ""

Регулярное выражение выглядит следующим образом: «Для любой строки, состоящей из пробела, за которым следует строкаиз пробелов повторите эту строку один или несколько раз и сохраните результат в группе захвата 1. Сопоставьте содержимое группы захвата один или несколько раз, а затем содержимое группы захвата. Если gsub! делает хотя бы одинзаменено, s обновлено, иначе gsub! возвращает nil. Обратите внимание, что перед заменой текста я вставил пробел в начале строки, а затем удалил его после завершения всех замен.

/((?: \S+)+)\1/ также работает в приведенных выше примерах, но может потребовать больше итераций для получения решения.

Я не смог доказать это работает во всех случаях. Я приглашаю читателей предложить доказательство того, что это так иликонтрпример.

Answer 2

s = "i sat down to write an article an article this morning but found that i i could make no progress"

max = s.scan(/\S+/).length
# => 20
1.upto(max).each_with_object(s) do
  |n, s| s.gsub!(/((?:\b\s*\S+){#{n}})\1/, '\1')
end
# => "i sat down to write an article this morning but found that i could make no progress"

Кстати,

"I like to move it move it, I like to move it move it"

приведет к:

"I like to move it, I like to move it"

not:

"I like to move it"

, как вы упомянули в комментарии, потому чтоза вышеприведенной строкой нет повторяющихся соседей (следите за запятой и пробелом).