This repository contains an implementation of suffix trees extracted from LLVM, with dependencies on other parts of LLVM removed. This allows the compilation scope to be restricted to only the core files.
During practical use, I observed that the implementation incurs significant build overhead when handling large-scale input sets. This overhead is particularly evident in terms of wall time, CPU cycles, and peak memory usage. Although removing the external dependencies mitigates some of this overhead, there remains considerable room for optimization in the design itself.
Such overhead presents a major challenge for deployment on resource-constrained devices. A typical scenario is Android's Ahead-of-Time (AOT) compilation: if this method is used to reduce the size of OAT files on the target devices, the high build overhead becomes a critical concern for mobile devices with limited resources.
To address this, I introduced several optimizations that transform the current suffix tree implementation into a lightweight structure suitable for resource-limited devices. The key theoretical improvements focus on node pruning and compression within the suffix tree, as well as leveraging the partial order relationships inherent in the tree to reduce the search space—particularly for the selection of redundant sequences.