Matching unmatched strings based on a unknown pattern
- by Polity
Alright guys, i really hurt my brain over this one and i'm curious if you guys can give me any pointers towards the right direction i should be taking.
The situation is this:
Lets say, i have a collection of strings (let it be clear that the pattern of this strings is unknown. For a fact, i can say that the string contain only signs from the ASCII table and therefore, i dont have to worry about weird Chinese signs).
For this example, i take the following collection of strings (note that the strings dont have to make any human sence so dont try figguring them out :)):
"[001].[FOO].[TEST] - 'foofoo.test'",
"[002].[FOO].[TEST] - 'foofoo.test'",
"[003].[FOO].[TEST] - 'foofoo.test'",
"[001].[FOO].[TEST] - 'foofoo.test.sample'",
"[002].[FOO].[TEST] - 'foofoo.test.sample'",
"-001- BAR.[TEST] - 'bartest.xx1",
"-002- BAR.[TEST] - 'bartest.xx1"
Now, what i need to have is a way of finding logical groups (and subgroups) of these set of strings, so in the above example, just by rational thinking, you can combine the first 3, the 2 after that and the last 2. Also the resulting groups from the first 5 can be combined in one main group with 2 subgroups, this should give you something like this:
{
{
"[001].[FOO].[TEST] - 'foofoo.test'",
"[002].[FOO].[TEST] - 'foofoo.test'",
"[003].[FOO].[TEST] - 'foofoo.test'",
}
{
"[001].[FOO].[TEST] - 'foofoo.test.sample'",
"[002].[FOO].[TEST] - 'foofoo.test.sample'",
}
{
"-001- BAR.[TEST] - 'bartest.xx1",
"-002- BAR.[TEST] - 'bartest.xx1"
}
}
Sorry for the layout above but indenting with 4 spaces doesnt seem to work correctly (or im frakk'n it up).
Anyways, I'm not sure how to approach this problem (how to get the result desired as indicated above).
First of, i thought of creating a huge set of regexes which would parse most known patterns but the amount of different patterns is just to huge that this isn't realistic.
Another think i thought of was parsing each indidual word within a string (so strip all non alphabetic or numeric characters and split by those), and if X% matches, i can assume the strings belong to the same group. (where X wil probably be around 80/90). However, i find the area of speculation kinda big. For example, when matching strings with each 20 words, the change of hitting above 80% is kinda big (that means that 4 words can differ), however when matching only 8 words, 2 words at most can differ.
My question to you is, what would be a logical approach in the above situation?
Thanks in advance!
