How to match regex with multiple overlapping patterns?

Question

The context

I have a string made of mixed mp3 information that I must try to match against a pattern made of arbitrary strings and tokens. It works like that :

The program shows the user a given string

the Beatles_Abbey_Road-SomeWord-1969

User enter a pattern to help program parse the string

the %Artist_%Album-SomeWord-%Year

Then I'd like to show results of the matches (but need your help for that)

2 possible matches found :
[1] {'Artist': 'Beatles', 'Album':'Abbey_Road', 'Year':1969}
[2] {'Artist': 'Beatles_Abbey', 'Album':'Road', 'Year':1969}

The problem

As an example, let say pattern is artist name followed by title (delimiter: '-').

Example 1:

>>> artist = 'Bob Marley'
>>> title = 'Concrete Jungle'
>>> re.findall(r'(.+)-(.+)', '%s-%s' % (artist,title))
[('Bob Marley', 'Concrete Jungle')]

So far, so good. But...
I have no control over the delimiter used and have no guarantee that it's not present in the tags, so trickier cases exist :

Example 2:

>>> artist = 'Bob-Marley'
>>> title = 'Roots-Rock-Reggae'
>>> re.findall(r'(.+)-(.+)', '%s-%s' % (artist,title))
[('Bob-Marley-Roots-Rock', 'Reggae')]

As expected, it doesn't work in that case.

How can I generate all possible combinations of artist/title ?

[('Bob', 'Marley-Roots-Rock-Reggae'),
 ('Bob-Marley', 'Roots-Rock-Reggae')
 ('Bob-Marley-Roots', 'Rock-Reggae'),
 ('Bob-Marley-Roots-Rock', 'Reggae')]

Are regex the tool to use for that job ?

Please keep in mind that number of tags to match and delimiters between those tags are not fixed but user defined (so the regex to use has to be buildable dynamically).
I tried to experiment with greedy vs minimal matching and lookahead assertions with no success.

Thanks for your help

@Acorn in linked question, delimiter doesn't belong to the same class (upper vs lower case) than pattern to match, making the problem easier to resolve imo — kraymer
– kraymer, Commented Jul 15, 2011 at 9:54

Andrew Clark · Accepted Answer · 2011-07-15 21:23:12Z

1

This solution seems to work. In addition to the regex you will need a list of tuples to describe the pattern, where each element corresponds to one capturing group of the regex.

For your Beatles example, it would look like this:

pattern = r"the (.+_.+)-SomeWord-(.+)"
groups = [(("Artist", "Album"), "_"), ("Year", None)]

Because the Artist and Album are only split by a single separator, they will be captured together in one group. The first item in the list indicates that the first capture group will be split into and Artist and an Album, and will use _ as the separator. The second item in the list indicates that the second capture group will be used as the Year directly, since the second element in the tuple is None. You could then call the function like this:

>>> get_mp3_info(groups, pattern, "the Beatles_Abbey_Road-SomeWord-1969")
[{'Album': 'Abbey_Road', 'Year': '1969', 'Artist': 'Beatles'}, {'Album': 'Road', 'Year': '1969', 'Artist': 'Beatles_Abbey'}]

Here is the code:

import re
from itertools import combinations

def get_mp3_info(groups, pattern, title):
    match = re.match(pattern, title)
    if not match:
        return []
    result = [{}]
    for i, v in enumerate(groups):
        if v[1] is None:
            for r in result:
                r[v[0]] = match.group(i+1)
        else:
            splits = match.group(i+1).split(v[1])
            before = [d.copy() for d in result]
            for comb in combinations(range(1, len(splits)), len(v[0])-1):
                temp = [d.copy() for d in before]
                comb = (None,) + comb + (None,)
                for j, split in enumerate(zip(comb, comb[1:])):
                    for t in temp:
                        t[v[0][j]] = v[1].join(splits[split[0]:split[1]])

                if v[0][0] in result[0]:
                    result.extend(temp)
                else:
                    result = temp
    return result

And another example with Bob Marley:

>>> pprint.pprint(get_mp3_info([(("Artist", "Title"), "-")],
...               r"(.+-.+)", "Bob-Marley-Roots-Rock-Reggae"))
[{'Artist': 'Bob', 'Title': 'Marley-Roots-Rock-Reggae'},
 {'Artist': 'Bob-Marley', 'Title': 'Roots-Rock-Reggae'},
 {'Artist': 'Bob-Marley-Roots', 'Title': 'Rock-Reggae'},
 {'Artist': 'Bob-Marley-Roots-Rock', 'Title': 'Reggae'}]

answered Jul 15, 2011 at 21:23

Andrew Clark

210k36 gold badges286 silver badges310 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

kraymer Over a year ago

Thanx Andrew, am not able to apply this solution yet though. I generate the regex dynamically, by defining a group for each token met (%Artist, %album, etc) So for the Beatles example i have regex: the (?P<Artist>.+)_(?P<Album>.+)-SomeWord-(?P<Year>.+) For your function to work, one need to capture together tokens in one regex group, eg Artist and Album. It's not clear to me why you choose to group Artist and Album (split by string '_') and not 'Album' and 'Year' (split by string '-SomeWord-'). Can you explain on what criteria you make this grouping decision so i can automate the process ?

kraymer Over a year ago

OK, I slightly modified your code so it matches my inputs. It works great, thanks.

Acorn · Accepted Answer · 2011-07-15 10:29:40Z

0

What about something like this instead of using a regular expression?

import re

string = "Bob-Marley-Roots-Rock-Reggae"

def allSplits(string, sep):
    results = []
    chunks = string.split('-')
    for i in xrange(len(chunks)-1):
        results.append((
            sep.join(chunks[0:i+1]),
            sep.join(chunks[i+1:len(chunks)])
        ))

    return results

print allSplits(string, '-')

[('Bob', 'Marley-Roots-Rock-Reggae'),
 ('Bob-Marley', 'Roots-Rock-Reggae'),
 ('Bob-Marley-Roots', 'Rock-Reggae'),
 ('Bob-Marley-Roots-Rock', 'Reggae')]

edited Jul 15, 2011 at 10:29

answered Jul 15, 2011 at 10:04

Acorn

50.8k30 gold badges143 silver badges180 bronze badges

1 Comment

kraymer Over a year ago

It works for the example I gave but not in the general case. I added a "Context" paragraph to my post to make it more clear.

Collectives™ on Stack Overflow

How to match regex with multiple overlapping patterns?

The context

The problem

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

The context

The problem

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related