Re: Re: Re: Pattern Finding

Hi, This is one of the classic problem in AI.

The problem I posted, is actaully an exercise on segmentation section of the OpenLab on http://www.a-i.com.(You will need to register) I have extended it to some other critera such as 'spaces allowed' to meet more general problems. I tried runrig's solution and it doesn't work when number of patterns is 6, for the condition that one pattern cannot be part of another pattern.

I am trying to solve this problem myself also, what I am looking for is good design to begin with.

Artist.
(My computer doesn't keep the login for more than one page, Please let me know if you know the soltuion).

Comment on Re: Re: Re: Pattern Finding

Replies are listed 'Best First'.
Re: Re: Re: Re: Pattern Finding by runrig (Abbot) on Sep 13, 2001 at 21:12 UTC
for the condition that one pattern cannot be part of another pattern This is the toughest condition, and so I don't think it can be done with a regex, at least not with perl's regex engine (hope someone can prove me wrong :). At every stage of capuring a pattern, you'd have to be able to fail if the longer of the current pattern and each of all past patterns doesn't contain the other. Here's some psuedo perl regex code which, if it worked would accomplish this (hope you get the idea), but I'm using things in the wrong way, the regex engine isn't re-entrant, it uses "$1" instead of "\1" (and in a symbolic reference sort of way), etc, but I though it was interesting nonetheless. It would go right after each pattern caputure in my solution: `join('', map { "(?{(length($$i)>length($$_))$$i !~ /$$_/ \| $$_ !~ /$$i/})" } 1..$_)` [download]	[reply] [d/l]

Replies are listed 'Best First'.

Re: Re: Re: Re: Pattern Finding
by runrig (Abbot) on Sep 13, 2001 at 21:12 UTC

for the condition that one pattern cannot be part of another pattern

This is the toughest condition, and so I don't think it can be done with a regex, at least not with perl's regex engine (hope someone can prove me wrong :). At every stage of capuring a pattern, you'd have to be able to fail if the longer of the current pattern and each of all past patterns doesn't contain the other. Here's some psuedo perl regex code which, if it worked would accomplish this (hope you get the idea), but I'm using things in the wrong way, the regex engine isn't re-entrant, it uses "$1" instead of "\1" (and in a symbolic reference sort of way), etc, but I though it was interesting nonetheless. It would go right after each pattern caputure in my solution:

join('', map {
 "(?{(length($$i)>length($$_))$$i !~ /$$_/ | $$_ !~ /$$i/})"
} 1..$_)
[download]

[reply]
[d/l]