Suffix arrays in O(n), via SA-IS — from text or from bytes.
part of dear — small Swift libraries from obscure tools.
.package(url: "https://github.com/obscure-tools/dear-sais.git", from: "1.0.0").product(name: "DearSAIS", package: "dear-sais")import DearSAIS
SuffixArray.from(string: "banana") // [5, 3, 1, 0, 4, 2]
SuffixArray.from(Array("banana".utf8)) // [5, 3, 1, 0, 4, 2]The result is the starting index of every suffix, in sorted order. For
banana, suffix 5 is a, suffix 3 is ana, suffix 1 is anana, and so on.
Because the suffixes are sorted, every occurrence of a needle occupies one contiguous run of the array, so substring search becomes a binary search:
let haystack = Array("banana".utf8)
let needle = Array("ana".utf8)
let sa = SuffixArray.from(haystack)
var lo = 0, hi = sa.count
while lo < hi {
let mid = (lo + hi) / 2
if haystack[sa[mid]...].lexicographicallyPrecedes(needle) { lo = mid + 1 } else { hi = mid }
}
let matches = sa[lo...].prefix { haystack[$0...].starts(with: needle) }
Array(matches).sorted() // [1, 3]SA-IS classifies each suffix as S (smaller than its successor) or L (larger), sorts only the left-most S suffixes, and induces the position of everything else from those — recursing on a reduced problem that is at most half the size. Total cost is linear.
The naive alternative sorts all n suffixes against each other at O(n × log n), with each comparison itself potentially O(n).
Ported to idiomatic Swift from Chromium's zucchini.
Suffix arrays underpin binary diffing. This one was written for a bsdiff-style patcher that ships low-footprint over-the-air updates to the dictionaries in an electronic dictionary app.
Roughly a millisecond for 5 KiB of random bytes on an M1 Pro — enough to say the constant factor is small, not enough to quote to two decimal places. Measure on your own data and hardware:
swift test --filter Performance -Xswiftc -OThe -O is not optional. Debug builds of this code are slower by an order of
magnitude and tell you nothing.
Swift 6 · macOS 10.15+ · iOS 15+ · tvOS 15+ · watchOS 8+ · visionOS 1+ · Linux
Open an issue before a pull request — see CONTRIBUTING.md.
MIT-0 — MIT with the attribution clause removed. Use it, ship it, no credit required.