The challenge of direct parameterized suffix sorting (p-suffixsorting) for a parameterized string (p-string), say T of length-n, is the dynamic nature of the n parameterizedsuffixes (p-suffixes) of T. In this work, ...
详细信息
The challenge of direct parameterized suffix sorting (p-suffixsorting) for a parameterized string (p-string), say T of length-n, is the dynamic nature of the n parameterizedsuffixes (p-suffixes) of T. In this work, we propose transformative approaches to direct p-suffixsorting by generating and sorting lexicographically numeric fingerprints and arithmetic codes that correspond to individual p-suffixes. Our algorithm to p-suffix sort via fingerprints is the first theoretical linear time algorithm for p-suffixsorting for nonbinary parameter alphabets, which assumes that, in practice, all codes are within the range of an integral data type. We eliminate the key problems of fingerprints by introducing an algorithm that exploits the ordering of arithmetic codes to sort p-suffixes in linear time on average. The arithmetic coding approach is further extended to handle p-strings in the worst case. This algorithm is the first direct p-suffixsorting approach in theory to execute in o(n(2)) time in the worst case, which improves on the best known theoretical result on this problem that sorts p-suffixes based on p-suffix classifications in O(n(2)) time. We show that, based on the algorithmic parameters and the input data, our algorithm does indeed execute in linear time in various cases, which is confirmed with experimental results. (C) 2012 Elsevier B. V. All rights reserved.
The challenge of direct parameterized suffix sorting (p-suffixsorting) for a parameterized string (p-string) is the dynamic nature of parameterizedsuffixes (p-suffixes). In this work, we propose transformative appro...
详细信息
ISBN:
(纸本)9783642250101
The challenge of direct parameterized suffix sorting (p-suffixsorting) for a parameterized string (p-string) is the dynamic nature of parameterizedsuffixes (p-suffixes). In this work, we propose transformative approaches to direct p-suffixsorting by generating and sorting lexicographically numeric fingerprints and arithmetic codes that correspond to individual p-suffixes. Our algorithm to p-suffix sort via fingerprints is the first theoretical linear time algorithm for p-suffixsorting for non-binary parameter alphabets, which assumes that each code is represented by a practical integer. We eliminate the key problems of fingerprints by introducing an algorithm that exploits the ordering of arithmetic codes to sort p-suffixes in linear time on average.
暂无评论