Re: Completion heuristics (was Re: bug in _rpm?)

[Sven Wischnowsky <wischnow@informatik.hu-berlin.de>]

Bart Schaefer wrote:

> On Sep 17, 10:45am, Sven Wischnowsky wrote:
> } Subject: Re: bug in _rpm?
> }
> } >   % rpm -ihv /usr/src/redhat/RPMS/i386/<TAB>
> } >   % rpm -ihv /usr/src/redhat/RPMS/i386/--
> } >   zsh: do you wish to see all 28 possibilities? 
> } > 
> } > Where did that `--' come from?
> } 
> } Do you have many files in that directory, all of the form `*-*-*'
> 
> He must.  That's what RPM file names look like.

I know, that one wasn't meant that serious.

> In this situation the amount of information and typing assistance that
> is provided by inserting any ambiguous string at all is so small as to
> be merely confusing.  The whole point of ambigous string insertion is
> that the human is supposed to be better than zsh at resolving the
> ambiguity, which ceases to be true below a certain information-content
> threshold.

[unambiguous]

Yes, in fact, I've already been thinking in the same direction after
the latest discussion.

> Better cursor placement would only help a little, and I think in this
> example not at all.

Well, if done right... see below.

> One approach would be to figure out some heuristic for determining that
> the ambiguous string "looks enough like" an element of the set of possible
> matches, and not insert it at all if it looks "too different."
> 
> A wild guess at such a heuristic:
> 
> 1.  There's exactly one choice for cursor placement to resolve the
>     ambiguity; OR
> 
> 2.  The ambiguous string shares a common (non-empty) prefix with ALL
>     of the possible matches; OR
> 
> 3.  The ambiguous string is at least half as long as the difference
>     between the lengths of the shortest match and the longest and at
>     least one-fourth as long as the length of the shortest.
> 
> Number (3) is obviously the wildest of the guesses.  I'd probably go with
> just the first two, but I don't rely on intra-word match-specs all that
> often, so I don't know exactly how to predict what's useful there.

I'm not so sure about (1) either. But I need play with different
implementations to be better able to think about this. Maybe at the
weekend.

> As for cursor placement:  Put it wherever the addition of a character
> would make the greatest difference in the number of matches; another
> way to say this is, place the cursor at the implicit * that matches the
> greatest number of alternatives.

That's what I tried to implement before 7630. The problem is that we
can't reliably calculate that information, as you thought.

> This may be beyond our ability to
> determine ... but the whole point of completion is to help the user
> reduce the set of alternatives from N to 1 as quickly as possible, so
> wherever will help throw out the most alternatives is the right place
> to ask for more input.

And that's what I've tried to achieve from the beginning. Remember the 
older discussions about cursor positioning? The completion code even
puts the cursor preferably in a position where the user can continue
by simply inserting something instead of having to type backspace-<char>.

The problem we have now is a problem at a lower level. How to find the 
best position between those that look equally interesting for the
completion code and if to insert string-parts for which there is
nothing on the line at all.

Bye
 Sven


--
Sven Wischnowsky                         wischnow@informatik.hu-berlin.de