FIT3155: Lab questions for week 4 (Based on previous week 03 topic)
Objectives: Understanding Ukkonen¡¯s algorithm for suffix tree construction. Notes: It is advised that you implement Ukkonen¡¯s algorithm step-by-step as sug- gested below. After each step, test your implementation on simple string inputs.
1. ImplementUkkonen¡¯salgorithmforsuffixtreeconstructionwithoutany optimizations/speed-ups/tricks. (Refer to slide 17 from your lecture slides.)
2. Before anything, ensure your implementation uses the space-efficient representation for edge-labels. (Refer slide 29.)
Copyright By PowCoder代写 加微信 powcoder
3. Extend the above implementation by computing the suffix links during each phase. (Refer slide 22-23.)
4. Add further, the ability to traverse via the suffix links during suffix extensions in any given phase. (Refer slides 24-28.)
5. Enhance this implementation using the ¡®skip/count¡¯ trick. (Refer slide 30.)
6. Add to this, the premature stopping criterion. (Refer slide 31.)
7. Improve this further to handle rapid leaf extensions. (Refer slides 32- 36.)
8. Finally, extend this to generate the explicit suffix tree from the implicit suffix tree you have computed for the input string. ( This involves a new suffix extension phase, which extends all the suffixes in the implicit suffix tree by the terminal ¡®$¡¯ character). (Refer slide 37.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com