Loading ...
Sorry, an error occurred while loading the content.

Suffix trees

Expand Messages
  • citromatik
    Hi all, Does anybody know of any high-performance http://en.wikipedia.org/wiki/Suffix_tree suffix tree implementation in OCaml? Naive implementations are also
    Message 1 of 5 , Apr 16, 2009
    • 0 Attachment
      Hi all,

      Does anybody know of any high-performance
      http://en.wikipedia.org/wiki/Suffix_tree suffix tree implementation in
      OCaml?
      Naive implementations are also welcome. I need a fast algorithm to compare
      strings allowing errors, so any other implementation of approximate string
      matching is also welcome.

      Thanks in advance,

      M;
      --
      View this message in context: http://www.nabble.com/Suffix-trees-tp23081534p23081534.html
      Sent from the Ocaml Beginner mailing list archive at Nabble.com.
    • Peng Zang
      ... Hash: SHA1 First google hit =] http://alan.petitepomme.net/cwn/2007.09.04.html Peng ... Version: GnuPG v2.0.7 (GNU/Linux)
      Message 2 of 5 , Apr 16, 2009
      • 0 Attachment
        -----BEGIN PGP SIGNED MESSAGE-----
        Hash: SHA1

        First google hit =]

        http://alan.petitepomme.net/cwn/2007.09.04.html

        Peng


        On Thursday 16 April 2009 12:27:13 pm citromatik wrote:
        > Hi all,
        >
        > Does anybody know of any high-performance
        > http://en.wikipedia.org/wiki/Suffix_tree suffix tree implementation in
        > OCaml?
        > Naive implementations are also welcome. I need a fast algorithm to compare
        > strings allowing errors, so any other implementation of approximate string
        > matching is also welcome.
        >
        > Thanks in advance,
        >
        > M;
        -----BEGIN PGP SIGNATURE-----
        Version: GnuPG v2.0.7 (GNU/Linux)

        iD8DBQFJ5130fIRcEFL/JewRAtZqAKCEt8it+WHXXHnTexYAgIxLfxUVfACgqtuO
        auGqJXvXOCupkmTZ1YcmCWI=
        =W/gI
        -----END PGP SIGNATURE-----
      • citromatik
        ... Yes, I have already checked that before. This implementation relies on several other modules from the author and is a bit complicated to follow it. That is
        Message 3 of 5 , Apr 16, 2009
        • 0 Attachment
          Peng Zang wrote:
          >
          > -----BEGIN PGP SIGNED MESSAGE-----
          > Hash: SHA1
          >
          > First google hit =]
          >
          > http://alan.petitepomme.net/cwn/2007.09.04.html
          >
          > Peng
          >
          >
          > On Thursday 16 April 2009 12:27:13 pm citromatik wrote:
          >> Hi all,
          >>
          >> Does anybody know of any high-performance
          >> http://en.wikipedia.org/wiki/Suffix_tree suffix tree implementation in
          >> OCaml?
          >> Naive implementations are also welcome. I need a fast algorithm to
          >> compare
          >> strings allowing errors, so any other implementation of approximate
          >> string
          >> matching is also welcome.
          >>
          >> Thanks in advance,
          >>
          >> M;
          > -----BEGIN PGP SIGNATURE-----
          > Version: GnuPG v2.0.7 (GNU/Linux)
          >
          > iD8DBQFJ5130fIRcEFL/JewRAtZqAKCEt8it+WHXXHnTexYAgIxLfxUVfACgqtuO
          > auGqJXvXOCupkmTZ1YcmCWI=
          > =W/gI
          > -----END PGP SIGNATURE-----
          >
          >

          Yes, I have already checked that before. This implementation relies on
          several other modules from the author and is a bit complicated to follow it.
          That is why I have asked for alternative implementations.

          Thanks anyway

          M;


          --
          View this message in context: http://www.nabble.com/Suffix-trees-tp23081534p23084986.html
          Sent from the Ocaml Beginner mailing list archive at Nabble.com.
        • Hugo Ferreira
          ... Don t know if this is of any help: Efficient Implementation of Lazy Suffix Trees http://www.zbh.uni-hamburg.de/pubs/pdf/GieKurSto1999.pdf Don t think it
          Message 4 of 5 , Apr 17, 2009
          • 0 Attachment
            citromatik wrote:
            > Hi all,
            >
            > Does anybody know of any high-performance
            > http://en.wikipedia.org/wiki/Suffix_tree suffix tree implementation in
            > OCaml?
            > Naive implementations are also welcome. I need a fast algorithm to compare
            > strings allowing errors, so any other implementation of approximate string
            > matching is also welcome.
            >
            > Thanks in advance,
            >
            > M;

            Don't know if this is of any help:

            Efficient Implementation of Lazy Suffix Trees
            http://www.zbh.uni-hamburg.de/pubs/pdf/GieKurSto1999.pdf

            Don't think it will work for aproximate matching though.

            Regards,
            Hugo F.
          • Jon Harrop
            ... Jean-Christophe Filliatre has a generic implementation that can be instantiated with different kinds of dictionary, IIRC. I played with it a few years ago
            Message 5 of 5 , Apr 20, 2009
            • 0 Attachment
              On Thursday 16 April 2009 17:27:13 citromatik wrote:
              > Hi all,
              >
              > Does anybody know of any high-performance
              > http://en.wikipedia.org/wiki/Suffix_tree suffix tree implementation in
              > OCaml?
              > Naive implementations are also welcome. I need a fast algorithm to compare
              > strings allowing errors, so any other implementation of approximate string
              > matching is also welcome.

              Jean-Christophe Filliatre has a generic implementation that can be
              instantiated with different kinds of dictionary, IIRC. I played with it a few
              years ago and it works but it over 10x slower than implementations in other
              languages.

              --
              Dr Jon Harrop, Flying Frog Consultancy Ltd.
              http://www.ffconsultancy.com/?e
            Your message has been successfully submitted and would be delivered to recipients shortly.