Journal of Systems Engineering and Electronics ›› 2009, Vol. 20 ›› Issue (5): 1104-1110.

• SOFTWARE ALGORITHM AND SIMULATION • Previous Articles     Next Articles

On-line linear time construction of sequential binary suffix trees

Lai Huoyao & Liu Gongshen   

  1. School of Information Security Engineering, Shanghai Jiaotong Univ., Shanghai 200240, P. R. China
  • Online:2009-10-22 Published:2010-01-03


Suffix trees are the key data structure for text string matching, and are used in wide application areas such as bioinformatics and data compression. Ukkonen algorithm is deeply investigated and a new algorithm, which decreases the number of memory operations in construction and keeps the result tree sequential, is proposed. The experiment result shows that both the construction and the matching procedure are more efficient than Ukkonen algorithm.