|
From: | Bruce Lilly |
Subject: | Re: [Gperf-bugs] Revised gperf 2.7.2 patch |
Date: | Thu, 21 Nov 2002 01:17:20 -0500 |
User-agent: | Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.2a) Gecko/20020910 |
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.
[Prev in Thread] | Current Thread | [Next in Thread] |