.\" @(#)refer 6.1 (Berkeley) 5/22/86
.... refer | tbl | nroff -ms
.EH 'USD:30-%''Some Applications of Inverted Indexes on the UNIX System'
.OH 'Some Applications of Inverted Indexes on the UNIX System''USD:30-%'
\".TM 77-1274-17 39199 39199-11
Some Applications of Inverted Indexes on the UNIX System
.\"I. Some Applications of Inverted Indexes \- Overview
.\"This memorandum describes a set of programs which
.\"make inverted indexes to
.\"retrieving and formatting citations for documents prepared using
.\"The indexing and searching programs make keyword
.\"indexes to volumes of material too large for linear searching.
.\"Searches for combinations of single words can be performed quickly.
.\"The programs for general searching are divided into
.\"two phases. The first makes an index from the original
.\"data; the second searches the index and retrieves
.\"Both of these phases are further divided into two parts
.\"to separate the data-dependent and algorithm dependent
.\"The major current application of these programs is
.\"A list of 4300 references is maintained on line,
.\"containing primarily papers written and cited by
.\"Whenever one of these references is required
.\"in a paper, a few words from the title or author list
.\"will retrieve it, and the user need not bother to re-enter
.\"Alternatively, authors can use their own lists of papers.
.\"This memorandum is of interest to
.\"those who are interested in facilities for searching large
.\"but relatively unchanging text files on
.\"and those who are interested in handling bibliographic
.\"II. Updating Publication Lists
.\"This section is a brief note describing the
.\"auxiliary programs for managing the updating
.\"It is written to aid clerical users in
.\"maintaining lists of references.
.\"Primarily, the programs described permit a large
.\"amount of individual control over the content
.\"of publication lists while retaining the
.\"usefulness of the files to other users.
.\"This section contains the pages from the
.\"UNIX programmer's manual
.\"dealing with these commands.
.\"It is useful for reference.
.\"* UNIX is a trademark of Bell Laboratories.
(e.g. \fIgrep, awk, lex, egrep, fgrep, ...\fR)
to search through files of text,
but most of them are based on a linear scan through the
entire file, using some deterministic automaton.
This memorandum discusses a program which uses inverted
%T The Art of Computer Programming: Vol. 3, Sorting and Searching
and can thus be used on much larger data bases.
As with any indexing system, of course, there are some disadvantages;
once an index is made, the files that have been indexed can not be changed
without remaking the index.
Thus applications are restricted
to those making many searches
of relatively stable data.
Furthermore, these programs depend on hashing, and can only
search for exact matches of whole keywords.
It is not possible to look for
arithmetic or logical expressions (e.g. ``date greater than 1970'') or
for regular expression searching such as that in
Currently there are two uses of this software,
preprocessor to format references,
command to search through all text files on
\(dd \fIlookall\fP is not part of the Berkeley UNIX distribution.
The remaining sections of this memorandum discuss
the searching programs and their uses.
Section 2 explains the operation of the searching algorithm and describes
the data collected for use with the
The more important application,
has a user's description in section 3.
Section 4 goes into more detail on
for the benefit of those who
wish to add references to data bases or
collect identical citations, or otherwise relocate and adjust references,
are described in section 5.
The indexing and searching process is divided into two phases,
Find keys \*(-- turn the input files into a sequence of tags and keys,
where each tag identifies a distinct item in the input
and the keys for each such item are the strings under which it is
prepare a set of inverted indexes from which, given a set of keys,
the appropriate item tags can be found quickly.
Retrieve an item in response to a query.
Given some keys, look through the files prepared by the hashing
and sorting facility and derive the appropriate tags.
Given the tags, find the original items. This completes the
The first phase, making the index, is presumably done relatively infrequently.
It should, of course, be done whenever the data being
In contrast, the second phase, retrieving items,
is presumably done often, and must be rapid.
An effort is made to separate code which depends on the data
being handled from code which depends on the searching procedure.
The search algorithm is involved only in programs
(2) and (3), while knowledge of the actual data files is
needed only by programs (1) and (4).
Thus it is easy to adapt to different data files or different
To start with, it is necessary to have some way of selecting
or generating keys from input files.
For dealing with files that are basically English, we have
a key-making program which automatically selects words
and passes them to the hashing and sorting program (step 2).
The format used has one line for each input item,
name:start,length (tab) key1 key2 key3 ...
is the starting byte number,
is the number of bytes in the entry.
These lines are the only input used to make the
The first field (the file name, byte position, and byte count)
and can be used to retrieve it quickly.
Normally, an item is either a whole file or a section of a file
delimited by blank lines.
After the tab, the second field contains the keys.
The keys, if selected by the automatic program, are
any alphanumeric strings which
are not among the 100 most frequent words in English
and which are not entirely numeric (except for four-digit
numbers beginning 19, which are accepted as dates).
Keys are truncated to six characters and converted to lower case.
Some selection is needed if the original items are very large.
We normally just take the first
less than 100 or so; this replaces any attempt at intelligent selection.
One file in our system is
a complete English dictionary; it would presumably be retrieved for all queries.
To generate an inverted index to the list of record tags and keys,
and sorted to produce an index.
What is wanted, ideally, is a series of lists showing the tags associated
what is actually produced is a list showing the tags associated
with each hash code, and thus with some set of keys.
To speed up access and further save space,
a set of three or possibly four files is produced.
entry Pointers to posting file
posting Lists of tag pointers for
The posting file comprises the real data: it contains a sequence of lists
of items posted under each hash code. To speed up searching,
the entry file is an array of pointers into the posting file, one per potential
Furthermore, the items in the lists in the posting file are not referred to by their
complete tag, but just by an address in the tag file, which
The key file is optional and contains a copy of the keys
The searching process starts with a query, containing several keys.
The goal is to obtain all items which were indexed under these keys.
The query keys are hashed, and the pointers in the entry file used
to access the lists in the posting file. These lists
are addresses in the tag file of documents posted under the
hash codes derived from the query.
The common items from all lists are determined;
this must include the items indexed by every key, but may also
contain some items which are false drops, since items referenced by
the correct hash codes need not actually have contained the correct keys.
Normally, if there are several keys in the query, there are not
likely to be many false drops in the final combined list even though
each hash code is somewhat ambiguous.
The actual tags are then obtained from the tag file, and to guard against
the possibility that an item has false-dropped on some hash code
in the query, the original items are normally obtained from the delivery
program (4) and the query keys checked against them
Usually, therefore, the check for bad drops is made against the original file.
However, if the key derivation procedure is complex, it may be preferable
to check against the keys fed to program (2).
In this case the optional key file which contains the
keys associated with each item is generated, and the item tag is supplemented
which indicates the starting byte number in the key file and the length of
the string of keys for each item.
This file is not usually necessary with the present
key-selection program, since the keys
always appear in the original document.
for coordination level searching.
This retrieves items which match all but
The items are retrieved in the order of the number
must be less than the number of query keys (nothing is
retrieved unless it matches at least one key).
As an example, consider one set of 4377 references, comprising
This included 51,000 keys, of which 5,900 were distinct
The hash table is kept full to save space (at the expense of time);
995 of 997 possible hash codes were used.
The total set of index files (no key file) included 171,000 bytes,
about 26% of the original file size.
It took 8 minutes of processor time to
hash, sort, and write the index.
To search for a single query with the resulting index took 1.9 seconds
while to find the same paper
with a sequential linear search
(reading all of the tags and keys)
took 12.3 seconds of processor time.
We have also used this software to index all of the English stored on our
This is the index searched by the
On a typical day there were
29,000 files in our user file system, containing about 152,000,000
5,300 files, containing 32,000,000 bytes (about 21%)
The total number of `words' (determined mechanically)
Of these 227,000 were selected as keys;
19,000 were distinct, hashing to 4,900 (of 5,000 possible) different hash codes.
resulting inverted file indexes used 845,000 bytes, or about
2.6% of the size of the original files.
The particularly small indexes are caused by the
fact that keys are taken from only the first 50 non-common words of
some very long input files.
Even this large \f2lookall\f1 index can be searched quickly.
For example, to find this document
``lesk inverted indexes''
1.7 seconds of processor time
By comparison, just to search the 800,000 byte dictionary (smaller than even
the inverted indexes, let alone the 27,000,000 bytes of text files) with
takes 29 seconds of processor time.
program is thus useful when looking for a document which you believe
is stored on-line, but do not know where. For example, many memos
from our center are in the file system, but it is often
difficult to guess where a particular memo might be (it might have several
authors, each with many directories, and have been worked on by
a secretary with yet more directories).
Instructions for the use of the
command are given in the manual section, shown
in the appendix to this memorandum.
The only indexes maintained routinely are those of publication lists and
To make other indexes, the programs for making keys, sorting them,
searching the indexes, and delivering answers must be used.
Since they are usually invoked as parts of higher-level commands,
they are not in the default command
directory, but are available to any user in the directory
Three programs are of interest:
which isolates keys from input files;
which makes an index from a set of keys;
which searches the index and delivers the items.
Note that the two parts of the retrieval phase are combined into
one program, to avoid the excessive system work and delay which
would result from running these as separate processes.
These three commands have a large number of options to adapt to different
The user not interested in the detailed description that now follows may
skip to section 3, which describes the
program, a packaged-up version of these tools specifically
oriented towards formatting references.
is the key-making program corresponding to step (1) in phase A.
Normally, it reads its input from the file names given as arguments,
and if there are no arguments it reads from the standard input.
It assumes that blank lines in the input delimit
separate items, for each of which a different line of
keys should be generated.
The lines of keys are written on the standard output.
Keys are any alphanumeric string in the input not
among the most frequent words in English and not entirely numeric
(except that all-numeric strings are acceptable if they
are between 1900 and 1999).
In the output, keys are translated to lower case, and truncated
to six characters in length; any associated punctuation is removed.
The following flag arguments are recognized by
Name of file of common words;
Read a list of files from
and take each as an input argument.
Ignore all lines which begin with `%' followed by any character
Ignore items shorter than
Ignore as a key any word in the first
words of the list of common English words.
from the output; just give the keys.
Used when searching rather than indexing.
Each whole file is a separate item;
blank lines in files are irrelevant.
The normal arguments for indexing references are
index of all English files is run,
When running on textual input,
program processes about 1000 English words per processor second.
option is used (and the input files are long enough for
is comparable in size to its input.
program computes the hash codes and writes
and writes the set of files described earlier
It expects one argument, which is used as the base name for
the three (or four) files to be written.
and the key file (if present)
program recognizes the following options:
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.
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.
Making \f2n\f1 bigger saves search time and spends disk space.
instead of the standard input;
is unlinked when the sort is started.
Using this option permits the sort scratch space
to overlap the disk space used for input keys.
Make a completely new set of inverted files, ignoring
Pipe into the sort program, rather than writing a temporary
This saves disk space and spends processor time.
Verbose mode; print a summary of the number of keys which
About half the time used in
is in the contained sort.
Assuming the sort is roughly linear, however,
a guess at the total timing for
The space used is usually of more importance:
the entry file uses four bytes per possible hash (note
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
Note that to minimize storage, the hash tables should be
for most of the files indexed in this way, there is no
other real choice, since the
Searching and Retrieving.
program retrieves items from an index.
It combines, as mentioned above, the two parts of phase (B):
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
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
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
If there were a separate key file, this argument would not apply,
but separate key files are not common.
is taken from the standard input,
all lower case, no punctuation.
program takes one argument which specifies the base name of the index
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
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
Give all output; ignore checking for false drops.
retrieve items with not more than
terms of the input missing;
implying that each search term must be in the output items.
``\-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.
to search files changed since the index was made;
print an error comment instead.
as input, instead of reading the standard input.
The maximum length of internal lists of candidate
Put text output (``\-Fy'') in
invoked from another program.
Print hash code frequencies; mostly
for use in optimizing hash table sizes.
``\-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.
Put tag output (``\-Ty'') in
when invoked from another program.
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
Thus if a query is underspecified (one search term)
many potential items will be examined and discarded as false
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.
cp8 cp8 cp8 cp8 | cp8 cp8 cp8 cp8
cp8 cp8 cp8 cp8 | cp8 cp8 cp8 cp8
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)
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
30 milliseconds per search key plus 75 milliseconds
per dropped document (whether it is a false drop or
In general, overspecification can be recommended;
it protects the user against additions to the data base
which turn previously uniquely-answered queries
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
The normal retrieval operation involves using the shell to
set up a pipeline through
and starting both processes; this adds a fixed overhead of about 1.7 seconds
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
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
and then assume a 4:1 elapsed/processor time
ratio, it will be 8 seconds before any response is printed.
Selecting and Formatting References for T\s-2ROFF\s0
The major application of the retrieval software
kernighan cherry acm 1975
It scans its input looking for items of the form
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
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
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.
the data base covers a large fraction of local citations.
For example, the reference for the
paper above was specified as
\&kernighan cherry acm 1975
\&It scans its input looking for items
This paper was itself printed using
The above input text was processed by
refer memo-file | tbl | troff \-ms
and the reference was automatically translated into a correct
citation to the ACM paper on mathematical typesetting.
The procedure to use to place a reference in a paper
command to check that the paper is in the data base
and to find out what keys are necessary to retrieve it.
and then typing some potential queries until
a suitable query is found.
For example, had one started to find
paper shown above by presenting the query
would have found several items; experimentation would quickly
have shown that the query given above is adequate.
Overspecifying the query is of course harmless.
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 common
extra keywords, such as common abbreviations for journals
or other sources, to aid in searching.
If the reference is in the data base, the query
that retrieved it can be inserted in the text,
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
used to search this private file.
Such a command might read
(if the private references are called
refer \-p myfile document | tbl | eqn | troff \-ms \*. \*. \*.
could be omitted if not needed.
lesk typing documents unix gcos
or some other macro package, however,
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.
the references are numbered sequentially,
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.
A reference file is a set of bibliographic references usable with
It can be indexed using the software described in section 2
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
The format of the full citation is arranged to make it
convenient for a macro package, such as the
macros, to format the reference
the format of the final reference is determined
by the desired style of output,
which is determined by the macros used,
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
nothing at all will be printed.
are taken directly from the files of references, which
are in the following format.
The references should be separated
Each reference is a sequence of lines beginning with
The remainder of that line, and successive lines until the next line beginning
contain the information specified by the key-letter.
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
The meaning of the key-letters given below, in particular,
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
citation, a field is available which is searched but not
The key letters currently recognized by
with the kind of information implied, are:
Key Information specified Key Information specified
A Author's name N Issue number
B Title of book containing item O Other information
C City of publication P Page(s) of article
D Date R Technical report reference
E Editor of book containing item T Title
G Government (NTIS) ordering number V Volume number
K Keys (for searching) X or
M Memorandum label Z Information not used by \f2refer\f1
For example, a sample reference could be
%T Bounds on the Complexity of the Maximal
Common Subsequence Problem
Order is irrelevant, except that authors are shown in the order
is a stream of string definitions, one
for each of the fields of each reference, as
\*.ds [A authors' names \*.\*.\*.
\*.ds [J journal \*.\*.\*.
precedes the string definitions
These are changed from the input
so that running the same file through
macro can be used by the macro package to
macro, which should be used
to print the reference, is given an
to indicate the kind of reference, as follows:
5 Bell Labs technical memorandum
The reference is flagged in the text
\e*\|([\*.number\e*\|(\*.\^]
should be used by the macro package
to format the reference flag in the text.
These strings can be replaced for a particular
footnote, as described in section 5.
The footnote number (or other signal) is available
In some cases users wish to suspend the searching, and merely
use the reference macro formatting.
That is, the user doesn't want to provide a search key
the reference lines for the appropriate document.
to add a few fields to those in the reference
as in the standard file, or
Altering or replacing fields, or supplying whole references, is easily done
by inserting lines beginning
any such line is taken as
direct input to the reference
processor rather than keys to be searched.
makes the indicated changes to the result of searching for
All of the search keys must be given before the first
If no search keys are provided, an entire citation can
be provided in-line in the text.
paper citation were to be inserted in
this way, rather than by searching for it in the data base,
\&%T A System for Typesetting Mathematics
\&It scans its input looking for items
This would produce a citation of the same appearance as that
resulting from the file search.
As shown, fields are normally turned into
Sometimes users would rather have them defined as macros,
commands can be placed into the data.
When this is necessary, simply double the control character
is defined as a macro to be invoked by
while the information after
is turned into a string to be invoked by
expects all information as strings.
Collecting References and other Refer Options
Normally, the combination of
footnotes which are consecutively numbered and placed
at the bottom of the page. However,
place the references at the end; to arrange references alphabetically
by senior author; and to indicate references by strings in the text of the form
Whenever references are not placed at the bottom of a page
identical references are coalesced.
specifies that references are to be collected; in this case
they are output whenever the sequence
Thus, to place references at the end of a paper, the user would run
option and place the above $LIST$ commands after the last
will then move all the references to that point.
To aid in formatting the collected references,
writes the references preceded by the line
to invoke special macros before and after the references.
Another possible option to
sorting of references. The default,
of course, is to list references in the order presented.
option, and thus requires
entry to call out the reference list.
option may be followed by a string of letters, numbers, and `+' signs indicating how
the references are to be sorted.
The sort is done using the fields whose key-letters are
in the string as sorting keys; the numbers indicate how many
of the fields are to be considered, with `+'
meaning ``Sort on senior author, then date.'' To
sort on all authors and then title, specify
And to sort on two authors and then the journal,
change the signal or label inserted in the text for each reference.
Normally these are just sequential numbers,
and their exact placement (within brackets, as superscripts, etc.) is determined
option replaces reference numbers by
strings composed of the senior author's last name, the date,
and a disambiguating letter.
only that many letters of the last name are used
To abbreviate the date as well the form
shortens the last name to the
letters and the date to the
paper (reference 3) by the signal
since it is the first cited reference by Kernighan in 1975.
A user wishing to specify particular labels for
a private bibliography may use the
causes the field \f2x\f1 to be used as a label.
If this field ends in \f3\-\f1, that character
is replaced by a sequence letter; otherwise the field
is used exactly as given.
option entirely suppresses automatic text signals.
If the user wishes to override the
treatment of the reference signal (which is normally to
enclose the number in brackets in
and make it a superscript in
contain anything following these characters,
the remainders of these lines are used to surround
the reference signal, instead of the default.
Thus, for example, to say ``See reference (2).''
``See reference.\s-3\u2\d\s+3'' the
Note that blanks are significant in this construction.
If a permanent change is desired in the style of reference
signals, however, it is probably easier to redefine the strings
(which are used to bracket each signal)
than to change each citation.
limits itself to retrieving the data for the reference,
and leaves to a macro package the job of arranging that
data as required by the local format, there are two
special options for rearrangements that can not be
option puts fields into all upper case
(C\s-2APS\s+2-S\s-2MALL\s+2 C\s-2APS\s+2
The key-letters indicated what information is to be translated
means that authors' names and journals are to be in caps.
option writes the names of authors last name first, that is
.I "Journal of the ACM" ,
for example, would require
This produces authors' names in the style
K\s-2ERNIGHAN\s0, B. W. \s-2AND\s0 C\s-2HERRY\s0, L. L.\&
for the previous example.
option may be followed by a number to indicate how many
author names should be reversed;
Kernighan, B. W. and L. L. Cherry,
Finally, there is also the previously-mentioned
option to let the user specify
a private file of references to be searched before the public files.
does not insist on a previously made index for these files.
If a file is named which contains reference
data but is not indexed, it will be searched
it is easy for users to keep small files of
new references, which can later be added to the
.SG MH-1274-MEL-\s8UNIX\s0