Greedy algorithm

An easy way to break a paragraph into lines is to use the greedy algorithm. This algorithm basically puts as many words on the line as it can contain, repeating the process for each line until there are no more words in the paragraph. The greedy algorithm is a line-by-line process. Each line is handled independently. The following pseudo-code implements this algorithm for left-to-right texts:

Where LineWidth is the width of a line, SpaceLeft is the remaining width of space on the line to fill, SpaceWidth is the width of a single space character, Text is the input text to iterate for each line, and Word is a word in this text. This algorithm is very simple and fast, and it puts the words on a minimum number of lines. It is used by many text processors, including Open Office and Microsoft Word.

Optimum-fit algorithm

In the optimum-fit algorithm, justification of some lines is sacrificed to improve the justification of other lines, even those that may not follow immediately. The main goal is to get an optimum result for the whole paragraph.

For example, the optimum-fit algorithm might have to break the sequence xxx xx xx xxxxx over a line whose width is xxxxxx. The greedy algorithm would break this list of words as follows:

The result is a long line followed by a short one, and a rather unpleasant pair of right edges. In contrast, the same paragraph processed with the paragraph-based line-breaking optimum-fit algorithm results in a better right margin:

The key idea behind such a paragraph-based algorithm is to use dynamic programming to globally optimize an aesthetic cost function (Knuth and Plass 1981). The strategy adopted in the optimum-fit algorithm is to find a break opportunity at a given distance from the beginning of the line. The algorithm typically finds several candidate points for breaking the line. For each line break, a cost function e_i and error on the line is defined. If the line is perfect, e_i = 0; if a line composition is not possible, e_i will be ∞. The algorithm then seeks the best arrangement to minimize the total errors e = ∑e_i for all the lines in a paragraph.

This principle was first introduced by Donald E. Knuth and used in T_EX (Knuth 1986). This algorithm will be discussed in more detail below.

Spacing

The algorithms that break paragraphs into lines are each designed to search for an optimum approach in different ways. Typically they adjust the spaces between words and even between characters. The goal is to obtain lines that end on the right margin.

To give a line the necessary flexibility, a space between two words is not always changed into a space character. Some of these spaces are transformed into line ends. Others are transformed into triple values (id, max, min). Thus, spaces have a normal size id that can be stretched up to a max or shrunk to a value min. If necessary, a space’s value beyond max can be tolerated, but the space’s value can never be less than min.

The logic of the spacing is:

1. Put the words on the line, word after word.
2. Continue until a word comes at the end of a line and overflows onto the margin.
3. Try to shrink inter-word spaces without going less than min.
4. If that is not possible, try to stretch inter-words spaces without exceeding max.
5. If that is not possible, stretch while exceeding max.

Hyphenation

To obtain e-documents with visually homogeneous paragraphs, the spaces between words should be minimized. Hyphenation improves the text’s alignment by reducing the space between the last word of the line and the right margin. A word that is too long to fit at the end of a line is then broken, typically between syllables.

The logic for hyphenation is the same as for spacing through step 4, and then:

• 5. If that is not possible, try to hyphenate.
• 6. If that is not possible, stretch while exceeding max.

A value called badness can be associated with each possible line break. This value is increased if the space between the words must stretch or shrink too much to make the line the correct width. A best-fit strategy can help in deciding among shrinking, stretching, and hyphenation, in order to minimize the value of badness.

In the past, the hyphenation was done manually, often based on a hyphenation dictionary that identified hyphen locations. An elaborated method find nearly all of the legitimate places to insert hyphens in words in Latin-based languages (Liang 1983). This method is based on an organized tree structure of tries: a particular class of tree structure, the term was derived from the word retrieval (Fredkin 1960). The tree contains a list of hyphenation patterns, combinations of letters that allow or prohibit word-breaking. The method assigns priorities to breakpoints in letter groups. The patterns reflect the hyphenation rules of a language, so there are as many pattern tree structures as there are languages. This algorithm was implemented by Donald E. Knuth in TEX.

Gutenberg’s typography

Five hundred years ago, Johannes Gutenberg struggled to reach, in typesetting, the same quality as in contemporary handwritten manuscripts. By hand, words can be written tightly or loosely without getting too many dark spots or too many clear spots in the proof. Gutenberg used and improved existing techniques (Wild 1995). When he typeset the 42-line Bible, he used types of various widths, and he employed ligatures and abbreviations so that he could get the right justification.

Nowadays, we can imagine how his typesetting works. When he set a line, he tried types of variant glyphs with various widths for the same characters until the line had the right length. Gutenberg also used abbreviations and ligatures freely to make line justification easier. Those approaches were similar to what copyists were doing at the time, but those techniques are now rarely used in text processing and publishing systems. To use Gutenberg’s techniques successfully, the presence or absence of ligatures (links between letters) or glyph variants must not change the reader’s experience. Today, in Latin text, the only commonly used ligatures are the f-ligatures (fl, ff, fi, ffi, ffl).

Horizontal glyph scaling

Hz-program: The hz-program is software for advanced typography. It was designed by Hermann Zapf in collaboration with URW.[3] Its main goal was “to produce the perfect gray type area without rivers or holes with too-wide word spacing” (Zapf 1993). Zapf describes his program as a complete aesthetic program for micro-typography. In the beginning, he wanted to match, through computers, the level of justification reached by Gutenberg in typography—a quality that has been considered unreachable in the following 550 years (Karow 1997).

The hz-program strategy is partly based on a typographically acceptable stretching or shrinking of letters, called scaling. In addition, a kerning program calculates kerning values. The kerning is not limited to negative changes of space between two critical glyphs; in some cases it allows positive kerning, which adds space on the line. Zapf ignored Gutenberg’s ligatures and abbreviations to make the typesetting both easier to do and easier to understand. The abbreviations of the 15th century are not familiar today.

The hz-program is not available for purchase, testing or reviewing, and no information about its implementation is available; it is URW’s black box.

Improved optimum-fit: In his dissertation, Hàn Thé Thành (1999) attempted to improve the quality of the typographical gray produced by the optimum-fit algorithm. The idea is based on adapting the spaces between words once the paragraphs have been broken into lines. Instead of changing the inter-word spacing only, he expands the fonts on the line slightly as well. This approach can minimize excessive stretching of the inter-word spaces. Thành’s ideas were inspired by the hz-program. He attempted to closely control the limits where such manipulations are allowed. He set parameters for better control of the acceptable stretching or shrinking of glyphs. This width modification is implemented through a horizontal scaling of fonts in pdfT_EX.

Breaking the vertical list into pages

After the paragraph has been broken into lines, a typesetting system places the lines onto the current vertical list, also known as the current page. Each line of the paragraph is a horizontal box. In typesetting, a vertical list can contain vertical glue and vertical penalties. A line-breaking algorithm places vertical glue between the lines, so that the distance between baselines[4] is uniform. A line-breaking algorithm also inserts vertical penalties (or rules against breaks) between the lines, to assist the page-breaking process. For example, there is usually a penalty for a page break immediately after the first line of a paragraph, or a penalty for a page break immediately before the last line of a paragraph.

Look-ahead problem

The line-breaking algorithm “looks ahead” before it makes any decisions as to where the first, or any other, line break occurs. Each line break is considered not by itself but in the context of the other line breaks. The page-breaking algorithm does not carry out such a look-ahead. Each page break is considered in isolation, without regard for the other pages in the document.

The line-breaking algorithm produces lines of text. These lines are then placed on the main vertical list. If enough material has collected, the page-breaking algorithm cuts off the material for one page, and the output routine is called.

The page-breaking algorithm can use the idea underlying the line-breaking algorithm to improve its look-ahead performances (Fine 2000).

Ligatures

The cursive nature of Arabic writing implies, among other things, a wide use of ligatures (Haralambous 1995). Indeed, Arabic writing is rich in ligatures. Some of them are mandatory and obey grammatical and contextual rules (Haralambous 1995). Others are optional and exist only for aesthetic reasons, legibility, or justification. Moreover, the connection of letters can lead to the introduction of implicit contextual ligatures. An explicit ligature is the fusion of two, three, or even more graphemes.

Generally, the ligature’s width is less than the one of a fused graphemes group. The aesthetic ligature

Figure 4:

Contextual and aesthetic transformations

Controlling the ligatures’ behavior by converting the implicit ligatures into aesthetic ones gives some flexibility to adjust the word for the available space on the line. The example in figure 5 shows three ligature levels: mandatory simple substitutions, aesthetic ligatures of the second degree, and finally, aesthetic ligatures of the third degree. The last two ligature levels provide different possibilities for shrinking of the same word.

Figure 5:

Various levels of ligatures

The use of second and third degree aesthetic ligatures has to take into consideration the constraints of legibility. A typesetting system should take into account three options for ligatures. For the first level, there are only implicit contextual ligatures. This level also covers mandatory grammatical ligatures, such as the Lam-Alef ligature; it is recommended for textbooks or books for the general public where it is necessary to avoid confusion between letters and reading ambiguities. In a second-level publication, it is possible to take some liberty and use some aesthetic ligatures. In the third level, the use of aesthetic ligatures of higher degrees is allowed, and graphic expressions are free.

The decision to use explicit ligatures to improve justification must take into account the graphic environment and the block regularity of the text. In calligraphy, once an aesthetic ligature is used, there is no obligation to use this ligature in all the text occurrences. The justification problem can be sorted out with kashida in texts composed only by implicit ligatures.

The use of ligatures to justify lines is not limited to Arabic writing. Adolf Wild, conservator of the Gutenberg Museum in Mainz, examined the Gutenberg Bible from a typographical point of view and determined that at the lines level, in some cases, Gutenberg justified the text through using ligatures instead of using the variable spaces we are familiar with today. (Wild 1995)

Kashida

The connections between Arabic letters are curvilinear bridges. They are extensible. This property—called kashida, tamdid, madda, maT, tTwil, or aliTalat, etc.—is a feature of Arabic script that is rarely met or maintained in other writing systems (see figure 6). Kashida is used in various circumstances for different purposes:

• emphasis: stretching to emphasize an important word or to correspond to phonetic inflection;
• legibility: to find a better letter layout on the baseline, and to correct the cluttering that can appear at the joint between two successive letters in the same word;
• aesthetics, to embellish a word;
• justification, to justify a text.

Kashida is not a character in itself. It allows stretching some letter parts while its body is kept rigid. The example in figure 6 shows compositions of the Arabic word Mohamed. The arrows indicate the use of kashida, in two extensibility levels.

Figure 6:

Various curvilinear kashida

There are three kinds of stretching: mandatory, allowed, and prohibited. The typographical strength of a text can be determined, among other factors, by whether it respects mandatory stretching and/or eschews prohibited stretching.

In terms of Arabic text justification, kashida is a typographical effect that allows lengthening letters in some carefully selected points on the line within determined parameters so that the paragraph can be justified. The Arabic term tansil refers to selecting good places to insert kashida.

Current typesetting systems: In terms of text processing tools, curvilinear kashida is, generally, still beyond what the majority of typesetting systems can offer. As we have seen, kashida is not a character in itself, but an elongation of some letter parts. To implement kashida, the majority of typesetting systems proceed by inserting rectilinear segments between letters. The resulting typographical quality is unpleasant. Due to the lack of adequate tools, the solution consists of inserting a glyph. That is, rather than computing parameterized Bézier curves in real time, a ready-to-use glyph is inserted. Moreover, whenever stretching is performed by means of a parameterized glyph coming from an external dynamic font, the current font context is changed.

Curvilinear extensibility of glyphs can be offered through the a priori generation of curvilinear glyphs for some predefined sizes. Beyond these sizes, the system will choose curvilinear primitive and linear fragments. Of course, this will violate the curvilinear shape of letters and symbols if they are extended greatly.

A better approach consists of building a dynamic font (Berry 1999; Lazrek 2003; Sherif and Fahmy 2008; Bayar and Sami 2009) through parameterizations of the composition procedure of each letter. To handle the elongations, a letter is decomposed into two parts: the static body of the letter and its dynamic part, capable of stretching. The introduced parameters indicate the extensibility size or degree.

Allographs

Essentially, there are up to four different shapes for each letter in Arabic: isolated, initial, median, or final form. Allographs are the various shapes that a letter can have while keeping its place in the word. For instance, the initial form of the letter Beh can have—in the same calligraphic style—more than one shape. Allometry is the study of the allograph phenomenon, shape, position, context, etc. Generally, allographs are chosen by the writer for aesthetic reasons. However, in Arabic calligraphy, sometimes an allograph is desired and even recommended. The shapes of letters may change according to the nature of the neighboring letters, and in some cases according to the presence of kashida. Some rules concerning use of the allograph are:

• the shape of the median form of the letter Beh should be more acute when it comes between two spine letters:
  
• the initial form of the letter Beh can take one of three allograph shapes, determined by the letter that follows:
  
• the initial form of the letter Hah should be a lawzi Hah if it precedes an ascending letter:
  
• the initial form of the letter Ain should be a finjani Ain if it precedes an ascending letter:
  
• the initial form of the letter Hah, as well as the final form of the letter Meem, change their morphologies in presence of kashida:
  
• the letter Kaf changes its morphological shape in case of stretching and should be changed into zinadi Kaf:
  

Back to Zapf and Thành

Adapting the approaches used to improve the justification of Latin text to Arabic typography does not seem to be the best solution. Zapf and Thành reasoned on the basis of Latin typography, where there are individual glyphs and no tools similar to kashida that can be used to justify lines. Indeed, kashida is not a simple horizontal scaling to enlarge letter width. In some cases, operation of kashida on the letter can totally change its glyph’s morphological shape (see figure 7). The use of kashida is governed by rules and customs inspired by manuals and treatises on Arabic calligraphy (Benaatia, Elyaakoubi, and Lazrek, 2006).

Figure 7:

Arabic stretching letter

Diacritic marks

A diacritical mark is a sign added to a letter, like the acute accent on the letter e which produces é. Diacritics are placed above or below letters, or in some other position such as within the letter or between two letters. In different scripts, diacritical marks have common phonetic and linguistic roles: they change the sound value of the letter to which they are added. However, in other alphabetic systems, diacritics may perform other functions. For example, Arabic vocalization marks indicate short vowels applied to consonantal base letters. This vocalization is sometimes omitted altogether in writing.

Arabic diacritical marks have an additional typographical role, which is to fill the void produced by position and juxtaposition of letters on the line. This task is influenced by the effects of Arabic text justification. If kashida is used to manage Arabic lines, it influences the positioning and the measurements of the Arabic diacritical marks (Hssini, Lazrek, and Benatia 2008) (see figure 8). Additionally, the presence of diacritical marks either above or below glyphs adds a vertical inter-line space that should be taken into account in vertical adjustments. Thus, the vertical document adjustment is more delicate.

In this paper we are considering text without taking into account the effect of vocalization, and we have chosen only to address horizontal justification, without considering vertical justification, which is also an issue in Arabic.

Figure 8:

Diacritical marks with various sizes

Glue/penalty model

In the glue/penalty model, a glyph or a ligature is represented by a box with fixed dimensions (width, height, depth) while spaces, or their equivalents, are represented by glues. The concept of glue is more general than that of space. Indeed, a glue is not an empty box with a fixed width; it can be stretched or shrunk. Therefore, in addition to its natural width, it has two more attributes: its stretchability and its shrinkability. The glues do not become wider or narrower in the same way as a normal space, but in proportion to their stretchability and shrinkability. For example, according to the English and German typographic traditions, the inter-word space should be increased whenever it comes after a punctuation mark ending a sentence. The glue in such situations should have more stretchability than a space between two words in the same line. The composition weakness of a text is determined, among other things, by the quality of its spacing. In a good composition, the glues approach their natural sizes. Meanwhile, the badness reflects the amount of space at the right margin.

A penalty is an element that we can insert in a horizontal list representing the paragraph to discourage or encourage the typesetting system to break the list at that place. A positive penalty indicates a bad breakpoint, whereas a negative one indicates a good breakpoint. A positive infinite penalty prevents breaks and a negative infinite penalty forces breaks. A penalty is associated with each breakpoint, even if this penalty is null. However, in some situations the composition presents an aesthetic cost. Consequently, there are many types of penalties. For example, the presence of hyphenation adds a non-null penalty. If two consecutive lines end with hyphen breaks, or if they are visually incompatible, positive penalties are added. A value measuring the composition quality is calculated according to glue badness and whole penalties are assigned to the current breakpoints or the current lines. The computed value is called demerit.

Algorithm

Considering the example of the section “Optimum-fit algorithm”, we demonstrate that the result given by the optimum-fit is more optimal than the result given by the greedy algorithm. The first one optimizes a square of the remaining spaces, also called badness of lines, to produce a more aesthetically satisfying result.

In this example, the horizontal list to break is: xxx xx xx xxxxx, for a line width 6. For simplicity, we consider a fixed-width font. If the cost of a line is defined by the square of remaining space, the greedy algorithm would give a sub-optimal solution for the problem, and would look like this:

The total cost equals 17. An optimal solution gives a total cost of 11 and it would look like this:

Donald Knuth proves that such optimization can be efficiently accomplished using dynamic programming. According to Knuth, a paragraph can be modelled by an acyclic graph. The candidate lines represent the edges of the graph, and a numerical value—the demerit—is assigned to each edge. The paragraph selected is the one represented by the shortest path of the graph. Figure 9 shows the acyclic graph modeling the paragraph in the previous example.

Figure 9:

Acyclic graph modeling the two versions of the same paragraph

A paragraph is a horizontal list that has to be broken into lines in an optimal way, depending on the run time as well as on the visual result. Of course, certain lines may be sacrificed to save the paragraph’s justification quality. In the beginning, a paragraph is represented by a long list of elements, called nodes: character node, ligature node, discretionary node, math node, penalty node, glue node, or kerning node, which can be explicitly set by the user or implicitly provided by the font. On the basis of this list, the algorithm will generate another list of nodes called feasible breakpoint nodes.[5] Each such node is characterized by three things:

• the position of this breakpoint in the horizontal list;
• the number of the line following this breakpoint;
• the fitness classification of the line ending at this breakpoint.

The strategy adopted by optimum-fit algorithm is:

1. Create an active node representing the beginning of the paragraph.
2. Run through the given horizontal list representing the paragraph.
3. For each legal breakpoint, run through the list of active nodes previously created.
4. Check if there is a way to achieve each feasible combination with the current breakpoint and create an active node in this place, if possible.
5. Assign a cost to the feasible line.
6. If two or more active nodes end a line at the same point, keep only the best one.
7. Choose the paragraph version with the optimal cost.

The algorithm creates the first active breakpoint node representing the beginning of the paragraph. The second active node is a feasible breakpoint depending on the first one; it can be a finite penalty node, a glue node, or a discretionary-hyphen node placed at an acceptable distance to make a potential line.

Acceptable distance

Let L be the inter-margin space and let l be the natural length of the material—boxes and glues—to put down in a line. Let X be the sum of stretching and Y the sum of shrinking of glues. If l < L, then the line needs to be stretched, and let r = (L-l)/X, a value needed to calculate the badness.

In practice, the line’s badness b is given by b=100 * r3. If this value exceeds 10000, the badness is treated as infinite. To save runtime, the algorithm tries first to make a paragraph without any hyphenation. The parameters pretolerance and tolerance are the limits on how bad a line can be before and after hyphenation, respectively. For simplicity, we will assume that hyphenation is never tried.[6] The badness is compared to pretolerance. If b < pretolerance, the breakpoint is feasible. Next, the fitness classification will be calculated for the line that has just ended:

• decent if 0 ≤ b ≤ 12
• loose if it has been stretched with 12 < b < 100
• very-looseif it has been stretched with b ≥ 100.

As we advance in the horizontal list of nodes, sometimes l becomes greater than L, then the line needs to be shrunk, in which case the value r = (l-L)/Y. The fitness classification will then be calculated:

• decent if 0 ≤ b ≤ 12
• tight if it has been shrunk with b > 12.

If r > 1, let b = ∞ + 1. It is important to distinguish between the situation where b = ∞ and that where b = ∞ + 1. In the first case, the current active node should be still active; in the second case, the current active node should no longer be active.

Normally, if everything goes well, and badness is less than pretolerance, the current node is placed at an acceptable distance to make a potential line. For each potential line, a demerit is calculated, taking into account the badness and the different penalties, which include:

• hyphenation penalty;
• double hyphenation penalty;
• penalty for adjacent incompatible lines.

Based on the badness tolerated on each line, and because the system can expand or contract inter-word spaces, the algorithm considers various ways to achieve a feasible line from the current active node. The nodes created in this way will be linked in a list.

If we are too far from an active node, i.e., l is sufficiently large than L, that node is deactivated. The newly generated nodes will be used to identify other active nodes and so on, until the paragraph’s end is reached. For formal reasons, the paragraph’s end is considered to be a breakpoint. After all, it is the end of a line. Given the different nodes, we build an acyclic graph. The vertices of this graph are the different feasible breakpoints, and the edges are pairs of adjacent nodes making a feasible line. The problem is then to find the shortest path of the graph, choosing from among all the candidate paragraphs the version with the smallest possible value for the total demerit. Therefore, the paragraph is chosen after considering all its lines.

If the paragraph contains n breakpoints, the number of situations that are to be evaluated naively is 2ⁿ. However, using the dynamic programming method, the complexity of the algorithm can be reduced to O(n²). Other simplifications can be evoked as well. For example, the system does not examine unlikely cases such as a break in the first word of the paragraph. This leads to an efficient algorithm with a running time almost of order n.

The following pseudo-code implements the optimum-fit algorithm:

Texteme and paragraph-breaking

The digital text representation model used today is the one proposed by the Unicode standard (Unicode Consortium 2006). It is based on the concepts of character and glyph. In the last few years, text processing tools have made use of characters first, while glyph issues are handled in the last stage, namely the rendering. Before being displayed, an e-document undergoes changes. In the beginning, a document is a string of structured characters. After processing, it becomes a string of glyphs arranged according to the rules of the typographic art.

Going from characters to glyphs and back can be a complicated process (Haralambous and Bella 2005a). One glyph can be associated with multiple characters and one character can be associated with multiple glyphs. Moreover, multiple glyphs can be associated with multiple characters in a different order.

Y. Haralambous proposes a new approach to the relationship between characters and glyphs: he merges them with a number of additional properties related to language presentation or other types of metadata into a single atomic text unit called texteme (Haralambous and Bella 2005b). A texteme is a set {c, g, p1 = v1 ... pn = vn}, where c is a character code, g a glyph index and a list of named properties p_i (1 ≤ i ≤ n) taking value v_i. A simple texteme is a pair (c, g) and a pointer to an empty list of properties; text processing can be considered to be a process of enriching textemes with properties.

This concept of textemes, along with dynamic typography, points to a new approach to paragraph-breaking (Haralambous and G. Bella 2006). This approach starts with a paragraph as a linked list of textemes. The text processing enriches the textemes with alternative glyph properties whenever the current font provides an alternative form for such a glyph. The breaking algorithm takes into account the existence of such alternative forms to provide more flexibility and therefore more possibilities for breaking. This approach suggests thinking on a more theoretical level for solving problems that are admittedly fundamental, but still mostly practical.

Smart fonts

A modern typesetting system should be able to manipulate the so-called “smart font” formats, such as OpenType. In an Arabic rendering process, OpenType tables can carry out the following basic functions:

• supply the glyph corresponding to the pair (character, contextual form);
• supply grammatical ligatures (ex. Lam-Alef) and aesthetic ones;
• supply specific alternative forms for glyphs depending on context;
• supply kerning between single or ligatured glyphs;
• place short vowels and other diacritics on isolated glyphs or on ligatured components.

One could imagine some of these features being contextual, with or without backtrack and look-ahead. OpenType also provides what we can call “super-OpenType” features, including the “jalt” (justification alternative) feature (Microsoft Corporation 2009). The jalt table shows some glyph variants—wider or narrower letters that are intended to improve justification. WYSIWYG (what you see is what you get) software would probably show all the variants and offer the user the choice in an interactive manner. Or better, this feature can assist the paragraph builder engine to optimize the paragraph typographical gray during justification. For example, this feature in the Arabic Typesetting font provides us stretched alternative forms for fourteen glyphs (see table 1).

Table 1:

jalt table in Arabic Typesetting font

As we have seen above, Arabic writing provides various techniques from its handwriting traditions to perform text justification. These techniques are not based on the insertion of variable spaces between words or the horizontal scaling of glyphs, but in changing the shapes of letters themselves. That is how Arabic avoids unpleasant spaces and presents a balanced page.

A paragraph builder algorithm, either one based on a simple line-by-line justification or one based on a paragraph, can use other glyph variants—wider or narrower—to improve line justifications. These variants could be ligatures, allographs, or stretched glyphs with kashida. It’s important not to break the strict rules governing the use of some allographs and to keep context in mind (Benaatia, Elyaakoubi, and Lazrek, 2006).

Such a text composition system, were it to be built, would allow us to distinguish between allographs for contextual use and glyph variants provided by the font for justification purposes. A “calt” (contextual alternative) table could specify the context where each substitution can occur. Thus, the contextual variants may be elements of the calt table while the variants used to improve justification may be elements of the jalt table.

Dynamic typography

Dynamic typesetting is a set of typesetting techniques where glyphs can be modified during the line break process. Gutenberg applied such techniques in the 42-line Bible. He was exploiting alternate forms, ligatures, and abbreviations to optimize justification on the line level.

Ligatures in the 42-line Bible were certainly a good way to achieve fine control over the widths of words. In Arabic script, ligatures are very numerous. Unlike Latin readers, Arabic readers are used to ligatures and our implementation is restricted to the use of simple substitutions rather than multiple substitutions or ligatures.

Our main motivation for designing a justification program is to add alternative forms to the paragraph-based line-breaking algorithm. That allows us to enhance the acyclic graph-modeling paragraph by introducing other breakpoint nodes so that the optimization of the paragraph will be improved. We recognize two breakpoint nodes that generate an acceptable distance for a potential line, and we build in a unique stretched alternative according to Arabic calligraphic rules (Benaatia, Elyaakoubi, and Lazrek, 2006).

For instance, suppose that a variable l contains the width produced by the group of glyphs and glues on the line, while L is the value where the line should be justified. We go through the horizontal list, and whenever a glyph node is encountered, we check if the jalt table provides another alternative. As long as we find no entries in the jalt, we proceed as in the ordinary optimum-fit algorithm. The value l is increased by the width of that glyph and the feasibility of the legal breakpoints is checked. This procedure consists of running through the active list to see what lines can be made from the active nodes to the current legal breakpoint node. An active node is generated for each feasible breakpoint and added to the active list.

If, however, the current node is a glyph with an alternative form in the jalt table, we calculate the difference between the two widths: the default glyph width and the alternative form width. The variable backward contains this difference. The widths of the two lines augment with a shift amount of backward. The badness is calculated twice, taking account of the backward produced by the alternative form.

We include two tests for the breakpoint feasibility: first using the default width, and second using the alternative form’s width. If all goes well, and one of the two values b₁or b₂ is less than the pretolerance, the current legal breakpoint is a feasible one, based on the default glyph’s use or the alternate form’s use. We create an active node and we label this node to indicate from which glyph use it came. We indicate the position of the glyph in the node we have created. If that node comes from the two calculations, and both badness b₁ and b₂ satisfy the feasibility condition, both demerits d₁ and d₂ are calculated, and we keep only the one with the minimal demerit, since the second situation will never be chosen in the final paragraph breaks. This process allows us to omit a substantial number of feasible breakpoints from the rest of the process. If the two demerits are close in value, we keep the composition with the non-stretched glyph.

If two stretchable letters occur in the same line, we consider the two possibilities of stretching, giving us the opportunity to avoid situations such as two elongations in two consecutive lines. However, we do not consider combinations of the two possibilities and we follow the convention of Arabic text justification (Benaatia, Elyaakoubi, and Lazrek, 2006) that prohibits the use of two elongations in the same line.

If a stretched line justifies better than a non-stretched line, the program considers it in the context of the rest of the paragraph, and may resort to the non-stretched line to make the paragraph work better.

Authorized and prohibited elongations

We wanted to determine the contexts behind the use of kashida and allographs (Benaatia, Elyaakoubi, and Lazrek, 2006) and to include Arabic’s graphical grammar. This study relies on an exploration in calligraphic compositions and historical references on the subject. Although our purpose was not to imitate handwriting, the best rules may be found in calligraphy. These rules take care not to replace the white “rivers” with black ones produced by successions of kashidas in consecutive lines. Some of these rules are mandatory, some are very common, and others are rare. Generally, when a calligrapher creates a visual work of art it is through intuition. We have tried to validate, formalize, and make some of that intuition explicit, but automating it is hard.

For instance, determining where to use kashida and allographs (Benaatia, Elyaakoubi, and Lazrek, 2006) can be based on graphic design—the number of kashidas and their degree of extensibility, their positions on the line, occurrences where stretching is allowed and so on—or semantic. For example, Vlad Atanasiu asserts that Ottoman calligraphers used the stretched Kaf, known as zinadi Kaf, to write the word kufr (disbelief) in order to stigmatize disbeliever persons (Atanasiu 2003).

Penalties are an efficient tool for communicating choices to the line-break process. Using penalties, a professional or a novice user can tell the system about his typographic and semantic preferences. In our model we associate penalties with each use of a stretched alternative form. These parameters specify the demerits added for lines. These penalties are independent from the line break; on the contrary, they depend on the use of the stretched alternative forms to achieve the line. Increasing the value of these parameters encourages the system to avoid prohibited elongations, even at the cost of other aesthetic considerations like avoiding too loose inter-word spacing. The user should assign a rather large value to these parameters to have an effect. The penalties themselves are of various types, explained below.

Position penalty

The historical references on the legitimate places for kashida differ in some details (Benaatia, Elyaakoubi, and Lazrek, 2006). In terms of justification, calligraphers use kashida at the end of a line because they can estimate the elongation only when they come near the limit of a line. Therefore, kashida is triggered by the distance from the end of line. Two elongations on two consecutive lines can only be seen as a defect. To avoid the “stairs” effect resulting from such superposition, a uniform typographical grid is useful.

In our model, for adjacent lines where two elongations are superposed, the system put a penalty on the second line. The superposition of three elongations on three adjacent lines evokes, of course, a higher penalty.

Occurrence penalty

By classifying words according to their number of letters, we can identify where stretching is allowed (Benaatia, Elyaakoubi, and Lazrek, 2006). Generally, it is strictly prohibited to stretch a word with two letters and usually kashida is not used in a word composed of three letters. Words with four letters are the most susceptible to stretching, and it is preferable to use kashida in the second letter.

We also incorporate rules concerning degrees of extensibility for each letter according to its context (Benaatia, Elyaakoubi, and Lazrek, 2006). For example, the elongation of letter Beh is authorized, but not approved, if it is followed by Alef, Jeem, Dal, Reh, and Lam; it is authorized and also approved if it is followed by Tah; and it is prohibited if it is followed by Ain, Seen, Feh, Qaf and Kaf. If elongation is authorized, the letter Beh can be stretched up to twelve diacritic points.

In our model, a pointer variable runs through the given horizontal list as we look for breakpoints. Another variable stays a step behind this pointer, and a second one stays two steps behind the pointer variable running through the horizontal list. These variables allow us to analyze the context of a glyph if it has an alternative form in the jalt. We add penalties where elongations are strictly prohibited. In the other cases, we should be parsimonious in the use of penalties in order to not compromise the typographical gray quality.

Semantic penalties

Contrary to the previous types of penalties, the semantic penalties depend on where the break occurs. Increasing the value of these penalties will encourage the system to avoid some semantically prohibited breaking, for example, between two words where a break is not recommended, such as within person’s name or inside a compound word.