Help: Creating condensed expressions

[David Hirschfield]

Here's the problem: Given a list of item names like:

apple1
apple2
apple3_SD
formA
formB
formC
kla_MM
kla_MB
kca_MM

which is a subset of a much larger list of items,
is there an efficient algorithm to create condensed forms that match
those items, and only those items? Such as:

apple[12]
apple3_SD
form[ABC]
kla_M[MB]
kca_MM

The condensed expression syntax only has [...] and * as operators. [...]
matches a set of individual characters, * matches any string.
I'd be satisfied with a solution that only uses the [...] syntax, since
I don't think it's possible to use * without potentially matching items
not explicitly in the given list.

I'm not sure what this condensed expression syntax is called (looks a
bit like shell name expansion syntax), and I'm not even sure there is an
efficient way to do what I'm asking. Any ideas would be appreciated.

Thanks,
-David

--
Presenting:
mediocre nebula.

[bearophileHUGS@lycos.com]

Re: Help: Creating condensed expressions

This is a first try, is something like this enough for you?


data = """apple1
apple2
apple3_SD
formA
formB
formC
kla_MM
kla_MB
kca_MM""".split ()

headtails = {}
for word in data:
head = word[:-1]
if head in headtails:
headtails[head].append(word[-1])
else:
headtails[head] = [word[-1]]
for head, tails in sorted(headtail s.iteritems()):
if len(tails) == 1:
print head + tails[0]
else:
print head + "[%s]" % "".join(tai ls)


Output:
apple[12]
apple3_SD
form[ABC]
kca_MM
kla_M[MB]

It looks only the last letters. It modifies the original order (it
sorts the sequence on the root-word).
If you don't need sorted results you can remove the sorted().

Bye,
bearophile

[Bruno Desthuilliers]

Re: Help: Creating condensed expressions

David Hirschfield a écrit :[color=blue]
> Here's the problem: Given a list of item names like:
>
> apple1
> apple2
> apple3_SD
> formA
> formB
> formC
> kla_MM
> kla_MB
> kca_MM
>
> which is a subset of a much larger list of items,
> is there an efficient algorithm to create condensed forms that match
> those items, and only those items? Such as:
>
> apple[12]
> apple3_SD
> form[ABC]
> kla_M[MB]
> kca_MM[/color]


[color=blue]
> The condensed expression syntax only has [...] and * as operators. [...]
> matches a set of individual characters, * matches any string.
> I'd be satisfied with a solution that only uses the [...] syntax, since
> I don't think it's possible to use * without potentially matching items
> not explicitly in the given list.
>
> I'm not sure what this condensed expression syntax is called (looks a
> bit like shell name expansion syntax),[/color]

Looks like a very restricted subset of regular expressions.
[color=blue]
> and I'm not even sure there is an
> efficient way to do what I'm asking. Any ideas would be appreciated.[/color]


import re

lines = """
apple1
apple2
apple3_SD
formA
formB
formC
kla_MM
kla_MB
kca_MM
""".strip().spl it()

patterns = [
r'apple[12]',
r'apple3_SD',
r'form[ABC]',
r'kla_M[MB]',
r'kca_MM',
]

for pat in patterns:
for line in lines:
m = re.match(pat, line)
print "%s match %s : %s" % (pat, line, m and "Yes" or 'No')


HTH

[Bruno Desthuilliers]

Re: Help: Creating condensed expressions

Bruno Desthuilliers a écrit :[color=blue]
> David Hirschfield a écrit :
>[color=green]
>> Here's the problem:[/color][/color]
(snip)[color=blue][color=green]
>>
>> is there an efficient algorithm to create condensed forms that match
>> those items,[/color][/color]

Sorry, answered to fast... Well, at least you have a way to test the
algo !-)

[bearophileHUGS@lycos.com]

Re: Help: Creating condensed expressions

Nevermind, I didn't understand the problem/question... Sorry.

Bye,
bearophile

[Bruno Desthuilliers]

Re: Help: Creating condensed expressions

bearophileHUGS@ lycos.com a écrit :[color=blue]
> Nevermind, I didn't understand the problem/question... Sorry.[/color]

actually, I think *you* got it right.

[Eddie Corns]

Re: Help: Creating condensed expressions

David Hirschfield <davidh@ilm.com > writes:
[color=blue]
>Here's the problem: Given a list of item names like:[/color]
[color=blue]
>apple1
>apple2
>apple3_SD
>formA
>formB
>formC
>kla_MM
>kla_MB
>kca_MM[/color]
[color=blue]
>which is a subset of a much larger list of items,
>is there an efficient algorithm to create condensed forms that match
>those items, and only those items? Such as:[/color]
[color=blue]
>apple[12]
>apple3_SD
>form[ABC]
>kla_M[MB]
>kca_MM[/color]
[color=blue]
>The condensed expression syntax only has [...] and * as operators. [...]
>matches a set of individual characters, * matches any string.
>I'd be satisfied with a solution that only uses the [...] syntax, since
>I don't think it's possible to use * without potentially matching items
>not explicitly in the given list.[/color]
[color=blue]
>I'm not sure what this condensed expression syntax is called (looks a
>bit like shell name expansion syntax), and I'm not even sure there is an
>efficient way to do what I'm asking. Any ideas would be appreciated.[/color]

If you used regular expressions instead of globs then I think what you want is
to optimize the regular expression for:

'apple1|apple2| apple3_SD|formA |formB|formC|kl a_MM|kla_MB|kca _MM'

then spit the optimised finite automaton back out. Of course if you're just
searching Python might do a decent job of optimising it anyway.

Looking at:

http://en.wikipedia.org/wiki/Finite_state_machine#Optimization

they make it sound so easy!. There's also a whole bunch of tools on that
page. Maybe there's an optimiser you can use in one of them.

Failing that I guess you build a tree and try to merge nodes where they fork.
I suspect an optimal solution would be hard but if you knew your input did
have lots of redundancy a simple algorithm might work.

Or I could be talking crap as usual.

Eddie

[Michael Spencer]

Re: Help: Creating condensed expressions

bearophileHUGS@ lycos.com wrote:[color=blue]
> Nevermind, I didn't understand the problem/question... Sorry.
>
> Bye,
> bearophile
>[/color]
Really? Your solution looks fine to me.

In any case, here's an alternative approach to the (based on the same
understanding of the problem as bearophile's, but with the additional
requirement that the input terms be sorted)
[color=blue][color=green][color=darkred]
>>> from itertools import groupby
>>> from operator import itemgetter
>>> src_iter = ((i[:-1],i[-1]) for i in src.splitlines( )) #src must be sorted
>>> grouped = groupby(src_ite r, itemgetter(0))
>>> stemmed = ((stem, "".join(i[1] for i in values)) for stem, values in grouped)
>>> [(len(s[1])>1 and "%s[%s]" or "%s%s") % s for s in stemmed][/color][/color][/color]
['apple[12]', 'apple3_SD', 'form[ABC]', 'kla_M[MB]', 'kca_MM'][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]


Michael