How Date Inference Works, and Why Ambiguity Is the Problem

dateinfer does one small thing: you hand it a list of date strings and it hands you back a strptime format string.

>>> import dateinfer
>>> dateinfer.infer(['2014-03-16', '2013-11-26'])
'%Y-%m-%d'

It’s a fun library to work on because the algorithm is simple enough to hold in your head, and the interesting failures all come from one place: dates are genuinely ambiguous, and some wrong answers are indistinguishable from right ones unless you know exactly where to look.

The algorithm

Four steps.

Tokenize. Each example is split into a sequence of tokens: runs of digits, runs of letters, and single non-alphanumeric separators. Jan 13, 2014 becomes ['Jan', ' ', '13', ',', ' ', '2014'].

Match candidates per slot. For each token position, every date element in the library’s catalog gets asked whether it could produce that token. 13 matches DayOfMonth (1 to 31), Hour24 (0 to 23), Minute, Second, and MonthNum if it were smaller. Jan matches MonthTextShort. Each element that matches gets a tally.

Score and pick. For each position, the element matching the largest fraction of examples wins. When two elements tie, a tie-break function picks the more restrictive one, on the reasonable theory that the narrower pattern is more informative.

Rewrite. A list of rules then rewrites suspicious sequences of chosen elements into more sensible ones. This is where the domain knowledge lives, and it’s the part that grows over time.

The tie is where the bugs live

Consider Jan 13, 2014.

The day slot contains 13. Both DayOfMonth and Hour24 match it perfectly, across every example, so the match fractions are identical and we’re in a tie. The tie-break picks by restrictiveness, and both have the same span of legal values in the overlapping range. So the winner comes down to which element appears first in the catalog, and Hour24 happens to precede DayOfMonth.

The result:

>>> dateinfer.infer(['Jan 13, 2014', 'Feb 21, 2013'])
'%b %H, %Y'

Now look at what that format does:

>>> datetime.strptime('Jan 13, 2014', '%b %H, %Y')
datetime.datetime(2014, 1, 1, 13, 0)

The day is discarded and replaced with 1, and an hour of 13 is invented. The wrong format parses without error. No exception, no warning, a perfectly well-formed datetime that is off by up to thirty days. This is the worst possible failure profile for an inference library, because every downstream consumer will believe it.

Fixing it with adjacency

The rewrite layer is the right place for this, because the information that resolves the ambiguity is not in the token, it’s in the neighbors. A number sitting immediately beside a textual month is a day of the month. Hours do not appear next to month names in any real format.

So the rules demote an Hour12 or Hour24 that sits immediately adjacent to a MonthTextShort or MonthTextLong into a DayOfMonth, in both orders, since Jan 13 and 13 Jan are both common. They follow the shape of rules that already existed for the numeric-month case, like MonthNum . Hour24.

Two properties keep these rules from eating a genuine hour:

Adjacency is strict. The pattern is month, one separator, number. In a format like %a %b %d %H:%M:%S %Z %Y, the real hour is separated from the month by the day slot, so the rule never matches it.

Order within the rule list matters. These rules sit after the rules that split H:M:S groups and after the duplicate-hour rule, both of which have already resolved the day slot in formats that contain a real time. Rule ordering is part of the semantics of this kind of system, which is worth stating explicitly in the code, because it looks like a flat list and behaves like a pipeline.

Why the test corpus missed it

dateinfer’s test suite is a corpus: a YAML file of real example sets with their expected formats. That’s a good way to test an inference library and it has a structural blind spot.

Every textual-month example in the corpus happened to use a day outside the 13 to 23 range. And that’s enough to hide the bug completely, because the tie never happens. A day of 24 or higher does not match Hour24 at all, so Hour24’s match fraction drops below DayOfMonth’s, and the scoring step resolves it before the tie-break is ever consulted.

Think about what that means. The bug is invisible for any example set containing at least one day above 23, which is most real datasets, because months have 31 days and real data spans them. The corpus was not unrepresentative of real data. It was unrepresentative of ambiguous data, which is a different and much harder thing to be representative of.

When your test suite is a corpus, coverage is a property of your data, not your code. Real examples cluster where real data clusters and systematically under-sample the ambiguity frontier, which is exactly where the algorithm makes decisions. So an inference library wants two suites: a corpus of real examples as a regression net, and a hand-built adversarial suite that walks the boundaries on purpose.

The adversarial cases for dates, for anyone building something similar:

• Day of month in 13 to 23, where day and hour are mutually consistent.
• Day of month in 1 to 12, where day and month are mutually consistent (03/04/2014).
• Year-first versus day-first numeric orderings with no four-digit year to anchor them.
• UTC offsets in every legal spelling: +00:00, +0000, Z, +00.
• Single-element example sets, where there is no cross-example signal at all.
• Empty input, which should be a clear error rather than a confusing downstream failure.

The general lesson

The thing I keep taking from this library into other work: in any system that infers a structure from examples, rank your hypotheses explicitly and treat enumeration order as a bug rather than a tie-break.

Hour24 beat DayOfMonth because of its position in a list, and nobody wrote that decision down as a decision. When the answer depends on an ordering that was never intended to carry meaning, you have a coin flip pretending to be a rule.

And the sharper version, which applies well beyond dates: the dangerous output of an inference system is the one that stays valid downstream. A format that raises on the first parse gets found in five minutes. A format that parses cleanly and returns the wrong day gets found in a quarterly report.