Page 68 - 2024S

UEC Int’l Mini-Conference No.52 61

Implementation of the Sliding Window Suffix Tree

Construction and Its Applications

1
Leon FLAACK and Prof. Takuya MIENO 2
1 UEC Exchange Study Program (JUSST Program)
2 Department of Computer and Network Engineering
The University of Electro-Communications, Tokyo, Japan

Keywords: Suffix Tree, String Matching, Online Matching, Sliding Window Construction, Leaf Point-
ers.

Abstract

The Sliding Window Suffix Tree is a data structure that is designed to address some of the problems
of classic Suffix Trees, such as the large space consumption with increasing input string size and the
difficulty of adding further characters. By utilizing and maintaining leaf pointers in the construction of
this Sliding Window Suffix Tree, this approach makes the construction and maintenance of the Suffix
Tree within the sliding window more efficient and intuitive. Using this method allows for piecewise
updates of the Tree and especially the edge labels as the window shifts, avoiding the need for a complete
rebuild or a relabeling of edges that a classical Suffix Tree might have. This research presents the
implementation of this approach to Sliding Window Suffix Trees by Leonard et al.