SomeApplicationsofInvertedIndexesontheUNIXSystem M.E.Lesk ABSTRACT I.SomeApplicationsofInvertedIndexes−Overview Thismemorandumdescribesasetofprogramswhichmakeinvertedindexes toUNIX*textfiles,andtheirapplicationtoretrievingandformattingcitations fordocumentspreparedusingtroff. Theindexingandsearchingprogramsmakekeywordindexestovolumesof materialtoolargeforlinearsearching.Searchesforcombinationsofsinglewords canbeperformedquickly.Theprogramsforgeneralsearchingaredividedinto twophases.Thefirstmakesanindexfromtheoriginaldata;thesecondsearches theindexandretrievesitems.Bothofthesephasesarefurtherdividedintotwo partstoseparatethedata-dependentandalgorithmdependentcode. Themajorcurrentapplicationoftheseprogramsisthetroffpreprocessor refer.Alistof4300referencesismaintainedonline,containingprimarilypapers writtenandcitedbylocalauthors.Wheneveroneofthesereferencesisrequired inapaper,afewwordsfromthetitleorauthorlistwillretrieveit,andtheuser neednotbothertore-entertheexactcitation.Alternatively,authorscanuse theirownlistsofpapers. Thismemorandumisofinteresttothosewhoareinterestedinfacilitiesfor searchinglargebutrelativelyunchangingtextfilesontheUNIXsystem,and thosewhoareinterestedinhandlingbibliographiccitationswithUNIXtroff. II.UpdatingPublicationLists Thissectionisabriefnotedescribingtheauxiliaryprogramsformanaging theupdatingprocessing.Itiswrittentoaidclericalusersinmaintaininglistsof references.Primarily,theprogramsdescribedpermitalargeamountofindividual controloverthecontentofpublicationlistswhileretainingtheusefulnessofthe filestootherusers. III.ManualPages ThissectioncontainsthepagesfromtheUNIXprogrammer’smanualdealingwiththesecommands.Itisusefulforreference. *UNIXisaTrademarkofBellLaboratories. 1.Introduction. TheUNIX◯rsystemhasmanyutilities(e.g.grep,awk,lex,egrep,fgrep,...)tosearch throughfilesoftext,butmostofthemarebasedonalinearscanthroughtheentirefile,using somedeterministicautomaton.Thismemorandumdiscussesaprogramwhichusesinverted indexes1andcanthusbeusedonmuchlargerdatabases. 1D.Knuth,‘‘TheArtofComputerProgramming:Vol.3,SortingandSearching,’’Addison-Wesley, -2-Aswithanyindexingsystem,ofcourse,therearesomedisadvantages;onceanindexis made,thefilesthathavebeenindexedcannotbechangedwithoutremakingtheindex.Thus applicationsarerestrictedtothosemakingmanysearchesofrelativelystabledata.Furthermore, theseprogramsdependonhashing,andcanonlysearchforexactmatchesofwholekeywords.It isnotpossibletolookforarithmeticorlogicalexpressions(e.g.‘‘dategreaterthan1970’’)orfor regularexpressionsearchingsuchasthatinlex.2 Currentlytherearetwousesofthissoftware,thereferpreprocessortoformatreferences, andthelookallcommandtosearchthroughalltextfilesontheUNIXsystem. Theremainingsectionsofthismemorandumdiscussthesearchingprogramsandtheiruses. Section2explainstheoperationofthesearchingalgorithmanddescribesthedatacollectedfor usewiththelookallcommand.Themoreimportantapplication,referhasauser’sdescriptionin section3.Section4goesintomoredetailonreferencefilesforthebenefitofthosewhowishto addreferencestodatabasesorwritenewtroffmacrosforusewithrefer.Theoptionstomake refercollectidenticalcitations,orotherwiserelocateandadjustreferences,aredescribedinsection5.TheUNIXmanualsectionsforrefer,lookall,andassociatedcommandsareattachedas appendices. 2.Searching. Theindexingandsearchingprocessisdividedintotwophases,eachmadeoftwoparts. Theseareshownbelow. A.Constructtheindex. (1)Findkeys—turntheinputfilesintoasequenceoftagsandkeys,whereeachtagidentifiesadistinctitemintheinputandthekeysforeachsuchitemarethestringsunder whichitistobeindexed. (2)Hashandsort—prepareasetofinvertedindexesfromwhich,givenasetofkeys,the appropriateitemtagscanbefoundquickly. B.Retrieveaniteminresponsetoaquery. (3)Search—Givensomekeys,lookthroughthefilespreparedbythehashingandsorting facilityandderivetheappropriatetags. (4)Deliver—Giventhetags,findtheoriginalitems.Thiscompletesthesearchingprocess. Thefirstphase,makingtheindex,ispresumablydonerelativelyinfrequently.Itshould,ofcourse, bedonewheneverthedatabeingindexedchange.Incontrast,thesecondphase,retrievingitems, ispresumablydoneoften,andmustberapid. Aneffortismadetoseparatecodewhichdependsonthedatabeinghandledfromcode whichdependsonthesearchingprocedure.Thesearchalgorithmisinvolvedonlyinprograms(2) and(3),whileknowledgeoftheactualdatafilesisneededonlybyprograms(1)and(4).Thusit iseasytoadapttodifferentdatafilesordifferentsearchalgorithms. Tostartwith,itisnecessarytohavesomewayofselectingorgeneratingkeysfrominput files.FordealingwithfilesthatarebasicallyEnglish,wehaveakey-makingprogramwhichauto-maticallyselectswordsandpassesthemtothehashingandsortingprogram(step2).Theformat usedhasonelineforeachinputitem,arrangedasfollows: name:start,length(tab)key1key2key3... wherenameisthefilename,startisthestartingbytenumber,andlengthisthenumberofbytes intheentry. Theselinesaretheonlyinputusedtomaketheindex.Thefirstfield(thefilename,byte position,andbytecount)isthetagoftheitemandcanbeusedtoretrieveitquickly.Normally, Reading,Mass.(1977).Seesection6.5. 2 -3-anitemiseitherawholefileorasectionofafiledelimitedbyblanklines.Afterthetab,thesec-ondfieldcontainsthekeys.Thekeys,ifselectedbytheautomaticprogram,areanyalphanumeric stringswhicharenotamongthe100mostfrequentwordsinEnglishandwhicharenotentirely numeric(exceptforfour-digitnumbersbeginning19,whichareacceptedasdates).Keysare truncatedtosixcharactersandconvertedtolowercase.Someselectionisneedediftheoriginal itemsareverylarge.Wenormallyjusttakethefirstnkeys,withnlessthan100orso;this replacesanyattemptatintelligentselection.OnefileinoursystemisacompleteEnglishdictionary;itwouldpresumablyberetrievedforallqueries. Togenerateaninvertedindextothelistofrecordtagsandkeys,thekeysarehashedand sortedtoproduceanindex.Whatiswanted,ideally,isaseriesoflistsshowingthetagsassociatedwitheachkey.Tocondensethis,whatisactuallyproducedisalistshowingthetagsassociatedwitheachhashcode,andthuswithsomesetofkeys.Tospeedupaccessandfurthersave space,asetofthreeorpossiblyfourfilesisproduced.Thesefilesare: FileContents eennttrryyPointerstopostingfile foreachhashcode ppoossttiinnggListsoftagpointersfor eachhashcode ttaaggTagsforeachitem kkeeyyKeysforeachitem (optional) Thepostingfilecomprisestherealdata:itcontainsasequenceoflistsofitemspostedundereach hashcode.Tospeedupsearching,theentryfileisanarrayofpointersintothepostingfile,one perpotentialhashcode.Furthermore,theitemsinthelistsinthepostingfilearenotreferredto bytheircompletetag,butjustbyanaddressinthetagfile,whichgivesthecompletetags.The keyfileisoptionalandcontainsacopyofthekeysusedintheindexing. Thesearchingprocessstartswithaquery,containingseveralkeys.Thegoalistoobtainall itemswhichwereindexedunderthesekeys.Thequerykeysarehashed,andthepointersinthe entryfileusedtoaccessthelistsinthepostingfile.Theselistsareaddressesinthetagfileof documentspostedunderthehashcodesderivedfromthequery.Thecommonitemsfromalllists aredetermined;thismustincludetheitemsindexedbyeverykey,butmayalsocontainsome itemswhicharefalsedrops,sinceitemsreferencedbythecorrecthashcodesneednotactually havecontainedthecorrectkeys.Normally,ifthereareseveralkeysinthequery,therearenot likelytobemanyfalsedropsinthefinalcombinedlisteventhougheachhashcodeissomewhat ambiguous.Theactualtagsarethenobtainedfromthetagfile,andtoguardagainstthepossibilitythatanitemhasfalse-droppedonsomehashcodeinthequery,theoriginalitemsarenormally obtainedfromthedeliveryprogram(4)andthequerykeyscheckedagainstthembystringcomparison. Usually,therefore,thecheckforbaddropsismadeagainsttheoriginalfile.However,ifthe keyderivationprocedureiscomplex,itmaybepreferabletocheckagainstthekeysfedtoprogram(2).Inthiscasetheoptionalkeyfilewhichcontainsthekeysassociatedwitheachitemis generated,andtheitemtagissupplementedbyastring ;start,length whichindicatesthestartingbytenumberinthekeyfileandthelengthofthestringofkeysfor eachitem.Thisfileisnotusuallynecessarywiththepresentkey-selectionprogram,sincethekeys alwaysappearintheoriginaldocument. Thereisalsoanoption(-Cn)forcoordinationlevelsearching.Thisretrievesitemswhich matchallbutnofthequerykeys.Theitemsareretrievedintheorderofthenumberofkeysthat theymatch.Ofcourse,nmustbelessthanthenumberofquerykeys(nothingisretrievedunless itmatchesatleastonekey).

-4-Asanexample,consideronesetof4377references,comprising660,000bytes.Thisincluded 51,000keys,ofwhich5,900weredistinctkeys.Thehashtableiskeptfulltosavespace(atthe expenseoftime);995of997possiblehashcodeswereused.Thetotalsetofindexfiles(nokey file)included171,000bytes,about26%oftheoriginalfilesize.Ittook8minutesofprocessor timetohash,sort,andwritetheindex.Tosearchforasinglequerywiththeresultingindextook 1.9secondsofprocessortime,whiletofindthesamepaperwithasequentiallinearsearchusing grep(readingallofthetagsandkeys)took12.3secondsofprocessortime. WehavealsousedthissoftwaretoindexalloftheEnglishstoredonourUNIXsystem.This istheindexsearchedbythelookallcommand.Onatypicaldaytherewere29,000filesinouruser filesystem,containingabout152,000,000bytes.Ofthese5,300files,containing32,000,000bytes (about21%)wereEnglishtext.Thetotalnumberof‘words’(determinedmechanically)was 5,100,000.Ofthese227,000wereselectedaskeys;19,000weredistinct,hashingto4,900(of5,000 possible)differenthashcodes.Theresultinginvertedfileindexesused845,000bytes,orabout 2.6%ofthesizeoftheoriginalfiles.Theparticularlysmallindexesarecausedbythefactthat keysaretakenfromonlythefirst50non-commonwordsofsomeverylonginputfiles. Eventhislargelookallindexcanbesearchedquickly.Forexample,tofindthisdocumentby lookingforthekeys‘‘leskinvertedindexes’’required1.7secondsofprocessortimeandsystem time.Bycomparison,justtosearchthe800,000bytedictionary(smallerthaneventheinverted indexes,letalonethe27,000,000bytesoftextfiles)withgreptakes29secondsofprocessortime. Thelookallprogramisthususefulwhenlookingforadocumentwhichyoubelieveisstoredonline,butdonotknowwhere.Forexample,manymemosfromourcenterareinthefilesystem, butitisoftendifficulttoguesswhereaparticularmemomightbe(itmighthaveseveralauthors, eachwithmanydirectories,andhavebeenworkedonbyasecretarywithyetmoredirectories). Instructionsfortheuseofthelookallcommandaregiveninthemanualsection,showninthe appendixtothismemorandum. TheonlyindexesmaintainedroutinelyarethoseofpublicationlistsandallEnglishfiles.To makeotherindexes,theprogramsformakingkeys,sortingthem,searchingtheindexes,anddeliveringanswersmustbeused.Sincetheyareusuallyinvokedaspartsofhigher-levelcommands, theyarenotinthedefaultcommanddirectory,butareavailabletoanyuserinthedirectory /usr/lib/refer.Threeprogramsareofinterest:mkey,whichisolateskeysfrominputfiles;inv, whichmakesanindexfromasetofkeys;andhunt,whichsearchestheindexanddeliversthe items.Notethatthetwopartsoftheretrievalphasearecombinedintooneprogram,toavoidthe excessivesystemworkanddelaywhichwouldresultfromrunningtheseasseparateprocesses. Thesethreecommandshavealargenumberofoptionstoadapttodifferentkindsofinput. Theusernotinterestedinthedetaileddescriptionthatnowfollowsmayskiptosection3,which describesthereferprogram,apackaged-upversionofthesetoolsspecificallyorientedtowardsfor-mattingreferences. MakeKeys.Theprogrammkeyisthekey-makingprogramcorrespondingtostep(1)in phaseA.Normally,itreadsitsinputfromthefilenamesgivenasarguments,andifthereareno argumentsitreadsfromthestandardinput.Itassumesthatblanklinesintheinputdelimitseparateitems,foreachofwhichadifferentlineofkeysshouldbegenerated.Thelinesofkeysare writtenonthestandardoutput.Keysareanyalphanumericstringintheinputnotamongthe mostfrequentwordsinEnglishandnotentirelynumeric(exceptthatall-numericstringsare acceptableiftheyarebetween1900and1999).Intheoutput,keysaretranslatedtolowercase, andtruncatedtosixcharactersinlength;anyassociatedpunctuationisremoved.Thefollowing flagargumentsarerecognizedbymkey: −cname Nameoffileofcommonwords;defaultis/usr/lib/eign. −fname Readalistoffilesfromnameandtakeeachasaninputargument. −ichars Ignorealllineswhichbeginwith‘%’followedbyanycharacterin chars. −kn Useatmostnkeysperinputitem.

-5- −ln Ignoreitemsshorterthannletterslong. −nm IgnoreasakeyanywordinthefirstmwordsofthelistofcommonEnglishwords.Thedefaultis100. −s Removethelabels(file:start,length)fromtheoutput;justgive thekeys.Usedwhensearchingratherthanindexing. −w Eachwholefileisaseparateitem;blanklinesinfilesareirrelevant. Thenormalargumentsforindexingreferencesarethedefaults,whichare−c/usr/lib/eign, −n100,and−l3.Forsearching,the−soptionisalsoneeded.Whenthebiglookallindexofall Englishfilesisrun,theoptionsare−w,−k50,and−f(filelist).Whenrunningontextualinput, themkeyprogramprocessesabout1000Englishwordsperprocessorsecond.Unlessthe−k optionisused(andtheinputfilesarelongenoughforittotakeeffect)theoutputofmkeyiscomparableinsizetoitsinput. Hashandinvert.Theinvprogramcomputesthehashcodesandwritestheinvertedfiles. Itreadstheoutputofmkeyandwritesthesetoffilesdescribedearlierinthissection.Itexpects oneargument,whichisusedasthebasenameforthethree(orfour)filestobewritten.AssuminganargumentofIndex(thedefault)theentryfileisnamedIndex.ia,thepostingfileIndex.ib, thetagfileIndex.ic,andthekeyfile(ifpresent)Index.id.Theinvprogramrecognizesthefollowingoptions: −a Appendthenewkeystoaprevioussetofinvertedfiles,making newfilesifthereisnooldsetusingthesamebasename. −d Writetheoptionalkeyfile.Thisisneededwhenyoucannot checkforfalsedropsbylookingforthekeysintheoriginal inputs,i.e.whenthekeyderivationprocedureiscomplicatedand theoutputkeysarenotwordsfromtheinputfiles. −hn Thehashtablesizeisn(default997);nshouldbeprime.Makingnbiggersavessearchtimeandspendsdiskspace. −i[u]name Takeinputfromfilename,insteadofthestandardinput;ifuis presentnameisunlinkedwhenthesortisstarted.Usingthis optionpermitsthesortscratchspacetooverlapthediskspace usedforinputkeys. −n Makeacompletelynewsetofinvertedfiles,ignoringprevious files. −p Pipeintothesortprogram,ratherthanwritingatemporary inputfile.Thissavesdiskspaceandspendsprocessortime. −v Verbosemode;printasummaryofthenumberofkeyswhichfinishedindexing. Abouthalfthetimeusedininvisinthecontainedsort.Assumingthesortisroughlylinear,however,aguessatthetotaltimingforinvis250keyspersecond.Thespaceusedisusually ofmoreimportance:theentryfileusesfourbytesperpossiblehash(notethe−hoption),andthe tagfilearound15-20bytesperitemindexed.Roughly,thepostingfilecontainsoneitemforeach keyinstanceandoneitemforeachpossiblehashcode;theitemsaretwobyteslongifthetagfile islessthan65336byteslong,andtheitemsarefourbyteswideifthetagfileisgreaterthan65536 byteslong.Notethattominimizestorage,thehashtablesshouldbeover-full;formostofthe filesindexedinthisway,thereisnootherrealchoice,sincetheentryfilemustfitinmemory. SearchingandRetrieving.Thehuntprogramretrievesitemsfromanindex.Itcombines,asmentionedabove,thetwopartsofphase(B):searchanddelivery.Thereasonwhyitis efficienttocombinedeliveryandsearchispartlytoavoidstartingunnecessaryprocesses,and partlybecausethedeliveryoperationmustbeapartofthesearchoperationinanycase.Because ofthehashing,thesearchparttakesplaceintwostages:firstitemsareretrievedwhichhavethe righthashcodesassociatedwiththem,andthentheactualitemsareinspectedtodeterminefalse drops,i.e.todetermineifanythingwiththerighthashcodesdoesn’treallyhavetherightkeys.

-6-Sincetheoriginalitemisretrievedtocheckonfalsedrops,itisefficienttopresentitimmediately, ratherthanonlygivingthetagasoutputandlaterretrievingtheitemagain.Iftherewereaseparatekeyfile,thisargumentwouldnotapply,butseparatekeyfilesarenotcommon. Inputtohuntistakenfromthestandardinput,onequeryperline.Eachqueryshouldbein mkey−soutputformat;alllowercase,nopunctuation.Thehuntprogramtakesoneargument whichspecifiesthebasenameoftheindexfilestobesearched.Onlyonesetofindexfilescanbe searchedatatime,althoughmanytextfilesmaybeindexedasagroup,ofcourse.Ifoneofthe textfileshasbeenchangedsincetheindex,thatfileissearchedwithfgrep;thismayoccasionally slowdownthesearching,andcareshouldbetakentoavoidhavingmanyoutofdatefiles.The followingoptionargumentsarerecognizedbyhunt: −a Givealloutput;ignorecheckingforfalsedrops. −Cn Coordinationleveln;retrieveitemswithnotmorethannterms oftheinputmissing;defaultC0,implyingthateachsearchterm mustbeintheoutputitems. −F[ynd] ‘‘−Fy’’givesthetextofalltheitemsfound;‘‘−Fn’’suppresses them.‘‘−Fd’’wheredisanintegergivesthetextofthefirstd items.Thedefaultis−Fy. −g Donotusefgreptosearchfileschangedsincetheindexwas made;printanerrorcommentinstead. −istring Takestringasinput,insteadofreadingthestandardinput. −ln Themaximumlengthofinternallistsofcandidateitemsisn; default1000. −ostring Puttextoutput(‘‘−Fy’’)instring;ofuseonlywheninvoked fromanotherprogram. −p Printhashcodefrequencies;mostlyforuseinoptimizinghash tablesizes. −T[ynd] ‘‘−Ty’’givesthetagsoftheitemsfound;‘‘−Tn’’suppressesthem. ‘‘−Td’’wheredisanintegergivesthefirstdtags.Thedefault is−Tn. −tstring Puttagoutput(‘‘−Ty’’)instring;ofuseonlywheninvokedfrom anotherprogram. Thetimingofhuntiscomplex.Normallythehashtableisoverfull,sothattherewillbe manyfalsedropsonanysingleterm;butamulti-termquerywillhavefewfalsedropsonall terms.Thusifaqueryisunderspecified(onesearchterm)manypotentialitemswillbeexamined anddiscardedasfalsedrops,wastingtime.Ifthequeryisoverspecified(adozensearchterms) manykeyswillbeexaminedonlytoverifythatthesingleitemunderconsiderationhasthatkey posted.Thevariationofsearchtimewithnumberofkeysisshowninthetablebelow.Queriesof varyinglengthwereconstructedtoretrieveaparticulardocumentfromthefileofreferences.In thesequencetotheleft,searchtermswerechosensoastoselectthedesiredpaperasquicklyas possible.Inthesequenceontheright,termswerechoseninefficiently,sothatthequerydidnot uniquelyselectthedesireddocumentuntilfourkeyshadbeenused.Thesamedocumentwasthe targetineachcase,andthefinalsetofeightkeysarealsoidentical;thedifferencesatfive,sixand sevenkeysareproducedbymeasurementerror,notbytheslightlydifferentkeylists. EfficientKeys InefficientKeys No.keysTotaldropsRetrievedSearchtimeNo.keysTotaldropsRetrievedSearchtime (incl.false)Documents(seconds)(incl.false)Documents(seconds) 11531.27168555.96 2110.11229292.72 3110.143880.95 4110.174110.18 5110.195110.21 -7-6110.236110.22 7110.277110.26 8110.298110.29 Aswouldbeexpected,theoptimalsearchisachievedwhenthequeryjustspecifiestheanswer; however,overspecificationisquitecheap.Roughly,thetimerequiredbyhuntcanbeapproximatedas30millisecondspersearchkeyplus75millisecondsperdroppeddocument(whetheritis afalsedroporarealanswer).Ingeneral,overspecificationcanberecommended;itprotectsthe useragainstadditionstothedatabasewhichturnpreviouslyuniquely-answeredqueriesinto ambiguousqueries. Thecarefulreaderwillhavenotedanenormousdiscrepancybetweenthesetimesandthe earlierquotedtimeofaround1.9secondsforasearch.Thetimesherearepurelyforthesearch andretrieval:theyaremeasuredbyrunningmanysearchesthroughasingleinvocationofthehunt programalone.Thenormalretrievaloperationinvolvesusingtheshelltosetupapipeline throughmkeytohuntandstartingbothprocesses;thisaddsafixedoverheadofabout1.7seconds ofprocessortimetoanysinglesearch.Furthermore,rememberthatallthesetimesareprocessor times:onatypicalmorningonourPDP11/70system,withaboutonedozenpeopleloggedon,to obtain1secondofprocessortimeforthesearchprogramtookbetween2and12secondsofreal time,withamedianof3.9secondsandameanof4.8seconds.Thus,althoughtheworkinvolved inasinglesearchmaybeonly200milliseconds,afteryouaddthe1.7secondsofstartupprocessor timeandthenassumea4:1elapsed/processortimeratio,itwillbe8secondsbeforeanyresponse isprinted. 3.SelectingandFormattingReferencesforTROFF Themajorapplicationoftheretrievalsoftwareisrefer,whichisatroffpreprocessorlike eqn.3Itscansitsinputlookingforitemsoftheform .[ imprecisecitation .] whereanimprecisecitationismerelyastringofwordsfoundintherelevantbibliographiccitation.Thisistranslatedintoaproperlyformattedreference.Iftheimprecisecitationdoesnot correctlyidentifyasinglepaper(eitherselectingnopapersortoomany)amessageisgiven.The databaseofcitationssearchedmaybetailoredtoeachsystem,andindividualusersmayspecify theirowncitationfiles.Onoursystem,thedefaultdatabaseisaccumulatedfromthepublication listsofthemembersofourorganization,plusabouthalfadozenpersonalbibliographiesthatwere collected.Thepresenttotalisabout4300citations,butthisincreasessteadily.Evennow,the databasecoversalargefractionoflocalcitations. Forexample,thereferencefortheeqnpaperabovewasspecifiedas ... preprocessorlike .Ieqn. .[ kernighancherryacm1975 .] Itscansitsinputlookingforitems ... Thispaperwasitselfprintedusingrefer.Theaboveinputtextwasprocessedbyreferaswellas tblandtroffbythecommand refermemo-file|tbl|troff−ms 3 -8-andthereferencewasautomaticallytranslatedintoacorrectcitationtotheACMpaperonmath-ematicaltypesetting. Theproceduretousetoplaceareferenceinapaperusingreferisasfollows.First,usethe lookbibcommandtocheckthatthepaperisinthedatabaseandtofindoutwhatkeysarenecessarytoretrieveit.Thisisdonebytypinglookbibandthentypingsomepotentialqueriesuntila suitablequeryisfound.Forexample,hadonestartedtofindtheeqnpapershownabovebypresentingthequery $lookbib kernighancherry (EOT) lookbibwouldhavefoundseveralitems;experimentationwouldquicklyhaveshownthatthequery givenaboveisadequate.Overspecifyingthequeryisofcourseharmless.Aparticularlycareful readermayhavenoticedthat‘‘acm’’doesnotappearintheprintedcitation;wehavesupplementedsomeofthedatabaseitemswithcommonextrakeywords,suchascommonabbreviations forjournalsorothersources,toaidinsearching. Ifthereferenceisinthedatabase,thequerythatretrieveditcanbeinsertedinthetext, between.[and.]brackets.Ifitisnotinthedatabase,itcanbetypedintoaprivatefileofreferences,usingtheformatdiscussedinthenextsection,andthenthe−poptionusedtosearchthis privatefile.Suchacommandmightread(iftheprivatereferencesarecalledmyfile) refer−pmyfiledocument|tbl|eqn|troff−ms... wheretbland/oreqncouldbeomittedifnotneeded.Theuseofthe−msmacros4orsomeother macropackage,however,isessential.Referonlygeneratesthedataforthereferences;exactformattingisdonebysomemacropackage,andifnoneissuppliedthereferenceswillnotbeprinted. Bydefault,thereferencesarenumberedsequentially,andthe−msmacrosformatreferences asfootnotesatthebottomofthepage.Thismemorandumisanexampleofthatstyle.Other possibilitiesarediscussedinsection5below. 4.ReferenceFiles. Areferencefileisasetofbibliographicreferencesusablewithrefer.Itcanbeindexedusing thesoftwaredescribedinsection2forfastsearching.Whatreferdoesistoreadtheinputdocumentstream,lookingforimprecisecitationreferences.Itthensearchesthroughreferencefilesto findthefullcitations,andinsertsthemintothedocument.Theformatofthefullcitationis arrangedtomakeitconvenientforamacropackage,suchasthe−msmacros,toformatthereferenceforprinting.Sincetheformatofthefinalreferenceisdeterminedbythedesiredstyleofoutput,whichisdeterminedbythemacrosused,referavoidsforcinganykindofreferenceappearance.Allitdoesisdefineasetofstringregisterswhichcontainthebasicinformationaboutthe reference;andprovideamacrocallwhichisexpandedbythemacropackagetoformatthereference.Itistheresponsibilityofthefinalmacropackagetoseethatthereferenceisactually printed;ifnomacrosareused,andtheoutputofreferfeduntranslatedtotroff,nothingatallwill beprinted. Thestringsdefinedbyreferaretakendirectlyfromthefilesofreferences,whichareinthe followingformat.Thereferencesshouldbeseparatedbyblanklines.Eachreferenceisasequence oflinesbeginningwith%andfollowedbyakey-letter.Theremainderofthatline,andsuccessive linesuntilthenextlinebeginningwith%,containtheinformationspecifiedbythekey-letter.In general,referdoesnotinterprettheinformation,butmerelypresentsittothemacropackagefor finalformatting.Auserwithaseparatemacropackage,forexample,canaddnewkey-lettersor usetheexistingonesforotherpurposeswithoutbotheringrefer. Themeaningofthekey-lettersgivenbelow,inparticular,isthatassignedbythe−ms macros.Notallinformation,obviously,isusedwitheachcitation.Forexample,ifadocumentis 4 -9-bothaninternalmemorandumandajournalarticle,themacrosignorethememorandumversion andciteonlythejournalarticle.Somekindsofinformationarenotusedatallinprintingthereference;ifauserdoesnotlikefindingreferencesbyspecifyingtitleorauthorkeywords,andprefers toaddspecifickeywordstothecitation,afieldisavailablewhichissearchedbutnotprinted(K). Thekeyletterscurrentlyrecognizedbyreferand−ms,withthekindofinformationimplied, are: KeyInformationspecifiedKeyInformationspecified AAuthor’sname NIssuenumber BTitleofbookcontainingitemOOtherinformation CCityofpublication PPage(s)ofarticle DDate RTechnicalreportreference EEditorofbookcontainingitemTTitle GGovernment(NTIS)orderingnumberVVolumenumber IIssuer(publisher) JJournalname KKeys(forsearching) Xor LLabel Yor MMemorandumlabel ZInformationnotusedbyrefer Forexample,asamplereferencecouldbetypedas: %TBoundsontheComplexityoftheMaximal CommonSubsequenceProblem %Zctr127 %AA.V.Aho %AD.S.Hirschberg %AJ.D.Ullman %JJ.ACM %V23 %N1 %P1-12 %Mabcd-78 %DJan.1976 Orderisirrelevant,exceptthatauthorsareshownintheordergiven.Theoutputofreferisa streamofstringdefinitions,oneforeachofthefieldsofeachreference,asshownbelow. .]- .ds[Aauthors’names... .ds[Ttitle... .ds[Jjournal... ... .][type-number Thespecialmacro.]−precedesthestringdefinitionsandthespecialmacro.][follows.Theseare changedfromtheinput.[and.]sothatrunningthesamefilethroughreferagainisharmless. The.]−macrocanbeusedbythemacropackagetoinitialize.The.][macro,whichshouldbe usedtoprintthereference,isgivenanargumenttype-numbertoindicatethekindofreference,as follows:

-10-ValueKindofreference 1Journalarticle 2Book 3Articlewithinbook 4Technicalreport 5BellLabstechnicalmemorandum 0Other Thereferenceisflaggedinthetextwiththesequence \*([.number\*(.] wherenumberisthefootnotenumber.Thestrings[.and.]shouldbeusedbythemacropackagetoformatthereferenceflaginthetext.Thesestringscanbereplacedforaparticularfootnote,asdescribedinsection5.Thefootnotenumber(orothersignal)isavailabletothereference macro.][asthestringregister[F. Insomecasesuserswishtosuspendthesearching,andmerelyusethereferencemacroformatting.Thatis,theuserdoesn’twanttoprovideasearchkeybetween.[and.]brackets,but merelythereferencelinesfortheappropriatedocument.Alternatively,theusercanwishtoadda fewfieldstothoseinthereferenceasinthestandardfile,oroverridesomefields.Alteringor replacingfields,orsupplyingwholereferences,iseasilydonebyinsertinglinesbeginningwith%; anysuchlineistakenasdirectinputtothereferenceprocessorratherthankeystobesearched. Thus .[ key1key2key3... %QNewformatitem %ROverridereportname .] makestheindicateschangestotheresultofsearchingforthekeys.Allofthesearchkeysmustbe givenbeforethefirst%line. Ifnosearchkeysareprovided,anentirecitationcanbeprovidedin-lineinthetext.For example,iftheeqnpapercitationweretobeinsertedinthisway,ratherthanbysearchingforit inthedatabase,theinputwouldread ... preprocessorlike .Ieqn. .[ %AB.W.Kernighan %AL.L.Cherry %TASystemforTypesettingMathematics %JComm.ACM %V18 %N3 %P151-157 %DMarch1975 .] Itscansitsinputlookingforitems ... Thiswouldproduceacitationofthesameappearanceasthatresultingfromthefilesearch. Asshown,fieldsarenormallyturnedintotroffstrings.Sometimesuserswouldratherhave themdefinedasmacros,sothatothertroffcommandscanbeplacedintothedata.Whenthisis necessary,simplydoublethecontrolcharacter%inthedata.Thustheinput -11- .[ %V23 %%M BellLaboratories, MurrayHill,N.J.07974 .] isprocessedbyreferinto .ds[V23 .de[M BellLaboratories, MurrayHill,N.J.07974 .. Theinformationafter%%Misdefinedasamacrotobeinvokedby.[Mwhiletheinformation after%Visturnedintoastringtobeinvokedby\∗([V.Atpresent−msexpectsallinformation asstrings. 5.CollectingReferencesandotherReferOptions Normally,thecombinationofreferand−msformatsoutputastrofffootnoteswhichareconsecutivelynumberedandplacedatthebottomofthepage.However,optionsexisttoplacethe referencesattheend;toarrangereferencesalphabeticallybyseniorauthor;andtoindicatereferencesbystringsinthetextoftheform[Name1975a]ratherthanbynumber.Wheneverreferences arenotplacedatthebottomofapageidenticalreferencesarecoalesced. Forexample,the−eoptiontoreferspecifiesthatreferencesaretobecollected;inthiscase theyareoutputwheneverthesequence .[ $LIST$ .] isencountered.Thus,toplacereferencesattheendofapaper,theuserwouldrunreferwiththe −eoptionandplacetheabove$LIST$commandsafterthelastlineofthetext.Referwillthen moveallthereferencestothatpoint.Toaidinformattingthecollectedreferences,referwrites thereferencesprecededbytheline .]< andfollowedbytheline .]> toinvokespecialmacrosbeforeandafterthereferences. Anotherpossibleoptiontoreferisthe−soptiontospecifysortingofreferences.The default,ofcourse,istolistreferencesintheorderpresented.The−soptionimpliesthe−e option,andthusrequiresa .[ $LIST$ .] entrytocalloutthereferencelist.The−soptionmaybefollowedbyastringofletters,numbers, and‘+’signsindicatinghowthereferencesaretobesorted.Thesortisdoneusingthefields whosekey-lettersareinthestringassortingkeys;thenumbersindicatehowmanyofthefields aretobeconsidered,with‘+’takenasalargenumber.Thusthedefaultis−sADmeaning‘‘Sort onseniorauthor,thendate.’’Tosortonallauthorsandthentitle,specify−sA+T.Andtosort ontwoauthorsandthenthejournal,write−sA2J.

-12-Otheroptionstoreferchangethesignalorlabelinsertedinthetextforeachreference.Nor-mallythesearejustsequentialnumbers,andtheirexactplacement(withinbrackets,assuper-scripts,etc.)isdeterminedbythemacropackage.The−loptionreplacesreferencenumbersby stringscomposedoftheseniorauthor’slastname,thedate,andadisambiguatingletter.Ifa numberfollowsthelasin−l3onlythatmanylettersofthelastnameareusedinthelabelstring. Toabbreviatethedateaswelltheform-lm,nshortensthelastnametothefirstmlettersandthe datetothelastndigits.Forexample,theoption−l3,2wouldrefertotheeqnpaper(reference3) bythesignalKer75a,sinceitisthefirstcitedreferencebyKernighanin1975. Auserwishingtospecifyparticularlabelsforaprivatebibliographymayusethe−koption. Specifying−kxcausesthefieldxtobeusedasalabel.ThedefaultisL.Ifthisfieldendsin−, thatcharacterisreplacedbyasequenceletter;otherwisethefieldisusedexactlyasgiven. Ifnoneoftherefer-producedsignalsaredesired,the−boptionentirelysuppressesauto-matictextsignals. Iftheuserwishestooverridethe−mstreatmentofthereferencesignal(whichisnormally toenclosethenumberinbracketsinnroffandmakeitasuperscriptintroff)thiscanbedoneeasily.Ifthelines.[or.]containanythingfollowingthesecharacters,theremaindersoftheselines areusedtosurroundthereferencesignal,insteadofthedefault.Thus,forexample,tosay‘‘See reference(2).’’andavoid‘‘Seereference.2’’theinputmightappear Seereference .[( imprecisecitation... .]). Notethatblanksaresignificantinthisconstruction.Ifapermanentchangeisdesiredinthestyle ofreferencesignals,however,itisprobablyeasiertoredefinethestrings[.and.](whichareused tobracketeachsignal)thantochangeeachcitation. Althoughnormallyreferlimitsitselftoretrievingthedataforthereference,andleavestoa macropackagethejobofarrangingthatdataasrequiredbythelocalformat,therearetwospecialoptionsforrearrangementsthatcannotbedonebymacropackages.The−coptionputs fieldsintoalluppercase(CAPS-SMALLCAPSintroffoutput).Thekey-lettersindicatedwhat informationistobetranslatedtouppercasefollowthec,sothat−cAJmeansthatauthors’ namesandjournalsaretobeincaps.The−aoptionwritesthenamesofauthorslastnamefirst, thatisA.D.Hall,Jr.iswrittenasHall,A.D.Jr.ThecitationformoftheJournalofthe ACM,forexample,wouldrequireboth−cAand−aoptions.Thisproducesauthors’namesin thestyleKERNIGHAN,B.W.ANDCHERRY,L.L.forthepreviousexample.The−aoptionmay befollowedbyanumbertoindicatehowmanyauthornamesshouldbereversed;−a1(without any−coption)wouldproduceKernighan,B.W.andL.L.Cherry,forexample. Finally,thereisalsothepreviously-mentioned−poptiontolettheuserspecifyaprivatefile ofreferencestobesearchedbeforethepublicfiles.Notethatreferdoesnotinsistonapreviously madeindexforthesefiles.Ifafileisnamedwhichcontainsreferencedatabutisnotindexed,it willbesearched(moreslowly)byreferusingfgrep.Inthiswayitiseasyforuserstokeepsmall filesofnewreferences,whichcanlaterbeaddedtothepublicdatabases.