||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||l||||||||||||||
`
`U5006163811A
`
`United States Patent
`Porter
`
`[19]
`
`[11] Patent Number:
`
`6,163,811
`
`[451 Date of Patent:
`
`Dec. 19, 2000
`
`[54] TDKEN BASED SOURCE FILE
`COMPRESSION1l)lCCOMPRESSl0N AND ITS
`APPLICATION
`
`[75]
`
`Inventor: Swain W. Porter, NE Kirkland, Wash.
`
`[73] Assignee: Wildseed, Limited, Kirkland, Wash.
`
`[21] Appl. No.: 091177,!1141
`
`[22
`
`Filed:
`
`Oct. 21, 1998
`
`[51]
`
`Int. Cl.7 ............................. GOGI“ 15116; GUGF 71011;
`(.1061: 13138
`............................. 7091247; 7071101; 710168
`[52] U.S. C1.
`[58]
`Field of Search .................................... 7091246—247;
`710168; 7071101, 540, 203, 511
`
`[515]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,386,416
`............................ 7101158
`511983 (iillner ct al.
`4,558,413
`..
`111112113
`1211986 Schmidt et al.
`
`4,912,637
`7071203
`311990 Shecdy cl. al.
`5,357,631
`1011994 llowcll ct at.
`.. 707121.13
`7091221
`
`5,495,610
`21111911 Siting etal.
`..
`7071532
`5,530,645
`...........
`611996 131111
`
`7071201
`5,5149% 1111991: Morris
`
`.. 70701203
`5,715,454
`211908 Smith
`
`611998 Sonderegger
`.
`...... 707110
`5,761,499
`
`911998 Morris
`5,813,017
`111112114
`
`5,832,520
`1111998 Miller
`7071203
`
`................
`5,845,077 1211998 Fawcett
`7071221
`311999 Huttenlocher et al.
`5,884,014
`35811.15
`
`511999 Carrier. 111 et a1.
`..
`.. 7071203
`5.903.897
`
`
`5,905,896
`511999 Delannoy .........
`39517l2
`................................ 701419
`5,991,713
`111l999 [lager et a1.
`5,999,949 1211999 Crandail
`.................................. 7071532
`6.011.905
`112000 iltittcnlochcr et al.
`35811.15
`0.0121163
`1121701} Bodnar .................
`71171101
`
`6,018,747
`112000 Burns cl :1].
`............................ 7071203
`
`OTHER PUBLICATIONS
`
`(Tormen ct '41., Introduction to Algorithms, The MIT Press,
`pp. 337-343, 1990.
`Pocket Soft, Inc, White Paper re .R’l‘l’atch Professional
`Binary Update System, http:11wnv.pocketsot't.com, pp.
`1—12, Nov. 1996.
`
`"Comparing and Merging Files." from the World Wlde Web.
`pp. 1—44, Jun. 1996.
`Zeller et at, Unified versioning through feature logic, ACM
`Trans. SW Eng. & Methd. vol. 6, No. 4, pp 398—441, Oct.
`1997.
`l-Ioel et a}, “Versioncd software architecture", ISA ACM, pp
`73—76, Mar. 1998.
`Cohen et a], “Version management
`201—215, 1988.
`Black, A, at 111., "A Compact Representation for File Ver-
`sions: a Preliminary Report,” l’roc. 5th Int’l. Conf. 0n Data
`Engineering, 1989., IEEE, pp. 321-629, Feb. 1989.
`Bell, '12, et at, “Modeling for Text Compression,“ ACM
`Computer Surveys, vol. 21, No. 4, pp. 557—591, Feb. 1989.
`
`in Gypsy”, ACM pp
`
`Primary Exnminer—Zarni Maung
`Assistant Exmttincr—Andrew Caldwell
`
`Attorney, Agent, 01‘ Fit‘m—Colu mhia IP law Group, [.1 .C
`
`[57]
`
`ABSTRACT
`
`Disclosed is a software distribution system using both
`dill’erencing a nd compression techniques to distribute source
`files over a network while minimizing the network band-
`width needed to maintain and update a set ot‘source files. In
`an embodiment, a sending computer maintains sets of source
`files in base and delta form. The delta source files contain
`difference information allowing a new version of a source
`file to be constructed, or reconstituted, from a previously
`reconstituted version. Prior to transmitting a source file in
`either base or delta form to a
`receiving computer,
`the
`sending computer compresses the source file using a
`dictionary~bascd compression scheme. The resulting token-
`ized source file is. stored and then transmitted to the receiv-
`ing computer along with versioning control
`information.
`The receiving computer stores the tokcnized source file
`along with the versioning control information. Upon request,
`the receiving computer decompresses the tokenized source
`file(s) and then reconstitutes an updated version of the
`source using the versioning control information and received
`decompressed source lile(s). In another embodiment,
`the
`sending computer provides provides source updates for
`multiple software vendors.
`In this case,
`the versionng
`control information also identifies the baseklelta source files
`using a universally unique identifier (UUID) that distin—
`guishes between the base1delta source files of the dilIerent
`vendors.
`
`22 Claims, 8 Drawing Sheets
`
`
`
`HECEIVIIG SYSIEM
`
`
`
`
`
`
`
`
`
`
`
`RPX-1015
`RPX-1015
`Page 1 of 15
`Page 1 of 15
`
`

`

`US. Patent
`
`a9.,1
`
`m
`
`ma:
`
`%$55azamowm
`
`mEnzmmDII852%?Jo:
`
`mmuzmxohImmE
`
`momnow
`
`09N2Edam:
`
`
`
`Em.._.m>w0252mm
`
`m8%ng
`
`
`
`o52%:$28?aa:
`
`mQKDOw
`
`mij
`
`mmflzmxohmm
`
`6,163,811
`
`ammohmmm
`
`_wwjm
`momaow
`
`
`
`,3GE
`
`RPX-1015
`RPX-1015
`Page 2 of 15
`Page 2 of 15
`
`
`
`
`
`

`

`US. Patent
`
`Dec. 19, 2000
`
`Sheet 2 0f 8
`
`6,163,811
`
`mm..__u_
`
`momzow
`
`812.0%I
`
`\Edmm:
`
`
`
`Ewhw>woz_>_momw_
`
`mmzwomm
`
`mum—zmxohmo
`
`.om_.
`
`>m<mm3 Emhw>m
`
`0252mm
`
`3.0E
`
`-mgmgII._Om_2>m-m5:
`
`momDOm
`
`omNHzwxOH
`
`RPX-1015
`RPX-1015
`Page 3 of 15
`Page 3 of 15
`
`
`
`
`
`
`

`

`US. Patent
`
`Dec. 19, 2000
`
`Sheet 3 0f 8
`
`6,163,811
`
`
`
` omflzmxoh_mmij.a:6E5
`
`womaDw
`
`Kwamomm
`
`mm_N_zm¥O._..mn_
`
`23829
`
`$41
`
`momDOm
`
`eggI339me
`
`2.0E
`
`=2;
`
`Oz_zo_wmm>
`
`."Omhzoo
`
`Cuz—
`
`$3me
`
`
`
`
`oz_zo_mmw>-wmij.
`.-.6925
`
`.._Om._.zOU
`
`
`
`Ewhw>mGZSEme
`
`=2:
`
`.69
`
`.2:$5meOH
`
`25mg-que8.:I8x38
`8.55on
`
`
`
`Em._.w>w@zfizmm
`
`>m<mmj
`
`RPX-1015
`RPX-1015
`Page 4 of 15
`Page 4 of 15
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Dec. 19, 2000
`
`Sheet 4 0f 8
`
`6,163,811
`
`
`
`mozfidmoz_ozw”my—2.0m
`o_.—.mEI._._m<
`
`
`
`
`mozsdm.oz_2mn_o._Oms_>mOh.Mmkzamozémmo
`a.532..Om§>wO._.magnumbamz
`
`
`
`nx.5440921.69.mm...2_0n_zo_mm<
`
`
`
`
`m._m<._.._Om2>w
`
`.6923
`
`40m§>w
`
`mum—2:2
`
`
`
`mohémao«9.5130
`
`m0xmmznz
`
`
`
`moEmmaomohémmo
`
`
`
`nommmzaz._(zo_._.5mm
`
`
`
`mzozzmmaiEm:
`
`
`
`szzzmmEFIOE
`
`525%62.230
`
`_mozfi<m-OZEZm
`
`pm.9“.
`
`mm.9“.
`
`RPX-1015
`RPX-1015
`Page 5 of 15
`Page 5 of 15
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Dec. 19, 2000
`
`Sheet 5 0f 8
`
`6,163,811
`
`+
`
`TOKENIZED SOURCE
`FILES
`
`302
`
`304
`
`308
`
`310
`
`CREATE ENTRIES FOR
`SYMBOL TABLE
`
`'00
`
`REQUEST
`
`?
`
`
`
`SEND TOKENIZED
`SOURCE FILE
`
`SEND SYMBOL TABLE
`
`OR UPDATE ENTRIES FOR
`
`SYMBOL TABLE
`
`FIG. 33
`
`RPX-1015
`RPX-1015
`Page 6 of 15
`Page 6 of 15
`
`

`

`US. Patent
`
`Dec. 19, 2000
`
`Sheet 6 on;
`
`6,163,811
`
`NO
`
`322
`
`REC'D
`SOURCE FILE
`OR
`
`DE-TOK REQ
`
`SOURCE
`FILE
`
`
`
`STORE TOKENIZED SOURCE
`FILES
`
`324
`
`DE-TOK
`
`REQUEST
`
`RESTORE REQUESTED
`
`
`
`SOURCE FILE
`
`STOREIUPDATE SYMBOL
`TABLE
`
`326
`
`323
`
`330
`
`”0
`
`FIG 3b
`
`RPX-1015
`RPX-1015
`Page 7 of 15
`Page 7 of 15
`
`

`

`US. Patent
`
`Dec. 19, 2000
`
`Sheet 7 0f 8
`
`6,163,811
`
`
`
`9e.05.052392
`
`
`
`4825$9345::89¢
`
`$.5593%:(2%_«5%
`
`
`Eszz.omuExE
`
`4.5:
`
`8v
`
`mbmmma
`
`
`
`
`
`.ohw9min?(>5.mm04m42...:
`
`
`
`25.96hzmjo
`
`39¢42%
`
`Ed":«2%
`
`ammzmxoc
`
`23323
`
`>mO.:wOn_mm
`
`
`
`
`
`0%:AOmHzOo(Smommim
`
`III
`>motm0¢mm
`
`
`
`$05..35
`
`33%;.$2..
`
`um
`
`2332a
`
`E;49:28
`
`2.".
`
`w.OE
`
`RPX-1015
`RPX-1015
`Page 8 of 15
`Page 8 of 15
`
`339me
`
`$5momm§
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Dec. 19, 2000
`
`Sheet 8 0f 8
`
`6,163,811
`
`502
`/_/
`
`504
`
`@
`
`
`
`MEMORY
`
`
`
`
`
`USER INPUT
`NON-VOLATILE
`
`& OTHER IIO
`
`STORAGE
`DEVICES
`
`
`
`510
`+
`520
`508
`
`522
`
`FIG. 5
`
`RPX-1015
`RPX-1 01 5
`Page 9 of 15
`Page 9 of 15
`
`

`

`6,163,811
`
`1
`’I‘OKEN BASED SOURCE FILE
`COM PRESSIONJ’DECOM PRESSION AND ITS
`APPLICATION
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`2
`the tokenized form, at least language elements present in the
`source file in its original form are substituted with corre-
`sponding tokens. In one embodiment, operands present in
`the source file in the original form are also substituted with
`corresponding tokens, and entries mapping the operand
`substituting tokens to the operands are maintained in a
`symbol table. In this case, the symbol table is also provided
`to the other computer system.
`In one embodiment, the source file is also in either a base
`or delta form. A new entry is created for the symbol table
`whenever a new operand is encountered and substituted. In
`this case, subsequent to the initial provision of the symbol
`table, new entries associated with a baset’delta sou ree file are
`also provided to the other computer system to update the
`previously provided symbol table.
`In one embodiment, the baseldelta source files also have
`associated versioning control information. In this case, the
`versioning control information is also provided to the other
`computer system.
`In one embodiment, the computer system is a web server,
`and the source file is a web page. The other computer system
`is a client computer system requesting the web page from the
`web server. The requested web page is provided by the web
`server to the client computer system in the tokenized form,
`and the client computer system is equipped with a browser
`having been enhanced with the ability to restore the pro-
`vided web page to its original form. In one embodiment, the
`web page is also in a basefdelta form having associated
`versioning control
`information, and the client computer
`system browser is enhanced with the ability to reconstitute
`the requested web page using the associated versioning
`control information.
`
`BRIEF DESCRIP’I'ION OF DRAWINGS
`
`The present invention will be described by way of exem~
`plary embodiments, but not
`limitations,
`illustrated in the
`accompanying drawings in which like references denote
`similar elements, and in which:
`I-‘IGS.
`lrr—lc illustrate three exemplary embodiments of
`the token based compressed source file transmission of the
`present invention;
`FIGS. 2(i—2b illustrate one exemplary embodiment each
`for a collection of tokens and an associated symbol table
`suitable for use to practice the present invention;
`FIGS. Sir—31b illustrate one exemplary embodiment each
`of the sender and the receiver’s method steps in accordance
`to the present invention;
`FIG, 4 illustrates one exemplary application of the present
`invention to web servers and client systems accessing web
`servers; and
`FIG. 5 illustrates one embodiment of an exemplary com-
`puter system suitable for use as either a sender or a receiver
`system to practice the present invention.
`DETAILED DESCRIPTION 01-" THE
`INVENTION
`
`In the following description, various aspects of the
`present
`invention will be described. However,
`it will be
`apparent to those skilled in the art that the present invention
`may be practiced with only some or all aspects of the present
`invention. For purposes of explanation, specific numbers,
`materials and configurations are set forth in order to provide
`a thorough understanding of the present invention. However,
`it will also be apparent
`to one skilled in the art
`that the
`present
`invention may be practiced without
`the specific
`
`RPX-1015
`RPX-1015
`Page 10 of 15
`Page 10 of 15
`
`It]
`
`IS
`
`an
`
`invention relates to the field of computer
`The present
`systems. More specifically, the present invention relates to
`methods and apparatuses associated with the distribution or
`provision of source files to other computer systems.
`2. Background Information
`With the recent advances in microprocessor, telecommu-
`nication and networking technology, increasing number of
`computer systems are being networked together. In turn,
`increasing number of situations arise where source files have
`to be transferred from one computer system to another
`computer system. The term "source files” as used herein
`includes but not
`limited to compilable or interpretable
`source files written in machine programming languages such
`as C, C++, HTML, XML, JAVA”, JAVAScript, and so
`forth. For example, everyday, millions of users are con-
`nected to the Internet downloading web pages from a
`multitude of web sites. Similarly, millions of users are doing
`the same within thousands of “corporate" intranets. In a new —
`user centric software distribution paradigm, disclosed in
`co-pending U.S. patent application Ser. No. OWN—1,443,
`filed contemporaneously, and entitled “User centric source
`control", it is envisioned that software products are distrib-
`uted to client systems or their proxies in source form. All
`these activities further exacerbate the well known bandwidth
`problem confronting private as well as public networks.
`(Note that
`the “user centric” approach to source control
`contributes to the bandwidth problem only in the sense that
`the approach is expected to increase the demand for source
`file transmission. For a given set of source files, its delta
`feature actually reduces bandwidth demand for maintaining
`and updating the set of source files.)
`Various compressiont‘decompression techniques are
`known in the art
`in the data or link layer to reduce the
`amount of data that needs to be transmitted from a sender to
`
`35
`
`40
`
`a receiver. For examples, a dictionary based approach
`replacing previously transmitted character string (cg. "this
`string has been sent before") with a code is often employed
`in modem communication;
`the run length encoding
`approach (cg. encoding a series of 10 0-bit as [0, 10]) is
`often employed in video signal compression, and a code
`based approach supplying the identity of a linear excitation
`code vector
`is often employed in audio compression.
`However, notwithstanding these multitude of data or link
`layer compressiont’deoompression techniques available, as
`evident by the amount of research and development going
`into Quality of Service, Bandwidth Reservation, Virtual
`Private Network, and so forth, the problem of bandwidth in
`private as well as public networks is expected to remain with
`the computer and communication industry for years to
`come.
`
`Thus, further improvement or contribution to alleviating
`the bandwidth problem,
`in particular,
`improvement
`that
`further advances the connectivity and exchange of informa~
`tion between computer systems, is desired.
`
`SUMMARY OF THE INVENTION
`
`In accordance with the present invention, a source file is
`provided from one computer system to another in a token-
`ized form to reduce transmission bandwidth requirement. In
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`6,163,811
`
`3
`details. In other instances, well known features are omitted
`or simplified in order not to obscure the present invention.
`Parts of the description will be presented in terms of
`operations performed by a computer system, using terms
`such as tables, files. data and the like, consistent with the
`manner commonly employed by those skilled in the art to
`convey the substance of their work to others skilled in the
`art. As well understood by those skilled in the art, these
`quantities take the form of electrical, magnetic, or optical
`signals capable of being stored, transferred, combined, and
`otherwise manipulated through mechanical and electrical
`components of a digital system; and the term digital system
`include general purpose as well as special purpose data
`processing machines, systems, and the like,
`that are
`standalone. adjunct or embedded.
`Various operations will be described as multiple discrete
`steps performed in turn in a manner that is most helpful in
`understanding the present invention, however, the order of
`description should not be construed as to imply that these
`operations are necessarily order dependent, in particular, the
`order the steps are presented.
`Referring now to FIGS. ln—le, wherein three exemplary
`embodiments of the present
`invention are shown. These
`three exemplary embodiments will be described in turn,
`referencing also FIGS. Zia-21). First, referring to FIG. 1a,
`exemplary sending and receiving systems 100 and 140 are
`illustrated as being coupled to one another via communica-
`tion medium 180. More importantly, in accordance with the
`present invention, sending system 100 advantageously pro-
`vides source files to receiving system 140 in a tokenized
`form, generated from an original form,
`thereby reducing
`transmission bandwidth requirement on communication
`medium 180. For the illustrated embodiment, sending sys-
`tem 100 includes library 102, tokenizcr 104 and sender 106,
`whereas receiving system 140 includes library 142,
`de-tokenizer 144 and receiver 146.
`
`Over in sending system 100, library 102 is used to store
`source files 110 in the original form and source files 112 in
`the tokenized fon'n.
`'I'okenizer 104 is used to transform
`source liles 110 in the original form to source file 112 in the
`tokenized form. For the illustrated embodiment, tokenizer
`104 effectuates the transformation by substituting language
`elements, such as arithmetic operators, relational operators
`and so forth, with tokens. The term “token" as used herein
`is intended to have similar meaning as the term is commonly
`used by those skilled in the art of compiler technology,
`which typically includes a
`token class designation, cg.
`arithmetic operator, and a class value, which may be a value
`designating a particular operator of the class, e.g. the value
`designating the "+" operator (see FIG. 2a, wherein an
`exemplary collection of
`language element substituting
`tokens is illustrated). Sender 106 is used to send source files
`112 in the tokenized form to receiving system 140, as
`described earlier. Sender 106 may send source files 112 in
`the tokenized form to receiving system 140 at
`its own
`initiative, at the request of a local requestor (not shown), e.g.
`an application, or a remote requestor (also not shown), e.g.
`an application on receiving system 140.
`In one embodiment, the programming language a particu—
`lar source file 110t112 is written in is inferred from the file
`name of the source file, cg. the file name including a file
`extension, such as “htm” for the hypertext markup language
`(II'I'ML).
`In another embodiment,
`the programming lan-
`guage a particular source file 110112 is written in is
`determinable from the properties associated with the par-
`ticular source file 110i‘112, which is integrally provided
`
`ll]
`
`15
`
`an
`
`35
`
`4t]
`
`45
`
`50
`
`55
`
`60
`
`55
`
`4
`along with a particular source lile 112, when the particular
`source file 112 in tokenized form is provided to receiving
`system 140. In yet another embodiment, sender 106 informs
`receiver 146,
`the programming language the particular
`source file 110112 is written in.
`Still referring to FIG. In, over in receiving system 140.
`receiver 146 is used to receive source files 112 in the
`tokenizcd form from sending system 100,
`including as
`described earlier, its programming language, either inte-
`grally or particularly. Library 142 is used to store received
`source tiles 112 in the tokeniiaed form, as well as restored
`source files 152 in the original form. De—tokcnizcr 144 is
`used to restore source files 112 in the tokenincd form to
`source file 152 in the original form. For the illustrated
`embodiment. de-tokenizer 144 elfcctuates the transforma—
`tion by restoring language element substituting tokens with
`their corresponding language elements. De—tokenizer 144- is
`equipped with the language element substituting token to
`language element mappings for a number of programming
`languages.
`In one embodiment, source files 1101112,?115
`may be written in include but not limited to C, C++, HTML,
`XML, Java“, and JavaScripl, and rte-tokenirer 144 is
`accordingly equipped to handle the supported programming
`languages.
`Communication medium 180 is intended to represent a
`broad range of communication medium known in the art,
`from local area networks {ethernet, token ring, etc.) to wide
`area networks (ATM,
`frame relay, and so forth).
`Accordingly, communication medium 180 will not be fur-
`ther described. Libraries 102 and 142. sendcrtreceiver 106
`and 146, as wel1 as tokenizerfdewtokenizer 104 and 144 are
`also intended to represent a broad range of these elements
`known in the art. 'l‘hus, except for the manner these elements
`are employed to practice the present invention, individually,
`these elements will also not be further described.
`In this
`FIG. 1!)
`illustrates an attemate embodiment.
`embodiment, sending system 100‘ also advantageously pro—
`vides source files to receiving system 140’ in the tokenized
`form, thereby reducing the bandwidth requirement on com-
`mu nication medium 180’. Sending system 100‘ similarly
`includes library 102‘, tokenizier 104' and sender 106', while
`receiving system 140' similarly includes library 142',
`de—tokenizcr 144' and receiver 146‘. Each of these elements
`perform the same functions as the corresponding element
`described earlier for the embodiment of FIG. 1a. The key
`differences between these two embodiments are in the
`manner in which tokenizcr 104' transforms source files 110’
`in the original form to source files 112‘
`in the tokenized
`form, and de-tokenzier 144' restores source tiles 112' in the
`tokenized form to source files 115'
`in the original form.
`More specifically,
`in addition to substituting language
`elements with corresponding tokens to reduce transmission
`bandwidth requirement, as described earlier, tokenizer 104'
`further substitutes operands present in source file 110' in the
`original
`form with corresponding tokens. Additionally,
`tokenizer 104‘ further creates and maintains a symbol table
`114‘ for each group of related source files, e.g. those to be
`compiled and linkedited together.
`In particular, tokenizer
`104‘ creates a mapping entry for symbol table 114' for each
`new operand it encounters and substitutes with a new token.
`For the exemplary embodiment of tokens illustrated in FIG
`2a, the class value of the operand class token will be set to
`a pointer pointing to the appropriate mapping entry in the
`symbol table (see FIG. 252, wherein an exemplary embodi-
`ment of a symbol table is illustrated).
`Symbol tables 114' are also provided to receiving system
`140‘ by sender 106' of sending system 100'. In like manner.
`
`RPX-1015
`RPX-1015
`Page 11 of 15
`Page 11 of 15
`
`

`

`6,163,811
`
`5
`receiver 146‘ stores the received symbol tables 114‘ in library
`142‘, making them available to de-tokeni‘ner 144' when it
`restores source files 112' in the tokenized form to source files
`152‘ in the original form. In other words, in addition to the
`language element substituting token to language mappings
`de-tokeniaer 144‘ is equipped with, de-tokenizer 144‘ further
`uses the operand substituting token to operand mappings in
`symbol tables 114‘ to effectuate the restoration.
`FIG. 1r: illustrates yet another altemale embodiment. In
`this embodiment, sending system 100" also advantageously
`provides source files to receiving system 140“ in the token-
`ized form, thereby reducing the bandwidth requirement on
`communication medium 180". Sending system 100" simi-
`larly includes library 102”, tokenizer 104" and sender 106",
`while receiving system 140" similarly includes library 142",
`de-tokenizer 144" and receiver 146". Each of these elements
`perform the same functions as the corresponding element
`described earlier for the embodiments of FIGS. Int—lb. The
`key difference between this and the earlier embodiments is
`the fact that source files 110“f112"t‘ 115" are also in either a
`base or delta form, having associated versioning control
`information 116". Accordingly, sender 106" also provides
`receiving system 140" with new operand substituting token
`to operand mappings for symbol
`tables 114“, whenever
`sender 106" provides receiving system 140" with a base!
`delta source file 112" in the tokenized form involving new
`operand substituting tokens, not previously employed in
`basei‘delta source files 112" earlier provided to receiving
`system 140". Additionally, for this embodiment, sender 106"
`also provides versioning control information 116" to receiv-
`ing system 140“.
`In one embodiment, each of basetdelta source files 110“!
`112"f115" is identified with a universally unique identifier
`(UUID), as disclosed in co—pending U.S. patent application
`Ser. No. 09i177.443.
`filed contemporaneously, entitled
`“User Centric Source Control”, which is hereby fully incor-
`porated by reference (except for the reciprocating incorpo—
`ration by reference). In other words, sender 106“ and receiv-
`ing system 140" are one each of the vendor and user systems
`respectively, practicing the “user centric“ source distribution
`method of the copending application, wherein vendor soft-
`ware products are distributed to the user systems in a base
`and delta source form, along with versioning control infor—
`mation. Each of the UUIDs universally identifies the par-
`ticular baseidelta source file 110"t‘112"t115" among other
`baseldelta source files of the program product as well as
`among other basetdelta source files of all other program
`products of all other software vendors. For this embodiment,
`the versioning control information 116“ includes predeces-
`sor UUID information and other control information, such
`as locking and privileges, for the basetdelta source files
`110"l112"t115“, as described in the co—pending application.
`As described earlier, sender 106" provides these predecessor
`UUID and other control
`information to receiving system
`140".
`
`Also in like manner, receiver 146" updates symbol tables
`114" stored in library 14 ", whenever it
`receives new
`operand substituting token to operand mappings from send-
`ing system 100". Receiver 146" also stores versioning
`control information in library 14 ", upon receiving them
`from sending system 100”, and making the versioning
`control infomation available for use on receiving system
`140".
`
`While the present invention is being described with FIG.
`In as an extension of FIG. 1b, those skilled in the art will
`appreciate that the present invention may also be practiced
`with FIG, la being extended with the additional basei’delta
`
`ll]
`
`15
`
`so
`
`35
`
`4t]
`
`45
`
`50
`
`55
`
`60
`
`55
`
`6
`and versioning control features of FIG. 1c, but without the
`additional tokenizing operand feature of FIG. 1b. In fact,
`those skilled in the art will appreciate that
`the present
`invention may be practiced with other additional features,
`andtor without some of the earlier described features.
`Referring now to FIGS. 3fl—3f), wherein one embodiment
`each of the operational steps of sending and receiving
`systems 100 and 140 are shown.
`In the remaining
`descriptions, when reference is made to an element, such as
`tokenizer 102, unless specifically noted,
`the reference is
`intended to include all embodiments earlier described,
`i.e.
`tokenizer 102, 102' as well as 102" of FIG. In, It: and 1c.
`First, over in sending system 100, as illustrated in FIG. 3a,
`at step 302, tokenizer 102 is initially employed to transform
`the source files from the original form to the tokenized form,
`with at least
`the language elements being substituted by
`corresponding tokens. Step 304 is an optional step for those
`embodiments where at step 302, operands are also substi-
`tuted by corresponding tokens. Where applicable, tokenizer
`102 further creates a symbol table, or new operand substi-
`tuting token mapping entries for an existing symbol table,
`depending on whether the source file being processed is a
`first of a collection of interrelated source files or merely
`additional ones of the collection. Steps 302 and 304 are
`presented as two separate discrete steps [or case of under-
`standing. They may be practiced as separate steps as
`described or as a single combined step.
`Upon generating the transformed source files, sending
`system 100 awaits for requests for the source files, step 306.
`As described earlier, the requests may be made by a local
`requester, such as an application on sending system 100, or
`by a remote requester, such as an application on receiving
`system 140.
`In any event, upon receipt of a request
`to
`provide selected ones of the source files to receiving system
`140, sender 106 provides requested ones of the source files
`in the tokenized form, reducing transmission bandwidth
`requirement on communication medium 180. Step 310 is
`also an optional step for those embodiments where at step
`302, operands are also substituted by tokens, andtor the
`source files are being kept in basei‘delta form with versionng
`control information. Where applicable, sender 106 further
`provides the symbol
`table, update entries for the symbol
`table, or versioning control information, as the situation may
`call for. Similarly, steps 308 and 310 are presented as two
`discrete steps for case 01‘ understanding. They too may be
`practiced as separate steps as described or as one single
`combined step.
`Upon providing the requested ones of source files, and
`other applicable symbol table{s) andt’or versioning control
`information to receiving system 140, sending system 100
`returns to step 306, unless sending system 100 is to termi-
`nate operation. Steps 308—310 are repeated as many times as
`necessary to satisfy the various requests received by sending
`system 100 for receiving system 140 and the likes.
`Furthennore, while for ease of understanding, FIG. 3a
`illustrates the process of tokenizing the source files as being
`performed for a number of source liles before requests for
`selected ones of the source files are received and serviced,
`those skill
`in the art will appreciate that
`in alternate
`embodiments, the process of tokenizing the source files may
`be dynamically performed subsequent to receiving a request
`for the source files instead.
`
`Over in receiving system 140, as illustrated in FIG. 3b, at
`step 322, receiving system 140 either proceeds with steps
`324—326 or step 328 depending on whether it is receiver 146
`who has received source liles provided by sending system
`100 or it is de-tokeniaer 144 who has received a request to
`
`RPX-1015
`RPX-1015
`Page 12 of 15
`Page 12 of 15
`
`

`

`6,163,811
`
`5
`
`it]
`
`15
`
`7
`restore selected ones of the tokeni'zied source files. If it is the
`former, receiver 146 stores the received source files in
`tokenired forth into library 142 as described earlier. Step
`326 is an optional step for those embodiments where the
`operands are also substituted by tokens andfor the source
`files are being kept
`in baset'delta form with versioning
`control
`information. Where applicable, receiver 146 also
`stores the symbol table or versioning control
`information
`into library 142 or updates the symbol table, as the situation
`may call for.
`At step 328, de-tokeniner 144 restores the source files
`from the tokenized form back to the original form, restoring
`at
`least
`the language element substituting tokens to the
`corresponding tokens. For embodiments where operands are
`also substituted by tokens, de—tokenizer 144 further restores
`the operand substituting tokens to the corresponding
`operands, using the appropriate symbol tables.
`Upon responding to the receipt of source files in tokenized
`form or
`their associated information, or responding to
`requests to restore selected ones of the source files, receiving
`system 140 returns to step 322, unless receiving system 140 '
`is to terminate operation. Steps 324—326 and step 328 are
`repeated as many times as necessary to service the receipts
`and various requests received by receiving system 140.
`Funhermore, while for ease of understanding, FIG. 3b
`illustrates the process of restoration as being performed _
`“on-demand", those skill in the art will appreciate that
`in
`alternate embodiments, the process of restoration may also
`be performed in batch prior to making the restored source
`files available for use on receiving system I40.
`Referring now to FIG. 4, wherein an exemplary applica-
`tion of the present invention to the provision of web pages
`by web server is illustrated. As shown, web site 400 and an
`exemplary client system 440 is coupled to one another
`through lntemet 480. Web site 400 provides web pages to
`client system 440 responsive to requests from client system
`440.
`Incorporated with the teachings of the present
`invention, web site 400 advantageously provides the
`requested web pages to client system 440 in the above
`described tokenized form, reducing the transmission band-
`width requirement on lnternet 480, which as those skilled in
`the art will appreciate, will also likely to result in improving
`perceived response time to a user of client system 440.
`As described earlier for sending system 100" of FIG. 1c,
`web site 400 includes library 402. lokenizer 404 and HTTP
`interface 406 (in the role of sender 106). Library 402 is used
`to store HTML web pages, JAVA scripts and so forth in
`original as well as tokenized form 410 and 412 (hereinafter
`simply web page or web pages), including symbol tables
`414. For the illustrated embodiment, web pages 410 and 412
`are kept
`in basefdelta form having associated versioning
`control information 416. However, for preferred implemen-
`tation reasons, versioning control information 416 are stored
`in a separate repository 418 as opposed to library 402. For
`alternate embodiments, repository 418 may be implemented
`as an integral part of library 402. Tokenizer 404 and HTTP
`interface 406 operate as described earlier for the correspond-
`ing elements of sending system 100'"
`to effectuate the
`desired reduction in bandwidth requirement on Internet 480.
`Similarly, as described earlier for receiving system 140"
`of FIG. 1e, client system 440 includes library 442,
`de-tokeniaer 444 and browser 446 (in the role of receiver
`146). Library 442 is used to store web pages in tokenized
`form 412 and symbol tables 414. Also for preferred imple—
`mentation reasons, versioning control information 416 are
`st