÷ƒ’À;è TeX output 1994.10.13:2153‹ÿÿÿÿ …(õ ý†×  [(õ ýÿ½u‘põ(óDÓítG®G®cmr17ÆIndex–7tPreparation“and“ProsŽcessingŸùº¯ó !",š cmsy10ËŽŽŽŸ%lÏ’Ä,;ó0}h!Ó cmsl12ÛP¬rehong‘ê¨ChenŸû¥2ó8¾KÈ cmsy8ãyŽŽŽŽ¤’²p^ÛMic¬rhael–ê¨A.“HarrisonŽŽ¡¡’¡ ¿óX«Q cmr12ÇComputer–ê¨Science“DivisionŽŽ¡’ª¨Univ•¬rersit“y–ê¨of“CaliforniaŽŽ¡’´ÏBerk¬reley‘ÿV,–ê¨CA“94720ŽŽŽŽŽ ›é’Ð\,ó#ò"V cmbx10ÎAbstractŽŸ9C‘3h¨óKñ`y cmr10²Index–/Ýpreparation“is“a“tedious“and“time-consuming“task.‘`This“papGer“indicates“ho¸ãwŽ¤ ‘$h§the–jnindexing“prošGcess“can“b˜e“automated“in“a“w•¸ãa“y–jnthat“is“largely“indep˜enden¸ãt“of“a“sp˜eci cŽ¡‘$h§t¸ãypšGesetting–²•system“and“indep˜enden¸ãt“of“the“format“b˜eing“used.‘;‡F‘ÿ*ªundamen¸ãtal“issues“relatedŽ¡‘$h§to–ÜSthis“prošGcess“are“iden¸ãti ed“and“analyzed.‘ ÀSp˜eci cally‘ÿ*ª,‘>wš¸ãe“dev˜elop“a“framew˜ork“forŽ¡‘$h§placing–Ìñindex“commands“in“the“došGcumen¸ãt.‘ØšIn“addition,‘ê×the“design“of“a“general“purp˜oseŽ¡‘$h§index–8˜proGcessor“that“transforms“a“raš¸ãw“index“in˜to“an“alphabGetized“v˜ersion“is“describGed.Ž¡‘$h§The–õVresulting“system“has“pro•¸ãv“ed›õVv“ery˜useful˜and˜e ectiv“e˜in˜proGducing˜indexes˜for˜sev“eralŽ¡‘$h§b•Go“oks,›˜6tec¸ãhnical‘hîrep“orts,˜and–hîman¸ãuals.‘"ûA‘h³comparison“of“our“system“with“indexing“facilitiesŽ¡‘$h§a¸ãv›ÿqÇailable–UUfrom“a“v˜arietš¸ãy“of“other“doGcumen˜t“preparation“en˜vironmen˜ts“is“giv˜en.Ž¡‘3h¨ó,ý': cmti10×Keywor‘ÿ}'ds‘Ò!²:‘Xƒindex–"Íplacemen¸ãt,›,èindex“proGcessing,˜source-language“moGdel,˜direct“manipu-Ž¡‘$h§lation.ŽŸ+.¼‘ £óXÂÖN ff cmbx12ëX1Ž‘!UnInŒÌtros3ductionŽŸ>X‘ £óKñ`y ó3 cmr10¹Although–_:there“has“bMÞeen“a“great“deal“of“activit²!y“in“electronic“publishing“[1],‘othere“are“stillŽ¤fg‘ £aspšMÞects–Wof“do˜cumen²!t“comp˜osition“that“ha•²!v“e–Wnot“b˜een“fully“automated.‘ÕOne“of“the“most“time-Ž¡‘ £consuming––9concerns“is“the“preparation“of“an“index.‘ƒ$In“ordinary“b•MÞo“oks,‘Ì©an––9index“allo²!ws“a“readerŽ‘ £Ÿ-£‰ff± Ÿ LÍ‘ Q Ÿü-=ó9q¡% cmsy6䎎‘¦aóFo´‹Ç cmr9ëFSpAÇonsored–Ízin“part“bš¾9y“the“National“Science“F‘ÿ:«oundation“under“Gran˜t“MCS-8311787,‘ûƒand“b˜y“the“DefenseŽ¤ Adv‘ÿ|ranced–8³Researcš¾9h“Pro‘ƒŽjects“Agency“(DoD),“ARP‘ÿ:«A‘8ªOrder“No.‘†Ž4871,‘A‹monitored“b˜y“Space“and“Na˜v‘ÿ|ral“W‘ÿ:«arfareŽ¡Systems–TCommand,“under“Con¾9tract“No.‘pN00039-84-C-0089.ŽŸ J=‘ ´œŸü-=äyŽŽ‘¦aëFAdditional–TsuppšAÇort“has“b˜een“proš¾9vided“b˜y“an“IBM“Graduate“F‘ÿ:«ello˜wship.ŽŽŸ’㟄¹1ŽŽŒ‹* …(õ ý†× Ÿü™š’¾6e¹2Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £to–\access“essenš²!tial“information“easily‘ÿe.‘A‘\np•MÞo“or–\index“with“man˜y“omissions“or“p•MÞo“orly‘\c˜hosenŽ¤fg‘ £concepts–Q(detracts“from“other“aspšMÞects“of“the“b˜o˜ok.‘ÁsF‘ÿeor“highly“complex“tec²!hnical“material“thatŽ¡‘ £maš²!y–±Õinclude“computer“programs,‘´°di eren˜t“kinds“of“indices“ma˜y“reference“ev˜en“the“iden˜ti ersŽ¡‘ £of–÷ya“programming“language.‘£ŽA‘÷Mgo•MÞo“d–÷yexample“of“an“elabšMÞorate“indexing“sc²!heme“can“b˜e“found“inŽ¡‘ £Kn²!uth's›ËêóYý': ó3 cmti10ëYT‘þ"RŸ[wEŽ‘)¡X:‘N|The‘ mPr–ÿp¹o“gr“am‘¢õ¹[2]˜and˜his˜WEB‘Ëàsystem˜[3]˜in˜general.‘NhF‘ÿeor˜computer˜programsŽ¡‘ £likš²!e–x0these,‘¬£completeness“is“essen˜tial“and“the“accuracy“of“traditional“hand“methoMÞds“will“notŽ¡‘ £suce–¦ffor“soft•²!w“are–¦fengineering“applications.Ž¡‘£Standard–®Œauthors'“guides,›°–suc²!h“as“Reference“[4],˜recommend“that“index“terms“bMÞe“mark²!edŽ¡‘ £on–í page“prošMÞofs“or“on“a“separate“set“of“galley“pro˜ofs.‘³ŠThe“traditional“metho˜d“is“to“use“3–žgó[!",š ó3 cmsy10ë[“¹5Ž¡‘ £cards,‘-Ëappropriately–¤called“index“cards.‘«A‘~page“n•²!um“bMÞer–¤is“added“to“a“card“when“a“reference“isŽ¡‘ £encounš²!tered.‘ÆSorting–^ùis“done“b˜y“hand“and“the“proMÞcess“is“tedious“and“error-prone.‘ÆComputersŽ¡‘ £o er–;šan“oppMÞortunitš²!y“to“signi can˜tly“reduce“the“amoun˜t“of“labMÞor“in˜v˜ested“in“this“proMÞcess“whileŽ¡‘ £noticeably–¦fimproš²!ving“the“qualit˜y“of“the“resulting“index.Ž¡‘£This–¡ÅpapšMÞer“indicates“ho²!w“the“indexing“pro˜cess“can“b˜e“automated“in“a“w•²!a“y–¡Åthat“is“largelyŽ¡‘ £indepšMÞenden²!t–‹‹of“a“sp˜eci c“t²!yp˜esetting“system“and“indep˜enden²!t“of“the“format“b˜eing“used.‘”Sp˜ecif-Ž¡‘ £ically‘ÿe,‘;ww•²!e› »dev“elop˜a˜framew“ork˜for˜placing˜index˜commands˜in˜the˜doMÞcumen“t.‘±OIn˜addition,‘;wtheŽ¡‘ £design–O of“a“general“purpšMÞose“index“pro˜cessor“that“transforms“a“raš²!w“index“in˜to“an“alphabMÞetizedŽ¡‘ £vš²!ersion–òtis“describMÞed.‘¡âThese“concepts“ha˜v˜e“bMÞeen“implemen˜ted“as“part“of“an“extensiv˜e“authoringŽ¡‘ £en•²!vironmen“t–bÔ[5].‘'This“en•²!vironmen“t–bÔincludes“a“suite“of“Lisp“programs“for“the“index“placingŽ¡‘ £facilit²!y–±—and“a“C‘±Rprogram“for“the“index“prošMÞcessor.‘ÿoThe“resulting“system“has“b˜een“success-Ž¡‘ £fully–used“in“prošMÞducing“indexes“for“some“b˜o˜oks“[6,7]“and“a“n•²!um“b˜er–of“tec²!hnical“rep˜orts“andŽ¡‘ £man²!uals.Ž¡‘£Indexing–Ïissues“under“bMÞoth“ëYsour–ÿp¹c“e-language‘ïp¹and›ÏëYdir“e“ct-manipulation‘óÚ¹[8,9]˜paradigms˜areŽ¡‘ £considered.‘_In–;‘a“source-language“based“system,‘`Üthe“user“spšMÞeci es“the“do˜cumenš²!t“with“in˜ter-Ž¡‘ £spMÞersed–‹¿commands,›Åwhic²!h“is“then“passed“to“a“formatter,˜and“the“output“is“obtained.‘çTheŽ¡‘ £source-language–ÎHusually“proš²!vides“some“abstraction“and“con˜trol“mec˜hanisms“suc˜h“as“proMÞce-Ž¡‘ £dures,–ì—macros,“conditionals,“v‘ÿdDariables,“etc.‘rin›¾$m•²!uc“h˜the˜same˜w“a“y˜as˜a˜high-lev“el˜programmingŽ¡‘ £language–%došMÞes.‘€In“a“direct-manipulation“en•²!vironmen“t,‘Åethe–%user“manipulates“the“do˜cumen²!t“out-ŽŽŽŒ‹ m …(õ ý†× Ÿü™š’¾6e¹3Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £put–o,appMÞearance“directly“bš²!y“in˜v˜oking“built-in“opMÞerators“a˜v‘ÿdDailable“through“men˜us“and“buttons.Ž¤fg‘ £These–&†systems“are“highly“in•²!teractiv“e;‘Q&the–&†result“of“in•²!v“oking–&†an“opMÞeration“is“observš²!ed“instan˜ta-Ž¡‘ £neously‘ÿe,‘åóthereb²!y–Ù=creating“an“illusion“that“the“user“is“\directly"“manipulating“the“underlyingŽ¡‘ £ob‘›»ject.Ž¡‘£The–‹došMÞcumen²!t“attributes“in“direct-manipulation“systems“are“usually“sp˜eci ed“b²!y“a“declar-Ž¡‘ £ativš²!e–äÕlanguage“encapsulated“as“form-based“propMÞert˜y“sheets.‘XThese“propMÞert˜y“sheets“correspMÞondŽ¡‘ £to–{textual“markup“tags“that“can“bšMÞe“imp˜orted“to“or“exp˜orted“from“the“direct-manipulationŽ¡‘ £system–[for“doMÞcumenš²!t“in˜terc˜hange“purpMÞoses.‘ ûòWhile“a“source“represen˜tation“is“main˜tainedŽ¡‘ £explicitly–;in“the“source-language“mošMÞdel,‘Zpthe“notion“of“a“do˜cumenš²!t“seman˜tics“spMÞeci cationŽ¡‘ £language–¦fis“somewhat“implicit“in“direct-manipulation“systems.Ž¡‘£Some–Ÿ]pMÞeople“ha•²!v“e–Ÿ]called“direct-manipulation“systems“óŒ-ø cmcsc10ÅWYSIWYG‘Ÿ[¹(ëYwhat-you-se‘ÿp¹e-is-what-Ž¡‘ £you-get‘ ê¹).‘=æThe›Æit•²!w“o˜concepts˜are˜not˜equiv‘ÿdDalen“t,‘iho“w“ev“er.‘=æÅWYSIWYG‘ƹrefers˜to˜the˜corre-Ž¡‘ £sp•MÞondence›x1b“et•²!w“een˜what˜is˜presen“ted˜on˜a˜video˜displa“y˜and˜what˜can˜bMÞe˜generated˜on˜someŽ¡‘ £other–³8device.‘RIn“the“conš²!text“of“electronic“publishing,‘¶lÅWYSIWYG‘³4¹means“that“there“is“a“v˜eryŽ¡‘ £close–±lrelationship“in“terms“of“došMÞcumen²!t“app˜earance“b˜et•²!w“een–±la“screen“represen²!tation“and“theŽ¡‘ £ nal–Z™hardcopš²!y‘ÿe.‘úuDirect“manipulation“is“a“more“general“concept“that“moMÞdels“user“in˜terfaces.Ž¡‘ £A‘Gdirect-manipulation–doMÞcumenš²!t“preparation“system“ma˜y“not“ha˜v˜e“a“ÅWYSIWYG‘G¹relation-Ž¡‘ £ship›•|bMÞet•²!w“een˜its˜displa“y˜represen“tation˜and˜the˜ nal˜hardcop“y›ÿe.‘Ø:Con“v“ersely˜,‘˜Þa‘•|batc“h-orien“ted,Ž¡‘ £source-language–¦fbased“formatter“maš²!y“bMÞe“coupled“with“a“preview˜er“that“is“ÅWYSIWYG¹.Ž¡‘£This–(‹papMÞer“presenš²!ts“some“general“indexing“problems“and“our“solutions“in“a“top-do˜wnŽ¡‘ £fashion.‘/First–Ðw²!e“discuss“the“desirable“features“of“an“index“proMÞcessor“and“then“some“designŽ¡‘ £and–Áimplemenš²!tation“considerations“for“suc˜h“a“proMÞcessor.‘õîOur“goal“is“to“arriv˜e“at“generalŽ¡‘ £purpMÞose–3solutions.‘ ƒùNext,‘–Fa“framewš²!ork“is“in˜troMÞduced“under“whic˜h“an“author“en˜ters“indexŽ¡‘ £commands–eor“tags“with“m•²!uc“h–ereduced“o•²!v“erhead.‘ñThe–eexamples“sho²!wn“are“in“L‘üÙŸþ•ëÅaŽ‘Œ„¹T‘þ,³ŸLØEŽ‘B X“[10],‘”ÃaŽ¡‘ £high-lev•²!el›•èdoMÞcumen“t˜preparation˜language˜based˜on˜T‘þ,³Ÿ[wEŽ‘B X˜[11].‘¬cThe˜moMÞdel,›ÑÈho“w“ev“er,˜is‘•ènotŽ¡‘ £restricted–.$to“an²!y“particular“formatting“language,‘Pnor“to“the“source-language“paradigm.‘uW‘ÿeeŽ¡‘ £also–­eexamine“some“unique“indexing“issues“in“electronic“doMÞcumenš²!t“dev˜elopmen˜t“en˜vironmen˜tsŽ¡‘ £that–%—do“not“seem“to“ nd“appropriate“counš²!terparts“in“traditional“prin˜ted“material.‘²îFinally“ourŽŽŽŒ‹ …(õ ý†× Ÿü™š’¾6e¹4Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £indexing–$Ffacilities“are“ev›ÿdDaluated“against“those“a²!v˜ailable“in“other“formatting“systems“suc²!h“asŽ¤fg‘ £ó`p®0J ó3 cmsl10ë`ScribMÞe‘Cm¹[12],–¦fë`tro ‘Äá¹[13],“and“some“direct-manipulation“en•²!vironmen“ts.ŽŸ+l‡‘ £ëX2Ž‘!UnBasic‘ffT‘þ¦fasksŽŸ>X‘ £¹Index–¦fpreparation“is“a“proMÞcess“in•²!v“olving–¦fthe“follo²!wing“steps:ŽŸýÊ‘ðI.ŽŽŽ‘$h§Placing–dindex“commands“in“the“doMÞcumenš²!t“source,‘0Ëwhic˜h“presumably“comprises“m˜ultipleŽ¡‘$h§ les.‘ÝÝAn–¦findex“command“takš²!es“a“single“argumen˜t:‘ÝÝthe“k˜ey“to“bMÞe“indexed.Ž©<‘­üIMÞI.ŽŽŽ‘$h§Creating–Fa“raš²!w“index“ le“whose“en˜tries“eac˜h“consists“of“t˜w˜o“argumen˜ts:‘•žthe“index“k˜eyŽ¡‘$h§and–¦fthe“page“on“whic²!h“the“index“command“appMÞears.Ž¦‘kÚI•MÞI“I.ŽŽŽ‘$h§ProMÞcessing– òthe“raš²!w“index“ le.‘ M€Here,‘”all“index“k˜eys“are“sorted“alphabMÞetically‘ÿe.‘ M€P˜ageŽ¡‘$h§n•²!um“bMÞers–’under“the“same“kš²!ey“are“merged“and“successiv˜e“n˜um˜bMÞers“ma˜y“bMÞe“collected“in˜toŽ¡‘$h§in²!terv‘ÿdDals›W (e.g.,‘ƒîó^ßêIn“Step“I˜I˜I,“this“ra²!w“index“together“withŽ¡‘ £some–óÚoptional“stš²!yle“information“are“tak˜en“as“input“to“the“index“prošMÞcessor“and“an“alphab˜etizedŽ¡‘ £v²!ersion–¦fis“created.‘ÝÝFinally“in“Step“IV,“the“index“is“formatted“to“yield“the“ultimate“result.ŽŽŽŽŒ‹. …(õ ý†× Ÿü™š’¾6e¹6Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õŸÔIa þ*Ée’ç1qŸ}„ ™™ffŽŽ¤ ™™‘³Ië`P²!age‘¦fiv‘ð¹:Ž‘F-¶ë^\index{alpha}‘VHŸ}„ ™™ffŽŽ¡‘³Ië`P²!age‘¦f1‘ß9¹:Ž‘F-¶ë^\index{alpha}‘VHŸ}„ ™™ffŽŽ¡‘³Ië`P²!age‘¦f2‘ß9¹:Ž‘F-¶ë^\index{alpha}‘VHŸ}„ ™™ffŽŽ¡‘³Ië`P²!age‘¦f3‘ß9¹:Ž‘F-¶ë^\index{alpha}‘VHŸ}„ ™™ffŽŽ¡‘³Ië`P²!age‘¦f11‘ß9¹:Ž‘F-¶ë^\index{alphabeta|see{beta}}‘ÌÍŸ}„ ™™ffŽŽ¡‘³Ië`P²!age‘¦f14‘ß9¹:Ž‘F-¶ë^\index{alpha@{\it‘¿ªalpha\/}}‘ÌÍŸ}„ ™™ffŽŽ¡‘F-¶\index{beta|bold}‘?IqŸ}„ ™™ffŽŽ¡‘³Ië`P²!age‘¦f22‘ß9¹:Ž‘F-¶ë^\index{alpha!beta!gamma}‘ ËŸ}„ ™™ffŽŽ¡‘³Ië`P²!age‘¦f38‘ß9¹:Ž‘F-¶ë^\index{alpha!delta}‘3ÊŸ}„ ™™ffŽŽ¡’ç1qŸ}„ ™™ffŽŽŽŽ¤ ™š’íq\indexentry{alpha}{iv}ŽŽ¡’íq\indexentry{alpha}{1}ŽŽ¡’íq\indexentry{alpha}{2}ŽŽ¡’íq\indexentry{alpha}{3}ŽŽ¡’íq\indexentry{alphabeta|see{beta}}{11}ŽŽ¡’íq\indexentry{alpha@{\it‘¿ªalpha\/}}{14}ŽŽ¡’íq\indexentry{beta|bold}{14}ŽŽ¡’íq\indexentry{alpha!beta!gamma}{22}ŽŽ¡’íq\indexentry{alpha!delta}{38}ŽŽ¡ŽŽ‘ £ ˜zç‰ffº§\Ÿ…’궟}„ ™™ffŽŽ¤ ™™‘HèS\begin{theindex}Ž’궟}„ ™™ffŽŽ¡’궟}„ ™™ffŽŽ¡‘HèS\item–¿ªalpha,“iv,“1-3Ž’궟}„ ™™ffŽŽ¡‘Tg§\subitem‘¿ªbetaŽ’궟}„ ™™ffŽŽ¡‘_æû\subsubitem–¿ªgamma,“22Ž’궟}„ ™™ffŽŽ¡‘Tg§\subitem–¿ªdelta,“38Ž’궟}„ ™™ffŽŽ¡‘HèS\item–¿ª{\it“alpha\/},“14Ž’궟}„ ™™ffŽŽ¡‘HèS\item–¿ªalphabeta,“\see{beta}{11}Ž’궟}„ ™™ffŽŽ¡’궟}„ ™™ffŽŽ¡‘HèS\indexspaceŽ’궟}„ ™™ffŽŽ¡’궟}„ ™™ffŽŽ¡‘HèS\item–¿ªbeta,“\bold{14}Ž’궟}„ ™™ffŽŽ¡’궟}„ ™™ffŽŽ¡‘HèS\end{theindex}Ž’궟}„ ™™ffŽŽŽŽ¤ ™š’tó¹alpha,–¦fiv,“1{3ŽŽ¡’(tóbMÞetaŽŽ¡’2tógamma,‘¦f22ŽŽ¡’(tódelta,‘¦f38ŽŽ¡’tóëYalpha‘× ¹,‘¦f14ŽŽ¡’tóalphab•MÞeta,‘¦fëYse‘ÿp¹e‘y¹b“etaŽŽ¡¡’tóbMÞeta,‘¦fó\ò"V ó3 cmbx10ë\14ŽŽ¡ŽŽ á…¹Figure›ÄÔ2:‘¹ëYThe–éstepwise“development“of“index“pr–ÿp¹o“c“essing‘ø¹.‘9'This˜example˜is˜spMÞeci ed˜in˜L‘üÙŸþ•ëÅaŽ‘Œ„¹T‘þ,³ŸLØEŽ‘B X.Ž¤ ™š(a)–?Âë`T‘ÿeop“Left=¹:‘–Occurrences“of“index“commands“in“the“doMÞcumen²!t“source.‘ ©òNote“that“pageŽ¡n•²!um“bMÞers–oßare“unknoš²!wn“at“the“time“of“input“when“a“source-based“formatter“lik˜e“L‘üÙŸþ•ëÅaŽ‘Œ„¹T‘þ,³ŸLØEŽ‘B X‘oÑis“used.Ž¡P•²!age›¶ñn“um“bMÞers˜are˜included˜here˜simply˜to˜illustrate˜where˜eac“h˜instance˜will˜oMÞccur.‘}(b)˜ë`T‘ÿeopŽ¡Righ•²!tš=¹:‘Üâra“w–%èindex“ le“generated“b²!y“L‘üÙŸþ•ëÅaŽ‘Œ„¹T‘þ,³ŸLØEŽ‘B X.“(c)“ë`Bottom“Left˜¹:‘ÜâalphabMÞetized“index“ le.‘ \d(d)Ž¡ë`Bottom–¦fRigh²!t=¹:‘ÝÝformatted“ nal“index.ŽŽŽŽŒ‹7] …(õ ý†× Ÿü™š’¾6e¹7Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘£Based–¯on“the“example“givš²!en“in“Figure“2,‘pAthese“four“steps“are“explained“bMÞelo˜w,‘pAwhereŽ¤fg‘ £Steps–çrI›çband“I•MÞI“I˜are–çrfurther“expanded“in“subsequenš²!t“sections.‘¡Issues“in˜v˜olv˜ed“in“Steps“IMÞI‘çbandŽ¡‘ £IV–¦fare“less“complex“and“are“co•²!v“ered–¦fonly“in“this“section.ŽŸ$R…‘ £ó"ÂÖN  cmbx12Í2.1Ž‘'È£Placing–€Index“CommandsŽŸxÌ‘ £¹Step–®I‘Qdeals“with“placing“index“commands“in“the“doMÞcumen²!t.‘ µIn“a“source-language“basedŽ¡‘ £en•²!vironmen“t,‘Ö%the–f2commands“can“simply“bšMÞe“inserted“in“the“do˜cumen²!t“source“with“a“textŽ¡‘ £editor.‘ f‹They–)Kwill“bMÞe“utilized“bš²!y“the“formatter“in“generating“ra˜w“index“en˜tries“(Step“IMÞI),Ž¡‘ £but–will“con²!tribute“nothing“to“the“output“appšMÞearance“as“far“as“the“corresp˜onding“pages“areŽ¡‘ £concerned.Ž¡‘£In–,_a“direct-manipulation“system,‘DÇindex“commands“cannot“bšMÞe“en²!tered“directly“in“the“do˜cu-Ž¡‘ £menš²!t–Ñsunder“manipulation.‘–âA‘Ñ=pMÞossible“solution“is“to“put“them“in“\shado˜w“pages"“instead“of“theŽ¡‘ £doMÞcumenš²!t–úAoutput“represen˜tation.‘ÙmA‘ú+shado˜w“doMÞcumen˜t“is“the“original“doMÞcumen˜t“plus“spMÞecialŽ¡‘ £tags–­that,›®«among“other“things,˜mark“logical“ob‘›»jects“likš²!e“commen˜ts,‘®«bibliographical“citations,Ž¡‘ £cross›Xreferences,–Tindexes,“etc.‘ý³These˜tags˜are˜essen•²!tial˜to˜doMÞcumen“t˜compMÞosition˜but˜do˜notŽ¡‘ £correspšMÞond–ûto“ph²!ysical“app˜earance“in“their“original“forms.‘Û¶Up˜on“request,‘+the“corresp˜ondingŽ¡‘ £markš²!ers–/^of“these“tags“can“bMÞe“displa˜y˜ed“along“with“the“original“doMÞcumen˜t“for“editing“purpMÞoses.Ž¡‘ £F‘ÿeor–¥æthe“user's“visual“cue,‘¦eacš²!h“t˜ypšMÞe“of“tags“can“b˜e“represenš²!ted“b˜y“a“di eren˜t“mark˜er“sym˜bMÞol.Ž¡‘ £Normally–aEfor“eacš²!h“tag“en˜tered“in“the“doMÞcumen˜t,‘ýan“em˜bšMÞedded“annotation“can“b˜e“sp˜eci ed.Ž¡‘ £An–Kýadditional“windoš²!w“can“bMÞe“created“to“sho˜w“the“assoMÞciated“annotation“if“necessary‘ÿe.‘΢ThisŽ¡‘ £shado•²!w›"doMÞcumen“t˜approac“h˜is˜widely˜adopted˜b“y˜direct-manipulation˜doMÞcumen“t˜dev“elopmen“tŽ¡‘ £or–©¼desktop“publishing“systems“sucš²!h“as“Xero˜x“ë`Star–rå¹[14],‘ÜDë`F‘ÿerameMak˜er“¹[15],‘ÜDë`MicroSoft‘©¼W‘ÿeord‘¹[16],Ž¡‘ £and–¦fë`V‘ÿeen²!tura“Publisher‘o¹[17].Ž¡‘£The–DÛprimary“issue“in“step“I‘DÂfor“bMÞoth“paradigms“is“whether“or“not“a“systematic“mec²!hanismŽ¡‘ £can–òöbMÞe“derivš²!ed“for“the“en˜tering“of“index“commands“or“tags.‘ÃDetails“of“a“general“moMÞdel“thatŽ¡‘ £accomplishes–¦fthis“task“are“givš²!en“bMÞelo˜w.ŽŽŽŒ‹B  …(õ ý†× Ÿü™š’¾6e¹8Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £Í2.2Ž‘'È£Generating–€the“Ra w“IndexŽ©xÌ‘ £¹Step–r‡IMÞI‘rSconcerns“attacš²!hing“the“curren˜t“page“n˜um˜bMÞer“to“eac˜h“index“command“placed“in“theŽ¤fg‘ £doMÞcumenš²!t.‘ †ªThe–4command“used“in“the“generated“ra˜w“index“ le“ma˜y“bMÞe“renamed“(in“ourŽ¡‘ £example,‘eit–Æfis“cš²!hanged“from“ë^\index“¹to“ë^\indexentry¹).‘=ÜThe“en˜tries“are“in“the“exact“orderŽ¡‘ £in–hwhic²!h“they“appšMÞear“in“the“do˜cumenš²!t“source.‘ôäTh˜us,‘©as“long“as“the“curren˜t“page“n˜um˜bMÞer“isŽ¡‘ £accessible,›7ìbMÞe–Ñit“source-language“or“direct-manipulation“based,˜generating“raš²!w“index“en˜triesŽ¡‘ £is–¦frelativš²!ely“straigh˜tforw˜ard.Ž¡‘£There–ryare“minor“di erences“bMÞet•²!w“een–rythe“t•²!w“o–ryparadigms“in“this“step,‘|Ûho•²!w“ev“er.‘ÌŽThe‘rygener-Ž¡‘ £ation–~dof“raš²!w“index“en˜tries“in“a“source-language“based“system,‘†dlik˜e“formatting“itself,‘†dis“b˜y“andŽ¡‘ £large–·a“\batcš²!h“job".‘FÏIn“a“direct-manipulation“editor,‘<Ëit“is“easier“to“main˜tain“the“list“of“ra˜wŽ¡‘ £index–´Œenš²!tries“incremen˜tally“bšMÞecause“the“do˜cumen²!t“b˜eing“manipulated“is“alw•²!a“ys–´Œformatted“soŽ¡‘ £the–¦fpage“n•²!um“bMÞer–¦fis“alw•²!a“ys‘¦fcurren“t.ŽŸ$R…‘ £Í2.3Ž‘'È£Index‘€Pro`cessingŽ¦‘ £¹ProMÞcessing–ŽXraš²!w“index“en˜tries“raises“sev˜eral“issues.‘ÕØSome“high-lev˜el“issues“are“describšMÞed“b˜elo²!wŽ¡‘ £with–¿àreferences“to“the“example“givš²!en“in“Figure“2;‘Ìho˜w“these“tasks“can“bMÞe“realized“is“detailedŽ¡‘ £in–¦fthe“next“section.Ž¡‘£ëYPermutation‘× ¹.›Ï‘Index–LMen²!tries“are“sorted“alphabMÞetically“(Figure“2.c).˜The“index“proMÞcessorŽ¡‘ £m•²!ust›¿ádi eren“tiate˜among˜di eren“t˜t“ypMÞes˜of˜k“eys˜suc“h˜as˜strings,›íün“um“b•MÞers,˜and›¿ásp“ecial˜sym²!b“ols.Ž¡‘ £UppšMÞer–)žand“lo•²!w“er–)žcase“letters“should“b˜e“distinguished.‘g„F‘ÿeurthermore,‘Jkit“ma²!y“b˜e“necessary“toŽ¡‘ £handle–¦froman,“arabic,“and“alphabšMÞetic“page“n•²!um“b˜ers.Ž¡‘£ëYMer‘ÿp¹ging‘ø¹.‘°#Di erenš²!t–AÓpage“n˜um˜bšMÞers“corresp˜onding“to“the“same“index“kš²!ey“are“merged“in˜toŽ¡‘ £one–Clist.‘÷sAlso,‘ºthree“or“more“successivš²!e“page“n˜um˜bMÞers“are“abbreviated“as“a“range“(as“in“theŽ¡‘ £case–=9of“ë^alpha,–¿ªiv,“1-3¹,‘bîFigure–=92.c).‘¢WIf“citations“on“successiv²!e“pages“are“logically“distinct,Ž¡‘ £go•MÞo“d–…¯indexing“practice“suggests“that“they“should“not“bMÞe“represenš²!ted“b˜y“a“range.‘ÒõOur“systemŽ¡‘ £alloš²!ws–¦fuser“con˜trol“of“this“practice.Ž¡‘£ëYSubindexing‘ø¹.›M4Multi-lev²!el–v.indexing“is“suppMÞorted.˜Here,‘ªen²!tries“sharing“a“common“pre xŽ¡‘ £are–N groupšMÞed“together“under“the“same“pre x“k²!ey‘ÿe.‘ÔÇThe“sp˜ecial“sym²!b˜ol“`ë^!¹'“servš²!es“as“the“lev˜elŽŽŽŒ‹ L~ …(õ ý†× Ÿü™š’¾6e¹9Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £opMÞerator–niin“the“example“(Figure“2.a“and“2.b).‘5çPrimary“indexes“are“con•²!v“erted–nito“ rst“lev²!elŽ¤fg‘ £items–\Ô(the“ë^\item“¹enš²!tries“in“Figure“2.c)“while“subindexes“are“con˜v˜erted“to“lo˜w˜er“lev˜el“itemsŽ¡‘ £(e.g.,–¦fë^\subitem“¹or“ë^\subsubitem“¹en²!tries“in“Figure“2.c).Ž¡‘£ëYA‘ÿp¹ctual›Q¸Field‘!ª¹.‘¦\The–ÿâdistinction“bMÞet•²!w“een–ÿâa“ëYsort˜key‘÷ã¹and“its“ëYactual˜ eld‘!Œ¹is“made“explicit.‘¦\SortŽ¡‘ £kš²!eys–s are“used“in“comparison“while“their“actual“coun˜terparts“are“what“end“up“bMÞeing“placedŽ¡‘ £in–Ûthe“prin²!ted“index.‘}-In“the“example,›èÇthe“`ë^@¹'“sign“is“used“as“the“actual“ eld“opMÞerator,˜whic²!hŽ¡‘ £means–áits“preceding“string“is“the“sort“kš²!ey“and“its“succeeding“string“is“the“actual“k˜ey“(e.g.,Ž¡‘ £the–¼ë^\index{alpha@{\it‘¿ªalpha\/}}“¹in“Figure“2.a).‘The“same“sort“k²!ey“with“and“without“anŽ¡‘ £actual–N eld“are“treated“as“t•²!w“o–Nseparate“en²!tries“(cf.›Àpë^alpha“¹and“ëYalpha‘%*¹in“the“example).˜If“a“k²!eyŽ¡‘ £con²!tains–¦fno“actual“opšMÞerator,“it“is“used“as“b˜oth“the“sort“ eld“and“the“actual“ eld.Ž¡‘£The–Êseparation“of“a“sort“kš²!ey“from“its“actual“ eld“mak˜es“en˜try“sorting“m˜uc˜h“easier.‘¯TIf“thereŽ¡‘ £wš²!ere–'only“one“ eld,‘=Wthe“comparison“routine“w˜ould“ha˜v˜e“to“ignore“syn˜tactic“sugar“related“toŽ¡‘ £output–¿appMÞearance“and“compare“only“the“\real"“k•²!eyw“ords.‘'ïF‘ÿeor–¿instance,‘ÅCin“ë^{\it‘¿ªalpha\/}¹,Ž¡‘ £the–»µprogram“has“to“ignore“the“fon²!t“setting“command“ë^\it¹,‘Á the“italic“correction“command“ë^\/¹,Ž¡‘ £and–wvthe“scopšMÞe“delimiters“ë^{}¹.‘Q In“general,‘«ºit“is“imp˜ossible“to“kno²!w“all“the“patterns“that“theŽ¡‘ £index–¡³proMÞcessor“should“ignore,›¢¤but“with“the“separation“of“the“ elds,˜the“sort“k²!ey“is“used“as“aŽ¡‘ £vš²!erbatim–¦fstring“in“comparison;“an˜y“spšMÞecial“e ect“can“b˜e“ac•²!hiev“ed–¦fvia“the“actual“ eld.Ž¡‘£ëYPage‘š¸Enc‘ÿp¹apsulation‘× ¹.‘%P•²!age›e~n“um“b•MÞers˜can˜b“e˜encapsulated˜using˜the˜`ë^|¹'˜op“erator.‘%In˜theŽ¡‘ £example,‘ã?page–£à14“on“whic²!h“ë^\index{beta}“¹ošMÞccurs“is“set“in“b˜oldface,‘ã?as“represenš²!ted“b˜y“theŽ¡‘ £command–Cë^\bold¹.‘ ³ñThe“abilitš²!y“to“set“page“n˜um˜bMÞers“in“di eren˜t“fon˜ts“allo˜ws“the“index“toŽ¡‘ £con•²!v“ey– mmore“information“abšMÞout“whatev²!er“is“b˜eing“indexed.‘KñF‘ÿeor“instance,‘>îthe“place“where“aŽ¡‘ £de nition–ŸošMÞccurs“can“b˜e“set“in“one“fon²!t,›ÝMits“primary“example“in“a“second,˜and“others“in“aŽ¡‘ £third.Ž¡‘£ëYCr–ÿp¹oss‘Ú=R“efer“encing‘ø¹.‘êGSome–ª‰index“enš²!tries“mak˜e“references“to“others.‘êGIn“our“example“theŽ¡‘ £ë^alphabeta–5î¹enš²!try“is“a“reference“to“ë^beta¹,‘YÐas“indicated“b˜y“the“ëYse‘ÿp¹e‘¹phrase.‘ŒvThe“page“n˜um˜bMÞer,Ž¡‘ £ho•²!w“ev“er,‘ disappMÞears–ìöafter“formatting“(Step“IV),“hence“it“is“immaterial“where“index“commandsŽ¡‘ £dealing–4Dwith“cross“references“lik²!e“ëYse‘ÿp¹e‘å¹ošMÞccur“in“the“do˜cumen²!t.‘‡vThis“is“a“sp˜ecial“case“of“pageŽ¡‘ £encapsulation–íˆ(ë^see{beta}“¹appšMÞears“after“the“`ë^|¹'“op˜erator).‘³BV‘ÿeariations“likš²!e“ëYse‘ÿp¹e‘àalso‘°ò¹,‘?Pwhic˜hŽŽŽŒ‹ Wx …(õ ý†× Ÿü™š’¸¼Ë¹10Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £givš²!es–¦fpage“n˜um˜bMÞers“as“w˜ell“as“references“to“other“en˜tries,“w˜ork“similarly‘ÿe.Ž¤fg‘£ëYInput/Output‘Ñ¡Style‘Ò¡¹.‘wóIn–t§order“to“bšMÞe“formatter-“and“format-indep˜enden²!t,‘±Îthe“index“pro˜cessorŽ¡‘ £mš²!ust–-bMÞe“able“to“handle“a“v‘ÿdDariet˜y“of“formats.‘ sXThere“are“t˜w˜o“reasons“for“considering“thisŽ¡‘ £indepMÞendence–w§issue“in“the“input“side:‘Æ}Raš²!w“index“ les“generated“b˜y“systems“other“than“L‘üÙŸþ•ëÅaŽ‘Œ„¹T‘þ,³ŸLØEŽ‘B XŽ¡‘ £maš²!y–mnot“comply“to“the“default“format,‘ž­and“the“basic“framew˜ork“established“for“proMÞcessingŽ¡‘ £indexes–Ðìcan“also“bšMÞe“used“to“pro˜cess“other“ob‘›»jects“of“similar“nature“(e.g.,‘glossaries).‘]nButŽ¡‘ £these–{…other“ob‘›»jects“will“certainly“ha•²!v“e–{…a“di erenš²!t“k˜eyw˜ord“(e.g.,‘„ë^\glossaryentry“¹as“oppMÞosedŽ¡‘ £to–¶ïë^\indexentry¹)“in“the“vš²!ery“least.‘ySimilarly“in“the“output“side“the“index“st˜yle“ma˜y“v‘ÿdDaryŽ¡‘ £for–ùJdi erenš²!t“systems.‘Ö‰Ev˜en“within“the“same“formatting“system,‘the“index“ma˜y“ha˜v˜e“to“loMÞokŽ¡‘ £di erenš²!tly– ûunder“di eren˜t“publishing“requiremen˜ts.‘ œIn“other“w˜ords,‘$ there“m˜ust“bMÞe“a“w˜a˜y“toŽ¡‘ £inform–¦fthe“proMÞcessor“of“the“input“format“and“the“output“st²!yle.ŽŸ$R…‘ £Í2.4Ž‘'È£Index‘€F‘þàormattingŽŸxÌ‘ £¹Tw•²!o›…“k“ey˜issues˜in˜this˜last˜step˜are˜suppMÞort˜for˜m“ultiple˜st“yles˜and˜formatting˜indepMÞendence.Ž¡‘ £First,‘Îthe–’ñformatting“stš²!yle“macros“used“in“Step“I•MÞI“I‘’´output–’ñm˜ust“bMÞe“de ned.‘£}In“our“exam-Ž¡‘ £ple,‘}ãthe–—global“en•²!vironmen“t–—(ë^\begin{theindex}...\end{theindex}¹)“tells“L‘üÙŸþ•ëÅaŽ‘Œ„¹T‘þ,³ŸLØEŽ‘B X‘6to“use“aŽ¡‘ £t•²!w“o-column–¢°page“la•²!y“out.‘ÒºEac“h–¢°ë^\item“¹is“left“justi ed“against“the“column“margin“and“eac²!hŽ¡‘ £ë^\subitem–¡ò¹is“indenš²!ted“b˜y“20“pMÞoin˜ts,‘¢Öë^\subsubitem“¹b˜y“30,‘¢Öetc.‘ÜaThere“is“a“v˜ertical“space“bMÞoundŽ¡‘ £to–¦fë^\indexspace“¹inserted“bšMÞefore“the“b˜eginning“of“a“new“letter“(e.g.,“b˜efore“ë^beta¹).Ž¡‘£The–[\formatting“indepšMÞendence“problem“refers“to“whether“or“not“the“ nal“index“can“b˜e“for-Ž¡‘ £matted–28indepMÞendenš²!tly“of“the“en˜tire“doMÞcumen˜t.‘·#Indexing“is“t˜ypically“the“last“step“of“doMÞcumen˜tŽ¡‘ £preparation,‘9 and–è•is“attempted“only“when“the“enš²!tire“doMÞcumen˜t“is“ nalized.‘¤iIt“is“desirableŽ¡‘ £to–jäbšMÞe“able“to“generate“the“index“without“reformatting“the“en²!tire“do˜cumen²!t.‘+WT‘ÿeo“b˜e“able“toŽ¡‘ £format–—the“index“separately‘ÿe,‘/Zthe“global“conš²!text“m˜ust“bMÞe“kno˜wn,‘/Zwhic˜h“is“made“pMÞossible“b˜y“theŽ¡‘ £extensible–m.stš²!yle“facilit˜y“in“our“design.‘ÊÊOne“can“rede ne“ë^preamble“¹and“ë^postamble“¹to“in˜v˜ok˜e“aŽ¡‘ £st•²!yle›¦fconsisten“t˜with˜the˜original˜doMÞcumen“t.Ž¡‘£The–êìother“information“needed“to“pMÞerform“e ectiv²!e“separate“formatting“is“the“starting“pageŽ¡‘ £n•²!um“bMÞer–©¹for“the“index.‘‰¤Some“stš²!yles“require“that“the“index“start“on“an“ev˜en“or“oMÞdd“page“n˜um˜bMÞer.ŽŽŽŒ‹ d …(õ ý†× Ÿü™š’¸¼Ë¹11Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ þÅôŸ–*®‘.ÿhŸ²Lωffn¹Ò¤fd‘UÔó1p®0J cmsl10ÜspGeci er‘ÚWŸ™œ„ ffŽ‘`¿Óattribute‘\4Ÿ™œ„ ffŽ’©ºkdefault‘…Ÿ™œ„ ffŽ’vÐmeaningŽŽ©‰ffn¹ÒŸ‰ffn¹Ò¡‘ó)ßêX‘ £¹The–‰[index“prošMÞcessor“p˜erforms“the“tasks“indicated“ab˜o•²!v“e–‰[|“p˜ermš²!utation,‘*page“n˜um˜bMÞer“merg-Ž¡‘ £ing,–ÃHsubindexing,“st²!yle›ŠNhandling,“and˜other˜spMÞecial˜e ects.‘‰–In˜order˜to˜ac•²!hiev“e˜format˜andŽ¡‘ £formatter–²õindepšMÞendence,‘öthe“index“pro˜cessor“m²!ust“b˜e“able“to“accept“ra²!w“index“terms“des-Ž¡‘ £ignated–=‡bš²!y“di eren˜t“k˜eyw˜ords“and“delimiters.‘£ALik˜ewise,‘cPit“m˜ust“bMÞe“able“to“generate“outputŽ¡‘ £in–:Wa“spšMÞeci c“st²!yle“so“that“the“result“can“b˜e“pro˜cessed“b²!y“the“corresp˜onding“formatter.‘™¯TheŽ¡‘ £in²!tended–3—tasks“can“bšMÞe“p˜erformed“in“m²!ultiple“passes:‘ø>First“the“input“format“ le“and“outputŽ¡‘ £stš²!yle–æÆ le“are“scanned“and“analyzed.‘ýEn˜tries“in“the“input“ le“are“then“proMÞcessed.‘ýNext,‘ all“legalŽ¡‘ £en²!tries–Úúare“sorted.›{šFinally‘ÿe,‘èthe“output“index“is“generated“in“the“last“pass.˜The“remainder“ofŽ¡‘ £this–Ò·section“discusses“the“essenš²!tial“attributes“for“input“formats“and“output“st˜yles“and“pMÞoin˜tsŽ¡‘ £out–¦frelev‘ÿdDanš²!t“issues“for“sorting“and“generating“the“en˜tries.ŽŽŽŒ‹ p; …(õ ý†× Ÿü™š’¸¼Ë¹12Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £Í3.1Ž‘'È£Input‘€F‘þàormatŽŸxÌ‘ £¹T‘ÿeable–Ló1“is“a“summary“of“the“input“format“that“consists“of“a“list“of“ë^<ëYsp–ÿp¹e“ci er‘-»¹,‘^×ëYattribute‘Ò¡ë^>‘Ló¹pairs.Ž¤fg‘ £These–Žattributes“are“the“essenš²!tial“tok˜ens“and“delimiters“needed“in“scanning“the“input“index“ le.Ž¡‘ £Default–1string“constanš²!ts“are“enclosed“in“double“quotes“(ë^"..."¹)“and“c˜haracter“constan˜ts“are“inŽ¡‘ £single–¸¼quotes“(ë^'x'¹).‘Ž¤The“user“can“o•²!v“erride–¸¼the“default“v‘ÿdDalue“b²!y“spšMÞecifying“a“sp˜eci er“and“a“newŽ¡‘ £attribute– ªin“the“format“ le“or“propMÞert²!y“sheet.‘¨The“attribute“of“ë^keyword“¹is“self-explanatory;Ž¡‘ £ë^arg_open–ó%¹and“ë^arg_close“¹denote“the“argumen²!t“opšMÞening“and“closing“delimiters,‘Tresp˜ectiv²!ely‘ÿe.Ž¡‘ £The–¦fmeanings“of“spšMÞecial“op˜erators“suc²!h“as“ë^level¹,“ë^actual¹,“and“ë^encap“¹are“describ˜ed“ab˜o•²!v“e.Ž¡‘£The›Ê„t•²!w“o˜range˜delimiters˜ë^range_open˜¹and˜ë^range_close˜¹are˜used˜with˜the˜ë^encap˜¹opMÞerator.Ž¡‘ £When–Ïë^range_open“¹immediately“follo²!ws“ë^encap“¹(i.e.,–>ë^\index{...|(...}¹),“it–Ïtells“the“indexŽ¡‘ £proMÞcessor–Zthat“an“explicit“range“is“starting.‘øÔCon•²!v“ersely–Zë^range_close“¹signals“the“closing“ofŽ¡‘ £a–mêrange.‘4hIn“our“design,‘ŸÊthree“or“more“successivš²!e“page“n˜um˜bMÞers“are“abbreviated“as“a“rangeŽ¡‘ £implicitly‘ÿe.‘£{This–èEëYimplicit‘ò/¹range“formation“can“bMÞe“turned“o “if“an“indexed“term“represen²!tsŽ¡‘ £logically–¥Adistinct“concepts“in“di eren²!t“pages.‘ÚmWhen“the“implicit“range“is“disabled,‘ä÷ëYexplicitŽ¡‘ £¹page–ranges“can“bMÞe“enforced“bš²!y“using“the“t˜w˜o“range“delimiters“ë^range_open“¹and“ë^range_close¹.Ž¡‘ £Therefore,‘‰²it–‚…is“pMÞossible“to“index“an“en²!tire“section“or“a“large“piece“of“text“related“to“a“certainŽ¡‘ £concept–¦fwithout“haš²!ving“to“insert“an“index“command“in“ev˜ery“single“page.Ž¡‘£The–ˆIë^quote“¹opšMÞerator“is“used“to“escap˜e“sym•²!b˜ols.‘ƒ†Th“us–ˆIë^\index{foo"@goo}“¹means“a“sortŽ¡‘ £kš²!ey–:Zof“ë^foo@goo“¹rather“than“a“sort“k˜ey“of“ë^foo"“¹and“an“actual“k˜ey“of“ë^goo¹.‘™¹As“an“exception,Ž¡‘ £ë^quote¹,›swhen–T preceded“b²!y“ë^escape“¹(i.e.‘æÊë^\index{...\"...}¹),˜došMÞes“not“escap˜e“its“succeedingŽ¡‘ £letter.‘wøThis–/spšMÞecial“case“is“included“b˜ecause“ë^\"“¹is“the“umlaut“command“in“T‘þ,³Ÿ[wEŽ‘B X.‘wøRequiringŽ¡‘ £ë^quote–:ó¹itself“to“bMÞe“quoted“in“this“case“(i.e.‘º ë^\""¹)“is“feasible“but“somewhat“a•²!wkw“ard;‘^Åë^quote‘:ó¹andŽ¡‘ £ë^escape–¦f¹m²!ust“bMÞe“distinct.Ž¡‘£A‘‚page›¤n•²!um“b•MÞer˜can˜b“e˜a˜comp“osite˜of˜one˜or˜more˜ elds˜separated˜b²!y˜the˜delimiter˜b“oundŽ¡‘ £to–ÂGë^page_compositor“¹(e.g.,‘É?IšMÞI-12“for“page“12“of“Chapter“I˜I).“This“attribute“allo²!ws“the“lexicalŽ¡‘ £analyzer–¦fto“separate“these“ elds,“simplifying“the“sorting“of“page“n•²!um“bMÞers.ŽŽŽŒ‹ |ì …(õ ý†× Ÿü™š’¸¼Ë¹13Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ÿH,T ÿ2÷~‘C ÿOŸ‰ffª2•¤fd‘UÔÜspGeci er‘ÚWŸ™œ„ ffŽ‘`¿Óattribute‘\4Ÿ™œ„ ffŽ’ÆšZdefault‘8dñŸ™œ„ ffŽ’Q!meaningŽŽ©‰ffª2•Ÿ‰ffª2•¡‘Ôpreamble‘*Œ¸Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"\\begin{theindex}\n"‘ÌÁŸ™œ„ ffŽ’#y ²index‘UUpream¸ãbleŽŽ¦‰ffª2•¡‘Ôpostamble‘%L»Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"\n\n\\end{theindex}\n"‘LÇŸ™œ„ ffŽ’#y ²index‘UUpGostam¸ãbleŽŽ¦‰ffª2•¡‘Ôsetpage_prefix‘ ÊŸ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"\n‘ ú\\setcounter{page}{"‘ÌÍŸ™œ„ ffŽ’#y ²page–UUsetting“command“pre xŽŽ¦‰ffª2•¡‘Ôsetpage_suffix‘ ÊŸ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"}\n"‘nÌ‘Ÿ™œ„ ffŽ’#y ²page–UUsetting“command“suxŽŽ¦‰ffª2•¡‘Ôgroup_skip‘ ¾Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"\n\n‘ ú\\indexspace\n"‘ŒÄŸ™œ„ ffŽ’#y ²in•¸ãtergroup›UUv“ertical˜spaceŽŽ¦‰ffª2•¡‘Ôlethead_prefix‘ ÊŸ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ""‘~ŒˆŸ™œ„ ffŽ’#y ²new–UUletter“heading“pre xŽŽ¦‰ffª2•¡‘Ôlethead_suffix‘ ÊŸ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ""‘~ŒˆŸ™œ„ ffŽ’#y ²new–UUletter“heading“suxŽŽ¦‰ffª2•¡‘Ôlethead_flag‘ŒÄŸ™œ„ ffŽ‘céâ×numb‘ÿ}'er‘ iŸ™œ„ ffŽ’”9ëÔ0’ƒÌ…Ÿ™œ„ ffŽ’#y ² ag–UUdesignating“new“letterŽŽ¦‰ffª2•¡‘Ôitem_0‘5 ²Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"\n‘ ú\\item‘?ý"‘DÌ©Ÿ™œ„ ffŽ’#y ²lev¸ãel–UU0“item“separatorŽŽ¦‰ffª2•¡‘Ôitem_1‘5 ²Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"\n‘ÿô\\subitem‘?ý"‘*Œ¸Ÿ™œ„ ffŽ’#y ²lev¸ãel–UU1“item“separatorŽŽ¦‰ffª2•¡‘Ôitem_2‘5 ²Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"\n‘î\\subsubitem‘?ý"‘LÇŸ™œ„ ffŽ’#y ²lev¸ãel–UU2“item“separatorŽŽ¦‰ffª2•¡‘Ôitem_01‘/̵Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"\n‘ÿô\\subitem‘?ý"‘*Œ¸Ÿ™œ„ ffŽ’#y ²lev¸ãels–UU0/1“separatorŽŽ¦‰ffª2•¡‘Ôitem_x1‘/̵Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"\n‘ÿô\\subitem‘?ý"‘*Œ¸Ÿ™œ„ ffŽ’#y ²lev¸ãels–UUx/1“separatorŽŽ¦‰ffª2•¡‘Ôitem_12‘/̵Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"\n‘î\\subsubitem‘?ý"‘LÇŸ™œ„ ffŽ’#y ²lev¸ãels–UU1/2“separatorŽŽ¦‰ffª2•¡‘Ôitem_x2‘/̵Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"\n‘î\\subsubitem‘?ý"‘LÇŸ™œ„ ffŽ’#y ²lev¸ãels–UUx/2“separatorŽŽ¦‰ffª2•¡‘Ôdelim_0‘/̵Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ",‘?ý"‘t ŽŸ™œ„ ffŽ’#y ²levš¸ãel–UU0“k˜ey/page“delimiterŽŽ¦‰ffª2•¡‘Ôdelim_1‘/̵Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ",‘?ý"‘t ŽŸ™œ„ ffŽ’#y ²levš¸ãel–UU1“k˜ey/page“delimiterŽŽ¦‰ffª2•¡‘Ôdelim_2‘/̵Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ",‘?ý"‘t ŽŸ™œ„ ffŽ’#y ²levš¸ãel–UU2“k˜ey/page“delimiterŽŽ¦‰ffª2•¡‘Ôdelim_n‘/̵Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ",‘?ý"‘t ŽŸ™œ„ ffŽ’#y ²inš¸ãter–UUpage“n˜um˜bGer“delimiterŽŽ¦‰ffª2•¡‘Ôdelim_r‘/̵Ÿ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"--"‘t ŽŸ™œ„ ffŽ’#y ²page–UUrange“designatorŽŽ¦‰ffª2•¡‘Ôencap_prefix‘ŒÄŸ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"\\"‘t ŽŸ™œ„ ffŽ’#y ²page–UUencapsulator“pre xŽŽ¦‰ffª2•¡‘Ôencap_infix‘ÌÁŸ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"{"‘yL‹Ÿ™œ„ ffŽ’#y ²page–UUencapsulator“in xŽŽ¦‰ffª2•¡‘Ôencap_suffix‘ŒÄŸ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"}".‘t ŽŸ™œ„ ffŽ’#y ²page–UUencapsulator“suxŽŽ¦‰ffª2•¡‘Ôpage_precedence‘ÌÍŸ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"rnaRA"‘dL—Ÿ™œ„ ffŽ’#y ²page–UUt¸ãypGe“precedenceŽŽ¦‰ffª2•¡‘Ôline_max‘*Œ¸Ÿ™œ„ ffŽ‘céâ×numb‘ÿ}'er‘ iŸ™œ„ ffŽ’”9ëÔ72‘~ŒˆŸ™œ„ ffŽ’#y ²maxim¸ãum–UUline“lengthŽŽ¦‰ffª2•¡‘Ôindent_space‘ŒÄŸ™œ„ ffŽ‘g–Q×string‘ …ÈŸ™œ„ ffŽ’”9ëÔ"\t\t"‘iŒ”Ÿ™œ„ ffŽ’#y ²inden¸ãtation–UUfor“wrappGed“linesŽŽ¦‰ffª2•¡‘Ôindent_length‘LÇŸ™œ„ ffŽ‘céâ×numb‘ÿ}'er‘ iŸ™œ„ ffŽ’”9ëÔ16‘~ŒˆŸ™œ„ ffŽ’#y ²length–UUof“inden¸ãtationŽŽ¦‰ffª2•ŽŽŽ Êçq’”KÞ¹T‘ÿeable–¦f2:‘ÝÝOutput“st²!yle“parameters.ŽŽŽŸ‘ £Í3.2Ž‘'È£Output‘€St yleŽŸxÌ‘ £¹T‘ÿeable–22“summarizes“the“output“st²!yle“parameters.‘0@Again,›3dit“is“a“list“of“ë^<ëYsp–ÿp¹e“ci er‘-»¹,˜ëYattribute‘Ò¡ë^>Ž¤fg‘ £¹pairs.‘©ÕIn–êcthe“default“column,›ûc`ë^\n¹'“and“`ë^\t¹'“denote“a“new“line“and“a“tab,˜respMÞectiv²!ely‘ÿe.‘©ÕTheseŽ¡‘ £parameters–¦fcan“bMÞe“further“divided“inš²!to“the“follo˜wing“groups:Ž¡‘£ëYContext‘ ê¹.‘6üT‘ÿeogether,‘ˈë^preamble–Ĺand“ë^postamble“¹de ne“the“conš²!text“in“whic˜h“the“index“is“toŽ¡‘ £bMÞe‘¦fformatted.Ž¡‘£ëYStarting‘øpPage‘Ò¡¹.‘ õThe–µstarting“page“n•²!um“bšMÞer–µcan“either“b˜e“supplied“bš²!y“the“user“or“retriev˜edŽ¡‘ £automatically–ùfrom“the“doMÞcumenš²!t“transcript.‘¤In“either“case,‘Åthis“n˜um˜bšMÞer“can“b˜e“enclosed“withŽŽŽŒ‹ˆs …(õ ý†× Ÿü™š’¸¼Ë¹14Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £ë^setpage_prefix–¦f¹and“ë^setpage_suffix“¹to“yield“a“page“n•²!um“bMÞer–¦finitializing“command.Ž¤fg‘£ëYNew‘ÙGr–ÿp¹oup/L“etter‘-»¹.‘u8The–ØÚstring“bMÞound“to“ë^group_skip“¹denotes“the“extra“v²!ertical“spaceŽ¡‘ £needed–/cwhen“a“group“is“started.‘¶1F‘ÿeor“a“group“bMÞeginning“with“a“di eren²!t“letter,‘G0the“parametersŽ¡‘ £ë^lethead_prefix–iZ¹and“ë^lethead_suffix“¹(bMÞoth“with“a“default“nil“string)“denote“the“groupŽ¡‘ £heading.‘ˆäThe–§z ag“ë^lethead_flag“¹has“a“default“v‘ÿdDalue“of“0,‘Úvwhic²!h“means“other“than“ë^group_skipŽ¡‘ £¹nothing–¡else“will“bšMÞe“inserted“b˜efore“the“group.‘ÜOn“the“other“hand,‘¢if“this“ ag“is“p˜ositiv²!e,‘¢theŽ¡‘ £strings–ÎbšMÞound“to“ë^lethead_prefix“¹and“ë^lethead_suffix“¹will“b˜e“inserted“with“an“instance“ofŽ¡‘ £the–Ranew“letter“in“uppšMÞercase“in“b˜et•²!w“een.‘áÍSimilarly‘ÿe,‘}_a›Ralo“w“ercase˜letter˜will˜bMÞe˜inserted˜if˜theŽ¡‘ £ ag–¦fis“negativ²!e.Ž¡‘£ëYEntry‘ŽxSep–ÿp¹ar“ators‘æ¹.›ó4This–X.group“includes“ev²!erything“with“the“ë^item_“¹pre x.˜First,‘„Ÿë^item_óZ  b> ó3 cmmi10ëZiŽ¡‘ £¹denotes–Ɔthe“command“and“indenš²!tation“to“bMÞe“inserted“when“a“k˜ey“is“started“from“a“lev˜el“greaterŽ¡‘ £than–ã@or“equal“to“ëZi¹.‘œÑSecond,› Hë^item_ëZij‘ƒ¶¹has“a“similar“meaning,˜but“with“ëZi– §¹=“ëZj‘‰ë[‘衹1.‘œÑFinally‘ÿe,˜the‘ã@t•²!w“oŽ¡‘ £ë^item_xëZj‘ v¹'s–Üüare“included“to“handle“the“situation“where“the“parenš²!t“lev˜el“has“no“page“n˜um˜bMÞers.Ž¡‘ £Some–¦fstš²!yles“require“cases“lik˜e“these“to“bMÞe“di eren˜t“from“those“with“page“n˜um˜bMÞers.Ž¡‘£T‘ÿeable–6ñ2“depicts“a“system“that“suppšMÞorts“three“lev²!els“of“subindexing.‘~In“general,‘[supp˜oseŽ¡‘ £ëZn–ì…¹is“the“n•²!um“bšMÞer–ì…of“index“lev²!els“supp˜orted,‘þ there“will“b˜e“ëZn“ë^item_ëZi¹'s“(0–…ë[“ëZi“ë[“ëZn–«ë[“¹1),‘þ (ëZn“ë[“¹1)Ž¡‘ £ë^item_ëZij‘ v¹'s›¦f(1– §ë[“ëZj‘«ë[“ëZn–nìë[“¹1ëZ;‘Ó1i– §¹=“ëZj‘bë[–nì¹1),˜and˜(ëZn“ë[“¹1)˜ë^item_xëZj‘ v¹'s˜(1– §ë[“ëZj‘«ë[“ëZn–nìë[“¹1).Ž¡‘£ëYPage‘Delimiters‘æ¹.‘9§Eac•²!h›Äÿlev“el˜has˜a˜k“ey/page˜delimiter˜that˜de nes˜what˜is˜to˜bMÞe˜insertedŽ¡‘ £bMÞet•²!w“een–2a“kš²!ey“and“its“ rst“page“n˜um˜bMÞer.‘‚ZThe“in˜ter-page“delimiter“is“spMÞeci ed“b˜y“ë^delim_n¹,Ž¡‘ £while–¦fthe“range“designator“is“givš²!en“b˜y“ë^delim_r¹.Ž¡‘£ëYPage‘xIEnc‘ÿp¹apsulator‘-»¹.‘ªÝThe–@attributes“of“ë^encap_prefix¹,–f{ë^encap_infix¹,“and‘@ë^encap_suffixŽ¡‘ £¹form–ÜÛwhat“is“to“bšMÞe“placed“in²!to“the“output“when“an“encapsulator“is“sp˜eci ed“for“a“certain“en²!try‘ÿe.Ž¡‘ £SuppšMÞose–¦fë^foo“¹is“the“sp˜eci ed“encapsulator“and“ë^N“¹is“the“page“n•²!um“b˜er,–¦fthe“output“sequence“isŽ¤”s‘%Æõë^encap_prefix– Tfoo“encap_infix“N“encap_suffixŽ¡‘£ëYPage‘SiPr–ÿp¹e“c“e“denc“e‘Ò¡¹.‘¦ùFiv•²!e›¸di eren“t˜t“ypMÞes˜of˜n“umerals˜are˜suppMÞorted˜b“y˜most˜systems˜for˜pageŽ¤fg‘ £n•²!um“bMÞering.‘‚/These–Ý,are“lo•²!w“ercase–Ý,roman“(ë^r¹),›êÝn²!umeric“or“arabic“(ë^n¹),˜lo•²!w“ercase–Ý,alphabMÞetic“(ë^a¹),Ž¡‘ £uppšMÞercase–ôHroman“(ë^R¹),“and“upp˜ercase“alphab˜etic“(ë^A¹).“The“string“b˜ound“to“ë^page_precedenceŽ¡‘ £¹(default–¦fë^"rnaRA"¹)“spMÞeci es“their“order.ŽŽŽŒ‹œ¦ …(õ ý†× Ÿü™š’¸¼Ë¹15Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘£ëYLine‘oýWr‘ÿp¹apping‘ø¹.‘±SIn– Éthe“output“index“ le,‘;‚the“merged“list“of“page“n•²!um“bšMÞers– Écan“b˜e“wrapp˜edŽ¤fg‘ £in–G mš²!ultiple“lines,‘¯4if“it“is“longer“than“ë^line_max¹.‘ ¿ÍThe“newly“wrappMÞed“line“is“inden˜ted“b˜yŽ¡‘ £ë^indent_space–ÿ¹whose“length“is“ë^indent_length¹.‘çâThis“arti cial“line“wrapping“doMÞes“not“mak²!eŽ¡‘ £anš²!y–ú;di erence“in“formatting,‘O0but“doMÞes“pro˜vide“increased“readabilit˜y“for“the“pre-formattedŽ¡‘ £ nal–ͪindex.‘S¨This“feature“ma²!y“seem“somewhat“trivial“at“ rst“glance,‘×{but“if“no“formatters“areŽ¡‘ £in•²!v“olv“ed›¦fwhatsoMÞev“er,˜the˜readabilit“y˜of˜the˜v“erbatim˜output˜index˜is˜impMÞortan“t.ŽŸ$R…‘ £Í3.3Ž‘'È£Sorting‘€En triesŽŸxÌ‘ £¹Enš²!tries–Yin“the“ra˜w“index“ le“are“sorted“primarily“on“their“index“k˜eys“and“secondarily“on“theirŽ¡‘ £page›Ëvn•²!um“bMÞers.‘”ãIndex˜k“eys˜are˜sorted˜ rst;‘qwithin˜the˜same˜index˜k“ey‘ÿe,‘÷@page˜n“um“bMÞers˜are˜sortedŽ¡‘ £n•²!umerically‘ÿe.‘¬Sort› k“eys˜and˜n“umeric˜page˜n“um“bMÞers˜are˜used˜in˜the˜comparison,‘%gwhile˜actualŽ¡‘ £kš²!eys–q†and“literal“page“ elds“are“en˜tered“in˜to“the“resulting“index.‘?=In“our“design,‘¤Na“completeŽ¡‘ £index–÷Ïkš²!ey“is“an“aggregate“of“one“or“more“sort“k˜eys“plus“the“same“or“a“smaller“n˜um˜bMÞer“of“actualŽ¡‘ £kš²!eys.‘?KThe–5comparison“is“based“on“sort“k˜eys,‘9©but“if“t˜w˜o“aggregates“ha˜v˜e“iden˜tical“sort“ eldsŽ¡‘ £and–¦fpage“n•²!um“bšMÞers,–¦fthe“actual“k²!eys“can“b˜e“used“to“distinguish“their“order.Ž¡‘£Index–ÞŸkš²!eys“can“bMÞe“categorized“in˜to“the“follo˜wing“groups:‘yúëYstrings–æ¹,›”ëYnumb‘ÿp¹ers“¹,˜and‘ÞŸëYsymb‘ÿp¹ols“¹.‘›FAŽ¡‘ £string–tÑis“a“pattern“whose“leading“cš²!haracter“is“a“letter“in“the“alphab•MÞet.‘ÍVA‘tÄn˜um˜b“er–tÑis“a“patternŽ¡‘ £consisting–Oof“all“digits.‘ØA‘Nòsym²!bšMÞol“is“a“pattern“b˜eginning“with“a“c²!haracter“not“in“the“unionŽ¡‘ £of–´hthe“English“alphabMÞet“and“arabic“digits“or“starting“with“a“digit“but“mixed“with“non-digits.Ž¡‘ £Mem²!bšMÞers–øòof“the“same“group“should“app˜ear“in“sequence.‘¤ Hence“there“are“t•²!w“o–øòissues“concerningŽ¡‘ £ordering:‘¯jone–I€deals“with“en²!tries“within“a“group;‘hxthe“other“is“the“global“precedence“among“theŽ¡‘ £three–¦fgroups“in“question.‘ÝÝDetails“of“sorting“index“k²!eys“can“bMÞe“found“in“Reference“[18].Ž¡‘£There–Oare“three“basic“tš²!ypMÞes“of“n˜umerals“for“page“n˜um˜bMÞers:‘²+ëYr–ÿp¹oman‘× ¹,›`|ëYalphab“etic‘žu¹,˜and‘OëYar“abic‘žu¹.Ž¡‘ £The–Hvsorting“of“arbitrary“comš²!binations“of“these“three“t˜ypMÞes“of“n˜umerals“(e.g.,–pù112,“iv,“IMÞI-12,Ž¡‘ £A.1.3,‘“getc.)‘Õómš²!ust–Ž¨bMÞe“based“on“their“n˜umeric“v‘ÿdDalues“and“relativ˜e“precedence.‘ÕóThe“attribute“ofŽ¡‘ £ë^page_precedence–”G¹in“T‘ÿeable“2,›—çfor“instance,˜spMÞeci es“the“precedence.‘×ÓAgain,˜details“of“sortingŽ¡‘ £page›¦fn•²!um“b•MÞers˜can˜b“e˜found˜in˜Reference˜[18].ŽŽŽŒ‹©‚ …(õ ý†× Ÿü™š’¸¼Ë¹16Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £Í3.4Ž‘'È£Creating–€Output“Index“En triesŽŸxÌ‘ £¹Once–k4all“input“en²!tries“are“sorted,‘œgthe“output“index“ le“can“bMÞe“created.‘,FFirst“the“attributeŽ©fg‘ £bMÞound–¦fto“ë^preamble“¹is“placed“inš²!to“the“output“ le,“follo˜w˜ed“b˜y“the“stringŽ¤‡‘$h§ë^setpage_prefix‘¿ªë`N‘ïXë^setpage_suffix¹,Ž¡‘ £proš²!vided–±êë`N‘ᕹis“the“starting“page“n˜um˜bMÞer“and“suc˜h“a“setting“is“requested.‘iNext,‘´Ëeac˜h“en˜try“inŽ¦‘ £the–чsorted“list“is“prošMÞcessed“in“order.‘_@Finally‘ÿe,‘ÜOthe“attribute“b˜ound“to“ë^postamble“¹is“app˜endedŽ¦‘ £at–*Dthe“end“of“the“output“ le.‘ ivThe“algorithm“for“generating“eacš²!h“en˜try“with“appropriateŽ¦‘ £formatter-spMÞeci c–ïcommands“or“delimiters“(i.e.› yë^item_ëZi¹'s,–lÑë^delim_ëZi¹'s,“etc.)˜is–ïdescribMÞed“inŽ¦‘ £Reference‘¦f[18].ŽŸ+%Þ‘ £ëX4Ž‘!UnPlacing–ffIndex“CommandsŽŸ>X‘ £¹This–¦Õsection“discusses“a“simple“framewš²!ork“for“placing“index“commands“in“a“doMÞcumen˜t.‘ß*ItŽ¦‘ £assumes–×õan“in•²!teractiv“e–×õeditor“is“aš²!v‘ÿdDailable“with“ëYstring‘‚se–ÿp¹ar“ch‘× ¹,‘äYwhic˜h–×õpMÞositions“the“cursor“to“aŽ¦‘ £spMÞeci ed–e×pattern,›•³and“ëYquery-insert‘ ê¹,˜whicš²!h“displa˜ys“a“men˜u“of“options“and,‘•³upMÞon“the“user'sŽ¦‘ £selection,›ËÝinserts–•:a“spMÞeci ed“k²!ey‘ÿe,˜together“with“other“constan²!t“strings“(e.g.,˜the“index“commandŽ¦‘ £and–¦fits“argumen²!t“delimiters).Ž¦‘£W‘ÿee–ìimplemenš²!ted“this“framew˜ork“on“top“of“GNU‘ë`Emacs‘„n¹[19]“as“part“of“an“in˜teractiv˜eŽ¦‘ £en•²!vironmen“t–S‚for“compšMÞosing“T‘þ,³Ÿ[wEŽ‘B X-based“do˜cumen²!ts“[5].‘Âits“acron²!ym,˜and“other“abbreviations.‘Á~F‘ÿeor“instance,˜the“follo²!wing“patternsŽ¡‘ £maš²!y–¦fall“bMÞe“indexed“b˜y“the“k˜ey“ë^UCB¹,Ž©”s‘7óë^University–¿ªof“California,“BerkeleyŽ¡‘7óBerkeleyŽ¡‘7óberkeleyŽ¡‘7óUCBŽ¦‘£¹As–Ó¸a“spMÞecial“case“of“this“ë^<ëYkey‘ø¹,›ß ëYp‘ÿp¹attern‘× ë^>“¹setup,˜one“can“use“wš²!ords“in“the“neigh˜b•MÞorho“o“d‘Ó¸ofŽ¡‘ £curren²!t–ÓGcursor“pšMÞosition“as“the“implicit“v‘ÿdDalue“for“b˜oth“the“k²!ey“and“the“pattern.‘dSome“editorsŽ¡‘ £alloš²!w–¨±the“use“of“spMÞecial“c˜haracters“to“delimit“w˜ord“bMÞoundaries.‘‰LThese“c˜haracters“can“bMÞe“used“inŽ¡‘ £searcš²!hing–IHto“reduce“on“the“n˜um˜bšMÞer“of“\false“drops".‘¾ÓF‘ÿeor“example,‘[èone“can“p˜osition“the“cursorŽ¡‘ £after–ûthe“desired“pattern“and“with“one“editor“command“(tš²!ypically“in“t˜w˜o“or“three“k˜ey“strok˜es),Ž¡‘ £an–ãcindex“enš²!try“will“bMÞe“inserted“with“the“preceding“w˜ord“(or“w˜ords)“as“the“implicit“k˜ey‘ÿe.‘”ÕTheŽ¡‘ £adv‘ÿdDanš²!tage–Qˆof“this“facilit˜y“is“that“there“is“no“need“to“t˜ypMÞe“the“k˜ey-pattern“pair.‘Á“The“same“ideaŽ¡‘ £also–ßiapplies“to“a“region“of“text,‘5whicš²!h“is“a“piece“of“con˜tin˜uous“text“in“the“doMÞcumen˜t.‘›‰In“ë`Emacss‚¹,Ž¡‘ £a–{region“is“evš²!erything“bMÞet˜w˜een“a“mark˜er“and“the“curren˜t“cursor“pMÞosition.‘ÏoMore“generally‘ÿe,‘ƒÄtheŽ¡‘ £implicit–yiopšMÞerand“can“b˜e“the“ëYcurr–ÿp¹ent‘­ sele“ction‘× ¹,‘®)in–yiwhic²!h“case“the“b˜ounding“p˜ositions“of“theŽ¡‘ £selected–¦ftext“are“not“necessarily“the“insertion“pMÞoin²!t.Ž¡‘£In–¼õour“system,‘™there“is“also“a“spMÞecial“facilitš²!y“to“index“ev˜ery“author“name“that“appMÞears“inŽ¡‘ £the–µ÷bibliographš²!y“or“references“section“of“a“doMÞcumen˜t.‘ This“feature“in˜v˜olv˜es“skipping“citationŽ¡‘ £enš²!tries–ð³without“an“author“ eld“and“for“eac˜h“author“name“found,‘ issuing“a“query-insert“promptŽ¡‘ £similar–kto“the“normal“case.‘ÊInstead“of“en²!tering“a“name“directly“as“the“index“term,‘vçit“is“bMÞetterŽ¡‘ £to–w”displaš²!y“it“in“the“form“of“last“name“follo˜w˜ed“b˜y“ rst“and“middle“names“for“con rmation,‘€ñasŽ¡‘ £inŽŽŽŒ‹¿] …(õ ý†× ŸôçŸü™š’¸¼Ë¹18Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘$h§ë^Confirm:–¿ªKnuth,“Donald“E.ŽŸfg‘ £¹This–ñ$reordering“yields“last“names“as“primary“sort“k²!eys.‘¾Our“name“separation“heuristic“doMÞesŽ¤fg‘ £not›¤alw•²!a“ys˜w“ork˜for˜m“ulti-w“ord˜last˜names.‘ì–The˜con rmation˜prompt˜allo“ws˜the˜user˜toŽ¡‘ £correct–¦fit“bMÞefore“insertion.Ž©$R…‘ £Í4.2Ž‘'È£Key-P attern‘€ListŽŸxÌ‘ £¹A›[collection–[Mof“these“ë^<ëYkey‘ø¹,‘ˆ†ëYp‘ÿp¹attern‘× ë^>“¹pairs“can“bMÞe“compiled“in“a“list.‘ü‘A˜global“function“canŽ¡‘ £then–ÓòbšMÞe“in•²!v“ok“ed–Óòto“pro˜cess“eacš²!h“pair“for“the“en˜tire“doMÞcumen˜t“or“parts“of“it.‘f‚This“list“can“bMÞeŽ¡‘ £created–ü.o -line“bš²!y“the“user,‘ or“automatically“in“an“incremen˜tal“fashion“as“the“user“con rmsŽ¡‘ £new–ÿ·index“insertions“in“an“in•²!teractiv“e–ÿ·session.‘¦MThe“pattern“matcš²!hing“mec˜hanism“m˜ust“bMÞe“ableŽ¡‘ £to–Énrecognize“and“skip“instances“already“indexed“so“that“unnecessary“repMÞetitions“are“a•²!v“oided.Ž¡‘ £In–pour“system,‘12this“k²!ey-pattern“list“is“a“pšMÞer“do˜cumen²!t“list.‘*ûIf“a“do˜cumenš²!t“includes“m˜ultipleŽ¡‘ £ les,‘iÈthe–Z¡global“function“proMÞcesses“eacš²!h“of“them“according“to“the“preorder“tra˜v˜ersal“of“the“ leŽ¡‘ £inclusion‘¦ftree.Ž¦‘ £Í4.3Ž‘'È£Indexing‘€Men uŽŸxÌ‘ £¹F‘ÿeor–ýeacš²!h“instance“of“the“pattern“found,‘~ba“men˜u“of“options“suc˜h“as“the“follo˜wing“ma˜y“bMÞeŽ¡‘ £presen²!ted.Ž¤fg‘usë[ŽŽŽ‘$h§ëYCon rm‘× ¹.Ž¡‘usë[ŽŽŽ‘$h§ëYIgnor‘ÿp¹e‘Ò¡¹.Ž¡‘usë[ŽŽŽ‘$h§ëYKey-Pattern‘J°List‘ ê¹.‘+Add–€the“curren²!t“ë^<ëYkey‘ø¹,‘(†ëYp‘ÿp¹attern‘× ë^>“¹pair“to“the“list“assoMÞciated“with“theŽ©fg‘$h§curren•²!t‘¦fdoMÞcumen“t.Ž¡‘usë[ŽŽŽ‘$h§ëYIndex‘hYL‘ÿp¹evel‘!ª¹.›®Prompt–zthe“user“for“an“index“pre x.˜The“ë^level“¹opMÞerator“(`ë^!¹'),‘4Ýif“not“giv²!enŽ¦‘$h§at–ù×the“end“of“the“spšMÞeci ed“string,‘³should“b˜e“inserted“automatically“b˜et•²!w“een–ù×the“pre xŽ¦‘$h§and–¦fthe“currenš²!t“k˜ey‘ÿe.ŽŽŽŒ‹ÊQ …(õ ý†× Ÿü™š’¸¼Ë¹19Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘usë[ŽŽŽ‘$h§ëYA‘ÿp¹ctual‘DåField‘!ª¹.‘FPrompt–4the“user“for“the“actual“ eld“correspMÞonding“to“the“curren²!t“(sort)Ž¤fg‘$h§k²!ey‘ÿe.‘ÝÝThe–¦fë^actual“¹opšMÞerator“(`ë^@¹')“should“b˜e“automatically“inserted“in“b˜et•²!w“een.ŽŸfg‘usë[ŽŽŽ‘$h§ëYPage‘Î?Enc‘ÿp¹apsulator‘-»¹.›Ã+Prompt–€the“user“for“the“page“n•²!um“bMÞer–€encapsulator.˜The“ë^encapŽ¡‘$h§¹opMÞerator–ìµ(`ë^|¹'),›þIif“not“giv²!en,˜should“bMÞe“attacš²!hed“in“fron˜t“of“the“spMÞeci ed“string.‘°ËEncap-Ž¡‘$h§sulators–ÀúcorrespšMÞonding“to“p˜opular“fonš²!ts“suc˜h“as“bMÞold,–žitalic,“and‘Àúslan˜ted,“or–Àúto“crossŽ¡‘$h§references–¦flik²!e“ëYse›ÿp¹e‘y¹and“ëYse˜e‘êêalso‘WX¹can“bMÞe“implemenš²!ted“as“a“submen˜u.ŽŸ$R…‘ £Í4.4Ž‘'È£Extended‘€F‘þàramew orkŽŸxÌ‘ £¹A‘þõtš²!ypical–ÿ scenario“for“placing“index“commands“under“the“extended“framew˜ork“is“as“follo˜ws.Ž¡‘ £There–Áare“t•²!w“o–Áquery-insert“moMÞdes:‘ž’one“based“on“a“single“k²!ey-pattern“pair“and“the“other“onŽ¡‘ £m•²!ultiple›¼k“ey-pattern˜pairs.‘àIn˜the˜former˜mo•MÞde,‘+Rthe˜user˜sp“eci es˜a˜pattern˜and˜a˜k²!ey‘ÿe,‘+RandŽ¡‘ £for–%)ev²!ery“instance“of“the“pattern“found,‘DÚdecides“whether“to“insert“the“index“command“withŽ¡‘ £the–…ÔspMÞeci ed“kš²!ey‘ÿe,‘ŒWor“a“v‘ÿdDarian˜t“of“it“(i.e.,‘ŒWa“com˜bination“of“ë^level¹,–ŒWë^actual¹,“and–…Ôë^encap¹).‘ÓIn“theŽ¡‘ £latter–.ˆmoMÞde,‘Fthere“is“a“collection“of“enš²!tries“that“ma˜y“bMÞe“represen˜ted“as“a“long“list“for“an“en˜tireŽ¡‘ £doMÞcumenš²!t,‘™Nor––as“a“short“list“for“a“section.‘ØhEac˜h“k˜ey-pattern“pair“in“the“list“is“proMÞcessed“as“inŽ¡‘ £the–¦fformer“case.‘ÝÝProš²!visions“are“also“a˜v‘ÿdDailable“to“help“construct“the“list.Ž¡‘£With– ùsucš²!h“pMÞo˜w˜erful“mec˜hanisms“a˜v‘ÿdDailable,‘¢there“is“a“tendency“to“\o˜v˜er“index"“bMÞecause“itŽ¡‘ £is–=¼so“easy“to“bMÞe“comprehensivš²!e.‘£àIn“some“cases,‘c‘\less“ma˜y“bMÞe“more".‘£àTherefore,‘c‘one“shouldŽ¡‘ £bMÞe–»áextremely“careful“in“con rming“the“insertion“of“ëYkey‘³â¹to“a•²!v“oid–»áfalse“drops“pic•²!k“ed–»áup“b²!y“theŽ¡‘ £searc•²!h‘¦fmec“hanism.ŽŸ+€A‘ £ëX5Ž‘!UnDirect‘ffManipulationŽŸ>X‘ £¹Although–[our“implemenš²!tation“of“these“facilities“w˜as“for“a“source-based“system,‘™a“n˜um˜bMÞer“ofŽ¡‘ £direct-manipulation–°»systems“do“suppšMÞort“a“similar“indexing“facilit²!y–ÿe.‘‹ùF“our–°»systems“are“describ˜edŽ¡‘ £brie y–˜to“indicate“the“applicabilit²!y“of“the“principles“depicted“in“the“previous“sections.‘4tAlsoŽ¡‘ £examined–3‚is“a“more“elabšMÞorate“on-line“indexing“facilit²!y“made“p˜ossible“using“the“electronicŽ¡‘ £media.ŽŽŽŒ‹ÒO …(õ ý†× Ÿü™š’¸¼Ë¹20Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £Í5.1Ž‘'È£Indexing–€under“Direct“ManipulationŽŸxÌ‘ £¹In–|Xeroš²!x“P‘ÿeAR˜C's“ë`Cedar‘E<¹en˜vironmen˜t“[20],‘±~the“ë`Tioga“¹editor“suppMÞorts“an“application“calledŽ¤fg‘ £ë`IndexT‘ÿeoMÞol‘6ä¹[21]–È’that“automatically“prepares“mš²!ultiple“m˜ulti-lev˜el“indexes“(general“index,‘ôïauthorŽ¡‘ £index,‘Úetc.)‘ÍÍwith–v7cross“references“(ëYse›ÿp¹e‘Hعand“ëYse˜e‘¾•also‘°ò¹)“and“with“substitution“phrases“(index“theŽ¡‘ £phrase–Æ\data“structures"“under“\data“structure"“to“handle“these“automatically).‘ûþë`IndexT‘ÿeoMÞolŽ¡‘ £¹takš²!es–ça“selection“and“creates“an“index“en˜try“attac˜hed“to“the“doMÞcumen˜t“o˜v˜er“the“selectionŽ¡‘ £range.‘¥Index–èÏen²!tries“can“bšMÞe“edited“in“a“separate“to˜ol“to“p˜ermit“creating“the“cross“referencesŽ¡‘ £and–¯ substitution“text.‘÷Ìë`Tioga“¹also“has“a“regular“expression“searcš²!h“capabilit˜y“via“ë`EditT‘ÿeoMÞolnR¹,Ž¡‘ £whicš²!h–¦falso“pMÞermits“a“wide“range“of“searc˜h“and“replace“opMÞerations.Ž¡‘£In–#fë`F‘ÿerameMakš²!er‘ì¹1.0“[15],‘‚¥index“tags“can“bMÞe“placed“and“edited“using“a“com˜bination“ofŽ¡‘ £the–ü¨ë`Markš²!ers‘p*¹and“the“ë`Searc˜h“¹toMÞols.‘à£ë`Mark˜ers‘p*¹allo˜ws“one“to“spMÞecify“in˜visible“tags“suc˜h“as“sub-Ž¡‘ £jects,–pìcommenš²!ts,“and–cof“course,‘pìindex“en˜tries.‘Ç•F‘ÿeor“eac˜h“mark˜er,‘pìan“assoMÞciated“annotation“canŽ¡‘ £b•MÞe›¤°sp“eci ed.‘غIn˜the˜indexing˜case,‘äAthe˜annotation˜is˜the˜k²!ey˜to˜app“ear˜in˜the˜ nal˜index.Ž¡‘ £A²!ttributes–— of“page“encapsulation“discussed“previously“can“also“bšMÞe“sp˜eci ed“in“the“ë`Mark²!ersŽ¡‘ £¹windoš²!w.‘¦~These–>œattributes“include“explicit“page“range,–d©fon˜ts,“and–>œan“option“to“disable“pageŽ¡‘ £n•²!um“bšMÞers–Ó¶so“that“cross“references“lik²!e“ëYse‘ÿp¹e‘¦W¹can“b˜e“realized.‘eÎë`F‘ÿerameMakš²!er‘É)¹'s“ë`Searc˜h“¹can“bMÞe“usedŽ¡‘ £to–JgloMÞcate“the“desired“pattern“in“plain“or“regular“expressions.‘ÉßAn“inš²!visible“c˜haracter“ë^\m“¹canŽ¡‘ £b•MÞe›À¬sp“eci ed˜in˜ë`Searc•²!h˜¹to˜iden“tify˜eac“h˜oMÞccurrence˜of˜index˜mark“ers˜in˜the˜doMÞcumen“t.‘,¯When-Ž¡‘ £evš²!er–€„a“mark˜er“is“found,‘· the“correspMÞonding“annotation“is“displa˜y˜ed“in“the“ë`Mark˜ers‘ô¹windo˜w.Ž¡‘ £The–Êannotated“text“can“incorpšMÞorate“sp˜ecial“sym²!b˜ols“to“yield“m•²!ulti-lev“el–Êindexing“and“actualŽ¡‘ £ eld–ø=substitution“similar“to“the“ones“describšMÞed“in“ab˜o•²!v“e.‘ÓaA‘ø(pro˜cessor–ø=called“ë`fmBo˜ok‘¢A¹can“b˜eŽ¡‘ £executed–Ö×o -line“to“collect“index“mark²!ers,›âósort“them,˜and“ nally“generate“a“formatted“indexŽ¡‘ £whose–¦fstš²!yle“is“customizable“via“system“supplied“propMÞert˜y“sheets.Ž¡‘£In–m\the“Macinš²!tosh“v˜ersion“of“ë`MicroSoft“W‘ÿeord‘Û®¹3.0“[16],‘xÅan“index“command“is“designated“b˜yŽ¡‘ £the–HÀ\index“cošMÞde"“ë^.i.“¹The“text“b˜et•²!w“een–HÀë^.i.“¹and“an“\end-of-en²!try“co˜de",‘[{suc²!h“as“a“semicolon,Ž¡‘ £is–:regarded“as“the“index“kš²!ey‘ÿe.‘÷ZA‘"colon“(ë^:¹)“in“the“en˜try“text“acts“as“the“index“lev˜el“opMÞerator.Ž¡‘ £The–¾output“appšMÞearance“can“b˜e“re ned“bš²!y“using“v‘ÿdDarian˜ts“of“the“index“coMÞde.‘¬¥F‘ÿeor“instance,‘0Fë^.iB.Ž¡‘ £¹and–9›ë^.iI.“¹set“the“page“n•²!um“bšMÞer–9›in“b˜oldface“and“italic“fon•²!ts,‘O]resp˜ectiv“ely‘ÿe,‘O]ë^.i(.–9›¹and“ë^.i).“¹createŽŽŽŒ‹Üò …(õ ý†× Ÿü™š’¸¼Ë¹21Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £an–Ýexplicit“page“range,‘ëEetc.‘ƒ)Index“enš²!tries“are“\compiled"“in˜to“the“actual“index“that“appMÞearsŽ¤fg‘ £at–¾¶the“end“of“the“doMÞcumenš²!t.‘&ÎBefore“that“tak˜es“place,‘ÄÊthe“system“m˜ust“bMÞe“noti ed“that“theseŽ¡‘ £index–îæcošMÞdes“are“ëYhidden‘-text‘ ê¹.‘·]An“option“in“the“preference“sheet“can“b˜e“set“to“displa²!y“hiddenŽ¡‘ £text–A\em²!bšMÞedded“in“the“do˜cumenš²!t.‘¼/Hidden“text“m˜ust“bMÞe“\hidden"“when“index“en˜tries“are“bMÞeingŽ¡‘ £compiled;‘HLotherwise–Upage“n•²!um“bšMÞer–Ucomputation“will“b˜e“incorrect.‘!©There“are“no“sp˜ecial“to˜olsŽ¡‘ £for–Cáenš²!tering“index“coMÞdes.‘½The“ë` nd‘²3¹and“ë`c˜hange‘àè¹commands“in“the“ë`Searc˜h“Men˜u“¹do“not“suppMÞortŽ¡‘ £regular–•´expressions.‘«ÆThere“are“no“query-insert“moMÞdes“in“the“searcš²!h“mec˜hanism.‘«ÆAlthoughŽ¡‘ £abbreviations–xÄcan“bMÞe“registered“as“glossary“enš²!tries,‘äa“great“man˜y“k˜eystrok˜es“are“still“requiredŽ¡‘ £in–¦fplacing“a“single“index“en²!try‘ÿe.Ž¡‘£In–•ë`V‘ÿeenš²!tura“Publisher‘^¸¹1.1“[17],‘ÑYa“desktop“publishing“system“for“doMÞcumen˜ts“prepared“onŽ¡‘ £anš²!y–ËÞof“sev˜eral“w˜ord“proMÞcessing“programs“on“the“IBM‘ËÕPC,“index“en˜tries“can“bMÞe“placed“in“theŽ¡‘ £doMÞcumen•²!t›`Pb“y˜in“v“oking˜a˜dialogue˜bMÞo“x˜at˜the˜desired˜pMÞosition.‘Æ€An˜alternativ“e˜is˜to˜use˜a˜w“ordŽ¡‘ £proMÞcessor–¦fto“enš²!ter“a“markup“tag“suc˜h“asŽŸw‘$h§ë^<$Ialpha[alpha];beta>ŽŸw‘ £¹where–ÔVë^<$Ië[–Ó1“Ž‘ Æcë^>“¹marks“ë[–Ó1“Ž‘o¹as“an“index“term,›Òë^alpha“¹is“the“actual“k²!ey“in“italic,˜ë^[ë[–Ó1“Ž‘ Æcë^]Ž¡‘ £¹designates‘`ùë[–Ó1“Ž‘ˆU¹as–`ùthe“correspMÞonding“sort“kš²!ey‘ÿe,‘nÜand“the“semicolon“is“the“index“lev˜el“opMÞerator.‘ƹItŽ¡‘ £suppMÞorts›Ú¤t•²!w“o˜lev“els˜of˜subindexing˜as˜w“ell˜as˜ëYse–ÿp¹e‘­E¹and˜ëYse“e‘úalso‘°ò¹.‘z—Index˜terms˜are˜hidden˜text;Ž¡‘ £the–0³wš²!ord“ë^Index“¹will“bMÞe“displa˜y˜ed“b˜y“its“ëYCurr–ÿp¹ent›~¢Sele“ction˜Indic“ator‘^n¹when–0³the“cursor“is“placedŽ¡‘ £at–2a“loMÞcation“where“an“index“term“is“ancš²!hored.‘‚SThe“output“index“st˜yle“can“bšMÞe“sp˜eci ed“b²!yŽ¡‘ £cš²!hanging–ãÿattributes“in“a“propMÞert˜y“sheet“called“ë^GENERATE‘¿ªINDEX¹.“The“collection“of“attributesŽ¡‘ £is–­Åa“propšMÞer“subset“of“T‘ÿeable“2.‘óúIndex“pro˜cessing“is“executed“as“a“batc²!h“job“similar“to“ë`fmBo˜okŽ¡‘ £¹in›¤ë`F‘ÿerameMak•²!er‘É)¹.‘­GSearc“hing˜is˜una“v‘ÿdDailable˜in˜ë`V‘ÿeen“tura˜Publisher‘É)¹,‘1Ëtherefore˜an˜automated˜indexŽ¡‘ £placing–¦fsubsystem“is“not“pMÞossible.ŽŸ#õ‘ £Í5.2Ž‘'È£Dynamic–€Indexing“and“Hyp`ertextŽŸxÌ‘ £¹Our–SpropMÞosed“implemenš²!tation“of“an“indexing“facilit˜y“under“direct“manipulation“and“the“fourŽ¡‘ £real–оsystems“discussed“previously“all“opMÞerate“in“a“mš²!ulti-pass“fashion,‘Tm˜uc˜h“the“same“as“aŽ¡‘ £source-language–qÓbased“system.‘wHo•²!w“ev“er,›¯Šbased–qÓon“its“in•²!teractiv“e–qÓnature,˜a“direct-manipulationŽŽŽŒ‹ê …(õ ý†× Ÿü™š’¸¼Ë¹22Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £došMÞcumen²!t–ñ€editor“can“b˜e“constructed“with“an“indexing“subsystem“that“folloš²!ws“the“same“cen˜tralŽ¤fg‘ £ideas,–¦fbut“with“an“user“in²!terface“more“closely“related“to“the“direct-manipulation“paradigm.Ž¡‘£The–‹\directness"“maš²!y“bMÞe“observ˜ed“in“the“follo˜wing“scenario.‘ ILThe“author“spMÞeci es“in-Ž¡‘ £put/output–m]stš²!yles“b˜y“selecting“options“a˜v‘ÿdDailable“in“system“supplied“propMÞert˜y“sheets.‘ÊÚF‘ÿeor“eac˜hŽ¡‘ £kš²!ey–¸selected“in“the“doMÞcumen˜t,‘¼mits“correspMÞonding“en˜try“in“the“index“is“immediately“displa˜y˜ed,Ž¡‘ £along–Üqwith“enš²!tries“already“en˜tered.‘ýSorting“is“done“as“the“en˜try“is“generated“for“the“output.Ž¡‘ £Consequen•²!tly‘ÿe,‘ûthe›ÐBin“ternal˜structure˜for˜these˜en“tries˜can˜no˜longer˜bMÞe˜an˜arra“y˜that˜is˜suitableŽ¡‘ £for–vfast“sorting“algorithms.›®Instead,‘4Úa“balanced“tree“ma²!y“bMÞe“the“preferred“structure.˜InsertionŽ¡‘ £and–!Odeletion“reorganize“the“tree“automatically“and“a“tra•²!v“ersal–!Oof“the“tree“yields“the“correctŽ¡‘ £ordering.‘¶’A‘0elink›0ƒbMÞet•²!w“een˜a˜page˜n“um“bMÞer˜in˜the˜index˜en“try˜and˜its˜correspMÞonding˜actual˜pageŽ¡‘ £is–jrequired“so“that“the“index“needs“not“bšMÞe“regenerated“when“the“do˜cumen²!t“is“reformatted.‘ÉÃInŽ¡‘ £other–Éwš²!ords,‘ÒYwhen“a“page“n˜um˜bMÞer“c˜hanges“due“to“reformatting,‘ÒYall“instances“of“that“page“inŽ¡‘ £the–¦findex“c²!hange“automatically‘ÿe.Ž¡‘£One–6÷pšMÞossible“extension“to“this“mo˜del“is“the“abilit²!y“to“p˜oinš²!t“at“an“en˜try“in“the“indexŽ¡‘ £and›˜ha•²!v“e˜the˜corresp•MÞonding˜page˜lo“cated˜automatically˜with˜a˜k•²!eyw“ord˜highligh“ted.‘“sTh“usŽ¡‘ £indexing–MbšMÞecomes“a“dynamic“activit²!y“from“the“reader's“p˜oinš²!t“of“view.‘ѾThis“feature“t˜ypi esŽ¡‘ £the›ù*pMÞo•²!w“er˜of˜\dynamics"˜that˜an˜electronic˜doMÞcumen“t˜en“vironmen“t˜is˜able˜to˜o er,‘Ðwhic“h˜doMÞesŽ¡‘ £not–Á9exist“in“traditional“static“prin²!ted“material.‘.WIn“addition“to“dynamic“indexing,‘Çîone“can“doŽ¡‘ £suc•²!h›‡°h“yp•MÞertext˜op“erations˜as˜na²!vigation,–Õ ltering,“summarizing,“etc.˜[22]˜e ectiv²!ely˜based˜onŽ¡‘ £markup–¦ftags,“em²!bšMÞedded“annotations,“and“links“among“comp˜ound“ob‘›»jects“in“the“do˜cumen²!t.ŽŸ+€A‘ £ëX6Ž‘!UnEv‘ÿ™aluationŽŸ×ñ‘ £Í6.1Ž‘'È£Index–€Placing“SubsystemŽŸxÌ‘ £¹An–% impšMÞortan²!t“asp˜ect“of“our“system“is“the“framew²!ork“for“placing“index“commands“in“theŽ¡‘ £došMÞcumen²!t.‘dThis–†ètask“has“b˜een“p˜erformed“traditionally“in“an“ad“ho˜c“fashion.‘dIt“is“unclearŽ¡‘ £ho•²!w›™½placemen“t˜is˜done˜in˜the˜UNIX‘™ºë`tro ‘¸8¹en“vironmen“t.‘Ù¥Reference˜[23]˜do•MÞes˜not˜describ“e˜an²!yŽ¡‘ £automated–¦fassistance“for“the“author.ŽŽŽŒ‹ö …(õ ý†× Ÿü™š’¸¼Ë¹23Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘£Enš²!tering–Þ&index“coMÞdes“in“ë`MicroSoft“W‘ÿeord‘Lx¹is“a˜wkw˜ard“bMÞecause“its“searc˜h“mec˜hanism“lac˜ksŽ¤fg‘ £full–0zregular“expression“suppšMÞort“and“query-insert“mo˜de“is“una²!v‘ÿdDailable.‘|T‘ÿeo“mark“one“piece“ofŽ¡‘ £text–J´as“an“index“enš²!try‘ÿe,‘sÇan“ordinary“session“requires“8“mouse“clic˜ks“and“4“k˜eystrok˜es.‘ÊÇEv˜enŽ¡‘ £with–Ý„accelerated“kš²!eybMÞoard“abbreviations,‘±it“still“tak˜es“2“mouse“clic˜ks“and“8“k˜eystrok˜es“to“markŽ¡‘ £a–single“index“enš²!try‘ÿe.‘,åThe“premise,–1ÿho˜w˜ev˜er,“is–that“the“index“pattern“has“bšMÞeen“lo˜cated“andŽ¡‘ £that–Z8it“is“idenš²!tical“to“the“index“k˜ey‘ÿe.‘ÄxLoMÞcating“the“pattern“ma˜y“in˜v˜olv˜e“extra“mouse“clic˜ks“andŽ¡‘ £k•²!eystrok“es.‘ÚMoreo“v“er,‘,%if–ethe“index“kš²!ey“and“the“searc˜h“pattern“are“distinct,‘,%more“k˜eystrok˜esŽ¡‘ £wš²!ould–bMÞe“necessary“to“en˜ter“the“text“for“the“index“k˜ey‘ÿe.‘¬šThis“situation“happMÞens“to“the“markingŽ¡‘ £of–S/eacš²!h“and“ev˜ery“instance“of“index“en˜tries.‘ No“global“sc˜heme“is“a˜v‘ÿdDailable“in“ë`MicroSoft“W‘ÿeordnR¹.Ž¡‘£ë`V‘ÿeen²!tura–Ï$Publisher‘˜M¹došMÞes“not“supp˜ort“anš²!y“searc˜hing“mec˜hanism;‘c‚it“assumes“searc˜hing“isŽ¡‘ £pMÞerformed–iin“a“fronš²!t-end“w˜ord“proMÞcessor.‘-åTherefore,‘2isystematic“index“placing“in“the“stand-Ž¡‘ £alone–¦fë`V‘ÿeen²!tura“Publisher‘o¹is“dicult.Ž¡‘£The–Åsituation“in“ë`F‘ÿerameMak²!er‘Ž8¹is“somewhat“bšMÞetter“b˜ecause“of“its“more“p˜o•²!w“erful‘Åk“eyb˜oardŽ¡‘ £macro–zregistration“capabilitš²!y“and“the“suppMÞort“for“regular“expression“searc˜h.‘ÏIn“ë`F‘ÿerameMak˜er‘É)¹,Ž¡‘ £a–­¹spšMÞeci c“com²!bination“of“to˜ols“can“b˜e“used“to“en²!ter“index“tags“at“desired“places.‘óÕOp˜erationsŽ¡‘ £can–}ÓbšMÞe“recorded“as“k²!eyb˜oard“macros“so“that“rep˜etitions“can“b˜e“done“bš²!y“a“single“k˜eystrok˜eŽ¡‘ £(the›Ñ4in•²!v“oMÞcation˜of˜the˜k“eybMÞoard˜macro).‘^HThe˜problem˜is˜that˜a˜new˜k“eybMÞoard˜macro˜hasŽ¡‘ £to–©bMÞe“de ned“for“eacš²!h“k˜ey-pattern“pair.‘%¦F‘ÿeurthermore,‘.úit“lac˜ks“the“systematic“global“sc˜hemeŽ¡‘ £aš²!v‘ÿdDailable–¦fin“our“extended“framew˜ork“to“mak˜e“the“whole“proMÞcess“ecien˜t.Ž¡‘£In–´Four“system,‘·¾it“takš²!es“only“1“to“3“k˜eystrok˜es“to“mark“an“index“en˜try‘ÿe.‘}Also“a˜v‘ÿdDailable“is“aŽ¡‘ £global–§scš²!heme“for“marking“index“en˜tries“in“the“en˜tire“doMÞcumen˜t“that“ma˜y“span“o˜v˜er“m˜ultipleŽ¡‘ £ les.‘ (In–ythe“single“kš²!ey-pattern“case,‘oýthe“same“k˜ey“can“bMÞe“inserted“at“a“v‘ÿdDariet˜y“of“placesŽ¡‘ £describMÞed–<#bš²!y“a“single“regular“expression.‘ºqP˜atterns“already“indexed“are“skippMÞed“automatically‘ÿe.Ž¡‘ £A‘OSn•²!um“bšMÞer–OÀof“options“are“a²!v‘ÿdDailable“up˜on“eac²!h“o˜ccurrence“of“the“pattern.‘ ÙìTh²!us,‘ºmarkingŽ¡‘ £eacš²!h–dDinstance“tak˜es“just“one“k˜eystrok˜e“to“con rm“and“it“w˜orks“uniformly“and“con˜tin˜uouslyŽ¡‘ £throughout–Ãvthe“enš²!tire“doMÞcumen˜t.‘5 This“can“bMÞe“expanded“to“a“sc˜heme“of“m˜ultiple“k˜ey-patternŽ¡‘ £pairs–SGthat“wš²!orks“iterativ˜ely“on“a“list“of“di eren˜t“index“en˜tries.‘äIn“our“system,‘~a“signi can˜tŽ¡‘ £amounš²!t–”‰of“time“is“sa˜v˜ed“not“just“in“t˜yping“ëYp‘ÿp¹er‘Úzse‘Ò¡¹,‘˜but“in“the“user's“men˜tal“reaction“time“dueŽŽŽŒ‹ì …(õ ý†× Ÿü™š’¸¼Ë¹24Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £to–”the“side“e ect“of“unautomated“discrete“repMÞetitions“as“in“ë`F›ÿerameMak²!er‘É)¹,‘ÏŒë`MicroSoft“W˜ordnR¹,Ž¤fg‘ £and–¦fë`V‘ÿeen²!tura“Publisher‘É)¹.Ž¡‘£In–Sºthe“prošMÞduction“of“an“index“for“a“b˜o˜ok“[6],‘dBour“ë`Emacs‘Ç<¹Lisp“implemen²!tation“of“the“indexŽ¡‘ £placing–n'subsystem“has“pro•²!v“ed›n'v“ery˜useful˜and˜e ectiv“e.‘5The˜pro“vision˜for˜m“ulti-pair˜ë^<ëYkey‘ø¹,Ž¡‘ £ëYp‘ÿp¹attern‘× ë^>–¹query-insert“has“bšMÞeen“the“most“time-sa²!ving“op˜eration“in“our“exp˜erience.‘§ÄWith“minorŽ¡‘ £moMÞdi cations,‘W»the–Dsame“facilitš²!y“should“w˜ork“on“placing“index“commands“for“other“formattingŽ¡‘ £languages–Á4likš²!e“ë`tro ‘߯¹and“ë`ScribMÞe‘¹.‘.HAdapting“it“to“direct-manipulation“en˜vironmen˜ts“is“moreŽ¡‘ £in•²!v“olv“ed,‘‡†but›Z€giv“en˜prop•MÞer˜editor˜programming˜p“o•²!w“er,‘‡†the˜basic˜principles˜discussed˜abMÞo“v“eŽ¡‘ £should‘¦fapply‘ÿe.ŽŸ$R…‘ £Í6.2Ž‘'È£Index‘€Pro`cessorŽŸxÌ‘ £¹The–Éother“ma‘›»jor“pšMÞortion“of“our“w²!ork“is“a“complete“index“pro˜cessor“implemen²!tation.‘EóTheŽ¡‘ £resulting–@proMÞcessor“is“a“single“C‘program“called“ë`Mak•²!eIndex‘Á_¹.‘°{Actually‘ÿe,‘9{ë`Mak“eIndex‘ߟ¹had‘@sev“eralŽ¡‘ £predecessors–Uvall“written“as“UNIX‘Uashell“scripts“with“em²!bšMÞedded“ë^sed“¹[24]“and“ë^awk“¹[25]“co˜de.‘ÂâW‘ÿeeŽ¡‘ £quicš²!kly–Q(bMÞecame“unsatis ed“with“them“for“v‘ÿdDarious“reasons.‘ÁsOne“of“the“concerns“w˜as“eciency‘ÿe.Ž¡‘ £Inš²!terpreted–F?languages“suc˜h“as“ë^sed“¹and“ë^awk“¹are“satisfactory“for“rapid“protot˜yping,‘n5but“theyŽ¡‘ £are–Éásloš²!w.‘HMIn“our“expMÞerience,‘Ò¿ë`Mak˜eIndex‘‹@¹w˜as“able“to“prošMÞcess“a“b˜o˜ok“index“of“3,300“en²!tries“inŽ¡‘ £less–ÿthan“50“seconds“of“user“time“plus“an“extra“5%“of“system“time“on“a“clien²!t“noMÞde“of“SUNŽ¡‘ £3/50–<ï(MC68020“at“12.5“MHz).‘¡yThis“is“at“least“an“order“of“magnitude“faster“than“using“itsŽ¡‘ £most–¦frecenš²!t“ë^sed¹/ë^awk“¹predecessor,“whic˜h“has“only“half“the“features“of“ë`Mak˜eIndex‘Á_¹.Ž¡‘£The–{Ëdecision“to“do“a“C‘{implemenš²!tation“w˜as“made“bšMÞecause“of“C's“dynamic“storage“allo˜cationŽ¡‘ £and–¿¬data“structures.‘)¯Since“wš²!e“w˜an˜ted“as“general“a“solution“as“pMÞossible,‘Åýit“w˜ould“bMÞe“dicult,Ž¡‘ £if–óSnot“impMÞossible,›to“implemen²!t“all“the“desired“features“using“ë^sed/awk¹.‘Ä¥F‘ÿeor“instance,˜in“ë^awkŽ¡‘ £¹a–­«dynamically“linkš²!ed“list“of“index“en˜tries“is“impMÞossible,‘ï|and“the“st˜yle“handling“mec˜hanismŽ¡‘ £with– da“comprehensivš²!e“error“proMÞcessing“facilit˜y“is“dicult“to“realize.‘ØOriginally“dev˜elopMÞed“inŽ¡‘ £UNIX–À¢C“with–À©pMÞortabilitš²!y“in“mind,‘Ç9ë`Mak˜eIndex‘‚¹also“runs“on“V‘þȈAX/VMS,“TOPS-20,‘Ç9MS/DOSŽ¡‘ £systems–¢ùwith“a“few“trivial“cš²!hanges.‘Ó•This“pMÞortabilit˜y“w˜ould“ha˜v˜e“bMÞeen“v˜ery“dicult“for“anŽ¡‘ £implemenš²!tation–Éiin“UNIX‘Éshell“scripts.‘FåF‘ÿeurthermore,‘)ë`Mak˜eIndex‘ŠÈ¹has“more“features“and“isŽŽŽŒ‹ þ …(õ ý†× Ÿü™š’¸¼Ë¹25Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £more–ßøextensible“than“toMÞols“lik²!e“ë`IdxT‘þ,³Ÿ[wEŽ›B X‘øL¹[26],‘î\a“L‘üÙŸþ•ëÅaŽ‘Œ„¹T‘þ,³ŸLØEŽ˜X-spšMÞeci c“index“pro˜cessor“that“runs“onlyŽ¤fg‘ £on–¦fV‘þȈAX/VMS“systems.Ž¡‘£Our–Õapproacš²!h“is“the“direct“oppMÞosite“of“that“tak˜en“b˜y“ë^make.index¹,‘l±a“host“of“indexingŽ¡‘ £tošMÞols–’[23]“built“for“ë`tro ‘{¹.‘¬—As“part“of“the“UNIX‘më`tro ‘1 ¹do˜cumenš²!t“preparation“en˜vironmen˜t,‘0#theseŽ¡‘ £tošMÞols–õ9are“canonical“examples“of“the“pip˜elining“mo˜del.‘ÊUThey“are“a“collection“of“small“ë^awkŽ¡‘ £¹programs–o…wš²!orking“together“in“a“v˜ery“long“pipMÞeline.‘Ë’The“claim“is“that“b˜y“breaking“the“systemŽ¡‘ £do•²!wn›œ6in“to˜small˜pieces,‘Ùªit˜is˜easier˜for˜the˜user˜to˜adapt˜the˜pac“k–ÿdDage˜to˜v“arious˜situationsŽ¡‘ £not–›RpMÞossible“to“enš²!vision“in“adv‘ÿdDance.‘¼ Their“approac˜h,–ØŒtherefore,“seems–›Rto“follo˜w“the“\do“itŽ¡‘ £yš²!ourself‘Ú"–ÿ®metaphor“whereb˜y“y˜ou“get“a“toMÞolkit“and“assem˜ble“the“ nal“proMÞduct“y˜ourself.‘é´TheŽ¡‘ £basic– Œpacš²!k‘ÿdDage“co˜v˜ers“only“those“features“used“b˜y“its“authors.‘ªêA‘ ethird“part˜y“user“has“to“moMÞdifyŽ¡‘ £their–¦fë^awk“¹coMÞde“if“something“di eren²!t“is“desired.Ž¡‘£The–òídesign“of“ë`Makš²!eIndex‘´L¹is“quite“di eren˜t.‘ÃrOur“in˜ten˜tion“is“to“build“a“complete“systemŽ¡‘ £bš²!y–›áanalyzing“the“tasks“in˜v˜olv˜ed“in“index“proMÞcessing.‘Ú[P˜arameters“are“deriv˜ed“to“form“a“table-Ž¡‘ £driv•²!en›JSst“yle˜handling˜facilit“y–ÿe.‘¿,F“ormatter˜and˜format˜indepMÞendence˜is˜ac•²!hiev“ed˜b“y˜simple˜st“yleŽ¡‘ £spšMÞeci cation.‘ÄÕAll–[Mthe“underlying“data“structures“and“pro˜cessing“mecš²!hanisms“are“transparen˜t.Ž¡‘ £Y‘ÿeet–Lit“is“robust“enough“to“handle“di erenš²!t“precedence“sc˜hemes,›/ëordering“rules,˜etc.‘¬T‘ÿeo“use“theŽ¡‘ £system,‘Cëthe–$juser“needs“not“deal“with“the“proMÞcessing“details.‘WêIf“the“default“is“inappropriate,Ž¡‘ £the–¦fonly“adaptation“required“is“a“table“spMÞeci cation“for“the“stš²!yle“facilit˜y‘ÿe.Ž¡‘£F‘ÿeor–Q[instance,‘b]b²!y“assigning“the“output“index“header“ë^index.head“¹de ned“in“ë^make.index“¹toŽ¡‘ £our–] ë^preamble“¹and“other“related“commands“to“ë^item_ëZi¹'s,‘k¶it“is“easy“to“prošMÞduce“an“alphab˜etizedŽ¡‘ £index–Zµin“ë`tro ‘y0¹format“from“a“raš²!w“index“generated“b˜y“ë`tro ‘{¹.‘úÉThe“same“tec˜hnique“applies“toŽ¡‘ £other–LÆformatting“systems.‘Ðýë`ScribMÞe‘¹,›v^for“example,˜has“an“indexing“subsystem“that“suppMÞorts“aŽ¡‘ £subset–5õof“the“functionalit²!y“describšMÞed“ab˜o•²!v“e.‘ŒŠBy–5õadapting“its“ra²!w“index“ le“format“as“inputŽ¡‘ £stš²!yle–®Øand“its“output“appMÞearance“commands“as“output“st˜yle,‘ðôits“indexing“capabilit˜y“can“bMÞeŽ¡‘ £readily–nJexpanded“using“ë`Mak²!eIndex‘Á_¹.‘5‰In“bšMÞoth“cases,‘ Cthere“is“no“need“to“mo˜dify“the“originalŽ¡‘ £cošMÞde–Kôused“to“generate“the“ra²!w“index“(Step“I˜I),“nor“is“it“necessary“to“mo˜dify“ë`Mak²!eIndex‘ S¹itself.Ž¡‘ £Lik•²!ewise,‘LÐë`Mak“eIndex‘ìç¹can–+ˆbšMÞe“in²!tegrated“with“direct-manipulation“do˜cumenš²!t“dev˜elopmen˜t“orŽ¡‘ £publishing–îsystems“bš²!y“binding“their“descriptiv˜e“markup“tags“to“the“attributes“of“ë`Mak˜eIndex‘Á_¹'sŽŽŽŒ‹å …(õ ý†× Ÿü™š’¸¼Ë¹26Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £input–¦fformat“and“output“st²!yle.Ž¤fg‘£T‘ÿeo–­›summarize“the“di erences“in“approacš²!h“bMÞet˜w˜een“ë`Mak˜eIndex‘nú¹and“ë^make.index¹,‘ïglet“usŽ¡‘ £examine–ö±the“pšMÞoin²!ts“of“comparison:‘~ssp˜eed,› Äsize“of“the“programs,˜ease“of“use,˜pMÞortabilit²!y‘ÿe,˜andŽ¡‘ £extensibilit•²!y‘ÿe.›m5ë`Mak“eIndex‘—¹is–Ö.an“order“of“magnitude“faster.˜The“ë^awk“¹programs“of“ë^make.indexŽ¡‘ £¹are–´Ÿless“than“100“lines“of“cošMÞde,‘¸-while“ë`Mak²!eIndex‘uþ¹is“large:‘úN6,000“lines“of“C‘´›co˜de“and“a“binaryŽ¡‘ £of›”õ70K‘”¸b•²!ytes.‘©‹ë`Mak“eIndex‘VT¹is˜a˜self-con“tained˜C‘”¸program,‘Йadapted˜from˜our˜original˜UNIXŽ¡‘ £implemenš²!tation,‘Fto–à¾run“on“a“v‘ÿdDariet˜y“of“mac˜hines“from“micros“to“mainframes.‘›ûThe“ë^make.indexŽ¡‘ £¹system–¬ will“run“on“anš²!y“UNIX‘¬žsystem“whic˜h“has“ë^awk“¹so“it“toMÞo“spans“man˜y“systems,‘®.althoughŽ¡‘ £it–¦fis“UNIX-spMÞeci c“while“ë`Mak²!eIndex‘gŹis“not.Ž¡‘£ë`Makš²!eIndex‘è¹is–V‰easy“to“use.‘Ã>It“is“monolithic“and“co˜v˜ers“almost“ev˜ery“conceiv‘ÿdDable“case“lik˜elyŽ¡‘ £to–JØošMÞccur.‘¿XW‘ÿee“actually“examined“man²!y“of“the“b˜o˜oks“in“the“Addison-W‘ÿeesley“Computer“ScienceŽ¡‘ £Series–j[and“found“that“more“than“95%“of“the“cases“could“bMÞe“handled“b²!y“the“program.‘)½TheŽ¡‘ £ë^make.index–[¹suite,›7*on“the“other“hand,˜handles“the“standard“cases“and“all“customizations“m²!ustŽ¡‘ £bMÞe–Ïdone“bš²!y“the“user“b˜y“mošMÞdifying“ë^awk“¹co˜de.‘WõWith“ë`Makš²!eIndex‘Á_¹,‘ÙEuser“c˜hanges“will“v˜ery“rarelyŽ¡‘ £ošMÞccur.‘ɇIf–icthey“should“o˜ccur,‘u–and“wš²!e“ha˜v˜e“nev˜er“had“them“happMÞen,‘u–then“the“user“m˜ust“c˜hangeŽ¡‘ £the–ÐC‘·source“cošMÞde.‘ÿThe“question“as“to“whether“it“is“easier“to“mo˜dify“ë^awk“¹co˜de“or“C‘·co˜de“isŽ¡‘ £left–¦fto“the“reader.‘ÝÝOur“answš²!er“is“giv˜en“in“ë`Mak˜eIndex‘Á_¹.ŽŸ+€A‘ £ëX7Ž‘!UnAc•ŒÌkno“wledgemen“tsŽŸ>X‘ £¹W‘ÿee–•¤wš²!ould“lik˜e“to“thank“Leslie“LampšMÞort“for“his“collab˜oration“in“the“design“of“ë`Mak²!eIndex‘Á_¹.‘ØGHeŽ¡‘ £pro²!vided–›ethe“initial“spMÞeci cation“and“did“some“serious“testing.‘Ú2Charles“Karney“furnished“theŽ¡‘ £patcš²!hes–=Åfor“ë`Mak˜eIndex‘ÿ$¹to“run“under“VMS.“Nelson“BeebšMÞe“p˜orted“ë`Mak²!eIndex‘ÿ$¹to“TOPS-20“andŽ¡‘ £MS/DOS.–¶ìSome“useful“feedbacš²!k“came“from“Art“W‘ÿeersc˜h˜ulz“who“tried“out“bMÞoth“ë`Mak˜eIndexŽ¡‘ £¹and–ù¹the“index“placing“facilitš²!y“with“ë[A‘þ,³Ÿ[wMŽ‘ ô©S‘Ò9¹-T‘þ,³Ÿ[wEŽ‘B X.‘×ÖW‘ÿee“are“grateful“to“Ric˜hard“Beac˜h“for“hisŽ¡‘ £description–A%of“ë`Tioga¹'s“index“proMÞcessing“facilitš²!y‘ÿe,‘gÔto“Ra˜vi“Sethi“for“the“information“on“ë`tro ‘{¹'sŽ¡‘ £index–)prošMÞcessing“to˜ols,‘I©and“to“V‘ÿeenš²!tura“Soft˜w˜are,‘I©Inc.‘e°for“giving“us“doMÞcumen˜tation“on“theirŽ¡‘ £indexing–{umecš²!hanism.‘ÏThanks“also“go“to“Ethan“Munson“and“the“anon˜ymous“referees“for“theirŽ¡‘ £helpful–¦fcommen²!ts“on“earlier“drafts“of“this“papMÞer.ŽŽŽŒ‹&ª …(õ ý†× ŸtçŸü™š’¸¼Ë¹27Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ ýÈ× ‘ £ëXReferencesŽŸç‘¤²[1]ŽŽ‘!œ×The–° Seyb›ÿ}'old“R˜ep˜ort“on“Publishing“Systems².‘RSeybGold–Š/Publications“Inc.,–×fMedia,“P¸ãennsylv‘ÿqÇania.Ž¤ ‘yPublished–UU22“times“a“y¸ãear.Ž©‘¤[2]ŽŽ‘yDonald–¤õE.“Knš¸ãuth.‘\8×T‘þKß'EŽ‘Í-X:‘,The‘Ý(Pr–ÿ}'o“gr“am²,‘¸Ýv˜olume–¤õB‘¤àof“×Computers–Ý(&“T‘ÿ;¼yp‘ÿ}'esetting².‘\8Addison-W‘ÿ*ªesleyŽ¡‘yPublishing–UUCompanš¸ãy‘ÿ*ª,“Reading,“Massac˜h˜usetts,“1986.Ž¦‘¤[3]ŽŽ‘yDonald–UUE.“Kn¸ãuth.›nïLiterate“programming.˜×The–“çComputer“Journal²,–UU27(2):97{111,“Ma¸ãy“1984.Ž¦‘¤[4]ŽŽ‘*×The–“çChic‘ÿ}'ago“Manual“of“Style²,–UU13th“edition,“1982.‘nïUniv•¸ãersit“y–UUof“Chicago“Press,“Chicago,“Illinois.Ž¦‘¤[5]ŽŽ‘yPš¸ãehong––øChen“and“Mic˜hael“A.“Harrison.‘2ˆIn˜tegrating“nonin˜teractiv˜e“doGcumen˜t“proGcessors“in˜to“anŽ¡‘yin•¸ãteractiv“e›®en“vironmen“t.‘¯­T‘ÿ*ªec“hnical˜RepGort˜87/349,–Computer˜Science˜Division,“Univ•¸ãersit“y˜ofŽ¡‘yCalifornia,–UUBerk¸ãeley‘ÿ*ª,“California,“April“1987.‘nïSubmitted“for“publication.Ž¦‘¤[6]ŽŽ‘yDaš¸ãvid–ÍÒH.“Brandin“and“Mic˜hael“A.“Harrison.‘Õþ×The›ÀT‘ÿ;¼e–ÿ}'chnolo“gy˜War².‘ÕþJohn–ÍÒWiley“and“Sons,‘ëñInc.,Ž¡‘yNew–UUY›ÿ*ªork,“New“Y˜ork,“1987.Ž¦‘¤[7]ŽŽ‘yJ.–—F.“T›ÿ*ªraub,‘½G.“W.“W˜asilk•¸ão“wski,‘½and–—H.“W˜o•¸ã‘ûGzniak“o“wski.–8¹×Information-Base‘ÿ}'d‘äÓComplexity².“AcademicŽ¡‘yPress,–UUNew“Y›ÿ*ªork,“New“Y˜ork,“1988.Ž¦‘¤[8]ŽŽ‘yEdwin–óôL.“Hutc¸ãhins,›nJames“D.“Hollan,˜and“Donald“A.“Norman.›Ð3Direct“manipulation“in¸ãterfaces.˜InŽ¡‘yD.–TnA.“Norman“and“S.“W.“DrapGer,–Tœeditors,“×User-Center–ÿ}'e“d–“System“Design²,‘Tœpages–Tn87{124“(ChapterŽ¡‘y5),–UUHillsdale,“New“Jersey‘ÿ*ª,“1986.“La¸ãwrence“Erlbaum“AssoGciates,“Inc.Ž¦‘¤[9]ŽŽ‘yBen–lâShneiderman.›ôDirect“manipulation:‘ýA‘l§step“bGey¸ãond“programming“languages.˜×IEEE‘½×Computer²,Ž¡‘y16(8):57{69,–UUAugust“1983.Ž¦‘ £[10]ŽŽ‘yLeslie‘Ì×LampGort.‘Ó×L‘ýqÈŸþµUó×2cmmi8ÃaŽm×T‘þKߌEŽ‘Í-X:–ÙA‘½Do›ÿ}'cument“Pr˜ep˜ar˜ation“System.“User's“Guide“and“R˜efer˜enc˜e“Manual².Ž¡‘yAddison-W›ÿ*ªesley–UUPublishing“Compan¸ãy˜,“Reading,“Massac•¸ãh“usetts,‘UU1986.Ž¦‘ £[11]ŽŽ‘yDonald–‡(E.“Kn¸ãuth.›Û×The–Ö:T‘þKß'EŽ‘Í-X“Bo‘ÿ}'ok².˜Addison-W›ÿ*ªesley–‡(Publishing“Compan¸ãy˜,–°eReading,“Massac•¸ãh“usetts,Ž¡‘y1984.‘nïReprin¸ãted–UUas“V‘ÿ*ªol.“A“of“×Computers–“ç&“T‘ÿ;¼yp‘ÿ}'esetting‘â}²,‘UU1986.Ž¦‘ £[12]ŽŽ‘yBrian–ê»K.“Reid.‘,%×Scrib–ÿ}'e:‘¬{A‘6do“cument›Ysp“e“ci c“ation˜language˜and˜its˜c“ompiler².‘,%PhD‘ê”thesis,‘Com-Ž¡‘yputer–/6Science“Departmenš¸ãt,‘6ÖCarnegie-Mellon“Univ˜ersit˜y‘ÿ*ª,–6ÖPittsburgh,“P˜ennsylv‘ÿqÇania,“OctobGer‘/61980.Ž¡‘yAv‘ÿqÇailable–UUas“tec¸ãhnical“repGort“CMU-CS-81-100.Ž¦‘ £[13]ŽŽ‘yJoseph–±F.“Ossanna.›cöNro /tro “user's“man¸ãual.˜Computer“Science“T›ÿ*ªec¸ãhnical“RepGort“No.“54,‘ÒOA˜T&TŽ¡‘yBell–ªkLabGoratories,›ÌšMurra¸ãy“Hill,˜New“Jersey‘ÿ*ª,˜OctobGer“1976.‘XUAlso“aš¸ãv‘ÿqÇailable“in“UNIX‘ª@User's“Man˜ual.Ž¦‘ £[14]ŽŽ‘ Žù×8010–9»ST‘ÿ;¼AR‘9‘Information“System“R–ÿ}'efer“enc“e›9»Libr“ary,‘c0R“ele“ase˜4.2².‘ˆXero¸ãx– •Oce“Systems,‘6¥El“Se-Ž¡‘ygundo,–UUCalifornia.“1984.Ž¦‘ £[15]ŽŽ‘üÎ×F‘ÿ;¼r›ÿ}'ame–QÍMaker“R˜efer˜enc˜e“Manual,‘_V‘ÿ;¼ersion“1.0².‘ùÐF–ÿ*ªrame› {T“ec¸ãhnology˜CorpGoration,–ÚSan˜Jose,“Califor-Ž¡‘ynia.–UUF‘ÿ*ªebruary“1987.Ž¦‘ £[16]ŽŽ‘ >×R–ÿ}'efer“enc“e–úªto“Micr›ÿ}'osoft“Wor˜d,‘[Wor˜d“Pr˜o˜c˜essing“Pr˜o˜gr˜am“for“the“Apple“Macintosh,‘[V‘ÿ;¼ersion“3.0².Ž¡‘yMicrosoft–UUCorpGoration,“Seattle,“W‘ÿ*ªashington.“Jan¸ãuary“1987.Ž¦‘ £[17]ŽŽ‘ iQ×V‘ÿ;¼entur›ÿ}'a–(ŸŒEŽ‘ãxX.“×TUGBo‘ÿ}'at²,–4–8(2):201{209,“July˜1987.ŽŽŽŒøB܃’À;è…(õïÿ ó`p®0J ó3 cmsl10ó^ßê ó3 cmmi10óYý': ó3 cmti10óXÂÖN ff cmbx12óFo´‹Ç cmr9ó9q¡% cmsy6ó8¾KÈ cmsy8ó1p®0J cmsl10ó0}h!Ó cmsl12ó,ý': cmti10ó)ßê