Lemma 9, p. 17 — at most 2rs distinct s-mers
ProvedGagieRIndex.Kmers.lemma_9burrows-wheeler-transformp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stringssubstring-complexity
Let be a text whose BWT has runs. For every integer with , the set of distinct substrings of length satisfies
This is the exact combinatorial bound on substring complexity underlying the paper's space claims for its text index.
Formalization Note The finite set counts each string once, even if it occurs in many windows. Windows may end at the unique terminator. The suffix array is a sorted permutation of positions; the BWT and are computed from it.
Preamble
import Mathlib import Definitions.Def_GagieRIndex_Kmers_Smers
Formal statement
namespace GagieRIndex.Kmers
theorem lemma_9 (n σ : ℕ) (T SA : ℕ → ℕ)
(hT : GagieRIndex.Locate.IsText n σ T) (hSA : GagieRIndex.Locate.IsSuffixArray n T SA)
(s : ℕ) (hs1 : 1 ≤ s) (hsn : s ≤ n) :
(smers n T s).card ≤ 2 * GagieRIndex.Locate.runs n T SA * s := by sorry
end GagieRIndex.Kmers
Source
Gagie, Navarro, Prezza, Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space, arXiv:1809.02792v2, p. 17, Lemma 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.