Suffix tree help!

This is a discussion on Suffix tree help! within the C Programming forums, part of the General Programming Boards category; Hi, I'm a first yr Software Eng student & is finding it a difficulty implementing suffix trees. I only know ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    51

    Suffix tree help!

    Hi,
    I'm a first yr Software Eng student & is finding it a difficulty implementing suffix trees. I only know binary search trees...
    Been looking for an example code on the node structure & tree particullarly, and especially the insertion of nodes and traversing, but i can only find one website
    http://mila.cs.technion.ac.il/~yona/.../suffix_tree.c

    However, i don't quite understand .... I wanna store a string and lists the string & its substrings...

    Help!

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,849
    http://www.nist.gov/dads/HTML/suffixtree.html

    > I wanna store a string and lists the string & its substrings
    So look at each letter in your word, follow the branch which refers to that letter (or create it), then follow that branch with the remainder of the string.

    Post your own code, not someone elses.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    51
    gee...thx for the link!

    Will check out da code

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    51
    concerning suffix trees -> Ukkonen's , Weiner's algorithms, are they something that u would normally write by urself or just rip it of somewhere like hash functions ?

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Well you'll get a better understanding of it if you write your own. It depends on what your intent is really. Get it done fast? Use a library of code. Learn? Write your own. Something else? Make up your own answer!


    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    51
    ok...so i'm burdened with a programming project.
    It's about extracting DNA seqs from a jumbled up file, letters G,A, T and C...
    list all the substrings of the extracted strand and print its frequency alongside...

    I've thought of suffix trees and recently discovered suffix arrays....

    So, which one would be more appropriate?
    I've heard tht suffix arrays consumes less memory, but how about the traversing/search time?

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,849
    > ok...so i'm burdened with a programming project.
    Gee, what did you expect when you enrolled as a "I'm a first yr Software Eng student ".
    You're going to get some more programming projects in the future.

    If you want to learn, then buckle down and do some work rather than surfing the net for half-baked answers and expecting others to fix those up for your own requirements.

    Or just drop the course now and find something else to do in life.

    > It's about extracting DNA seqs from a jumbled up file, letters G,A, T and C...
    It's an assignment we've seen before.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 06:59 PM
  2. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 09:09 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21