tag

#string-processing

7 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

DC3 Suffix Array Sort

DC3 Suffix Array Sort DC3 suffix array sort is the concrete formulation of the skew algorithm based on a difference cover modulo 3. It builds the suffix array in linear time by sorting a subset of suffixes, assigning them ranks, and merging with the remaining suffixes. It is widely used in high-performance string processing systems. Problem Given a string $S$ of length $n$, construct the suffix array: $$ SA =...
algorithms sorting string-processing suffix-array dc3
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

SA IS

SA IS SA IS is a linear-time suffix array construction algorithm. It sorts a carefully chosen subset of suffixes, called LMS suffixes, then induces the order of all remaining suffixes from them. It is one of the standard practical algorithms for building suffix arrays in linear time. Problem Given a string $S$ of length $n$, construct its suffix array: $$ SA = \text{sorted indices of all suffixes of } S...
algorithms sorting string-processing suffix-array sa-is
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Skew Suffix Array Sort

Skew Suffix Array Sort Skew suffix array sort, also known as the DC3 algorithm, constructs a suffix array in linear time by recursively sorting a subset of suffixes whose positions are not divisible by 3. The remaining suffixes are then merged using the already computed order. Problem Given a string $S$ of length $n$, construct its suffix array: $$ SA = \text{sorted indices of all suffixes of } S $$...
algorithms sorting string-processing suffix-array dc3
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Suffix Array Radix Sort

Suffix Array Radix Sort Suffix array radix sort is the radix-optimized version of the suffix array doubling method. It still sorts suffixes by rank pairs, but uses counting sort or radix sort instead of comparison sorting. This reduces each doubling round from comparison sorting over pairs to linear sorting over integer ranks. Problem Given a string $S$ of length $n$, construct the suffix array: $$ SA = \text{sorted indices of...
algorithms sorting string-processing suffix-array radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Induced Sorting

Induced Sorting Induced sorting is a technique used to construct suffix arrays in linear time. Instead of sorting all suffixes directly, it sorts a subset of suffixes and then induces the order of the remaining ones. This idea forms the foundation of modern linear-time suffix array algorithms such as SA-IS. Problem Given a string $S$ of length $n$, construct the suffix array: $$ SA = \text{sorted indices of all suffixes...
algorithms sorting string-processing suffix-array induced-sorting
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Suffix Array Doubling Sort

Suffix Array Doubling Sort Suffix array doubling sort builds a suffix array by repeatedly sorting suffixes based on prefixes of length (2^k). Each step uses previously computed ranks to compare longer prefixes efficiently. This method avoids direct string comparison and reduces the problem to sorting integer pairs. Problem Given a string (S) of length (n), construct the suffix array: $$ SA = \text{sorted indices of all suffixes of } S...
algorithms sorting string-processing suffix-array
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

DC7 Suffix Array Sort

DC7 Suffix Array Sort DC7 suffix array sort is a linear-time suffix array construction method based on a difference cover modulo 7. It generalizes the DC3 idea by sorting a larger sampled subset of suffixes, then using the resulting ranks to sort and merge the remaining suffixes. The method is mostly of theoretical and specialist interest. DC3 and SA-IS are more common in practice. Problem Given a string $S$ of...
algorithms sorting string-processing suffix-array dc7