Project: audit text intervals, score bounds, rank models, and ancestor tours

Acceptance trace

In cabacaba, backward search for aba returns count two and offsets one and five. A five-document score index ranks document 21 at ten above document 19 at eight and skips three low-bound blocks. A sorted case catalog gives lower-bound rank three for target 60, rank five for 103, and rank nine beyond its maximum. The seven-depot Euler tour has thirteen entries; nodes two and six share node one as their lowest common ancestor and are four roads apart. Verify these outputs against direct suffix scans, full document scoring, ordinary bisect, and parent-path ancestry.

Failure and cost review

Use repeated text characters and overlapping patterns to test the FM interval, and reject a sentinel in text or query. Fuzz nonnegative document weights, absent terms, equal scores, and ID ties against exhaustive ranking; an upper bound equal to the current cutoff must remain searchable. Test interpolation targets at every key, every between-key gap, and beyond the endpoints. Generate random trees and compare sparse-table answers with a direct ancestor walk. Change one source snapshot after building each index and record its required rebuild; none of these four examples includes a live incremental update protocol. Report Python memory separately from compact-index theory.

Common Mistakes

• Do not present full FM rank arrays as compressed storage.
• Do not skip an equal-bound block when a smaller document ID can win a tie.
• Do not use a predicted rank without exact correction.
• Do not compare depot IDs instead of depths in Euler range minimum queries.

Connected lessons

• FM-index backward search: narrow a suffix interval by character
• Block-max postings: skip safe document-score regions
• Piecewise interpolation indexes: predict a bounded rank window
• Euler-tour RMQ: answer static common ancestors in constant query time
• Projects
• Quizzes
• Data Structures