matches -> regexp ?

Discussion in 'Ruby' started by ako..., Dec 12, 2005.

  1. ako...

    ako... Guest

    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
    ako..., Dec 12, 2005
    #1
    1. Advertising

  2. 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 :>
    Robert Retzbach, Dec 12, 2005
    #2
    1. Advertising

  3. --o0ZfoUVt4BxPQnbU
    Content-Type: text/plain; charset=us-ascii
    Content-Disposition: inline

    > 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. ;-)

    --o0ZfoUVt4BxPQnbU
    Content-Type: application/pgp-signature; name="signature.asc"
    Content-Description: Digital signature
    Content-Disposition: inline

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.1 (GNU/Linux)

    iD4DBQFDneKDnhUz11p9MSARAhZdAJikR9LxgvRKe+HQx+NM/iFPTQPDAKCg7yyF
    k9ZvZV/M0aud/vCU9NxSLw==
    =EgnI
    -----END PGP SIGNATURE-----

    --o0ZfoUVt4BxPQnbU--
    Edward Faulkner, Dec 12, 2005
    #3
  4. ako...

    ako... Guest

    well, right, that is what i mean.
    ako..., Dec 12, 2005
    #4
  5. ako...

    ako... Guest

    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
    ako..., Dec 12, 2005
    #5
  6. 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
    Robert Klemme, Dec 13, 2005
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Boris Pelakh
    Replies:
    3
    Views:
    455
    Purl Gurl
    Apr 8, 2004
  2. Replies:
    3
    Views:
    1,552
  3. gry
    Replies:
    4
    Views:
    217
  4. Kevin Howe

    multiple regexp matches

    Kevin Howe, Aug 17, 2004, in forum: Ruby
    Replies:
    27
    Views:
    264
    Martin DeMello
    Aug 24, 2004
  5. Joao Silva
    Replies:
    16
    Views:
    343
    7stud --
    Aug 21, 2009
Loading...

Share This Page