10

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.

Tom
  • 6,991
  • 13
  • 60
  • 78
  • 1
    could you please display an example of what you're looking for, I don't quite understand. – Anders Jul 22 '10 at 14:19

5 Answers5

11

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.

Tim Pietzcker
  • 328,213
  • 58
  • 503
  • 561
  • 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! – Tom Jul 22 '10 at 14:58
  • 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` – Tom Jul 23 '10 at 11:08
  • @Tom: Excellent point. I have updated my answer. The word boundary assertion is also necessary in front of the backreference. – Tim Pietzcker Jul 23 '10 at 11:17
  • Did you test that .NET regex? It didn't work for me until I added the `RightToLeft` modifier. – Alan Moore Jul 23 '10 at 12:22
  • @Alan Moore: I tested it in RegexBuddy; I don't think it suggested the use of this modifier - thanks for the info! – Tim Pietzcker Jul 23 '10 at 19:48
  • 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 ;) – Yin Cognyto Apr 02 '21 at 13:30
2

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

Always a useful site when thinking about any regular expression.

Noon Silk
  • 54,084
  • 6
  • 88
  • 105
1
$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
Toto
  • 89,455
  • 62
  • 89
  • 125
  • +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. – NorthGuard Jul 22 '10 at 14:58
0

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.

Dan Monego
  • 9,637
  • 6
  • 37
  • 72
  • Sorting is not relevant, see my solution. – Tim Pietzcker Jul 22 '10 at 14:43
  • 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. – Alan Moore Jul 23 '10 at 12:48
  • @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` – Alan Moore Jul 23 '10 at 13:10
0

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.

ghostdog74
  • 327,991
  • 56
  • 259
  • 343