[LUCENE-3121] FST should offer lookup-by-output API when output strictly increases

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 3.6, 4.0-ALPHA
• Component/s: core/other
• Lucene Fields: New
• Assignee: Michael McCandless
• Reporter: Michael McCandless
• Created: 19/May/11 10:15
• Updated: 28/Aug/22 12:47
• Resolved: 19/Jan/12 14:22

Description

Spinoff from "FST and FieldCache" java-dev thread http://lucene.markmail.org/thread/swoawlv3fq4dntvl

FST is able to associate arbitrary outputs with the sorted input keys, but in the special (and, common) case where the function is strictly monotonic (each output only "increases" vs prior outputs), such as mapping to term ords or mapping to file offsets in the terms dict, we should offer a lookup-by-output API that efficiently walks the FST and locates input key (exact or floor or ceil) matching that output.

Issue Links

• is depended upon by: LUCENE-3729 Allow using FST to hold terms data in DocValues.BYTES_*_SORTED