Removing duplicate elements from the string

Hi there! :)
Well, this is actually my first post in this newly created blog.
The idea of keeping a blog was born a day ago, when there was a question on the Oracle forum (this thread). I’ve met the same one only a few days ago – but couldn’t find it, cause there were some problems with the search engine I usually face when I need to find something :))
So I decided – why don’t I keep my own blog – where I can post such solutions that can be interesting for others. And here we are!

Ok, let's go back to the problem, mentioned in those links.

Problem description:

Input data:

There is a string containing elements. They can be separated with any symbol, e.g. a comma:

SQL> with t as (select 'elem1, elem2, elem3, elem1, elem3, elem2, elem2' str
from dual)
--
select * from t
/

STR
-----------------------------------------------
elem1, elem2, elem3, elem1, elem3, elem2, elem2

SQL>

...or any other clear way, for example, it was formulated as "3 letter codes". So in this case there are no element delimiters, but we know that each element is of three same consequtive letters, e.g.:

SQL> with t as (select 'AAABBBCCCBBBDDDAAAEEEBBB' str from dual)
--
select * from t
/

STR
------------------------
AAABBBCCCBBBDDDAAAEEEBBB

SQL>

Goal:

The objective is to remove duplicate elements out of the string, to leave only one specimen of each element.

Expected output:

So in the first case the result should be:
elem1, elem2, elem3

In the second:
AAABBBCCCDDDEEE

Solution:

In both cases the first thing what we need - is to pick out elements from the string.
Regular expressions are very friendly for us in that job (espesially, when there are no delimiters).
So elements like AAA, BBB, CCC etc. can be written as '([[:alpha:]])\1{2}' - any letter trailed by two same letters.

Now we want to understand - what would be the mask for such an element followed by another elements and again the same first element, e.g. AAABBBCCCAAA, or it can be followed directly by the same element: AAAAAA.
In language of regular expressions it would look like '(([[:alpha:]])\2{2}).*\1'

That's it!
Now if we put regexp_replace(str, '(([[:alpha:]])\2{2})(.*)\1','\1\3') we would throw out one last element which is met firstly and has duplicate values in the string. It would be last, because we used greedy operator '*'.

So for example:

SQL> with t as (select 'AAABBBCCCBBBEEEDDDAAAEEEBBBEEE' str from dual)
--
select str,
regexp_replace(str, '(([[:alpha:]])\2{2})(.*)\1','\1\3') new_str
from t
/

STR NEW_STR
------------------------------ -------------------------------
AAABBBCCCBBBEEEDDDAAAEEEBBBEEE AAABBBCCCBBBEEEDDDEEEBBB

SQL>

What is the logic of this operation:

1. We look for the first element which has duplicated values. In our case it is AAA.
2. Then regular expression operator finds the last AAA met in the string and removes it.
3. Then, it goes to the rest of the string and again finds the first element, which has duplicated values in the rest of the string, now it is EEE.
   
4. And finally removes the last EEE element.
5. In our example it is the end of the operations, but if the string is longer it would proceed the previously mentioned operations again and again.
   

It would be more comprehensible if we mark the first met element with green, and the last, which would be removed, with red:
'AAABBBCCCBBBEEEDDDAAAEEEBBBEEE'.
As you can see, the first EEE element is not really the first EEE element in the string. It is the first one in the rest of the string after we removed AAA element.

If we iteratively apply this regular expression to our string - finally we remove all duplicated elements. But about it later. Now let's improve our expression a little bit.
First we'll change greedy operator '*' to non-greedy '*?'. So that we will do our job in fewer iterations.

Let's look at the following example:
we have string 'AAABBBAAAAAACCCAAA'.
with greedy regexp_replace(str, '(([[:alpha:]])\2{2})(.*)\1','\1\3') we'll have iterations:

1. AAABBBAAAAAACCCAAA
2. AAABBBAAAAAACCC
3. AAABBBAAACCC

result: 'AAABBBCCC'. So it took us 3 times to iterate.
And with the non-greedy regexp_replace(str, '(([[:alpha:]])\2{2})(.*?)\1','\1\3') we'll have iterations:

1. AAABBBAAAAAACCCAAA
2. AAABBBAAACCC

The same result and achieved in two iterations.

Let's make one more improvement: add '+' after the backreference '\1'. In the language of regular expressions - it means one or more occurencies of the element which is preceding this '+'.
Let's imagine we have a string: 'AAABBBAAAAAAAAAAAA'.
With regexp_replace(str, '(([[:alpha:]])\2{2})(.*?)\1','\1\3') we'll make three iterations:

1. AAABBBAAAAAAAAAAAA
2. AAABBBAAAAAA
3. AAABBBAAA

If we place '+' and use regexp_replace(str, '(([[:alpha:]])\2{2})(.*?)\1+','\1\3') we'll have to make only one iteration:

1. AAABBBAAAAAAAAAAAA

Finally, it is a time for implementing an iterative mechanism of applying the same function to the string. Starting from Oracle version 10g there was a nice Model clause introduced, which can be used to proceed operations iteratively.

So, the final query would look like:

SQL> WITH t AS (SELECT
'AAABBBCCCBBBDDDAAAEEEBBB' str FROM dual)
--
select str, str_new from t
model
dimension by (0 dim)
measures(str, str str_new)
rules iterate(100) until (str_new[0] = previous(str_new[0]))
(str_new[0]=regexp_replace(str_new[0],'(([[:alpha:]])\2{2})(.*?)\1+','\1\3'));

STR STR_NEW
------------------------ ------------------------
AAABBBCCCBBBDDDAAAEEEBBB AAABBBCCCDDDEEE

SQL>

Two words about Model clause here:

• With regexp_replace you are already familiar. It is applyed to the string during each iteration;
  
• iterate(100) means maximum of iterations could be proceeded is 100 (it can be increased if you want);
• until (str[0] = previous(str[0])) means stop iterations when the string is not changed during the previous iteration.

Well, that's it.

Now let's take the case when there is a delimited string, e.g. with commas. In that case we need to change our regular expression a little bit. Aketi Jyuuzou made this in one of the mentioned links. I just clarify it for readers. So for a string like 'elem1, elem2, elem3, elem1, elem3, elem2, elem2' we'll need the following:
regexp_replace(str,'(^|,)([^,]+,)(.*?,)?\2+','\1\2\3')
I just added non-greedy '*?' and '+' in the end, but you have already read about the impact of these. So you understand what are they needed for.

Backreference \1 stands for (^|,) - this is the symbol before the first met duplicated element. It is either begining of the string (^), either a comma trailing the previous element (,).
Backreference \2 stands for the ([^,]+,) - this is the element itself, which means one or more non-comma symbols followed by a comma.
Backreference \3 stands for (.*?,)? which is the minimum (non-greedy) number of symbols before one or more duplicated value (\2+).

So the final query would look like:

SQL> WITH t AS (SELECT 'elem1,elem2,elem3,elem1,elem3,elem2,elem2' str FROM dual)
--
select str, rtrim(str_new,',') new_str from t
model
dimension by (0 dim)
measures(str, str||',' str_new)
rules iterate(100) until (str_new[0] = previous(str_new[0]))
(str_new[0]=regexp_replace(str_new[0],'(^|,)([^,]+,)(.*?,)?\2+','\1\2\3'));

STR NEW_STR
----------------------------------------- -------------------------
elem1,elem2,elem3,elem1,elem3,elem2,elem2 elem1,elem2,elem3

SQL>

Hope it was useful!

PS
It is my first post, so I'll be grateful if you post your comments and notices about it. Was it too comlicatedely stated or maybe too detailed. Well,waiting for your replies :)