nx_sequence_fm.nx

nx_sequence_fm.nx -- FM-index construction + backward-search count. license_tier: INDEPENDENT_REDERIVE genealogy_id: international-research-sources/ferragina-manzini-2000 G0.3 of NISHI_GENOMICS_SUBSTRATE_ROADMAP.md. Built bits-up against the Ferragina-Manzini construction: 1. Suffix array SA of T (where T ends in a unique sentinel '$'). G0.3 uses a naive O(n^2 log n) insertion sort over suffix indices, lexicographically comparing the suffixes. Correct reference behaviour; SA-IS fast path is G0.5. 2. Burrows-Wheeler Transform: BWT[i] = T[(SA[i] - 1) mod n]. 3. C array: C[c] = number of bytes in BWT lexicographically smaller than c (0..255 entries; cumulative histogram). 4. Backward search (Ferragina-Manzini fm_count algorithm): c <- P[plen-1] lo <- C[c] hi <- C[c+1] - 1 for i = plen-2 downto 0: c <- P[i] lo <- C[c] + Occ(c, lo - 1) + 1 hi <- C[c] + Occ(c, hi) if lo > hi: return 0 return hi - lo + 1 where Occ(c, i) = count of byte c in BWT[0..i] inclusive. G0.3 recomputes Occ by walking BWT each query (O(plen * n)); the sampled-Occ wavelet-tree fast path is G0.5. Sentinel convention: Caller passes T with a trailing $ byte (0x24) which must not appear elsewhere in T. All construction + query helpers assume the sentinel is in place and is the lexicographically smallest byte present. fm_check_sentinel returns -1 if the convention is violated -- callers should run it once before fm_build_sa. API: fm_check_sentinel(t, n) -> i64 0 ok / -1 bad fm_build_sa(t, n, sa_out) -> i64 fm_build_bwt(t, n, sa, bwt_out) -> i64