Re: [Gperf-bugs] Revised gperf 2.7.2 patch

[Bruce Lilly]

Bruno Haible wrote:

> Can you explain what the distinction between
>   2: key position might be useful
>   3: key position uniquely identifies keywords of that length or longer
> brings in practice? I mean, in either case you can have several
> positions of the same type, and you don't know a priori which one to
> choose. So you need some form of backtracking anyway.

Consider the keyword set
foo
far
fat

Key position 1 has the same letter for all keywords so is not useful.
Key position 2 has the same letter for two of the keywords. In some
keyword sets, that might be useful as part of a key position set (but
not in this example).  Key position 3 has a different letter for each
keyword in the set; it therefore suffices to use only that key position
in hash computations for this keyword set -- key position 3 alone is
the minimal (optimal) key position set for hash computation for this
keyword set.

If keyword "fao" is added to the above set, key position 3 no longer
uniquely identifies keywords. Both positions 2 and 3 are potentially
useful in differentiating keywords, and in fact the combination of
positions 2 and 3 is the minimal key position set for that expanded
keyword set.