Re: Apropos commands and regexps

[Kai Großjohann]

address@hidden (Kim F. Storm) writes:

> Wouldn't it be simpler (for a novice user -- and for advanced users
> too) to simply write one or more words (substrings) and then search
> for all combinations of those words (substrings) in the relevant list.

There has been a lengthy discussion on this.  Since my research area
is Information Retrieval, maybe I should say something about this...

IMHO, the long-term goal for searching the Emacs documentation should
look similar to the following:

The user enters a query.  The system searches items of documentation
and computes a score for each one.  Then the items with the highest
score come out first.

Now we need to decide on the query language (query format), and we
need to decide on the method of computing a score for each item of
documentation.

For the query language, I see these possibilities:

* List of words.

  Here, items containing all words will come out first, followed by
  items with all but one word, and so on.  The presence or absence of
  a very common word has less effect on the score than the presence
  or absence of an unusual word.  (Extreme example: if the user types
  "A B C" and there is only one item of documentation matching C but
  A and B are very common, then that item should come out first.)

* List of words, with optional "+" or "-" prefixes.

  The idea is that words prefixed with + must occur, whereas words
  prefixed with - must not occur.  The presence or absence of
  unprefixed words just raises/lowers the score, as in the first
  alternative.

* Boolean expression with parentheses and AND, OR, NOT connectives.

  Actually, these connectives just combine the individual scores.
  For example, if some item has score X w.r.t. query A and score Y
  w.r.t. query B, then the score for A AND B could be X * Y, the
  score for A OR B could be X + Y - (X * Y), and so on.  These
  formulas come from a probabilistic interpretation of the scores
  (which are assumed to be between 0 and 1).  But other useful
  formulas could be found, with different theoretical foundations.

Maybe people can suggest other possibilities.

And then we need to compute the scores for each individual "word" in
the query.  The Emacs documentation has a complex structure (for the
traditional Information Retrieval crowd anyway, who looks at
retrieving "documents" where each such document is just a sequence of
terms).  A number of rules come to my mind that might be useful to
implement:

* If the word occurs in a command/function/variable name, then the
  score should be higher than a match in the docstring (or other
  explanatory text) only.

* If the word does not occur at all, but a synonym of the word does,
  the item should match (perhaps with a lowered score).

* Instead of just synonyms, also consider more general terms,
  more specific terms, related terms.

* If the word does not occur, but a derived form does, then the item
  should match (perhaps with a lowered score).  So "mouse" should
  find "mice" and so on.  The Porter stemming algorithm appears to be
  a useful thing here.

* I guess that "igrep" should be considered a "derived form" of "grep"
  in the context of the Emacs documentation.  Do we do this with an
  explicit synonym list?  Or perhaps with a metric of similarity
  between terms which is based on editing distance or suchlike?

And then, there is the issue of where to look when searching.
Sometimes, people want to search in the docstrings, sometimes only in
the command names.

When searching in info files, some subdivision makes sense I think.
Should each node be considered a retrievable item, or is another
subdivision more sensible?

The above should be interpreted as a source of ideas.  I think I
would like to implement most of the mechanisms someday, but who knows
when I will be able to do that.  You just select from this something
which appears useful and implement that.  I haven't covered result
presentation at all, yet.

For instance, a cool replacement (complement?) for M-x apropos RET
could be something that splits the query and each Lisp symbol into
words.  So now the query is a set of words and the Lisp symbol is a
set of words.  The score for the Lisp symbol would be the number of
elements in the intersection of these two sets.  Sort the result by
decreasing score.  (Also offer to sort by name of symbol, while
displaying the score.)

What do you think?

kai
-- 
Silence is foo!