÷ƒ’À;è TeX output 1994.10.13:2153‹ÿÿÿÿ …(õ� ý†×  [(õ� ýÿ½u�‘põ(óDÓítG®G®cmr17ÆIndex–7tPreparation“and“Pro�sŽ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“pap�Ger“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˜pro�Gcessor“that“transforms“a“raš¸ãw“index“in˜to“an“alphab�Getized“v˜ersion“is“describ�Ged.Ž¡�‘$h§The–õVresulting“system“has“pro•¸ãv“ed›õVv“ery˜useful˜and˜e ectiv“e˜in˜pro�Gducing˜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“do�Gcumen˜t“preparation“en˜vironmen˜ts“is“giv˜en.Ž¡�‘3h¨ó,ý': cmti10×Keywor‘ÿ}'ds‘Ò!²:‘Xƒindex–"Íplacemen�¸ãt,›,èindex“pro�Gcessing,˜source-language“mo�Gdel,˜direct“manipu-Ž¡�‘$h§lation.ŽŸ+.¼��‘ £óXÂÖN ff cmbx12ëX1Ž‘!UnIn�ŒÌtro�s3ductionŽŸ>X�‘ £óKñ`y ó3 cmr10¹Although–_:there“has“b�MÞeen“a“great“deal“of“activit�²!y“in“electronic“publishing“[1],‘�othere“are“stillޤfg�‘ £aspšMÞects–W�of“do˜cumen�²!t“comp˜osition“that“ha•²!v“e–W�not“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ëFSp�AÇ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“metho�MÞds“will“notŽ¡�‘ £suce–¦ffor“soft•²!w“are–¦fengineering“applications.Ž¡�‘£Standard–®Œauthors'“guides,›°–suc�²!h“as“Reference“[4],˜recommend“that“index“terms“b�MÞ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“b�MÞer–¤is“added“to“a“card“when“a“reference“isŽ¡�‘ £encounš²!tered.‘ÆSorting–^ùis“done“b˜y“hand“and“the“pro�MÞcess“is“tedious“and“error-prone.‘ÆComputersŽ¡�‘ £o er–;šan“opp�MÞortunitš²!y“to“signi can˜tly“reduce“the“amoun˜t“of“lab�MÞor“in˜v˜ested“in“this“pro�MÞ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˜do�MÞ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“alphab�MÞetizedŽ¡�‘ £vš²!ersion–òtis“describ�MÞed.‘¡âThese“concepts“ha˜v˜e“b�MÞ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“b�MÞ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-Ž¡�‘ £sp�MÞ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“pro�MÞ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,app�MÞearance“directly“bš²!y“in˜v˜oking“built-in“op�MÞ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“op�MÞ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“prop�MÞert˜y“sheets.‘�XThese“prop�MÞert˜y“sheets“corresp�MÞondŽ¡�‘ £to–{textual“markup“tags“that“can“bšMÞe“imp˜orted“to“or“exp˜orted“from“the“direct-manipulationŽ¡�‘ £system–[for“do�MÞcumenš²!t“in˜terc˜hange“purp�MÞ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“sp�MÞeci cationŽ¡�‘ £language–¦fis“somewhat“implicit“in“direct-manipulation“systems.Ž¡�‘£Some–Ÿ]p�MÞ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˜b�MÞ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“mo�MÞdels“user“in˜terfaces.Ž¡�‘ £A‘Gdirect-manipulation–do�MÞcumenš²!t“preparation“system“ma˜y“not“ha˜v˜e“a“ÅWYSIWYG‘G¹relation-Ž¡�‘ £ship›•|b�MÞ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“b�MÞe“coupled“with“a“preview˜er“that“is“ÅWYSIWYG¹.Ž¡�‘£This–(‹pap�MÞ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“pro�MÞcessor“and“then“some“designŽ¡�‘ £and–Áimplemenš²!tation“considerations“for“suc˜h“a“pro�MÞcessor.‘õîOur“goal“is“to“arriv˜e“at“generalŽ¡�‘ £purp�MÞose–3solutions.‘ ƒùNext,‘–Fa“framewš²!ork“is“in˜tro�MÞ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›•èdo�MÞcumen“t˜preparation˜language˜based˜on˜T�‘þ,³Ÿ[wEŽ‘B X˜[11].‘¬cThe˜mo�MÞ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“do�MÞ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ë`Scrib�MÞe‘Cm¹[12],–¦fë`tro ‘Äá¹[13],“and“some“direct-manipulation“en•²!vironmen“ts.ŽŸ+l‡��‘ £ëX2Ž‘!UnBasic‘ffT‘þ¦fasksŽŸ>X�‘ £¹Index–¦fpreparation“is“a“pro�MÞcess“in•²!v“olving–¦fthe“follo�²!wing“steps:ŽŸýÊ����‘ðI.ŽŽŽ‘$h§Placing–dindex“commands“in“the“do�MÞ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“b�MÞe“indexed.Ž©<�����‘­üI�MÞ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“app�MÞears.ަ����‘kÚI•MÞI“I.ŽŽŽ‘$h§Pro�MÞcessing– òthe“raš²!w“index“ le.‘ M€Here,‘”all“index“k˜eys“are“sorted“alphab�MÞetically‘ÿe.‘ M€P˜ageŽ¡�‘$h§n•²!um“b�MÞers–’under“the“same“kš²!ey“are“merged“and“successiv˜e“n˜um˜b�MÞers“ma˜y“b�MÞ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ób�MÞetaŽŽ¡��’2tógamma,‘¦f22ŽŽ¡��’(tódelta,‘¦f38ŽŽ¡��’tóëYalpha‘× ¹,‘¦f14ŽŽ¡��’tóalphab•MÞeta,‘¦fëYse‘ÿp¹e‘y¹b“etaŽŽ¡¡��’tób�MÞeta,‘¦fó\ò"V ó3 cmbx10ë\14ŽŽ¡ŽŽ á…�¹Figure›ÄÔ2:‘¹ëYThe–éstepwise“development“of“index“pr–ÿp¹o“c“essing‘ø¹.‘9'This˜example˜is˜sp�MÞeci ed˜in˜L�‘üÙŸþ•ëÅaŽ‘Œ„¹T�‘þ,³ŸLØEŽ‘B X.ޤ ™š�(a)–?Âë`T‘ÿeop“Left�=¹:‘–Occurrences“of“index“commands“in“the“do�MÞcumen�²!t“source.‘ ©òNote“that“pageŽ¡�n•²!um“b�MÞ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“b�MÞers˜are˜included˜here˜simply˜to˜illustrate˜where˜eac“h˜instance˜will˜o�MÞccur.‘}(b)˜ë`T‘ÿeopŽ¡�Righ•²!tš=¹:‘Üâra“w–%èindex“ le“generated“b�²!y“L�‘üÙŸþ•ëÅaŽ‘Œ„¹T�‘þ,³ŸLØEŽ‘B X.“(c)“ë`Bottom“Left˜¹:‘Üâalphab�MÞ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“b�MÞ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“I�MÞ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“do�MÞ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“b�MÞe“utilized“bš²!y“the“formatter“in“generating“ra˜w“index“en˜tries“(Step“I�MÞ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‘Ñ=p�MÞossible“solution“is“to“put“them“in“\shado˜w“pages"“instead“of“theŽ¡�‘ £do�MÞcumenš²!t–úAoutput“represen˜tation.‘ÙmA‘ú+shado˜w“do�MÞcumen˜t“is“the“original“do�MÞcumen˜t“plus“sp�MÞ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˜do�MÞcumen“t˜comp�MÞ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“b�MÞe“displa˜y˜ed“along“with“the“original“do�MÞcumen˜t“for“editing“purp�MÞ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˜b�MÞol.Ž¡�‘ £Normally–aEfor“eacš²!h“tag“en˜tered“in“the“do�MÞcumen˜t,‘�ýan“em˜bšMÞedded“annotation“can“b˜e“sp˜eci ed.Ž¡�‘ £An–Kýadditional“windoš²!w“can“b�MÞe“created“to“sho˜w“the“asso�MÞciated“annotation“if“necessary‘ÿe.‘΢ThisŽ¡�‘ £shado•²!w›"do�MÞcumen“t˜approac“h˜is˜widely˜adopted˜b“y˜direct-manipulation˜do�MÞ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“b�MÞoth“paradigms“is“whether“or“not“a“systematic“mec�²!hanismŽ¡�‘ £can–òöb�MÞe“derivš²!ed“for“the“en˜tering“of“index“commands“or“tags.‘Ã�Details“of“a“general“mo�MÞdel“thatŽ¡�‘ £accomplishes–¦fthis“task“are“givš²!en“b�MÞelo˜w.ŽŽŽŒ‹B  …(õ� ý†× ���Ÿü™š�’¾6e¹8Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ� ýÈ× ��‘ £Í2.2Ž‘'È£Generating–€the“Ra� w“IndexŽ©xÌ�‘ £¹Step–r‡I�MÞI‘rSconcerns“attacš²!hing“the“curren˜t“page“n˜um˜b�MÞer“to“eac˜h“index“command“placed“in“theޤfg�‘ £do�MÞcumenš²!t.‘ †ªThe–4command“used“in“the“generated“ra˜w“index“ le“ma˜y“b�MÞ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˜b�MÞer“isŽ¡�‘ £accessible,›7ìb�MÞ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“b�MÞ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“b�MÞer–¦fis“alw•²!a“ys‘¦fcurren“t.ŽŸ$R…��‘ £Í2.3Ž‘'È£Index‘€Pro�`cessingަ�‘ £¹Pro�MÞ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“b�MÞe“realized“is“detailedŽ¡�‘ £in–¦fthe“next“section.Ž¡�‘£ëYPermutation‘× ¹.›Ï‘Index–LMen�²!tries“are“sorted“alphab�MÞetically“(Figure“2.c).˜The“index“pro�MÞcessorŽ¡�‘ £m•²!ust›¿ádi eren“tiate˜among˜di eren“t˜t“yp�MÞ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˜b�MÞ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“b�MÞe“represenš²!ted“b˜y“a“range.‘ÒõOur“systemŽ¡�‘ £alloš²!ws–¦fuser“con˜trol“of“this“practice.Ž¡�‘£ëYSubindexing‘ø¹.›M4Multi-lev�²!el–v.indexing“is“supp�MÞ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º§\ŽŽŽ [(õ� ýÈ× �‘ £op�MÞ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“b�MÞ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“b�MÞeing“placedŽ¡�‘ £in–Û�the“prin�²!ted“index.‘}-In“the“example,›èÇthe“`ë^@¹'“sign“is“used“as“the“actual“ eld“op�MÞ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–¿app�MÞ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–¡³pro�MÞ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˜b�MÞ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˜b�MÞer,Ž¡�‘ £ho•²!w“ev“er,‘ disapp�MÞ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˜b�MÞ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–-�b�MÞe“able“to“handle“a“v‘ÿdDariet˜y“of“formats.‘ sXThere“are“t˜w˜o“reasons“for“considering“thisŽ¡�‘ £indep�MÞ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“pro�MÞ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“opp�MÞ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“lo�MÞokŽ¡�‘ £di erenš²!tly– ûunder“di eren˜t“publishing“requiremen˜ts.‘ œIn“other“w˜ords,‘$ there“m˜ust“b�MÞe“a“w˜a˜y“toŽ¡�‘ £inform–¦fthe“pro�MÞ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˜supp�MÞort˜for˜m“ultiple˜st“yles˜and˜formatting˜indep�MÞendence.Ž¡�‘ £First,‘Îthe–’ñformatting“stš²!yle“macros“used“in“Step“I•MÞI“I‘’´output–’ñm˜ust“b�MÞ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“p�MÞoin˜ts,‘¢Öë^\subsubitem“¹b˜y“30,‘¢Öetc.‘ÜaThere“is“a“v˜ertical“space“b�MÞ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–28indep�MÞendenš²!tly“of“the“en˜tire“do�MÞcumen˜t.‘·#Indexing“is“t˜ypically“the“last“step“of“do�MÞcumen˜tŽ¡�‘ £preparation,‘9 and–è•is“attempted“only“when“the“enš²!tire“do�MÞ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“b�MÞe“kno˜wn,‘/Zwhic˜h“is“made“p�MÞ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˜do�MÞcumen“t.Ž¡�‘£The–êìother“information“needed“to“p�MÞerform“e ectiv�²!e“separate“formatting“is“the“starting“pageŽ¡�‘ £n•²!um“b�MÞer–©¹for“the“index.‘‰¤Some“stš²!yles“require“that“the“index“start“on“an“ev˜en“or“o�MÞdd“page“n˜um˜b�MÞer.ŽŽŽŒ‹ d …(õ� ý†× ���Ÿü™š�’¸¼Ë¹11Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ� þ�Åô�Ÿ–*®���‘.ÿhŸ²Lωffn¹Ò¤fd��‘UÔó1p®0J cmsl10Üsp�Geci 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˜b�MÞer“merg-Ž¡�‘ £ing,–ÃHsubindexing,“st�²!yle›ŠNhandling,“and˜other˜sp�MÞ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“b�MÞ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“pro�MÞ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“p�MÞ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“prop�MÞ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˜¹op�MÞerator.Ž¡�‘ £When–Ïë^range_open“¹immediately“follo�²!ws“ë^encap“¹(i.e.,–>ë^\index{...|(...}¹),“it–Ïtells“the“indexŽ¡�‘ £pro�MÞ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˜b�MÞers“are“abbreviated“as“a“rangeŽ¡�‘ £implicitly‘ÿe.‘£{This–èEëYimplicit‘ò/¹range“formation“can“b�MÞ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“b�MÞe“enforced“bš²!y“using“the“t˜w˜o“range“delimiters“ë^range_open“¹and“ë^range_close¹.Ž¡�‘ £Therefore,‘‰²it–‚…is“p�MÞ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“b�MÞe“quoted“in“this“case“(i.e.‘º ë^\""¹)“is“feasible“but“somewhat“a•²!wkw“ard;‘^Åë^quote‘:ó¹andŽ¡�‘ £ë^escape–¦f¹m�²!ust“b�MÞ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“b�MÞers.ŽŽŽŒ‹ |ì …(õ� ý†× ���Ÿü™š�’¸¼Ë¹13Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ� ÿH,T� ÿ2÷~���‘C ÿOŸ‰ffª2•¤fd��‘UÔÜsp�Geci 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‘UUp�Gostam�¸ã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˜b�Ger“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�¸ãyp�Ge“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“wrapp�Ged“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,˜resp�MÞectiv�²!ely‘ÿe.‘©ÕTheseŽ¡�‘ £parameters–¦fcan“b�MÞ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Ž¡�‘ £b�MÞ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“do�MÞ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“b�MÞer–¦finitializing“command.ޤfg�‘£ëYNew‘ÙGr–ÿp¹oup/L“etter‘-»¹.‘u8The–ØÚstring“b�MÞound“to“ë^group_skip“¹denotes“the“extra“v�²!ertical“spaceŽ¡�‘ £needed–/cwhen“a“group“is“started.‘¶1F‘ÿeor“a“group“b�MÞeginning“with“a“di eren�²!t“letter,‘G0the“parametersŽ¡�‘ £ë^lethead_prefix–iZ¹and“ë^lethead_suffix“¹(b�MÞ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˜b�MÞ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“b�MÞ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˜b�MÞers.Ž¡�‘ £Some–¦fstš²!yles“require“cases“lik˜e“these“to“b�MÞe“di eren˜t“from“those“with“page“n˜um˜b�MÞ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˜b�MÞe˜insertedŽ¡�‘ £b�MÞet•²!w“een–2�a“kš²!ey“and“its“ rst“page“n˜um˜b�MÞer.‘‚ZThe“in˜ter-page“delimiter“is“sp�MÞ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“yp�MÞes˜of˜n“umerals˜are˜supp�MÞorted˜b“y˜most˜systems˜for˜pageޤfg�‘ £n•²!um“b�MÞering.‘‚/These–Ý,are“lo•²!w“ercase–Ý,roman“(ë^r¹),›êÝn�²!umeric“or“arabic“(ë^n¹),˜lo•²!w“ercase–Ý,alphab�MÞetic“(ë^a¹),Ž¡�‘ £uppšMÞercase–ôHroman“(ë^R¹),“and“upp˜ercase“alphab˜etic“(ë^A¹).“The“string“b˜ound“to“ë^page_precedenceŽ¡�‘ £¹(default–¦fë^"rnaRA"¹)“sp�MÞ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“wrapp�MÞed“line“is“inden˜ted“b˜yŽ¡�‘ £ë^indent_space–ÿ¹whose“length“is“ë^indent_length¹.‘çâThis“arti cial“line“wrapping“do�MÞes“not“mak�²!eŽ¡�‘ £anš²!y–ú;di erence“in“formatting,‘O0but“do�MÞ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›¦fwhatso�MÞev“er,˜the˜readabilit“y˜of˜the˜v“erbatim˜output˜index˜is˜imp�MÞ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“b�MÞers.‘”ãIndex˜k“eys˜are˜sorted˜ rst;‘qwithin˜the˜same˜index˜k“ey‘ÿe,‘÷@page˜n“um“b�MÞers˜are˜sortedŽ¡�‘ £n•²!umerically‘ÿe.‘¬Sort› k“eys˜and˜n“umeric˜page˜n“um“b�MÞ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˜b�MÞ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“b�MÞ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“alphab�MÞ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“b�MÞe“found“in“Reference“[18].Ž¡�‘£There–Oare“three“basic“tš²!yp�MÞes“of“n˜umerals“for“page“n˜um˜b�MÞers:‘²+ëYr–ÿp¹oman‘× ¹,›`|ëYalphab“etic‘žu¹,˜and‘OëYar“abic‘žu¹.Ž¡�‘ £The–Hvsorting“of“arbitrary“comš²!binations“of“these“three“t˜yp�MÞes“of“n˜umerals“(e.g.,–pù112,“iv,“I�MÞI-12,Ž¡�‘ £A.1.3,‘“getc.)‘Õómš²!ust–ލb�MÞe“based“on“their“n˜umeric“v‘ÿdDalues“and“relativ˜e“precedence.‘ÕóThe“attribute“ofŽ¡�‘ £ë^page_precedence–”G¹in“T‘ÿeable“2,›—çfor“instance,˜sp�MÞ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“b�MÞe“created.‘,FFirst“the“attributeŽ©fg�‘ £b�MÞ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˜b�MÞ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-sp�MÞeci c–ïcommands“or“delimiters“(i.e.› yë^item_ëZi¹'s,–lÑë^delim_ëZi¹'s,“etc.)˜is–ïdescrib�MÞed“inަ�‘ £Reference‘¦f[18].ŽŸ+%Þ��‘ £ëX4Ž‘!UnPlacing–ffIndex“CommandsŽŸ>X�‘ £¹This–¦Õsection“discusses“a“simple“framewš²!ork“for“placing“index“commands“in“a“do�MÞcumen˜t.‘ß*Itަ�‘ £assumes–×õan“in•²!teractiv“e–×õeditor“is“aš²!v‘ÿdDailable“with“ëYstring‘‚se–ÿp¹ar“ch‘× ¹,‘äYwhic˜h–×õp�MÞositions“the“cursor“to“aަ�‘ £sp�MÞeci ed–e×pattern,›•³and“ëYquery-insert‘ ê¹,˜whicš²!h“displa˜ys“a“men˜u“of“options“and,‘•³up�MÞon“the“user'sަ�‘ £selection,›ËÝinserts–•:a“sp�MÞ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“b�MÞe“indexed“b˜y“the“k˜ey“ë^UCB¹,Ž©”s�‘7óë^University–¿ªof“California,“BerkeleyŽ¡�‘7óBerkeleyŽ¡�‘7óberkeleyŽ¡�‘7óUCBަ�‘£¹As–Ó¸a“sp�MÞ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.‘d�Some“editorsŽ¡�‘ £alloš²!w–¨±the“use“of“sp�MÞecial“c˜haracters“to“delimit“w˜ord“b�MÞoundaries.‘‰LThese“c˜haracters“can“b�MÞ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“b�MÞ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˜yp�MÞ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“do�MÞcumen˜t.‘›‰In“ë`Emacs�s‚¹,Ž¡�‘ £a–{region“is“evš²!erything“b�MÞet˜w˜een“a“mark˜er“and“the“curren˜t“cursor“p�MÞ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“p�MÞoin�²!t.Ž¡�‘£In–¼õour“system,‘™there“is“also“a“sp�MÞecial“facilitš²!y“to“index“ev˜ery“author“name“that“app�MÞears“inŽ¡�‘ £the–µ÷bibliographš²!y“or“references“section“of“a“do�MÞ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“b�MÞ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“do�MÞ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“b�MÞefore“insertion.Ž©$R…��‘ £Í4.2Ž‘'È£Key-P� attern‘€ListŽŸxÌ�‘ £¹A›[collection–[Mof“these“ë^<ëYkey‘ø¹,‘ˆ†ëYp‘ÿp¹attern‘× ë^>“¹pairs“can“b�MÞ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“do�MÞcumen˜t“or“parts“of“it.‘f‚This“list“can“b�MÞ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“b�MÞe“ableŽ¡�‘ £to–Énrecognize“and“skip“instances“already“indexed“so“that“unnecessary“rep�MÞ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“pro�MÞ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“b�MÞ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“asso�MÞciated“with“theŽ©fg�‘$h§curren•²!t‘¦fdo�MÞcumen“t.Ž¡����‘usë[ŽŽŽ‘$h§ëYIndex‘hYL‘ÿp¹evel‘!ª¹.›®�Prompt–zthe“user“for“an“index“pre x.˜The“ë^level“¹op�MÞ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“corresp�MÞ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“b�MÞer–�€encapsulator.˜The“ë^encapŽ¡�‘$h§¹op�MÞerator–ìµ(`ë^|¹'),›þIif“not“giv�²!en,˜should“b�MÞe“attacš²!hed“in“fron˜t“of“the“sp�MÞeci ed“string.‘°ËEncap-Ž¡�‘$h§sulators–ÀúcorrespšMÞonding“to“p˜opular“fonš²!ts“suc˜h“as“b�MÞold,–žitalic,“and‘Àúslan˜ted,“or–Àúto“crossŽ¡�‘$h§references–¦flik�²!e“ëYse›ÿp¹e‘y¹and“ëYse˜e‘êêalso‘WX¹can“b�MÞ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“mo�MÞ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–…Ôsp�MÞ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–.ˆmo�MÞde,‘F�there“is“a“collection“of“enš²!tries“that“ma˜y“b�MÞe“represen˜ted“as“a“long“list“for“an“en˜tireŽ¡�‘ £do�MÞcumenš²!t,‘™Nor––as“a“short“list“for“a“section.‘ØhEac˜h“k˜ey-pattern“pair“in“the“list“is“pro�MÞcessed“as“inŽ¡�‘ £the–¦fformer“case.‘ÝÝProš²!visions“are“also“a˜v‘ÿdDailable“to“help“construct“the“list.Ž¡�‘£With– ùsucš²!h“p�MÞo˜w˜erful“mec˜hanisms“a˜v‘ÿdDailable,‘¢there“is“a“tendency“to“\o˜v˜er“index"“b�MÞecause“itŽ¡�‘ £is–=¼so“easy“to“b�MÞe“comprehensivš²!e.‘£àIn“some“cases,‘c‘\less“ma˜y“b�MÞe“more".‘£àTherefore,‘c‘one“shouldŽ¡�‘ £b�MÞ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˜b�MÞ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“supp�MÞorts“an“application“calledޤfg�‘ £ë`IndexT‘ÿeo�MÞ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‘ÿeo�MÞolŽ¡�‘ £¹takš²!es–ça“selection“and“creates“an“index“en˜try“attac˜hed“to“the“do�MÞ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‘ÿeo�MÞol�nR¹,Ž¡�‘ £whicš²!h–¦falso“p�MÞermits“a“wide“range“of“searc˜h“and“replace“op�MÞerations.Ž¡�‘£In–#fë`F‘ÿerameMakš²!er‘ì�¹1.0“[15],‘‚¥index“tags“can“b�MÞe“placed“and“edited“using“a“com˜bination“ofŽ¡�‘ £the–ü¨ë`Markš²!ers‘p*¹and“the“ë`Searc˜h“¹to�MÞols.‘à£ë`Mark˜ers‘p*¹allo˜ws“one“to“sp�MÞecify“in˜visible“tags“suc˜h“as“sub-Ž¡�‘ £jects,–pìcommenš²!ts,“and–c�of“course,‘pìindex“en˜tries.‘Ç•F‘ÿeor“eac˜h“mark˜er,‘pìan“asso�MÞ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“b�MÞe“usedŽ¡�‘ £to–Jglo�MÞ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˜o�MÞccurrence˜of˜index˜mark“ers˜in˜the˜do�MÞcumen“t.‘,¯When-Ž¡�‘ £evš²!er–€„a“mark˜er“is“found,‘· the“corresp�MÞ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“prop�MÞ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“op�MÞerator.Ž¡�‘ £The–¾output“appšMÞearance“can“b˜e“re ned“bš²!y“using“v‘ÿdDarian˜ts“of“the“index“co�MÞ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“app�MÞearsޤfg�‘ £at–¾¶the“end“of“the“do�MÞcumenš²!t.‘&ÎBefore“that“tak˜es“place,‘ÄÊthe“system“m˜ust“b�MÞ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“b�MÞe“\hidden"“when“index“en˜tries“are“b�MÞ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“co�MÞdes.‘½The“ë` nd‘²3¹and“ë`c˜hange‘àè¹commands“in“the“ë`Searc˜h“Men˜u“¹do“not“supp�MÞortŽ¡�‘ £regular–•´expressions.‘«ÆThere“are“no“query-insert“mo�MÞdes“in“the“searcš²!h“mec˜hanism.‘«ÆAlthoughŽ¡�‘ £abbreviations–xÄcan“b�MÞ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“do�MÞcumen˜ts“prepared“onŽ¡�‘ £anš²!y–ËÞof“sev˜eral“w˜ord“pro�MÞcessing“programs“on“the“IBM‘ËÕPC,“index“en˜tries“can“b�MÞe“placed“in“theŽ¡�‘ £do�MÞcumen•²!t›`Pb“y˜in“v“oking˜a˜dialogue˜b�MÞo“x˜at˜the˜desired˜p�MÞosition.‘Æ€An˜alternativ“e˜is˜to˜use˜a˜w“ordŽ¡�‘ £pro�MÞ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“corresp�MÞonding“sort“kš²!ey‘ÿe,‘nÜand“the“semicolon“is“the“index“lev˜el“op�MÞerator.‘ƹItŽ¡�‘ £supp�MÞ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“b�MÞe“displa˜y˜ed“b˜y“its“ëYCurr–ÿp¹ent›~¢Sele“ction˜Indic“ator‘^n¹when–0³the“cursor“is“placedŽ¡�‘ £at–2�a“lo�MÞ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“prop�MÞ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“p�MÞossible.ŽŸ#õ��‘ £Í5.2Ž‘'È£Dynamic–€Indexing“and“Hyp�`ertextŽŸxÌ�‘ £¹Our–�Sprop�MÞosed“implemenš²!tation“of“an“indexing“facilit˜y“under“direct“manipulation“and“the“fourŽ¡�‘ £real–оsystems“discussed“previously“all“op�MÞ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“b�MÞe“observ˜ed“in“the“follo˜wing“scenario.‘ ILThe“author“sp�MÞeci es“in-Ž¡�‘ £put/output–m]stš²!yles“b˜y“selecting“options“a˜v‘ÿdDailable“in“system“supplied“prop�MÞert˜y“sheets.‘ÊÚF‘ÿeor“eac˜hŽ¡�‘ £kš²!ey–¸selected“in“the“do�MÞcumen˜t,‘¼mits“corresp�MÞ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˜b�MÞe˜an˜arra“y˜that˜is˜suitableŽ¡�‘ £for–vfast“sorting“algorithms.›®�Instead,‘4Úa“balanced“tree“ma�²!y“b�MÞ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ƒb�MÞet•²!w“een˜a˜page˜n“um“b�MÞer˜in˜the˜index˜en“try˜and˜its˜corresp�MÞ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˜b�MÞ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›ù*p�MÞo•²!w“er˜of˜\dynamics"˜that˜an˜electronic˜do�MÞcumen“t˜en“vironmen“t˜is˜able˜to˜o er,‘Ðwhic“h˜do�MÞ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“co�MÞdes“in“ë`MicroSoft“W‘ÿeord‘Lx¹is“a˜wkw˜ard“b�MÞ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š²!eyb�MÞ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.‘ÄxLo�MÞ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–�b�MÞe“necessary“to“en˜ter“the“text“for“the“index“k˜ey‘ÿe.‘¬šThis“situation“happ�MÞ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‘ÿeord�nR¹.Ž¡�‘£ë`V‘ÿeen�²!tura–Ï$Publisher‘˜M¹došMÞes“not“supp˜ort“anš²!y“searc˜hing“mec˜hanism;‘c‚it“assumes“searc˜hing“isŽ¡�‘ £p�MÞerformed–iin“a“fronš²!t-end“w˜ord“pro�MÞ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“supp�MÞ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“o�MÞcation˜of˜the˜k“eyb�MÞoard˜macro).‘^HThe˜problem˜is˜that˜a˜new˜k“eyb�MÞoard˜macro˜hasŽ¡�‘ £to–©b�MÞ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“pro�MÞ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“do�MÞ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“b�MÞe“inserted“at“a“v‘ÿdDariet˜y“of“placesŽ¡�‘ £describ�MÞed–<#bš²!y“a“single“regular“expression.‘ºqP˜atterns“already“indexed“are“skipp�MÞ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“do�MÞcumen˜t.‘5 This“can“b�MÞ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“rep�MÞetitions“as“in“ë`F›ÿerameMak�²!er‘É)¹,‘ÏŒë`MicroSoft“W˜ord�nR¹,ޤ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Ž¡�‘ £mo�MÞdi cations,‘W»the–Dsame“facilitš²!y“should“w˜ork“on“placing“index“commands“for“other“formattingŽ¡�‘ £languages–Á4likš²!e“ë`tro ‘߯¹and“ë`Scrib�MÞ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˜ab�MÞ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–@pro�MÞ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(b�MÞ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“exp�MÞ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“no�MÞ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“p�MÞossible,‘Åýit“w˜ould“b�MÞe“dicult,Ž¡�‘ £if–óSnot“imp�MÞ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“imp�MÞossible,‘ï|and“the“st˜yle“handling“mec˜hanismŽ¡�‘ £with– da“comprehensivš²!e“error“pro�MÞcessing“facilit˜y“is“dicult“to“realize.‘ØOriginally“dev˜elop�MÞed“inŽ¡�‘ £UNIX–À¢C“with–À©p�MÞ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“p�MÞortabilit˜y“w˜ould“ha˜v˜e“b�MÞ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“to�MÞ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“opp�MÞ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“pip�MÞ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–›Rp�MÞ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“to�MÞolkit“and“assem˜ble“the“ nal“pro�MÞ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“mo�MÞdifyŽ¡�‘ £their–¦fë^awk“¹co�MÞ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“pro�MÞcessing.‘Ú[P˜arameters“are“deriv˜ed“to“form“a“table-Ž¡�‘ £driv•²!en›JSst“yle˜handling˜facilit“y–ÿe.‘¿,F“ormatter˜and˜format˜indep�MÞ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“pro�MÞcessing“details.‘WêIf“the“default“is“inappropriate,Ž¡�‘ £the–¦fonly“adaptation“required“is“a“table“sp�MÞ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.‘Ðýë`Scrib�MÞe‘�¹,›v^for“example,˜has“an“indexing“subsystem“that“supp�MÞ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“app�MÞearance“commands“as“output“st˜yle,‘ðôits“indexing“capabilit˜y“can“b�MÞ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“b�MÞ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,˜p�MÞ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“to�MÞo“spans“man˜y“systems,‘®.althoughŽ¡�‘ £it–¦fis“UNIX-sp�MÞ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“b�MÞe“handled“b�²!y“the“program.‘)½TheŽ¡�‘ £ë^make.index–[¹suite,›7*on“the“other“hand,˜handles“the“standard“cases“and“all“customizations“m�²!ustŽ¡�‘ £b�MÞ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“happ�MÞ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“sp�MÞ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“b�MÞ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“pro�MÞ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“do�MÞ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“pap�MÞer.ŽŽŽŒ‹&ª …(õ� ý†× �Ÿtç��Ÿü™š�’¸¼Ë¹27Ž‘ £Ÿff‰ffº§\ŽŽŽ [(õ� ýÈ× �‘ £ëXReferencesŽŸç���‘¤²[1]ŽŽ‘!�œ×The–° Seyb›ÿ}'old“R˜ep˜ort“on“Publishing“Systems².‘RSeyb�Gold–Š/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“do�Gcumen˜t“pro�Gcessors“in˜to“anŽ¡�‘yin•¸ãteractiv“e›®en“vironmen“t.‘¯­T‘ÿ*ªec“hnical˜Rep�Gort˜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.“Drap�Ger,–Tœeditors,“×User-Center–ÿ}'e“d–“System“Design²,‘Tœpages–Tn87{124“(ChapterŽ¡�‘y5),–UUHillsdale,“New“Jersey‘ÿ*ª,“1986.“La�¸ãwrence“Erlbaum“Asso�Gciates,“Inc.ަ���‘¤[9]ŽŽ‘yBen–lâShneiderman.›ôDirect“manipulation:‘ý�A‘l§step“b�Gey�¸ãond“programming“languages.˜×IEEE‘½×Computer²,Ž¡�‘y16(8):57{69,–UUAugust“1983.ަ���‘ £[10]ŽŽ‘yLeslie‘Ì×Lamp�Gort.‘Ó×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,“Octob�Ger‘/61980.Ž¡�‘yAv‘ÿqÇailable–UUas“tec�¸ãhnical“rep�Gort“CMU-CS-81-100.ަ���‘ £[13]ŽŽ‘yJoseph–±�F.“Ossanna.›cöNro /tro “user's“man�¸ãual.˜Computer“Science“T›ÿ*ªec�¸ãhnical“Rep�Gort“No.“54,‘ÒOA˜T&TŽ¡�‘yBell–ªkLab�Goratories,›ÌšMurra�¸ãy“Hill,˜New“Jersey‘ÿ*ª,˜Octob�Ger“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˜Corp�Goration,–Ú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–UUCorp�Goration,“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ó)ßê