Remove all replicas of a string more than x characters long (regex?)

Question

I'm not certain that regex is the best approach for this, but it seems to be fairly well suited. Essentially I'm currently parsing some pdfs using pdfminer, and the drawback is that these pdf's are exported powerpoint slides, which means that all animations show up as fairly long copies of strings. Ideally I would like just one copy of each of these strings instead of a copy for each stage of an animation. Right now the current regex pattern I'm using is this:

re.sub(r"([\w^\w]{10,})\1{1,}", "\1", string)

For some reason though, this doesn't seem to change the input string. I feel like for some reason python isn't recognizing the capture group, but I'm not sure how to remedy that issue. Any thoughts appreciated.

Examples:

I would like this
text to be

reduced
I would like this
text to be

reduced

output:

I would like this
text to be

reduced

Update: To get this to pass the pumping lemma I had to specifically make the assertion that all duplicates were adjacent. This was implied before, but I am now making it explicit to ensure that a solution is possible.

Answer 1

regexps are not the right tool for that task. They are based on the theory of context free languages, and they can't match if a string contains duplicates and remove the duplicates. You may find a course on automata and regexps interesting to read on the topic.

I think Josay's suggestion can be efficient and smart, but I think I got a more simple and pythonic solution, though it has its limits. You can split your string into a list of lines, and pass it through a set():

>>> s = """I would like this
... text to be
... 
... reduced
... I would like this
... text to be
... 
... reduced"""
>>> print "\n".join(set(s.splitlines()))
I would like this

text to be
reduced
>>>

The only thing with that solution is that you will loose the original order of the lines (the example being a pretty counter example). Also, if you have the same line in two different contexts, you will end up having only one line.

• To fix the first problem, you may have to then iterate over your original string a second time to put that set back in order, or simply use an ordered set.
• If you got any symbol separating each slide, it would help you merge only the duplicates, fixing the second problem of that solution.

Otherwise a more sophisticated algorithm would be needed, so you can take into account proximity and context. For that a suffix tree could be a good idea, and there are python libraries for that (cf that SO answer).

edit:

using your algorithm I could make it work, by adding support of multiline and adding spaces and endlines to your text matching:

>>> re.match(r"([\w \n]+)\n\1", string, re.MULTILINE).groups()
('I would like this\ntext to be\n\nreduced',)

Though, afaict the \1 notation is not a regular regular expression syntax in the matching part, but an extension. But it's getting late here, and I may as well be totally wrong. Maybe shall I reread those courses? :-)

I guess that the regexp engine's pushdown automata is able to push matches, because it is only a long multiline string that it can pop to match. Though I'd expect it to have side effects...