![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to refer CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / share / doc / usd / 30.invert|
Return to refer CVS log | Up to [CSRG BSD Unix] / 43BSDReno / share / doc / usd / 30.invert |
1.1 root 1: .\" @(#)refer 6.1 (Berkeley) 5/22/86
2: .\"
3: .... refer | tbl | nroff -ms
4: .EH 'USD:30-%''Some Applications of Inverted Indexes on the UNIX System'
5: .OH 'Some Applications of Inverted Indexes on the UNIX System''USD:30-%'
6: .nr LL 6.5i
7: .nr LT 6.5i
8: .de UC
9: \\s-2\\$1\\s0\\$2
10: ..
11: .ds . \&\s+2.\s0
12: .if t .ds -- \(em
13: .if n .ds -- --
14: .TR 69
15: \".TM 77-1274-17 39199 39199-11
16: .ND October 27, 1977
17: .ND June 21, 1978
18: .TL
19: Some Applications of Inverted Indexes on the UNIX System
20: .AU "MH 2C-572" 6377
21: M. E. Lesk
22: .AI
23: .MH
24: .\".AB
25: .\".LP
26: .\".ft B
27: .\"I. Some Applications of Inverted Indexes \- Overview
28: .\".ft R
29: .\".PP
30: .\"This memorandum describes a set of programs which
31: .\"make inverted indexes to
32: .\"UNIX*
33: .\"text files, and their
34: .\"application to
35: .\"retrieving and formatting citations for documents prepared using
36: .\".I troff.
37: .\".PP
38: .\"The indexing and searching programs make keyword
39: .\"indexes to volumes of material too large for linear searching.
40: .\"Searches for combinations of single words can be performed quickly.
41: .\"The programs for general searching are divided into
42: .\"two phases. The first makes an index from the original
43: .\"data; the second searches the index and retrieves
44: .\"items.
45: .\"Both of these phases are further divided into two parts
46: .\"to separate the data-dependent and algorithm dependent
47: .\"code.
48: .\".PP
49: .\"The major current application of these programs is
50: .\"the
51: .\".I troff
52: .\"preprocessor
53: .\".I refer.
54: .\"A list of 4300 references is maintained on line,
55: .\"containing primarily papers written and cited by
56: .\"local authors.
57: .\"Whenever one of these references is required
58: .\"in a paper, a few words from the title or author list
59: .\"will retrieve it, and the user need not bother to re-enter
60: .\"the exact citation.
61: .\"Alternatively, authors can use their own lists of papers.
62: .\".PP
63: .\"This memorandum is of interest to
64: .\"those who are interested in facilities for searching large
65: .\"but relatively unchanging text files on
66: .\"the
67: .\"UNIX
68: .\"system,
69: .\"and those who are interested in handling bibliographic
70: .\"citations with
71: .\"UNIX
72: .\".I troff.
73: .\".LP
74: .\".ft B
75: .\"II. Updating Publication Lists
76: .\".PP
77: .\"This section is a brief note describing the
78: .\"auxiliary programs for managing the updating
79: .\"processing.
80: .\"It is written to aid clerical users in
81: .\"maintaining lists of references.
82: .\"Primarily, the programs described permit a large
83: .\"amount of individual control over the content
84: .\"of publication lists while retaining the
85: .\"usefulness of the files to other users.
86: .\".LP
87: .\".ft B
88: .\"III. Manual Pages
89: .\".PP
90: .\"This section contains the pages from the
91: .\"UNIX programmer's manual
92: .\"dealing with these commands.
93: .\"It is useful for reference.
94: .\".sp
95: .\"\l'3i'
96: .\".br
97: .\"* UNIX is a trademark of Bell Laboratories.
98: .\".AE
99: .CS 10 4 14 0 0 4
100: .NH
101: Introduction.
102: .PP
103: The
104: .UX
105: system
106: has many utilities
107: (e.g. \fIgrep, awk, lex, egrep, fgrep, ...\fR)
108: to search through files of text,
109: but most of them are based on a linear scan through the
110: entire file, using some deterministic automaton.
111: .ev 1
112: .ps 8
113: .vs 10p
114: .ev
115: This memorandum discusses a program which uses inverted
116: indexes
117: .[
118: %A D. Knuth
119: %T The Art of Computer Programming: Vol. 3, Sorting and Searching
120: %I Addison-Wesley
121: %C Reading, Mass.
122: %D 1977
123: %O See section 6.5.
124: .]
125: and can thus be used on much larger data bases.
126: .PP
127: As with any indexing system, of course, there are some disadvantages;
128: once an index is made, the files that have been indexed can not be changed
129: without remaking the index.
130: Thus applications are restricted
131: to those making many searches
132: of relatively stable data.
133: Furthermore, these programs depend on hashing, and can only
134: search for exact matches of whole keywords.
135: It is not possible to look for
136: arithmetic or logical expressions (e.g. ``date greater than 1970'') or
137: for regular expression searching such as that in
138: .I lex.
139: .[
140: lex lesk cstr
141: .]
142: .PP
143: Currently there are two uses of this software,
144: the
145: .I refer
146: preprocessor to format references,
147: and the
148: .I lookall
149: command to search through all text files on
150: the
151: .UX
152: system.\(dd
153: .FS
154: \(dd \fIlookall\fP is not part of the Berkeley UNIX distribution.
155: .FE
156: .PP
157: The remaining sections of this memorandum discuss
158: the searching programs and their uses.
159: Section 2 explains the operation of the searching algorithm and describes
160: the data collected for use with the
161: .I lookall
162: command.
163: The more important application,
164: .I refer
165: has a user's description in section 3.
166: Section 4 goes into more detail on
167: reference files
168: for the benefit of those who
169: wish to add references to data bases or
170: write new
171: .I troff
172: macros for use with
173: .I refer.
174: The options to make
175: .I refer
176: collect identical citations, or otherwise relocate and adjust references,
177: are described in section 5.
178: .NH
179: Searching.
180: .PP
181: The indexing and searching process is divided into two phases,
182: each made of two parts.
183: These are
184: shown below.
185: .IP A.
186: Construct the index.
187: .RS
188: .IP (1)
189: Find keys \*(-- turn the input files into a sequence of tags and keys,
190: where each tag identifies a distinct item in the input
191: and the keys for each such item are the strings under which it is
192: to be indexed.
193: .IP (2)
194: Hash and sort \*(--
195: prepare a set of inverted indexes from which, given a set of keys,
196: the appropriate item tags can be found quickly.
197: .RE
198: .IP B.
199: Retrieve an item in response to a query.
200: .RS
201: .IP (3)
202: Search \*(--
203: Given some keys, look through the files prepared by the hashing
204: and sorting facility and derive the appropriate tags.
205: .IP (4)
206: Deliver \*(--
207: Given the tags, find the original items. This completes the
208: searching process.
209: .RE
210: .LP
211: The first phase, making the index, is presumably done relatively infrequently.
212: It should, of course, be done whenever the data being
213: indexed change.
214: In contrast, the second phase, retrieving items,
215: is presumably done often, and must be rapid.
216: .PP
217: An effort is made to separate code which depends on the data
218: being handled from code which depends on the searching procedure.
219: The search algorithm is involved only in programs
220: (2) and (3), while knowledge of the actual data files is
221: needed only by programs (1) and (4).
222: Thus it is easy to adapt to different data files or different
223: search algorithms.
224: .PP
225: To start with, it is necessary to have some way of selecting
226: or generating keys from input files.
227: For dealing with files that are basically English, we have
228: a key-making program which automatically selects words
229: and passes them to the hashing and sorting program (step 2).
230: The format used has one line for each input item,
231: arranged
232: as follows:
233: .DS
234: name:start,length (tab) key1 key2 key3 ...
235: .DE
236: where
237: .I name
238: is the file name,
239: .I start
240: is the starting byte number,
241: and
242: .I length
243: is the number of bytes in the entry.
244: .PP
245: These lines are the only input used to make the
246: index.
247: The first field (the file name, byte position, and byte count)
248: is the tag of the item
249: and can be used to retrieve it quickly.
250: Normally, an item is either a whole file or a section of a file
251: delimited by blank lines.
252: After the tab, the second field contains the keys.
253: The keys, if selected by the automatic program, are
254: any alphanumeric strings which
255: are not among the 100 most frequent words in English
256: and which are not entirely numeric (except for four-digit
257: numbers beginning 19, which are accepted as dates).
258: Keys are truncated to six characters and converted to lower case.
259: Some selection is needed if the original items are very large.
260: We normally just take the first
261: .I n
262: keys, with
263: .I n
264: less than 100 or so; this replaces any attempt at intelligent selection.
265: One file in our system is
266: a complete English dictionary; it would presumably be retrieved for all queries.
267: .PP
268: To generate an inverted index to the list of record tags and keys,
269: the keys
270: are hashed
271: and sorted to produce an index.
272: What is wanted, ideally, is a series of lists showing the tags associated
273: with each key.
274: To condense this,
275: what is actually produced is a list showing the tags associated
276: with each hash code, and thus with some set of keys.
277: To speed up access and further save space,
278: a set of three or possibly four files is produced.
279: These files are:
280: .KS
281: .bd 2 2
282: .TS
283: center;
284: c c
285: lI l.
286: File Contents
287: entry Pointers to posting file
288: for each hash code
289: posting Lists of tag pointers for
290: each hash code
291: tag Tags for each item
292: key Keys for each item
293: (optional)
294: .TE
295: .bd 2
296: .KE
297: The posting file comprises the real data: it contains a sequence of lists
298: of items posted under each hash code. To speed up searching,
299: the entry file is an array of pointers into the posting file, one per potential
300: hash code.
301: Furthermore, the items in the lists in the posting file are not referred to by their
302: complete tag, but just by an address in the tag file, which
303: gives the complete tags.
304: The key file is optional and contains a copy of the keys
305: used in the indexing.
306: .PP
307: The searching process starts with a query, containing several keys.
308: The goal is to obtain all items which were indexed under these keys.
309: The query keys are hashed, and the pointers in the entry file used
310: to access the lists in the posting file. These lists
311: are addresses in the tag file of documents posted under the
312: hash codes derived from the query.
313: The common items from all lists are determined;
314: this must include the items indexed by every key, but may also
315: contain some items which are false drops, since items referenced by
316: the correct hash codes need not actually have contained the correct keys.
317: Normally, if there are several keys in the query, there are not
318: likely to be many false drops in the final combined list even though
319: each hash code is somewhat ambiguous.
320: The actual tags are then obtained from the tag file, and to guard against
321: the possibility that an item has false-dropped on some hash code
322: in the query, the original items are normally obtained from the delivery
323: program (4) and the query keys checked against them
324: by string comparison.
325: .PP
326: Usually, therefore, the check for bad drops is made against the original file.
327: However, if the key derivation procedure is complex, it may be preferable
328: to check against the keys fed to program (2).
329: In this case the optional key file which contains the
330: keys associated with each item is generated, and the item tag is supplemented
331: by a string
332: .DS
333: ;start,length
334: .DE
335: which indicates the starting byte number in the key file and the length of
336: the string of keys for each item.
337: This file is not usually necessary with the present
338: key-selection program, since the keys
339: always appear in the original document.
340: .PP
341: There is also an option
342: (\f3-C\f2n\|\f1)
343: for coordination level searching.
344: This retrieves items which match all but
345: .I n
346: of the query keys.
347: The items are retrieved in the order of the number
348: of keys that they match.
349: Of course,
350: .I n
351: must be less than the number of query keys (nothing is
352: retrieved unless it matches at least one key).
353: .PP
354: As an example, consider one set of 4377 references, comprising
355: 660,000 bytes.
356: This included 51,000 keys, of which 5,900 were distinct
357: keys.
358: The hash table is kept full to save space (at the expense of time);
359: 995 of 997 possible hash codes were used.
360: The total set of index files (no key file) included 171,000 bytes,
361: about 26% of the original file size.
362: It took 8 minutes of processor time to
363: hash, sort, and write the index.
364: To search for a single query with the resulting index took 1.9 seconds
365: of processor time,
366: while to find the same paper
367: with a sequential linear search
368: using
369: .I grep
370: (reading all of the tags and keys)
371: took 12.3 seconds of processor time.
372: .PP
373: We have also used this software to index all of the English stored on our
374: .UX
375: system.
376: This is the index searched by the
377: .I lookall
378: command.
379: On a typical day there were
380: 29,000 files in our user file system, containing about 152,000,000
381: bytes.
382: Of these
383: 5,300 files, containing 32,000,000 bytes (about 21%)
384: were English text.
385: The total number of `words' (determined mechanically)
386: was 5,100,000.
387: Of these 227,000 were selected as keys;
388: 19,000 were distinct, hashing to 4,900 (of 5,000 possible) different hash codes.
389: The
390: resulting inverted file indexes used 845,000 bytes, or about
391: 2.6% of the size of the original files.
392: The particularly small indexes are caused by the
393: fact that keys are taken from only the first 50 non-common words of
394: some very long input files.
395: .PP
396: Even this large \f2lookall\f1 index can be searched quickly.
397: For example, to find this document
398: by looking for the keys
399: ``lesk inverted indexes''
400: required
401: 1.7 seconds of processor time
402: and system time.
403: By comparison, just to search the 800,000 byte dictionary (smaller than even
404: the inverted indexes, let alone the 27,000,000 bytes of text files) with
405: .I grep
406: takes 29 seconds of processor time.
407: The
408: .I lookall
409: program is thus useful when looking for a document which you believe
410: is stored on-line, but do not know where. For example, many memos
411: from our center are in the file system, but it is often
412: difficult to guess where a particular memo might be (it might have several
413: authors, each with many directories, and have been worked on by
414: a secretary with yet more directories).
415: Instructions for the use of the
416: .I lookall
417: command are given in the manual section, shown
418: in the appendix to this memorandum.
419: .PP
420: The only indexes maintained routinely are those of publication lists and
421: all English files.
422: To make other indexes, the programs for making keys, sorting them,
423: searching the indexes, and delivering answers must be used.
424: Since they are usually invoked as parts of higher-level commands,
425: they are not in the default command
426: directory, but are available to any user in the directory
427: .I /usr/lib/refer .
428: Three programs are of interest:
429: .I mkey ,
430: which isolates keys from input files;
431: .I inv ,
432: which makes an index from a set of keys;
433: and
434: .I hunt ,
435: which searches the index and delivers the items.
436: Note that the two parts of the retrieval phase are combined into
437: one program, to avoid the excessive system work and delay which
438: would result from running these as separate processes.
439: .PP
440: These three commands have a large number of options to adapt to different
441: kinds of input.
442: The user not interested in the detailed description that now follows may
443: skip to section 3, which describes the
444: .I refer
445: program, a packaged-up version of these tools specifically
446: oriented towards formatting references.
447: .PP
448: .B
449: Make Keys.
450: .R
451: The program
452: .I mkey
453: is the key-making program corresponding to step (1) in phase A.
454: Normally, it reads its input from the file names given as arguments,
455: and if there are no arguments it reads from the standard input.
456: It assumes that blank lines in the input delimit
457: separate items, for each of which a different line of
458: keys should be generated.
459: The lines of keys are written on the standard output.
460: Keys are any alphanumeric string in the input not
461: among the most frequent words in English and not entirely numeric
462: (except that all-numeric strings are acceptable if they
463: are between 1900 and 1999).
464: In the output, keys are translated to lower case, and truncated
465: to six characters in length; any associated punctuation is removed.
466: The following flag arguments are recognized by
467: .I mkey:
468: .TS
469: center;
470: lB lw(4i).
471: \-c \f2name T{
472: Name of file of common words;
473: default is
474: .I /usr/lib/eign.
475: T}
476: \-f \f2name T{
477: Read a list of files from
478: .I name
479: and take each as an input argument.
480: T}
481: \-i \f2chars T{
482: Ignore all lines which begin with `%' followed by any character
483: in
484: .I chars .
485: T}
486: \-k\f2n T{
487: Use at most
488: .I n
489: keys per input item.
490: T}
491: \-l\f2n T{
492: Ignore items shorter than
493: .I n
494: letters long.
495: T}
496: \-n\f2m T{
497: Ignore as a key any word in the first
498: .I m
499: words of the list of common English words.
500: The default is 100.
501: T}
502: \-s T{
503: Remove the labels
504: .I (file:start,length)
505: from the output; just give the keys.
506: Used when searching rather than indexing.
507: T}
508: \-w T{
509: Each whole file is a separate item;
510: blank lines in files are irrelevant.
511: T}
512: .TE
513: .PP
514: The normal arguments for indexing references are
515: the defaults, which are
516: .I "\-c /usr/lib/eign" ,
517: .I \-n100 ,
518: and
519: .I \-l3 .
520: For searching, the
521: .I \-s
522: option is also needed.
523: When the big
524: .I lookall
525: index of all English files is run,
526: the options are
527: .I \-w ,
528: .I \-k50 ,
529: and
530: .I "\-f (filelist)" .
531: When running on textual input,
532: the
533: .I mkey
534: program processes about 1000 English words per processor second.
535: Unless the
536: .I \-k
537: option is used (and the input files are long enough for
538: it to take effect)
539: the output of
540: .I mkey
541: is comparable in size to its input.
542: .PP
543: .B
544: Hash and invert.
545: .R
546: The
547: .I inv
548: program computes the hash codes and writes
549: the inverted files.
550: It reads the output of
551: .I mkey
552: and writes the set of files described earlier
553: in this section.
554: It expects one argument, which is used as the base name for
555: the three (or four) files to be written.
556: Assuming an argument of
557: .I Index
558: (the default)
559: the entry file is named
560: .I Index.ia ,
561: the posting file
562: .I Index.ib ,
563: the tag file
564: .I Index.ic ,
565: and the key file (if present)
566: .I Index.id .
567: The
568: .I inv
569: program recognizes the following options:
570: .TS
571: center;
572: lB lw(4i).
573: \-a T{
574: Append the new keys to a previous set of inverted files,
575: making new files if there is no old set using the same base name.
576: T}
577: \-d T{
578: Write the optional key file.
579: This is needed when you can not check for false drops by looking
580: for the keys in the original inputs, i.e. when the key derivation
581: procedure is complicated and
582: the output keys are not words from the input files.
583: T}
584: \-h\f2n T{
585: The hash table size is
586: .I n
587: (default 997);
588: .I n
589: should be prime.
590: Making \f2n\f1 bigger saves search time and spends disk space.
591: T}
592: \-i[u] \f2name T{
593: Take input from file
594: .I name ,
595: instead of the standard input;
596: if
597: .B u
598: is present
599: .I name
600: is unlinked when the sort is started.
601: Using this option permits the sort scratch space
602: to overlap the disk space used for input keys.
603: T}
604: \-n T{
605: Make a completely new set of inverted files, ignoring
606: previous files.
607: T}
608: \-p T{
609: Pipe into the sort program, rather than writing a temporary
610: input file.
611: This saves disk space and spends processor time.
612: T}
613: \-v T{
614: Verbose mode; print a summary of the number of keys which
615: finished indexing.
616: T}
617: .TE
618: .PP
619: About half the time used in
620: .I inv
621: is in the contained sort.
622: Assuming the sort is roughly linear, however,
623: a guess at the total timing for
624: .I inv
625: is 250 keys per second.
626: The space used is usually of more importance:
627: the entry file uses four bytes per possible hash (note
628: the
629: .B \-h
630: option),
631: and the tag file around 15-20 bytes per item indexed.
632: Roughly, the posting file contains one item for each key instance
633: and one item for each possible hash code; the items are two bytes
634: long if the tag file is less than 65336 bytes long, and the
635: items are four bytes wide if the tag file is greater than
636: 65536 bytes long.
637: Note that to minimize storage, the hash tables should be
638: over-full;
639: for most of the files indexed in this way, there is no
640: other real choice, since the
641: .I entry
642: file must fit in memory.
643: .PP
644: .B
645: Searching and Retrieving.
646: .R
647: The
648: .I hunt
649: program retrieves items from an index.
650: It combines, as mentioned above, the two parts of phase (B):
651: search and delivery.
652: The reason why it is efficient to combine delivery and search
653: is partly to avoid starting unnecessary processes, and partly
654: because the delivery operation must be a part of the search
655: operation in any case.
656: Because of the hashing, the search part takes place in two stages:
657: first items are retrieved which have the right hash codes associated with them,
658: and then the actual items are inspected to determine false drops, i.e.
659: to determine if anything with the right hash codes doesn't really have the right
660: keys.
661: Since the original item is retrieved to check on false drops,
662: it is efficient to present it immediately, rather than only
663: giving the tag as output and later retrieving the
664: item again.
665: If there were a separate key file, this argument would not apply,
666: but separate key files are not common.
667: .PP
668: Input to
669: .I hunt
670: is taken from the standard input,
671: one query per line.
672: Each query should be in
673: .I "mkey \-s"
674: output format;
675: all lower case, no punctuation.
676: The
677: .I hunt
678: program takes one argument which specifies the base name of the index
679: files to be searched.
680: Only one set of index files can be searched at a time,
681: although many text files may be indexed as a group, of course.
682: If one of the text files has been changed since the index, that file
683: is searched with
684: .I fgrep;
685: this may occasionally slow down the searching, and care should be taken to
686: avoid having many out of date files.
687: The following option arguments are recognized by
688: .I hunt:
689: .TS
690: center;
691: lB lw(4i).
692: \-a T{
693: Give all output; ignore checking for false drops.
694: T}
695: \-C\f2n T{
696: Coordination level
697: .I n;
698: retrieve items with not more than
699: .I n
700: terms of the input missing;
701: default
702: .I C0 ,
703: implying that each search term must be in the output items.
704: T}
705: \-F[yn\f2d\f3\|] T{
706: ``\-Fy'' gives the text of all the items found;
707: ``\-Fn'' suppresses them.
708: ``\-F\f2d\|\f1'' where \f2d\f1\| is an integer
709: gives the text of the first \f2d\f1 items.
710: The default is
711: .I \-Fy.
712: T}
713: \-g T{
714: Do not use
715: .I fgrep
716: to search files changed since the index was made;
717: print an error comment instead.
718: T}
719: \-i \f2string T{
720: Take
721: .I string
722: as input, instead of reading the standard input.
723: T}
724: \-l \f2n T{
725: The maximum length of internal lists of candidate
726: items is
727: .I n;
728: default 1000.
729: T}
730: \-o \f2string T{
731: Put text output (``\-Fy'') in
732: .I string;
733: of use
734: .I only
735: when
736: invoked from another program.
737: T}
738: \-p T{
739: Print hash code frequencies; mostly
740: for use in optimizing hash table sizes.
741: T}
742: \-T[yn\f2d\|\f3] T{
743: ``\-Ty'' gives the tags of the items found;
744: ``\-Tn'' suppresses them.
745: ``\-T\f2d\f1\|'' where \f2d\f1\| is an integer
746: gives the first \f2d\f1 tags.
747: The default is
748: .I \-Tn .
749: T}
750: \-t \f2string T{
751: Put tag output (``\-Ty'') in
752: .I string;
753: of use
754: .I only
755: when invoked from another program.
756: T}
757: .TE
758: .PP
759: The timing of
760: .I hunt
761: is complex.
762: Normally the hash table is overfull, so that there will
763: be many false drops on any single term;
764: but a multi-term query will have few false drops on
765: all terms.
766: Thus if a query is underspecified (one search term)
767: many potential items will be examined and discarded as false
768: drops, wasting time.
769: If the query is overspecified (a dozen search terms)
770: many keys will be examined only to verify that
771: the single item under consideration has that key posted.
772: The variation of search time with number of keys is
773: shown in the table below.
774: Queries of varying length were constructed to retrieve
775: a particular document from the file of references.
776: In the sequence to the left, search terms were chosen so as
777: to select the desired paper as quickly as possible.
778: In the sequence on the right, terms were chosen inefficiently,
779: so that the query did not uniquely select the desired document
780: until four keys had been used.
781: The same document was the target in each case,
782: and the final set of eight keys are also identical; the differences
783: at five, six and seven keys are produced by measurement error, not
784: by the slightly different key lists.
785: .TS
786: center;
787: c s s s5 | c s s s
788: cp8 cp8 cp8 cp8 | cp8 cp8 cp8 cp8
789: cp8 cp8 cp8 cp8 | cp8 cp8 cp8 cp8
790: n n n n | n n n n .
791: Efficient Keys Inefficient Keys
792: No. keys Total drops Retrieved Search time No. keys Total drops Retrieved Search time
793: (incl. false) Documents (seconds) (incl. false) Documents (seconds)
794: 1 15 3 1.27 1 68 55 5.96
795: 2 1 1 0.11 2 29 29 2.72
796: 3 1 1 0.14 3 8 8 0.95
797: 4 1 1 0.17 4 1 1 0.18
798: 5 1 1 0.19 5 1 1 0.21
799: 6 1 1 0.23 6 1 1 0.22
800: 7 1 1 0.27 7 1 1 0.26
801: 8 1 1 0.29 8 1 1 0.29
802: .TE
803: As would be expected, the optimal search is achieved
804: when the query just specifies the answer; however,
805: overspecification is quite cheap.
806: Roughly, the time required by
807: .I hunt
808: can be approximated as
809: 30 milliseconds per search key plus 75 milliseconds
810: per dropped document (whether it is a false drop or
811: a real answer).
812: In general, overspecification can be recommended;
813: it protects the user against additions to the data base
814: which turn previously uniquely-answered queries
815: into ambiguous queries.
816: .PP
817: The careful reader will have noted an enormous discrepancy between these times
818: and the earlier quoted time of around 1.9 seconds for a search. The times
819: here are purely for the search and retrieval: they are measured by
820: running many searches through a single invocation of the
821: .I hunt
822: program alone.
823: The normal retrieval operation involves using the shell to
824: set up a pipeline through
825: .I mkey
826: to
827: .I hunt
828: and starting both processes; this adds a fixed overhead of about 1.7 seconds
829: of processor time
830: to any single search.
831: Furthermore, remember that all these times are processor times:
832: on a typical morning on our \s-2PDP\s0 11/70 system, with about one dozen
833: people logged on,
834: to obtain 1 second of processor time for the search program
835: took between 2 and 12 seconds of real time, with a median of
836: 3.9 seconds and a mean of 4.8 seconds.
837: Thus, although the work involved in a single search may be only
838: 200 milliseconds, after you add the 1.7 seconds of startup processor
839: time
840: and then assume a 4:1 elapsed/processor time
841: ratio, it will be 8 seconds before any response is printed.
842: .NH
843: Selecting and Formatting References for T\s-2ROFF\s0
844: .PP
845: The major application of the retrieval software
846: is
847: .I refer,
848: which is a
849: .I troff
850: preprocessor
851: like
852: .I eqn .
853: .[
854: kernighan cherry acm 1975
855: .]
856: It scans its input looking for items of the form
857: .DS
858: \*.[
859: imprecise citation
860: \*.\^]
861: .DE
862: where an imprecise citation is merely a string
863: of words found in the relevant bibliographic citation.
864: This is translated into a properly formatted reference.
865: If the imprecise citation does not correctly identify
866: a single paper
867: (either
868: selecting no papers or too many) a message is given.
869: The data base of citations searched may be tailored to each
870: system, and individual users may specify their own
871: citation
872: files.
873: On our system, the default data base is accumulated from
874: the publication lists of the members of our organization, plus
875: about half a dozen personal bibliographies that were collected.
876: The present total is about 4300 citations, but this increases steadily.
877: Even now,
878: the data base covers a large fraction of local citations.
879: .PP
880: For example, the reference for the
881: .I eqn
882: paper above was specified as
883: .DS
884: \&\*.\*.\*.
885: \&preprocessor like
886: \&.I eqn.
887: \&.[
888: \&kernighan cherry acm 1975
889: \&.]
890: \&It scans its input looking for items
891: \&\*.\*.\*.
892: .DE
893: This paper was itself printed using
894: .I refer.
895: The above input text was processed by
896: .I refer
897: as well as
898: .I tbl
899: and
900: .I troff
901: by the command
902: .DS
903: .ft I
904: refer memo-file | tbl | troff \-ms
905: .ft R
906: .DE
907: and the reference was automatically translated into a correct
908: citation to the ACM paper on mathematical typesetting.
909: .PP
910: The procedure to use to place a reference in a paper
911: using
912: .I refer
913: is as follows.
914: First, use the
915: .I lookbib
916: command to check that the paper is in the data base
917: and to find out what keys are necessary to retrieve it.
918: This is done by typing
919: .I lookbib
920: and then typing some potential queries until
921: a suitable query is found.
922: For example, had one started to find
923: the
924: .I eqn
925: paper shown above by presenting the query
926: .DS
927: $ lookbib
928: kernighan cherry
929: (EOT)
930: .DE
931: .I lookbib
932: would have found several items; experimentation would quickly
933: have shown that the query given above is adequate.
934: Overspecifying the query is of course harmless.
935: A particularly careful reader may have noticed that ``acm'' does not
936: appear in the printed citation;
937: we have supplemented some of the data base items with common
938: extra keywords, such as common abbreviations for journals
939: or other sources, to aid in searching.
940: .PP
941: If the reference is in the data base, the query
942: that retrieved it can be inserted in the text,
943: between
944: .B \*.[
945: and
946: .B \*.\^]
947: brackets.
948: If it is not in the data base, it can be typed
949: into a private file of references, using the format
950: discussed in the next section, and then
951: the
952: .B \-p
953: option
954: used to search this private file.
955: Such a command might read
956: (if the private references are called
957: .I myfile )
958: .DS
959: .ft 2
960: refer \-p myfile document | tbl | eqn | troff \-ms \*. \*. \*.
961: .ft 1
962: .DE
963: where
964: .I tbl
965: and/or
966: .I eqn
967: could be omitted if not needed.
968: The use
969: of the
970: .I \-ms
971: macros
972: .[
973: lesk typing documents unix gcos
974: .]
975: or some other macro package, however,
976: is essential.
977: .I Refer
978: only generates the data for the references; exact formatting
979: is done by some macro package, and if none is supplied the
980: references will not be printed.
981: .PP
982: By default,
983: the references are numbered sequentially,
984: and
985: the
986: .I \-ms
987: macros format references as footnotes at the bottom of the page.
988: This memorandum is an example of that style.
989: Other possibilities are discussed in section 5 below.
990: .NH
991: Reference Files.
992: .PP
993: A reference file is a set of bibliographic references usable with
994: .I refer.
995: It can be indexed using the software described in section 2
996: for fast searching.
997: What
998: .I refer
999: does is to read the input document stream,
1000: looking for imprecise citation references.
1001: It then searches through reference files to find
1002: the full citations, and inserts them into the
1003: document.
1004: The format of the full citation is arranged to make it
1005: convenient for a macro package, such as the
1006: .I \-ms
1007: macros, to format the reference
1008: for printing.
1009: Since
1010: the format of the final reference is determined
1011: by the desired style of output,
1012: which is determined by the macros used,
1013: .I refer
1014: avoids forcing any kind of reference appearance.
1015: All it does is define a set of string registers which
1016: contain the basic information about the reference;
1017: and provide a macro call which is expanded by the macro
1018: package to format the reference.
1019: It is the responsibility of the final macro package
1020: to see that the reference is actually printed; if no
1021: macros are used, and the output of
1022: .I refer
1023: fed untranslated to
1024: .I troff,
1025: nothing at all will be printed.
1026: .PP
1027: The strings defined by
1028: .I refer
1029: are taken directly from the files of references, which
1030: are in the following format.
1031: The references should be separated
1032: by blank lines.
1033: Each reference is a sequence of lines beginning with
1034: .B %
1035: and followed
1036: by a key-letter.
1037: The remainder of that line, and successive lines until the next line beginning
1038: with
1039: .B % ,
1040: contain the information specified by the key-letter.
1041: In general,
1042: .I refer
1043: does not interpret the information, but merely presents
1044: it to the macro package for final formatting.
1045: A user with a separate macro package, for example,
1046: can add new key-letters or use the existing ones for other purposes
1047: without bothering
1048: .I refer.
1049: .PP
1050: The meaning of the key-letters given below, in particular,
1051: is that assigned by the
1052: .I \-ms
1053: macros.
1054: Not all information, obviously, is used with each citation.
1055: For example, if a document is both an internal memorandum and a journal article,
1056: the macros ignore the memorandum version and cite only the journal article.
1057: Some kinds of information are not used at all in printing the reference;
1058: if a user does not like finding references by specifying title
1059: or author keywords, and prefers to add specific keywords to the
1060: citation, a field is available which is searched but not
1061: printed (\f3K\f1).
1062: .PP
1063: The key letters currently recognized by
1064: .I refer
1065: and
1066: .I \-ms,
1067: with the kind of information implied, are:
1068: .KS
1069: .TS
1070: center;
1071: c c6 c c
1072: c l c l.
1073: Key Information specified Key Information specified
1074: A Author's name N Issue number
1075: B Title of book containing item O Other information
1076: C City of publication P Page(s) of article
1077: D Date R Technical report reference
1078: E Editor of book containing item T Title
1079: G Government (NTIS) ordering number V Volume number
1080: I Issuer (publisher)
1081: J Journal name
1082: K Keys (for searching) X or
1083: L Label Y or
1084: M Memorandum label Z Information not used by \f2refer\f1
1085: .TE
1086: .KE
1087: For example, a sample reference could be
1088: typed as:
1089: .DS
1090: %T Bounds on the Complexity of the Maximal
1091: Common Subsequence Problem
1092: %Z ctr127
1093: %A A. V. Aho
1094: %A D. S. Hirschberg
1095: %A J. D. Ullman
1096: %J J. ACM
1097: %V 23
1098: %N 1
1099: %P 1-12
1100: .\"%M TM 75-1271-7
1101: %M abcd-78
1102: %D Jan. 1976
1103: .DE
1104: Order is irrelevant, except that authors are shown in the order
1105: given. The output of
1106: .I refer
1107: is a stream of string definitions, one
1108: for each of the fields of each reference, as
1109: shown below.
1110: .DS
1111: \*.]-
1112: \*.ds [A authors' names \*.\*.\*.
1113: \*.ds [T title \*.\*.\*.
1114: \*.ds [J journal \*.\*.\*.
1115: \*.\*.\*.
1116: \*.]\|[ type-number
1117: .DE
1118: The special macro
1119: .B \&\*.]\-
1120: precedes the string definitions
1121: and the special macro
1122: .B \*.]\|[
1123: follows.
1124: These are changed from the input
1125: .B \*.[
1126: and
1127: .B \*.\^]
1128: so that running the same file through
1129: .I refer
1130: again is harmless.
1131: The
1132: .B \*.]\-
1133: macro can be used by the macro package to
1134: initialize.
1135: The
1136: .B \*.]\|[
1137: macro, which should be used
1138: to print the reference, is given an
1139: argument
1140: .I type-number
1141: to indicate the kind of reference, as follows:
1142: .KS
1143: .TS
1144: center;
1145: c c
1146: n l.
1147: Value Kind of reference
1148: 1 Journal article
1149: 2 Book
1150: 3 Article within book
1151: 4 Technical report
1152: 5 Bell Labs technical memorandum
1153: 0 Other
1154: .TE
1155: .KE
1156: The reference is flagged in the text
1157: with the sequence
1158: .DS
1159: \e*\|([\*.number\e*\|(\*.\^]
1160: .DE
1161: where
1162: .I number
1163: is the footnote number.
1164: The strings
1165: .B [\*.
1166: and
1167: .B \*.\^]
1168: should be used by the macro package
1169: to format the reference flag in the text.
1170: These strings can be replaced for a particular
1171: footnote, as described in section 5.
1172: The footnote number (or other signal) is available
1173: to the reference macro
1174: .B \*.]\|[
1175: as the
1176: string register
1177: .B [F .
1178: .PP
1179: In some cases users wish to suspend the searching, and merely
1180: use the reference macro formatting.
1181: That is, the user doesn't want to provide a search key
1182: between
1183: .B \*.[
1184: and
1185: .B \*.\^]
1186: brackets, but merely
1187: the reference lines for the appropriate document.
1188: Alternatively, the user
1189: can wish
1190: to add a few fields to those in the reference
1191: as in the standard file, or
1192: override some fields.
1193: Altering or replacing fields, or supplying whole references, is easily done
1194: by inserting lines beginning
1195: with
1196: .B % ;
1197: any such line is taken as
1198: direct input to the reference
1199: processor rather than keys to be searched.
1200: Thus
1201: .DS
1202: \*.[
1203: key1 key2 key3 \*.\*.\*.
1204: %Q New format item
1205: %R Override report name
1206: \*.\^]
1207: .DE
1208: makes the indicated changes to the result of searching for
1209: the keys.
1210: All of the search keys must be given before the first
1211: \f3%\f1 line.
1212: .PP
1213: If no search keys are provided, an entire citation can
1214: be provided in-line in the text.
1215: For example, if the
1216: .I eqn
1217: paper citation were to be inserted in
1218: this way, rather than by searching for it in the data base,
1219: the input would read
1220: .DS
1221: \&\*.\*.\*.
1222: \&preprocessor like
1223: \&.I eqn.
1224: \&.[
1225: \&%A B. W. Kernighan
1226: \&%A L. L. Cherry
1227: \&%T A System for Typesetting Mathematics
1228: \&%J Comm. ACM
1229: \&%V 18
1230: \&%N 3
1231: \&%P 151-157
1232: \&%D March 1975
1233: \&.]
1234: \&It scans its input looking for items
1235: \&\*.\*.\*.
1236: .DE
1237: This would produce a citation of the same appearance as that
1238: resulting from the file search.
1239: .PP
1240: As shown, fields are normally turned into
1241: .I troff
1242: strings.
1243: Sometimes users would rather have them defined as macros,
1244: so that other
1245: .I troff
1246: commands can be placed into the data.
1247: When this is necessary, simply double the control character
1248: .B %
1249: in the data.
1250: Thus the input
1251: .DS
1252: \&.[
1253: %V 23
1254: %%M
1255: Bell Laboratories,
1256: Murray Hill, N.J. 07974
1257: \&.]
1258: .DE
1259: is processed by
1260: .I refer
1261: into
1262: .DS
1263: \&.ds [V 23
1264: \&.de [M
1265: Bell Laboratories,
1266: Murray Hill, N.J. 07974
1267: \&..
1268: .DE
1269: The information after
1270: .B %%M
1271: is defined as a macro to be invoked by
1272: .B .[M
1273: while the information after
1274: .B %V
1275: is turned into a string to be invoked by
1276: .B \e\(**([V .
1277: At present
1278: .I \-ms
1279: expects all information as strings.
1280: .NH
1281: Collecting References and other Refer Options
1282: .PP
1283: Normally, the combination of
1284: .I refer
1285: and
1286: .I \-ms
1287: formats output as
1288: .I troff
1289: footnotes which are consecutively numbered and placed
1290: at the bottom of the page. However,
1291: options exist to
1292: place the references at the end; to arrange references alphabetically
1293: by senior author; and to indicate references by strings in the text of the form
1294: [Name1975a]
1295: rather than by number.
1296: Whenever references are not placed at the bottom of a page
1297: identical references are coalesced.
1298: .PP
1299: For example, the
1300: .B \-e
1301: option to
1302: .I refer
1303: specifies that references are to be collected; in this case
1304: they are output whenever the sequence
1305: .DS
1306: \*.[
1307: $LIST$
1308: \*.\^]
1309: .DE
1310: is encountered.
1311: Thus, to place references at the end of a paper, the user would run
1312: .I refer
1313: with the
1314: .I \-e
1315: option and place the above $LIST$ commands after the last
1316: line of the text.
1317: .I Refer
1318: will then move all the references to that point.
1319: To aid in formatting the collected references,
1320: .I refer
1321: writes the references preceded by the line
1322: .DS
1323: .B .]<
1324: .DE
1325: and
1326: followed by the line
1327: .DS
1328: .B .]>
1329: .DE
1330: to invoke special macros before and after the references.
1331: .PP
1332: Another possible option to
1333: .I refer
1334: is the
1335: .B \-s
1336: option to specify
1337: sorting of references. The default,
1338: of course, is to list references in the order presented.
1339: The
1340: .B \-s
1341: option implies the
1342: .B \-e
1343: option, and thus requires
1344: a
1345: .DS
1346: \*.[
1347: $LIST$
1348: \*.\^]
1349: .DE
1350: entry to call out the reference list.
1351: The
1352: .B \-s
1353: option may be followed by a string of letters, numbers, and `+' signs indicating how
1354: the references are to be sorted.
1355: The sort is done using the fields whose key-letters are
1356: in the string as sorting keys; the numbers indicate how many
1357: of the fields are to be considered, with `+'
1358: taken as a large number.
1359: Thus the default is
1360: .B \-sAD
1361: meaning ``Sort on senior author, then date.'' To
1362: sort on all authors and then title, specify
1363: .B \-sA+T .
1364: And to sort on two authors and then the journal,
1365: write
1366: .B \-sA2J .
1367: .PP
1368: Other options to
1369: .I refer
1370: change the signal or label inserted in the text for each reference.
1371: Normally these are just sequential numbers,
1372: and their exact placement (within brackets, as superscripts, etc.) is determined
1373: by the macro package.
1374: The
1375: .B \-l
1376: option replaces reference numbers by
1377: strings composed of the senior author's last name, the date,
1378: and a disambiguating letter.
1379: If a number follows the
1380: .B l
1381: as in
1382: .B \-l3
1383: only that many letters of the last name are used
1384: in the label string.
1385: To abbreviate the date as well the form
1386: \f3-l\f2m,n\f1
1387: shortens the last name to the
1388: first
1389: .I m
1390: letters and the date to the
1391: last
1392: .I n
1393: digits.
1394: For example, the option
1395: .B \-l3,2
1396: would refer to the
1397: .I eqn
1398: paper (reference 3) by the signal
1399: .I Ker75a ,
1400: since it is the first cited reference by Kernighan in 1975.
1401: .PP
1402: A user wishing to specify particular labels for
1403: a private bibliography may use the
1404: .B \-k
1405: option.
1406: Specifying
1407: \f3\-k\f2x\f1
1408: causes the field \f2x\f1 to be used as a label.
1409: The default is \f3L\f1.
1410: If this field ends in \f3\-\f1, that character
1411: is replaced by a sequence letter; otherwise the field
1412: is used exactly as given.
1413: .PP
1414: If none of the
1415: .I refer -produced
1416: signals are desired,
1417: the
1418: .B \-b
1419: option entirely suppresses automatic text signals.
1420: .PP
1421: If the user wishes to override the
1422: .I \-ms
1423: treatment of the reference signal (which is normally to
1424: enclose the number in brackets in
1425: .I nroff
1426: and make it a superscript in
1427: .I troff\\| )
1428: this can be done easily.
1429: If the lines
1430: .B \&.[
1431: or
1432: .B \&.]
1433: contain anything following these characters,
1434: the remainders of these lines are used to surround
1435: the reference signal, instead of the default.
1436: Thus, for example, to say ``See reference (2).''
1437: and avoid
1438: ``See reference.\s-3\u2\d\s+3'' the
1439: input might appear
1440: .DS
1441: \&See reference
1442: \&\*.[ (
1443: imprecise citation ...
1444: \&\*.\^])\*.
1445: .DE
1446: Note that blanks are significant in this construction.
1447: If a permanent change is desired in the style of reference
1448: signals, however, it is probably easier to redefine the strings
1449: .B \&[.
1450: and
1451: .B \&.]
1452: (which are used to bracket each signal)
1453: than to change each citation.
1454: .PP
1455: Although normally
1456: .I refer
1457: limits itself to retrieving the data for the reference,
1458: and leaves to a macro package the job of arranging that
1459: data as required by the local format, there are two
1460: special options for rearrangements that can not be
1461: done by macro packages.
1462: The
1463: .B \-c
1464: option puts fields into all upper case
1465: (C\s-2APS\s+2-S\s-2MALL\s+2 C\s-2APS\s+2
1466: in
1467: .I troff
1468: output).
1469: The key-letters indicated what information is to be translated
1470: to upper case follow the
1471: .B c ,
1472: so that
1473: .B \-cAJ
1474: means that authors' names and journals are to be in caps.
1475: The
1476: .B \-a
1477: option writes the names of authors last name first, that is
1478: .I "A. D. Hall, Jr."
1479: is written as
1480: .I "Hall, A. D. Jr" .
1481: The citation form of
1482: the
1483: .I "Journal of the ACM" ,
1484: for example, would require
1485: both
1486: .B \-cA
1487: and
1488: .B \-a
1489: options.
1490: This produces authors' names in the style
1491: .I
1492: K\s-2ERNIGHAN\s0, B. W. \s-2AND\s0 C\s-2HERRY\s0, L. L.\&
1493: .R
1494: for the previous example.
1495: The
1496: .B \-a
1497: option may be followed by a number to indicate how many
1498: author names should be reversed;
1499: .B \-a1
1500: (without any
1501: .B \-c
1502: option)
1503: would produce
1504: .I
1505: Kernighan, B. W. and L. L. Cherry,
1506: .R
1507: for example.
1508: .PP
1509: Finally, there is also the previously-mentioned
1510: .B \-p
1511: option to let the user specify
1512: a private file of references to be searched before the public files.
1513: Note that
1514: .I refer
1515: does not insist on a previously made index for these files.
1516: If a file is named which contains reference
1517: data but is not indexed, it will be searched
1518: (more slowly)
1519: by
1520: .I refer
1521: using
1522: .I fgrep.
1523: In this way
1524: it is easy for users to keep small files of
1525: new references, which can later be added to the
1526: public data bases.
1527: .SG MH-1274-MEL-\s8UNIX\s0
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.