refer

unix v7是最后一个广泛发布的研究型UNIX版本

program processes about 1000 English words per processor second.
Unless the
.I \-k
option is used (and the input files are long enough for
it to take effect)
the output of
.I mkey 
is comparable in size to its input.
.PP
.B
Hash and invert.
.R
The
.I inv
program computes the hash codes and writes
the inverted files.
It reads the output of
.I mkey
and writes the set of files described earlier
in this section.
It expects one argument, which is used as the base name for
the three (or four) files to be written.
Assuming an argument of
.I Index
(the default)
the entry file is named
.I Index.ia ,
the posting file
.I Index.ib ,
the tag file
.I Index.ic ,
and the key file (if present)
.I Index.id .
The
.I inv
program recognizes the following options:
.TS
center;
lB lw(4i).
\-a	T{
Append the new keys to a previous set of inverted files,
making new files if there is no old set using the same base name.
T}
\-d	T{
Write the optional key file.
This is needed when you can not check for false drops by looking
for the keys in the original inputs, i.e. when the key derivation
procedure is complicated and
the output keys are not words from the input files.
T}
\-h\f2n	T{
The hash table size is
.I n
(default 997);
.I n
should be prime.
Making \f2n\f1 bigger saves search time and spends disk space.
T}
\-i[u] \f2name	T{
Take input from file
.I name ,
instead of the standard input;
if
.B u
is present
.I name
is unlinked when the sort is started.
Using this option permits the sort scratch space
to overlap the disk space used for input keys.
T}
\-n	T{
Make a completely new set of inverted files, ignoring
previous files.
T}
\-p	T{
Pipe into the sort program, rather than writing a temporary
input file.
This saves disk space and spends processor time.
T}
\-v	T{
Verbose mode; print a summary of the number of keys which
finished indexing.
T}
.TE
.PP
About half the time used in
.I inv
is in the contained sort.
Assuming the sort is roughly linear, however,
a guess at the total timing for
.I inv
is 250 keys per second.
The space used is usually of more importance:
the entry file uses four bytes per possible hash (note
the
.B \-h
option),
and the tag file around 15-20 bytes per item indexed.
Roughly, the posting file contains one item for each key instance
and one item for each possible hash code; the items are two bytes
long if the tag file is less than 65336 bytes long, and the
items are four bytes wide if the tag file is greater than
65536 bytes long.
To minimize storage, the hash tables should be
over-full;
for most of the files indexed in this way, there is no
other real choice, since the
.I entry
file must fit in memory.
.PP
.B
Searching and Retrieving.
.R
The
.I hunt
program retrieves items from an index.
It combines, as mentioned above, the two parts of phase (B):
search and delivery.
The reason why it is efficient to combine delivery and search
is partly to avoid starting unnecessary processes, and partly
because the delivery operation must be a part of the search
operation in any case.
Because of the hashing, the search part takes place in two stages:
first items are retrieved which have the right hash codes associated with them,
and then the actual items are inspected to determine false drops, i.e.
to determine if anything with the right hash codes doesn't really have the right
keys.
Since the original item is retrieved to check on false drops,
it is efficient to present it immediately, rather than only
giving the tag as output and later retrieving the
item again.
If there were a separate key file, this argument would not apply,
but separate key files are not common.
.PP
Input to
.I hunt
is taken from the standard input,
one query per line.
Each query should be in
.I "mkey \-s"
output format;
all lower case, no punctuation.
The
.I hunt
program takes one argument which specifies the base name of the index
files to be searched.
Only one set of index files can be searched at a time,
although many text files may be indexed as a group, of course.
If one of the text files has been changed since the index, that file
is searched with
.I fgrep;
this may occasionally slow down the searching, and care should be taken to
avoid having many out of date files.
The following option arguments are recognized by
.I hunt:
.TS
center;
lB lw(4i).
\-a	T{
Give all output; ignore checking for false drops.
T}
\-C\f2n	T{
Coordination level
.I n;
retrieve items with not more than
.I n
terms of the input missing;
default
.I C0 ,
implying that each search term must be in the output items.
T}
\-F[yn\f2d\f3\|]	T{
``\-Fy'' gives the text of all the items found;
``\-Fn'' suppresses them.
``\-F\f2d\|\f1'' where \f2d\f1\| is an integer
gives the text of the first \f2d\f1 items.
The default is
.I \-Fy.
T}
\-g	T{
Do not use
.I fgrep
to search files changed since the index was made;
print an error comment instead.
T}
\-i \f2string	T{
Take
.I string
as input, instead of reading the standard input.
T}
\-l \f2n	T{
The maximum length of internal lists of candidate
items is
.I n;
default 1000.
T}
\-o \f2string	T{
Put text output (``\-Fy'') in
.I string;
of use
.I only
when
invoked from another program.
T}
\-p	T{
Print hash code frequencies; mostly
for use in optimizing hash table sizes.
T}
\-T[yn\f2d\|\f3]	T{
``\-Ty'' gives the tags of the items found;
``\-Tn'' suppresses them.
``\-T\f2d\f1\|'' where \f2d\f1\| is an integer
gives the first \f2d\f1 tags.
The default is
.I \-Tn .
T}
\-t \f2string	T{
Put tag output (``\-Ty'') in
.I string;
of use
.I only
when invoked from another program.
T}
.TE
.PP
The timing of
.I hunt
is complex.
Normally the hash table is overfull, so that there will
be many false drops on any single term;
but a multi-term query will have few false drops on
all terms.
Thus if a query is underspecified (one search term)
many potential items will be examined and discarded as false
drops, wasting time.
If the query is overspecified (a dozen search terms)
many keys will be examined only to verify that
the single item under consideration has that key posted.
The variation of search time with number of keys is
shown in the table below.
Queries of varying length were constructed to retrieve
a particular document from the file of references.
In the sequence to the left, search terms were chosen so as
to select the desired paper as quickly as possible.
In the sequence on the right, terms were chosen inefficiently,
so that the query did not uniquely select the desired document
until four keys had been used.
The same document was the target in each case,
and the final set of eight keys are also identical; the differences
at five, six and seven keys are produced by measurement error, not
by the slightly different key lists.
.TS
center;
c   s   s   s5  | c   s   s   s
cp8 cp8 cp8 cp8 | cp8 cp8 cp8 cp8
cp8 cp8 cp8 cp8 | cp8 cp8 cp8 cp8
n   n   n   n   | n   n   n   n  .
Efficient Keys	Inefficient Keys
No. keys	Total drops	Retrieved	Search time	No. keys	Total drops	Retrieved	Search time
	(incl. false)	Documents	(seconds)		(incl. false)	Documents	(seconds)
1	15	3	1.27	1	68	55	5.96
2	1	1	0.11	2	29	29	2.72
3	1	1	0.14	3	8	8	0.95
4	1	1	0.17	4	1	1	0.18
5	1	1	0.19	5	1	1	0.21
6	1	1	0.23	6	1	1	0.22
7	1	1	0.27	7	1	1	0.26
8	1	1	0.29	8	1	1	0.29
.TE
As would be expected, the optimal search is achieved
when the query just specifies the answer; however,
overspecification is quite cheap.
Roughly, the time required by
.I hunt
can be approximated as
30 milliseconds per search key plus 75 milliseconds
per dropped document (whether it is a false drop or
a real answer).
In general, overspecification can be recommended;
it protects the user against additions to the data base
which turn previously uniquely-answered queries
into ambiguous queries.
.PP
The careful reader will have noted an enormous discrepancy between these times
and the earlier quoted time of around 1.9 seconds for a search.  The times
here are purely for the search and retrieval: they are measured by
running many searches through a single invocation of the
.I hunt
program alone.
Usually, the UNIX command processor (the shell) must start both
the
.I mkey
and
.I hunt
processes for each query, and arrange for the output of
.I mkey
to be fed to
the
.I hunt
program.
This adds a fixed overhead of about 1.7 seconds
of processor time
to any single search.
Furthermore, remember that all these times are processor times:
on a typical morning on our \s-2PDP\s0 11/70 system, with about one dozen
people logged on,
to obtain 1 second of processor time for the search program
took between 2 and 12 seconds of real time, with a median of
3.9 seconds and a mean of 4.8 seconds.
Thus, although the work involved in a single search may be only
200 milliseconds, after you add the 1.7 seconds of startup processor
time
and then assume a 4:1 elapsed/processor time
ratio, it will be 8 seconds before any response is printed.
.NH
Selecting and Formatting References for T\s-2ROFF\s0
.PP
The major application of the retrieval software
is
.I refer,
which is a
.I troff
preprocessor
like
.I eqn .
.[
kernighan cherry acm 1975
.]
It scans its input looking for items of the form
.DS
\*.[
imprecise citation
\*.\^]
.DE
where an imprecise citation is merely a string
of words found in the relevant bibliographic citation.
This is translated into a properly formatted reference.
If the imprecise citation does not correctly identify
a single paper
(either
selecting no papers or too many) a message is given.
The data base of citations searched may be tailored to each
system, and individual users may specify their own
citation
files.
On our system, the default data base is accumulated from
the publication lists of the members of our organization, plus
about half a dozen personal bibliographies that were collected.
The present total is about 4300 citations, but this increases steadily.
Even now,
the data base covers a large fraction of local citations.
.PP
For example, the reference for the
.I eqn
paper above was specified as
.DS
\&\*.\*.\*.
\&preprocessor like
\&.I eqn.
\&.[
\&kernighan cherry acm 1975
\&.]
\&It scans its input looking for items
\&\*.\*.\*.
.DE
This paper was itself printed using
.I refer.
The above input text was processed by
.I refer
as well as
.I tbl
and
.I troff
by the command
.DS
.ft I
refer memo-file | tbl | troff \-ms
.ft R
.DE
and the reference was automatically translated into a correct
citation to the ACM paper on mathematical typesetting.
.PP
The procedure to use to place a reference in a paper
using
.I refer
is as follows.
First, use the
.I lookbib
command to check that the paper is in the data base
and to find out what keys are necessary to retrieve it.
This is done by typing
.I lookbib
and then typing some potential queries until
a suitable query is found.
For example, had one started to find
the
.I eqn
paper shown above by presenting the query
.DS
	$ lookbib
	kernighan cherry
	(EOT)
.DE
.I lookbib
would have found several items; experimentation would quickly
have shown that the query given above is adequate.
Overspecifying the query is of course harmless; it is even desirable,
since it decreases the risk that a document added to the publication
data base in the future will be retrieved in addition to the
intended document.
The extra time taken by even a grossly overspecified query is
quite small.
A particularly careful reader may have noticed that ``acm'' does not
appear in the printed citation;
we have supplemented some of the data base items with
extra keywords, such as common abbreviations for journals
or other sources, to aid in searching.
.PP
If the reference is in the data base, the query
that retrieved it can be inserted in the text,
between
.B \*.[
and 
.B \*.\^]
brackets.
If it is not in the data base, it can be typed
into a private file of references, using the format
discussed in the next section, and then
the
.B \-p
option
used to search this private file.
Such a command might read
(if the private references are called
.I myfile )
.DS
.ft 2
refer \-p myfile document | tbl | eqn | troff \-ms \*. \*. \*.
.ft 1
.DE
where
.I tbl
and/or
.I eqn
could be omitted if not needed.
The use
of the
.I \-ms
macros
.[
lesk typing documents unix gcos
.]
or some other macro package, however,
is essential.
.I Refer
only generates the data for the references; exact formatting
is done by some macro package, and if none is supplied the
references will not be printed.
.PP
By default,
the references are numbered sequentially,
and
the
.I \-ms
macros format references as footnotes at the bottom of the page.
This memorandum is an example of that style.
Other possibilities are discussed in section 5 below.
.NH
Reference Files.
.PP
A reference file is a set of bibliographic references usable with
.I refer.
It can be indexed using the software described in section 2
for fast searching.
What
.I refer
does is to read the input document stream,
looking for imprecise citation references.
It then searches through reference files to find
the full citations, and inserts them into the
document.
The format of the full citation is arranged to make it
convenient for a macro package, such as the
.I \-ms
macros, to format the reference
for printing.
Since
the format of the final reference is determined
by the desired style of output,
which is determined by the macros used,
.I refer
avoids forcing any kind of reference appearance.
All it does is define a set of string registers which
contain the basic information about the reference;
and provide a macro call which is expanded by the macro
package to format the reference.
It is the responsibility of the final macro package
to see that the reference is actually printed; if no
macros are used, and the output of
.I refer
fed untranslated to
.I troff,
nothing at all will be printed.
.PP
The strings defined by
.I refer
are taken directly from the files of references, which
are in the following format.
The references should be separated
by blank lines.
Each reference is a sequence of lines beginning with
.B %
and followed
by a key-letter.
The remainder of that line, and successive lines until the next line beginning
with
.B % ,
contain the information specified by the key-letter.
In general,
.I refer
does not interpret the information, but merely presents
it to the macro package for final formatting.
A user with a separate macro package, for example,
can add new key-letters or use the existing ones for other purposes
without bothering
.I refer.
.PP
The meaning of the key-letters given below, in particular,
is that assigned by the
.I \-ms
macros.
Not all information, obviously, is used with each citation.
For example, if a document is both an internal memorandum and a journal article,
the macros ignore the memorandum version and cite only the journal article.
Some kinds of information are not used at all in printing the reference;
if a user does not like finding references by specifying title
or author keywords, and prefers to add specific keywords to the