Copyright | Joshua Simmons 2017 |
---|---|

License | BSD3 |

Maintainer | joshua.simmons@emptypath.com |

Stability | unstable |

Safe Haskell | Safe |

Language | Haskell2010 |

Internal implementation details, unstable and not to be relied upon for any reason.

# Documentation

A character in a string (or set of strings) we're going to compute the
suffix array of.
Includes `Sentinal`

markers for the end of strings.

naive :: Ord a => [[a]] -> [Int] Source #

A naively implemented suffix array implementation which will be used for correctness checking and possibly to benchmark against. Shouldn't usually be used in production code, as it is quite slow in the worst case. In cases with few identical suffixes, it can actually perform quite well. See benchmarks for some details.

worst case O(n^2 lg n) time (where n is the sum of the string lengths + the number of strings)

naiveOne :: Ord a => [a] -> [Int] Source #

Convenience wrapper around `naive`

for a single string.

worst case O(n^2 lg n) time (where n is the length of the string)

naiveLcp :: Ord a => [[a]] -> [Int] Source #

A naively implemented LCP implementation, used for correctness testing the actual algorithm.

The Longest Common Prefix list gives the longest common prefix of each suffix and the previous suffix, with the suffixes in lexicographic order.

worst case O(n^2 lg n) time (where n is the sum of the string lengths + the number of strings)

The LCP part is an extra O(n^2) in addition to the work of computing the suffix array in the first place.

naiveLcpOne :: Ord a => [a] -> [Int] Source #

Convenience wrapper around `naiveLcp`

for a single string.

worst case O(n^2 lg n) time (where n is the length of the string)

The LCP part is an extra O(n^2) in addition to the work of computing the suffix array in the first place.

prepareOne :: [a] -> [Alpha a] Source #

Convenience function to `prepare`

a single string.

rank :: Ord a => [a] -> [Int] Source #

Take a sorted list of elements and replace each value with an `Int`

such that any comparisons between elements in the original list would
yield exactly the same result in the output list.

i.e.: let rs = rank xs
in all [ (xs!!i) `compare`

(xs!!j) == (rs!!i) `compare`

(rs!!j)
| let idx = [0 .. length xs - 1], i <- idx, j <- idx
]