Proof of Lemma 9, p. 17 — at most 2r sampled positions
ProvedGagieRIndex.Kmers.sampled_cardburrows-wheeler-transformp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stringssubstring-complexity
Let be the number of runs in the BWT of , and let be the set of text positions corresponding to the first or last character of a run. Then
This count is used with Lemma 8 to bound the number of distinct length- substrings.
Formalization Note The set is an image of run-boundary BWT cells under the wrapped predecessor-position map. Repeated text positions are counted once.
Preamble
import Mathlib import Definitions.Def_GagieRIndex_Locate_Core
Formal statement
namespace GagieRIndex.Kmers
theorem sampled_card (n σ : ℕ) (T SA : ℕ → ℕ)
(hT : GagieRIndex.Locate.IsText n σ T) (hSA : GagieRIndex.Locate.IsSuffixArray n T SA) :
(GagieRIndex.Locate.sampled n T SA).card ≤ 2 * GagieRIndex.Locate.runs n T SA := 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, proof of Lemma 9, second sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.