Patent ID: 8914415
Filing Date: 2014-12-16
Classification: G06F

Abstract:
1. A method for building a suffix tree for a string of text or data of size n, said method comprising: providing a processing device having an associated memory storage device, allocating a fixed amount of memory within said associated memory storage device for storing an output sub-tree of the suffix tree and a portion of the input string during suffix tree building, wherein the length n of said input string exceeds the allocated fixed memory amount; constructing, using said processing device, a set of prefixes (p) for said input string; building a suffix sub-tree (T accessing a sub-string block i; inserting each suffix starting with the prefix p into the suffix tree such that the input string references from the edges in the partially constructed suffix sub-tree lie in the i iteratively accessing each remaining equal sized sub-string block j>i of said plurality, one sub-string block at a time, to process suffixes in each block starting with said prefix (p) that have a string index in said equal sized block i and inserting those suffixes in said tree such that during suffix sub-tree building at each iteration, said equal sized sub-string blocks being referenced by said partially constructed suffix sub-tree, and said suffixes being inserted into the sub-tree are maintained within said fixed memory amount and reused; and, merging said suffix sub-trees to form said suffix tree.