[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

matches -> regexp ?

konsu

12/12/2005 8:32:00 PM

Hello,

this is not exactly a ruby problem, i hope people will not consider
this spamming.

does anyone know of any reference or an algorithm to build a regular
expression (a finite automaton, in general) that would match a given
set of strings? i of course mean a regexp that would match just the
given strings, and not any other. so solutions like /^.*$/ are not
acceptable ;-)

thanks
konstantin
6 Answers

Robert Retzbach

12/12/2005 8:36:00 PM

0

ako... schrieb:

>Hello,
>
>this is not exactly a ruby problem, i hope people will not consider
>this spamming.
>
>does anyone know of any reference or an algorithm to build a regular
>expression (a finite automaton, in general) that would match a given
>set of strings? i of course mean a regexp that would match just the
>given strings, and not any other. so solutions like /^.*$/ are not
>acceptable ;-)
>
>thanks
>konstantin
>
>
>
>
>
nice challenge, reminds me a bit of the 4th rubyquiz :>

Edward Faulkner

12/12/2005 8:51:00 PM

0

> ako... schrieb:
> >does anyone know of any reference or an algorithm to build a regular
> >expression (a finite automaton, in general) that would match a given
> >set of strings? i of course mean a regexp that would match just the
> >given strings, and not any other. so solutions like /^.*$/ are not
> >acceptable ;-)

This is essentially an information compression problem. There's
always a trivial solution:

s = %w{find only these strings}
r = Regexp.new(s.map {|w| '\A' + w + '\Z'}.join('|'))

The _real_ problem is finding the shortest possible regexp. ;-)

konsu

12/12/2005 8:53:00 PM

0

well, right, that is what i mean.

konsu

12/12/2005 9:00:00 PM

0

i suspect that from your trivial solution we can arrive at the final
solution by just performing a DFA minimization. the same thing that lex
and yacc do when they generate code. so i guess i have answered my own
question. thanks for helping me. your trivial solution just made my
brain work.

konstantin

Robert Klemme

12/13/2005 1:14:00 PM

0

ako... wrote:
> i suspect that from your trivial solution we can arrive at the final
> solution by just performing a DFA minimization. the same thing that
> lex and yacc do when they generate code. so i guess i have answered
> my own question. thanks for helping me. your trivial solution just
> made my brain work.

Another option is to build up a tree and create the RX from that. I once
wrote that:

14:12:23 [c]: ( echo foo; echo bar; echo band ) | create-rx.rb
(?:ba(?:nd|r)|foo)

Kind regards

robert

Dave Heil

9/16/2009 12:42:00 PM

0

Topaz wrote:
> ADOLF HITLER
> SCHWERIN, GUSTLOFF'S FUNERAL
> SPEECH OF FEBRUARY 12, 1936
>
> . . . BEHIND every murder stood the same power which is responsible
> for this murder; behind these harmless insignificant fellow-countrymen
> who were instigated and incited...

Are you under a doctor's care for a mental illness?