Abstract:
A computer-implemented incremental algorithm for updating globally optimized linebreaks for a paragraph following a change to that paragraph takes advantage of the fact that in many cases, the effect of a change on a paragraph is of only limited extent in the paragraph. As a result, in many cases, previously evaluated information concerning feasible breakpoints for the original paragraph can be used to obtain the optimal break for the changed paragraph. The computer-implemented incremental algorithm models the paragraph as an acyclic graph and identifies those portions of the graph that are unchanged as a result of the revision. The method then evaluates feasible breakpoints and combined these with feasible breakpoints obtained from the original paragraph. Using these breakpoints, the incremental algorithm uses dynamic programming to obtain the optimal break for the changed paragraph.

Description:
This invention relates to document processing systems, and in particular, to computer-implemented methods for updating breakpoints in a paragraph following a change to the paragraph. 
     BACKGROUND 
     When we type text into a word processor, we take it for granted that at some point, when the insertion point becomes too close to the right margin, the line will break and any additional text we type will appear on the following line. This typically results in one or more paragraphs, each of which is broken into one or more lines defined by breakpoints marking the beginning and ending of each line. One common problem that arises in word processors and other document processing systems is determining where in the paragraph to place these breakpoints. 
     Conventional line breaking algorithms, often referred to as “greedy algorithms,” seek to pack as much text as possible into a line without having the line exceed the maximum line length. Because of their relative simplicity, these algorithms have the advantage of being easy to implement and quick to execute. They are therefore particularly adapted to real-time editing with conventional interactive word processors, in which prompt response to user input is essential. 
     A disadvantage of such greedy algorithms, however, is that they optimize only one line at a time. These algorithms are generally incapable of considering how the position of a breakpoint on a particular line may affect the lengths of all other lines in the document (hence the term “greedy”). For example, it may be the case that by placing slightly less text on one line, many other lines can be made to more closely approach the desired line length. A greedy algorithm, because it optimizes only the current line, does not recognize this. As a result, the breakpoints selected by a greedy algorithm can result in paragraphs having a decidedly unattractive appearance, particularly when the paragraphs are to be set in narrow columns. For example, the paragraph may have lines that deviate significantly from the desired line lengths. In some cases, the last line of a paragraph may have only a single word. In the case of justified paragraphs, certain lines may have excessively large gaps between words. 
     Because of its ability to store the entire paragraph in memory, a computer need not be confined to considering only one line at a time. The presence of the entire paragraph in memory can, in principle, enable the computer to examine the entire paragraph before committing to a particular set of linebreaks. 
     As a result, the computer should, in principle, be able to consider the effect of a line break on the overall appearance of the paragraph. In some cases, a computer might refrain from packing as many words as possible into a line in order to generate a more aesthetically pleasing paragraph. For example, a short preposition might easily fit on the first line of a paragraph. However, this might result in the last line of the paragraph having only one word. 
     This ability to consider the entire paragraph at once before committing to any linebreaks gives rise to a second class of algorithms in which breakpoints are selected on the basis of a global parameter that measures the effect of the entire set of breakpoints on the paragraph as a whole. The leading algorithm of this type, which is referred to hereafter as the KP algorithm, is described in Knuth and Plass, “Breaking Paragraphs into Lines,” Software-Practice and Experience, 11:1119-1184 (1981), the teachings of which are herein incorporated by reference. 
     Throughout the specification, it will be necessary to refer to directions and locations within a paragraph. In keeping with the preferred direction for reading and writing English text, a paragraph is considered to begin at its left-most end and to end at its right-most end. The upstream direction is the direction towards the beginning of the paragraph; and the downstream direction is the direction towards the end of the paragraph. The adjectives “earlier” and “later” are used in the specification to refer to the locations that are upstream or downstream from other locations respectively. The method of the invention, however, does not depend on these definitions and can be applied to a paragraph that begins at its rightmost end and ends at its leftmost end. 
     Referring to FIG. 1, the KP algorithm considers a paragraph  10  to have a set of legal breakpoints  12 , each of which has a cost  14  associated with it. Some of these legal breakpoints are “feasible-breakpoints.” A feasible breakpoint is a legal breakpoint that results in a line having a length that is within a predefined tolerance of a target line length. From this set of legal breakpoints  12 , the KP algorithm selects a first set of feasible breakpoints  16  for the first line, as shown in FIG.  2 . 
     Each feasible breakpoint in this set of feasible breakpoints for the first line generates a set of feasible breakpoints for the second line. For example, if the first line breaks at b 1 , the second line can break at either b 3  or b 4 . A break earlier than b 3  will result in a second line that is too short relative to a desired line length, whereas a break later than b 4  will result in a second line that is too long relative to the desired line length. If, on the other hand, the first line breaks at b 2  instead of at b 1 , breaking the second line at b 3  results in a second line that is too short. A second line break following b 4  results in a second line that is too long. Hence, the only feasible break for the second line is at b 4 . 
     It is readily apparent that the above procedure continues until the end of the paragraph, with the feasible breakpoints for any line being determined by the selected feasible breakpoint for the immediately preceding line. Each feasible breakpoint for the first line thus generates a finite set of feasible breakpoint sequences for all subsequent lines. By adding the costs associated with each feasible breakpoint in a sequence of breakpoints, one can obtain a cumulative cost, for each of these feasible breakpoint sequences. The KP algorithm is an efficient way to select the feasible breakpoint sequence having the lowest such cost. 
     Although the KP algorithm is efficient, it is apparent that if one were to change a paragraph, for example by inserting or deleting text, the algorithm would be forced to regenerate all the feasible breakpoint sequences in the resulting changed paragraph. As a result, application of the KP algorithm to real-time editing, as it is commonly performed in modern word processors, results in undesirable delays caused by the need to re-evaluate all possible breaks in the changed paragraph following each insertion or deletion. 
     It is thus desirable in the art to provide a globally optimizing linebreaking algorithm that meets the stringent performance standards associated with real-time editing in a modern word processor. 
     SUMMARY 
     The method of the invention presupposes that a particular paragraph has been operated upon by a dynamic programming line breaking algorithm such as the KP algorithm described above. As shown in FIGS. 3 and 4, the operation of the KP algorithm generates a network of connecting arcs  18  from one feasible breakpoint  16  to the next, as well as costs associated with each arc. This network of connecting arcs, and their associated costs, will be collectively referred to as “auxiliary information.” 
     Although the ordinary meaning of a “paragraph” is that of a distinct division of a written work, usually marked by beginning on a new and indented line, as used herein, a “paragraph” refers to an ordered sequence of items which is to be divided into an ordered set of subsequences called “lines.” Hence, by this definition, an entire book can be considered as a single paragraph. The items themselves need not be alphanumeric characters. For example, the items might be frames in a comic strip or musical symbols in a composition. The method of the invention is sufficiently general to apply to any ordered sequence of items that is to be divided into a similarly ordered set of subsequences of such items. 
     When a user makes a change to a paragraph, the change can permeate the entire network of arcs. Breakpoints which were once feasible can be rendered unfeasible; previously unfeasible breakpoints can be made feasible; and the cost associated with a path between two feasible breakpoints can change. These changes can, in turn, precipitate the need to make wholesale changes to the distribution of linebreaks throughout the paragraph. Under these circumstances, it may be necessary to run the KP algorithm on the entire paragraph in order to update the auxiliary information and the distribution of linebreaks in the paragraph. 
     However, in many cases, a change to the paragraph results in highly localized changes to the distribution of linebreaks. For example, the insertion of one or two words to a paragraph can result in linebreaking changes to one or two lines following the insertion point but no changes anywhere else in the paragraph. The insertion or deletion of a punctuation mark may involve no changes at all to the distribution of linebreaks. Under these circumstances, large portions of the auxiliary information previously computed for the paragraph may still be valid and should therefore not have to be recomputed. 
     The method of the invention takes advantage of the fact that many changes to a paragraph require linebreaking changes only in the immediate neighborhood of the change. To do so, the method of the invention provides for caching auxiliary information that represents the underlying graph structure of a paragraph. This auxiliary information includes information on feasible breakpoints of the original paragraph as well as information concerning costs associated with different paths from one feasible breakpoint to another. 
     Following a change to the paragraph, the method of the invention identifies a changed section and an unchanged section of the underlying graph associated with the resulting changed paragraph. The method then processes only the changed section, thereby generating changed section information. This changed section information can include a set of changed feasible breakpoints corresponding to the changed section of the paragraph. The method then selects, from the auxiliary information, a selected portion associated with the unchanged section of the paragraph. This selected portion can include a reusable set of feasible breakpoints associated with the unchanged section of the paragraph. From the selected auxiliary information and the set of changed section information, the method obtains the optimal break for the changed paragraph. 
     By reusing previously obtained auxiliary information concerning the underlying graph structure of the original paragraph, the method of the invention provides an efficient way to incrementally update the linebreaks of a paragraph in a globally optimized manner. 
    
    
     These and other advantages of the invention will be apparent upon examining the following description and the accompanying figures in which: 
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is an abstract illustration of a paragraph having a plurality of breakpoints; 
     FIG. 2 is an abstract illustration of the paragraph of FIG. 1 with only the feasible breakpoints shown; 
     FIG. 3 shows all possible breaks for the paragraph of FIG. 2 that include the first feasible breakpoint; 
     FIG. 4 shows all possible breaks for the paragraph FIG. 2 that include the second feasible breakpoint; 
     FIG. 5 shows a processing system for implementing the optimal linebreaking algorithms in accordance with the teachings of the present invention; 
     FIG. 6 is a schematic illustration of the system components for practice of the teaching of the present invention in batch mode; 
     FIG. 7 is a schematic illustration of the system components for practice of the teaching of the present invention in interactive mode; 
     FIG. 8 shows the union of the graphs of FIGS. 3 and 4; 
     FIG. 9 shows the dynamic programming solution for the optimal break of the paragraph represented by the graph of FIG. 8; 
     FIG. 10 shows pseudo-code for the KP algorithm; 
     FIG. 11 shows pseudo-code for an incremental version of the KP algorithm for the insertion of an insertion section into a paragraph; 
     FIG. 12 is an abstract representation of an insertion into a paragraph; 
     FIG. 13 is a schematic flowchart diagram showing the steps in the incremental algorithms embodying the invention; 
     FIG. 14 shows pseudo-code for the incremental algorithm of FIG. 11 but adapted for the deletion of a section from a paragraph; 
     FIG. 15 is an abstract representation of a paragraph before and after deletion of a section; 
     FIG. 16 shows an incremental insertion algorithm in which the feasible breakpoints for an upstream section of a paragraph and the feasible breakpoints for a downstream section of a paragraph are spliced together following an insertion section; 
     FIG. 17 shows an algorithm similar to that of FIG. 16 but adapted for deletion of a section from a paragraph; 
     FIG. 18 shows an algorithm for retrieving active node lists from a graph representative of a paragraph; and 
     FIG. 19 shows the algorithm of FIG. 11 but modified to use the algorithm of FIG.  18 . 
    
    
     DETAILED DESCRIPTION 
     Referring to FIG. 5, a document processing system  20  embodying the invention includes: one or more input devices  22 , typically a keyboard operating in conjunction with a mouse or similar pointing device, for communicating instructions from a user to a main processor  24 ; and a display monitor  26  for viewing text and graphics displayed by the system  20 . 
     The main processor  24  is adapted to execute programmed instructions for implementing the method of the invention. The document processing system  20  also includes a storage element, such as a random access memory (RAM)  28 , for storing programmed instructions to be executed by the main processor  24  and for temporary storage of data representative of a document. 
     The system  20  further includes other storage devices, such as a non-volatile memory  30 , for storage of data representative of a document, and a computer bus  32 . The non-volatile memory  30  can be a hard disk local to the document processing system  20 . Alternatively, the non-volatile memory  30  can be associated with a server or distributed across several servers, or be incorporated into an enterprise-wide data management system. The computer bus  32  permits communication between the main processor  24 , RAM  28 , and non-volatile memory  30  to provide for the transfer of data between the document processing system components. 
     The present invention includes computer software  34 , such as a document processor operable on the document processing system  20 , for facilitating the layout and typesetting of a document. Such software is typically stored on a computer readable medium such as a magnetic disk or other non-volatile memory  30  and paged into RAM  28  as necessary. 
     Optionally, the system  20  can include a printer  36  in communication with the bus  32 . However, it is also possible for the software  34  to create a device independent file  38  that can be transported to an appropriate printer. 
     FIG. 6 shows the general workflow associated with the practice of the invention in batch mode. In the input stage  40 , a document author creates the content of a document and saves the content as a document file  42  on a disk. The document file  42  is then provided to a typesetting stage  44  which determines the optimal break associated with each paragraph in the document file  42 . The typesetting stage  44  then generates a device independent file  46  and sends that file to an output stage  48  that transforms it into a printed document  50 . 
     FIG. 7 shows the workflow of FIG. 6 but adapted for interactive processing rather than batch processing. In FIG. 7, the typesetting stage  44  is in communication with a display stage  52  as well as with the output stage  48 . The display stage  52  generates a representation of the document suitable for viewing on the display monitor  26 . 
     The computer software  34  for practice of the invention includes instructions for rapidly and efficiently updating line breaks in a paragraph following a change in the paragraph. Because the software  34  executes instructions that represent an improvement over the KP algorithm, an understanding of the KP algorithm is desirable. 
     To understand the KP algorithm further, it is useful to consider a paragraph as being an acyclic graph having a node  16  at each feasible breakpoint. A representative graph, shown in FIGS. 3 and 4, has several nodes  16  representing feasible breakpoints {b 0  . . . b 8 }, with the leftmost node b 0  corresponding to the beginning of the paragraph and the rightmost node b 8  corresponding to the end of the paragraph. Each node is connected to one or more other nodes by connecting arcs. Each arc connecting two nodes has a cost associated with traversing that arc  18 . The uneven thicknesses of the arcs connecting the nodes in FIGS. 3 and 4 are intended to illustrate the relative costs associated with each arc  18 . In considering FIGS. 3 and 4, note that these two figures represent the same graph. For the sake of clarity, only the connecting lines emanating from node b, are shown in FIG.  3 . The connecting lines emanating from node b 2  are shown separately in FIG.  4 . 
     It is apparent from considering FIGS. 3 and 4 that one can proceed along the connecting arcs  18  from the first node b 0  (the beginning of the paragraph) to the last node b 8  (the end of the paragraph) along several different paths, each of which is defined by a sequence of connecting arcs. The sequence of nodes encountered along a particular path corresponds to a sequence of linebreaks. Throughout this specification, the term “break” refers to a such a sequence of linebreaks corresponding to a path from a first node b 0  to a last node b m  in the acyclic graph representative of a paragraph. Each such break has a cumulative cost defined by the summing the costs of each individual connecting arc  18  in the sequence of connecting arcs. In this model of the paragraph breaking process, the KP algorithm can be viewed as selecting the break that corresponds to the path that has the smallest cumulative cost. 
     In FIGS. 3 and 4, a first node representing a first breakpoint is connected to a second node representing a second breakpoint if and only if a line break at the first breakpoint can result in a line break at the second breakpoint. Stated differently, given a node in the graph, the set of nodes directly connected to that node by connecting arcs represents a list of active nodes associated with the given node. This list of active nodes is a dynamic list consisting only of those nodes that are approximately one target line length from the given node. 
     Hence, as shown in FIG. 3, node b 1  is connected to nodes b 3  and b 4  because, as discussed above, line breaks at breakpoints b 3  and b 4  are permissible following a line break at b 1 . Similarly, as shown in FIG. 4, node b 2  is connected only to node b 4  because a line break at breakpoint b 4  is the only permissible line break following a line break at b 2 . 
     As defined above, a break for this paragraph is a sequence of nodes defining a path from b 0  to b 8  on the graph shown in FIGS. 3 and 4. For example, a line break at b 1  results in four possible paths to b 8 , and hence four possible ways to break the remainder of the paragraph. A line break at b 2  results in two possible ways to break the remainder of the paragraph. Hence, there are only six paths, or breaks, through the graph, representing six feasible ways to break the paragraph shown in FIG.  1 . Each of these six paths has an associated cumulative cost obtained by summing the costs for each arc along the path. The KP algorithm selects, from these six paths, the path having the lowest cost. 
     Because the choice of what feasible breakpoint can follow a given breakpoint depends only on the given breakpoint for the preceding line, the problem of selecting the optimal break for a paragraph can be cast as a multi-stage optimization problem in which each line corresponds to one stage. Such problems are ripe for solution by dynamic programming, a recursive technique described in Bellman and Dreyfus, “Applied Dynamic Programming,” Princeton Univ. Press (1962), the contents of which are herein incorporated by reference. 
     The dynamic programming algorithm can be understood by considering the graph of FIG. 8 formed by recombining the graphs in FIG.  3  and FIG.  4 . The circled numbers beside each connecting arc in FIG. 8 represent costs associated with traversing that arc. The KP algorithm seeks a path from the beginning of the paragraph at b 0  to the end of the paragraph at b 8  that minimizes the sum of these costs. For the case of the graph shown in FIG. 8, that path is shown as the dashed line connecting the nodes b 0 , b 1 , b 3 , and b 5 . 
     For each node, the dynamic programming algorithm determines the preceding nodes from which one can reach that node and the costs of reaching that node by passing through the preceding nodes. These paths are summarized in FIG.  9 . The optimal break for the paragraph represented by the graph of FIGS. 3-8 is thus shown by the line stitching together the two columns of FIG.  9 . The cost for this optimal break, together with the costs for all other breaks, is summarized at the bottom of FIG.  9 . 
     FIG. 10 shows, in pseudo-code, the KP algorithm  54  for selecting the optimal sequence of breakpoints. The use of pseudo-code to illustrate algorithms is well known to those of ordinary skill in computer science. Such illustrations are a useful alternative to flowcharts when the algorithm to be described becomes complex or when the algorithm includes recursive steps. 
     In the algorithm shown in FIG. 10, as well as in subsequently described algorithms: 
     ActiveNodeList is a list of all nodes in the graph that are candidates for future breaks given a starting point at a particular node; 
     b.dist is a field associated with node b that indicates the cost of breaking the line at node b; 
     b.fathers is a list of nodes from which one can reach node b directly from every node in the list. Put differently, (b′,b) is an arc of the graph of FIGS. 3 and 4 if, and only if, b′ is also a node in b.fathers. &lt;b i , b&gt; is a line extending between breakpoints b i  and b; 
     γ(&lt;b i , b&gt;) is a length associated with the line &lt;b i , b&gt;; 
     ShrinkBound and StretchBound refer to bounds on how much a particular line is permitted to deviate from a target line length; 
     b.bestFathers is a list of those nodes from b.fathers that result in the lowest cost break up to and including node b; 
     “@” is an operator that concatenates two lists. 
     Note that after determining the feasible break points and constructing the graph, the KP algorithm  54  backtracks, beginning at the last breakpoint b m  and proceeding back to the first breakpoint b 0 . At each step, the algorithm proceeds along a path defined by the nodes in the various bestFathers lists associated with each of the nodes it passes as it moves between b m  and b 0 . The nodes along this path represent the optimal set of breakpoints, or the optimal break, for the paragraph. 
     The method of the invention makes extensive use of portions of the KP algorithm  54  illustrated in FIG.  10 . This algorithm defines an active node list that represents the active breakpoints for the paragraph (step  56 ). The algorithm then enters an outer for-loop in which it selects, from the active node list, the feasible breakpoints for a particular choice of breakpoint b in the active node list (step  58 ). These feasible breakpoints will be stored in b.fathers, which is initialized with the empty set (step  60 ). The step  62  of executing the body of this outer for-loop, which extends between lines  4 - 14  inclusive, will be referred to as ForBody(b) in connection with the description of the incremental algorithm of the invention. 
     To determine the set of possible breakpoints, the KP algorithm  54  enters an inner for-loop in which it considers the line lengths &lt;b i ,b&gt; that would result from breaking the line at each possible breakpoint given that a break has occurred at b i  (step  64 ). Because, in the general case, interword spacings can be stretched or shrunken within limits to perturb the line length &lt;b i ,b&gt; of a line extending between b i  and b, the algorithm uses a quantity referred to as the “adjustment ratio” that measures the extent to which a line length can be varied (step  66 ). A suitable definition of an adjustment ratio is given in Knuth and Plass. 
     If the adjustment ratio indicates that any line between b and b i  would be unacceptably short, the KP algorithm deletes b i  from the active node list (step  68 ). If the adjustment ratio is such that a line within the acceptable limits can be formed between breakpoints b i  and b, then the KP algorithm adds the breakpoint b i  to the set b.fathers of feasible breakpoints associated with b (step  70 ). If the adjustment ratio indicates that a line from b i  to b would be unacceptably long, the breakpoint b i  is retained in the active node list. This is because although this breakpoint is not feasible for this choice of b, it may nevertheless be a feasible breakpoint for another choice of b. 
     Assuming that b.fathers is no longer the empty set following completion of step  64 , the next step is to select that break in b.fathers that results in the lowest cumulative cost. This break is determined by a cost-determining conditional statement (step  72 ). The function {overscore (δ)}(&lt;b′,b&gt;) in step  74  refers to the cost associated with forming a line between b′ and b. The algorithm then keeps track of the nodes that must be traversed to yield this minimum cumulative cost and, in step  76 , places them in b.bestFathers. Finally, the algorithm  54  constructs the optimal break using the nodes identified in bestFathers (step  78 ). 
     There are two possible changes that can be made to a paragraph: insertion of text at a change point or deletion of text beginning at a change point. Either of these changes results in a change to the underlying graph for the paragraph. However, depending on the nature of the change, most of the underlying graph may remain the same. The incremental algorithms disclosed herein exploit this fact in order to efficiently update the optimal break of a paragraph following a change to that paragraph. 
     While superficially there may appear to be a difference between a change made to the beginning or the end of a paragraph and a change made in the middle of a paragraph, an examination of the graph in FIG. 8 indicates that this is not the case. Since by definition every paragraph has feasible breakpoints b 0  and b m  that mark the beginning and the end of the paragraph, all changes to the paragraph can be considered as changes between these two feasible breakpoints. Hence, throughout this specification, when reference is made to an upstream or downstream section of a paragraph relative to a change point, it is to be understood that these sections can consist of no breakpoints other than the feasible breakpoints b 0  and b m  that mark the beginning and end of the paragraph. 
     An incremental insertion algorithm  80 , shown in FIG. 11, can best be understood by considering an original paragraph  82 , as shown in FIG. 12, having feasible breakpoints. {b 0 , b 1 , . . . b j , b j+1 , . . . b m }. A section to be inserted  84  (hereafter referred to as the “insertion section”) having breakpoints at {b′ 1 , . . . b′ m .} is inserted into the original paragraph  82  so as to divide the original paragraph  82  into an original-paragraph upstream section  86  with feasible breakpoints {b 0  . . . b j } and an original-paragraph downstream section  88  with feasible breakpoints {b j+1 , . . . b m }. The sequence of feasible breakpoints in a changed paragraph  90  thus created is such that b′ 1 , follows b j  and b′ m′ , precedes b j+1 . 
     In the resulting changed paragraph  90 , the history associated with the original-paragraph upstream section  86  is unchanged and can be reused. Consequently, the KP algorithm  54  need not be reapplied to the upstream section  86 . The auxiliary information associated with the insertion section  84  has never been evaluated. Consequently, the KP algorithm  54  is applied to the insertion section  84 . Referring now to the incremental insertion algorithm  80  shown in FIG. 11, this is performed, in step  92 , by a first for-loop in which ForBody(b)  62  is as indicated in FIG.  10 . 
     The incremental algorithms disclosed herein include steps  94  as shown in FIG.  13 . First, auxiliary information associated with the original paragraph is cached (step  96 ). This is followed by the step of identifying a changed section of the changed paragraph and an unchanged section of the changed paragraph (step  98 ). In this context, a changed section refers to a section in which the underlying acyclic graph that represents the changed paragraph is changed. The incremental algorithm then generates a set of feasible breakpoints associated with the changed section (step  100 ) and retrieves, from the cached auxiliary information, a set of feasible breakpoints associated with the unchanged section of the paragraph (step  102 ). On the basis of these two sets of breakpoints, the incremental algorithm then determines the optimal break for the changed paragraph (step  103 ). 
     Referring again to FIG. 12, in a preferred embodiment, the original-paragraph downstream section  88  is further divided into a first section  88   a , extending between feasible breakpoints b j+1  and b k , in which it is known for certain that the history has changed, and a second section  88   b  extending between feasible breakpoints b k+1  and b m , in which it is not known for certain that there has been a change in the history. Referring back to FIG. 1, a second for-loop then executes the KP algorithm for feasible breakpoints located in this first section  88   a  (step  104 ). 
     The boundary between the first and second sections  88   a ,  88   b  of the original-paragraph downstream section  88  is not known a priori and needs to be determined by the incremental insertion algorithm  80 . This is performed by proceeding downstream beginning at the feasible breakpoint b j+1  immediately following the end of the insertion section  84  and determining the first feasible breakpoint following b j+1  for which the adjustment ratio is less than ShrinkBound (step  106 ). This feasible breakpoint determines the boundary between the first and second sections  88   a ,  88   b.    
     In step  108 , the remaining outer for-loop in the incremental insertion algorithm  80  of FIG. 11 compares the auxiliary information cache for the second section  88   b  of the original paragraph downstream section  88  with the result of applying the KP algorithm beginning at b k+1  and proceeding toward the end of the paragraph at node b m . So long as the active node list from the auxiliary information cache and the active node list being computed in the remaining outer for-loop remain different, the flag changed is set to “true” and execution continues. However, as soon as the active node list from the auxiliary information cache and the active node list being computed in the remaining outer for-loop become the same, the changed flag is set to “false” and the incremental insertion algorithm exits the outer for-loop (step  110 ). The incremental insertion algorithm  80  then assumes that the active node lists from the current breakpoint onward remain the same as those in the auxiliary information cache. 
     The process for deleting a section from a paragraph is similar to that for inserting a section into a paragraph with the exception that there is no need to run the KP algorithm on the section that is deleted. An incremental deletion algorithm  112 , which is shown in FIG. 14, can best be understood by considering an original paragraph  114 , as shown in FIG. 15, having feasible breakpoints {b 0 , b 1 , . . . b j−1 , b j , b j′ , b j′+1  . . . b m }. A text section  116  marked for deletion (hereafter referred to as a “deletion section”) and having feasible breakpoints at {b j  . . . b j′ } divides the original paragraph  114  into an original-paragraph upstream section  118  with breakpoints {b 0  . . . b j−1 ,} and an original-paragraph downstream section  120  with breakpoints {b j′+1 , . . . b m }. Following deletion of this section, a changed paragraph  122  is formed in which b j−1 , immediately precedes b j+1 . 
     In the resulting changed paragraph  122 , the history associated with the original-paragraph upstream section  118  is unchanged and can be reused. Consequently, the KP algorithm need not be reapplied to the original-paragraph upstream section  118 . 
     In a preferred embodiment, the original-paragraph downstream section  120  is further divided into a first section  120   a , extending between feasible breakpoints b j′+1  and b k′ , in which it is known for certain that the history has changed as a result of the deletion, and a second section  120   b , extending between feasible breakpoints b k′+1  and b m , in which it is not known for certain that there has been a change in the history as a result of the deletion. In a first for-loop, the incremental deletion algorithm then executes the KP algorithm for feasible breakpoints located in this first section  120   a  (step  126 ). 
     As was the case with the incremental insertion algorithm  80 , the boundary between the first and second sections  120   a ,  120   b  of the original-paragraph downstream section  120  is not known a priori and needs to be determined by the incremental deletion algorithm  112 . This is performed by proceeding downstream beginning at the feasible breakpoint b j′+1  immediately following the end of the deletion section  116  and determining the first feasible breakpoint following b j′+1  for which the adjustment ratio is less than ShrinkBound (step  124 ). This feasible breakpoint determines the boundary between the first and second sections  120   a ,  120   b  of the original-paragraph downstream section  120 . The remaining steps in the incremental deletion algorithm  112  of FIG. 14 are identical to those discussed in connection with the incremental insertion algorithm  80 . 
     In another embodiment of the invention, performance can be further enhanced by caching auxiliary information for an upstream section and a downstream section of an original paragraph and splicing these sections together in the vicinity of a change point of the changed paragraph. 
     In this embodiment, the KP algorithm is also applied to the paragraph beginning at the end of the paragraph and directed toward the beginning of the paragraph. The auxiliary information generated by doing so provides the auxiliary information for the downstream section of the paragraph. This downstream auxiliary information for the downstream section remains the same following a change to the paragraph. Consequently, in this embodiment, the auxiliary information for both upstream and the downstream can be reused to obtain the optimal break following a change to the paragraph. Because both the upstream and the downstream auxiliary information are reused, the time required to determine the optimal break for the changed paragraph is significantly reduced. 
     This second embodiment of the invention can be understood by considering again the original paragraph  114  shown in FIG. 15, with its upstream section  118  having breakpoints {b 0  . . . b j−1 }, its downstream section  120  having breakpoints {b j+1  . . . b m } and its deletion section having breakpoints {b j  . . . b j′ }. Deletion of the deletion section  116  from the original paragraph  114  creates a changed paragraph  122  made up of the same upstream section  118  and downstream section  120  as the original paragraph  114 . In this case, the auxiliary information associated with the upstream section  118  and with the downstream section  120  will remain the same. Put differently, although the breakpoints selected to form the optimal break for the changed paragraph will most likely change, the underlying set of breakpoints, from which this selection is made, remains the same. In terms of the notation introduced above, the breakpoints for {(b 0  . . . b j−1 } and for {b j+1  . . . b m } will remain the same. 
     In selecting the optimal break for the changed paragraph  122 , it is useful to recognize that the optimal break must be selected from a set of feasible breaks having the property that there exists a line in the feasible break that is bounded by a feasible breakpoint, b 1 , from the upstream section  118  and a feasible breakpoint, b R , from the downstream section  120 . Hence, in order to select the optimal break, it is first necessary to compile a list of all such lines &lt;b L , b R &gt;. Having compiled such a list, one can then obtain the set of only those feasible breaks that satisfy this property. The optimal break can then be selected from this set of feasible breaks by backtracking in the manner described in connection with the KP algorithm. 
     In the case of insertion, the method is similar to that described above with the additional step of augmenting the feasible break set for the upstream section of the changed paragraph with the feasible breaks associated with the inserted section. For example, consider once again the original paragraph  82  shown in FIG. 12, with its upstream section  86  having feasible breakpoints {b 0  . . . b j } and its downstream section  88  having feasible breakpoints {b j+1  . . . b m }. Insertion of the insertion section  84  having feasible breakpoints {b′ 1  . . . b′ m′ } results in the formation of the changed paragraph  90 . The insertion section  84  is then used to augment the upstream section  86  so as to form an augmented upstream section  91 . Once this augmentation step is performed and the feasible breaks for the augmented section are evaluated, the procedure is identical to that described above in connection with deletion. 
     FIG. 16 shows an exemplary incremental insertion algorithm  128  that applies the foregoing principle to rapidly update line breaks throughout a changed paragraph  90  following the insertion of an insertion section  84  into an original paragraph  82 . The resulting changed paragraph  90 , shown in FIG. 12, includes an upstream section  86  for which there exists cached auxiliary information obtained from applying a dynamic programming algorithm to the original paragraph  82 , and a downstream section  88  for which there exists auxiliary information obtained in the same manner. The incremental insertion algorithm  128  described below uses the cached auxiliary information for the upstream section  86  and the downstream section  88  of the original paragraph  82  to efficiently obtain the optimal break for the changed paragraph  90 . 
     The incremental insertion algorithm  128  shown in FIG. 16 begins with the application of the KP algorithm to the insertion section (step  130 ). This results in the generation of auxiliary information for the insertion section and the formation of an augmented upstream section  91  as shown in FIG. 12. A pair of nested for-loops then obtains (step  134 ) pairs of feasible breakpoints {b L , b R } that result in permissible line breaks and that satisfy the following properties: 
     b L  is the last breakpoint in the upstream section, and 
     b R  is the first breakpoint in the downstream section. 
     The resulting feasible breakpoint pairs {b L , b R } are collected in a set denoted as FeasibleBreakPointPairSet (step  136 ). 
     The incremental insertion algorithm  128  then identifies a path from the beginning of the paragraph to the end of the paragraph that has the lowest cumulative cost and that also includes a feasible breakpoint pair from FeasibleBreakPointPairSet (step  138 ). The algorithm  128  then identifies the feasible breakpoint pair that lies on this path and that has the lowest cumulative cost (step  140 ). 
     Finally, the incremental insertion algorithm  128  backtracks along the cached auxiliary information for the upstream section  86 , the auxiliary information for the insertion section  84 , and the cached auxiliary information for the downstream section  88  to select the optimal break for the changed paragraph  90  (step  142 ). 
     The same principles used in implementing the incremental insertion algorithm  128  of FIG. 16 can be applied to an incremental deletion algorithm  144  as shown in FIG.  17 . The incremental deletion algorithm  144  of FIG. 17 is essentially identical to the incremental insertion algorithm of FIG. 16 with the exception that it lacks a step corresponding to the step  130 , shown in FIG. 16, of applying the KP algorithm to an insertion section  84 . 
     In the incremental deletion algorithm  144  of FIG. 17, a pair of nested for-loops obtains (step  146 ) pairs of feasible breakpoints {b L , b R } that result in permissible line breaks and that satisfy the following properties: 
     b L  is the last breakpoint in the upstream section, and 
     b R  is the first breakpoint in the downstream section. 
     The resulting feasible breakpoint pairs {b L , b R } are collected in a list denoted as FeasibleBreakPointPairSet (step  148 ). Following step  148 , the incremental deletion algorithm  144  is identical to the incremental insertion algorithm of FIG.  16 . 
     In the incremental algorithms presented thus far, the active node list for every breakpoint forms part of the cached auxiliary information. However, since the active node list can always be reconstructed from the underlying graph, it is not necessary to save the active node lists for each breakpoint in this manner. All that is necessary is to cache the underlying graph and to provide a routine for retrieving the active node list from the underlying graph. A retrieval routine  150  for performing this task is shown in FIG.  18 . 
     The retrieval routine  150  of FIG. 18 first identifies the first breakpoint that results in a line of sufficient length (step  151 ). Beginning with that breakpoint, the retrieval routine  150  enters a for-loop in which it considers all subsequent breakpoints (step  152 ). For each subsequent breakpoint, the retrieval routine  150  determines whether a line that breaks at that breakpoint can have a length that is within a threshold from a desired line length (step  154 ). If the subsequent breakpoint can result in such a line, then that breakpoint is added to the active node list (step  156 ). 
     It will be clear to one of ordinary skill in the art that the retrieval routine  150  can readily be incorporated into the incremental algorithm presented thus far. As an example, FIG. 19 shows an incremental insertion algorithm  158  that is identical to that shown in FIG. 11 with the exception that the retrieval algorithm is used to reconstruct the active node lists wherever necessary (steps  160 ,  162 ,  164 ). Similar modifications can readily be made to the incremental algorithms shown in FIGS. 14,  16 , and  17 .