cfpb/regulations-parser — pull request #249 by cmc333333 (2014-04-24 17:38:01+00:00)
Title: Constraint programming for regtext paragraph markers

This introduces a rule-based approach to deciphering paragraph marker depths and applies it to regtext paragraph markers.

Until this point, we've had ad hoc heuristics (one set for regtext, one for interpretations, one for appendices) that decided where in the tree each paragraph should be placed. This works out pretty well, but spawns some random issues, particularly around ambiguous markers like "i" and "v".

The proposed approach instead describes the order via constraints/rules. These rules effectively describe "good" solutions from "bad" solutions. We then provide a list of paragraph markers and let the constraint engine find all possible solutions. To pre-empt some concerns: the algorithms that resolve these constraints are smarter than simple brute-force -- though that was effectively what we did before.

The rules are instanced in derive_depths.py and described in rules.py. They amount to
1. the first marker must be at depth 0
2. the type an index of each marker must correspond to a known marker type and index (e.g. "i" can be either lower[8] or roman[0])
3. rules around pairs of the same type (e.g. if a lower-case letter is followed by another, they should be in sequence, like "a" then "b", not "a" then "i")
4. rules around pairs of different type (changing marker type indicates the tree depth must also change in some way)
5. paragraphs at the same level must be of the same marker type (as long as they share a parent)
6. stars (i.e. skipped text) can't be placed where they'd separate two adjacent paragraphs (e.g. 1, *, 2 doesn't make sense)

After rules are applied, heuristics are applied which help rank the possible solutions.