What regular expression can remove duplicate items from a string?

Question

Given a string of identifiers separated by :, is it possible to construct a regular expression to extract the unique identifiers into another string, also separated by :?

How is it possible to achieve this using a regular expression? I have tried s/(:[^:])(.*)\1/$1$2/g with no luck, because the (.*) is greedy and skips to the last match of $1.

Example: a:b:c:d:c:c:x:c:c:e:e:f should give a:b:c:d:x:e:f

Note: I am coding in perl, but I would very much appreciate using a regex for this.

Osteoclast

could you please display an example of what you're looking for, I don't quite understand. – Counterwork

Answer 1

In .NET which supports infinite repetition inside lookbehind, you could search for

(?<=\b\1:.*)\b(\w+):?

and replace all matches with the empty string.

Perl (at least Perl 5) only supports fixed-length lookbehinds, so you can try the following (using lookahead, with a subtly different result):

\b(\w+):(?=.*\b\1:?)

If you replace that with the empty string, all previous repetitions of a duplicate entry will be removed; the last one will remain. So instead of

a:b:c:d:x:e:f

you would get

a:b:d:x:c:e:f

If that is OK, you can use

$subject =~ s/\b(\w+):(?=.*\b\1:?)//g;

Explanation:

First regex:

(?<=\b\1:.*): Check if you can match the contents of backreference no. 1, followed by a colon, somewhere before in the string.

\b(\w+):?: Match an identifier (from a word boundary to the next :), optionally followed by a colon.

Second regex:

\b(\w+):: Match an identifier and a colon.

(?=.*\b\1:?): Then check whether you can match the same identifier, optionally followed by a colon, somewhere ahead in the string.

Sectionalize

The output order is irrelevant to me, which is why I didn't mention it in the question (maybe I should have mentioned that it was irrelevant :). Thank you, it worked like a charm! – Osteoclast

Please update your answer, the solution you provided worked only if the words were one-character long. Forgot to mention that as well. A better answer would be s/\b(\w+):(?=.*\1:?)//g – Osteoclast

@Tom: Excellent point. I have updated my answer. The word boundary assertion is also necessary in front of the backreference. – Sectionalize

Did you test that .NET regex? It didn't work for me until I added the RightToLeft modifier. – Oneiromancy

@Alan Moore: I tested it in RegexBuddy; I don't think it suggested the use of this modifier - thanks for the info! – Sectionalize

Brilliant answer - I ended up with a similar (?U)(.*,)(?=(.*,|)\1) on my own for a comma separated string (my string's last character is also a comma), so your answer confirms that I found the right solution. Didn't find your answer earlier to avoid figuring out things by myself, but I don't regret it, as the hard way is the only way to learn stuff like this ;) – Depurative

Answer 2

Check out: http://www.regular-expressions.info/duplicatelines.html

Always a useful site when thinking about any regular expression.

Becker

...but not really applicable to the problem, because these solution only deal with adjacent duplicates... – Sectionalize

Answer 3

$str = q!a:b:c:d:c:c:x:c:c:e:e:f!;

1 while($str =~ s/(:[^:]+)(.*?)\1/$1$2/g);

say $str

output :

a:b:c:d:x:e:f

Teague

+1 for empty while loop, though I think a more complete solution might be: while {$str =~ s/(:[^:]+|[^:]+:)(.*)\1(.*)/$1$2$3/g} to check the first letter. – Donner

Answer 4

If the identifiers are sorted, you may be able to do it using lookahead/lookbehind. If they aren't, then this is beyond the computational power of a regex. Now, just because it's impossible with formal regex doesn't mean it's impossible if you use some perl specific regex feature, but if you want to keep your regexes portable you need to describe this string in a language that supports variables.

Davisson

Sorting is not relevant, see my solution. – Sectionalize

What do you mean by Perl-specific features? Capturing groups, backreferences, word boundaries and lookaheads are very widely supported. Of the features being used in this discussion, the only one I would call non-portable is lookbehinds, especially unbounded lookbehinds. – Oneiromancy

@Tim: I'd say it's relevant in the sense that, if the identifiers were sorted, eliminating duplicates would be trivial: s/(\w+)(:\1)+(?=:|$)/$1/g – Oneiromancy

Answer 5

here's an awk version, no need regex.

$ echo "a:b:c:d:c:c:x:c:c:e:e:f" | awk -F":" '{for(i=1;i<=NF;i++)if($i in a){continue}else{a[$i];printf $i}}'
abcdxef

split the fields on ":", go through the splitted fields, store the elements in an array. check for existence and if exists, skip. Else print them out. you can translate this easily into Perl code.

Vedetta