2.1 An FST implementation

The XFST grammar is obtained by composing a large-scale lexicon of Hebrew (>20,000 entries) with a large set of rules, implementing mostly morphological and orthographic processes in the language. As the lexicon is developed independently (Itai, Wintner, and Yona Reference Itai, Wintner and Yona2006), and is represented in SQL and XML, it must be converted to XFST before it can be incorporated in the grammar. This is done by a set of Perl scripts that had to be specifically written for this purpose. In other words, the system itself is not purely finite state, and we maintain that few large-scale systems for morphological analysis can be purely finite state, as such systems must interact with independently developed components such as lexicons, annotation tools, user interfaces, etc.

Since the lexicon was developed independently, the grammar had to be adapted to the format of the lexicon. In particular, the citation form of lexical items is the traditional one (e.g., singular masculine for nouns and adjectives and third person singular masculine past tense for verbs). Consequently, the XFST lexicon is based on such citation forms. For example, the XFST variable noun denotes the set of all lexical items whose part of speech is noun; by default, these nouns are singular masculine, and this is indicated by adding number singular to the lexical specification (some nouns are inherently plural, e.g., mim ‘water’, and they are specified as number plural in the lexicon). Hebrew has two plural suffixes, im and wt, and by default masculine nouns take the former and feminine nouns the latter. However, there are many exceptions to this rule, and hence idiosyncratic nouns are lexically specified as to which suffix they take. In the XFST version of the lexicon, this is indicated by concatenating plural im or plural wt to the lexical representation of (irregular) nouns. Figure 1 depicts the lexical representation of the noun xlwn ‘window’.

Fig. 1.

The XFST lexical representation of the noun xlwn ‘window’.

A specialized set of rules implements the morphological processes that apply to each major part of speech. For example, Figure 2 depicts a somewhat simplified version of the rule that accounts for the wt suffix of Hebrew nouns. This rule makes extensive use of composition (denoted by ‘.o.’) and replace rules (‘->’ and ‘<-’). The effect of this rule is dual: on the surface level, it accounts for alterations in the concatenation of the suffix with the stem (e.g., iih becomes ih, wt changes to wi, and a final h or t are elided); on the lexical level, it changes the specification of number from the default singular to plural.

Fig. 2.

XFST account of plural nouns.

The rule should be read from the center outwards. The variable noun denotes the set of all lexical items whose part of speech is noun. In XFST, a set of words is identified with the identity transduction that relates each word in the set with itself. The first composition on top of the noun transduction selects only those nouns whose plural attribute is lexically specified as wt. Of those, only the ones whose number attribute is singular are selected. Then, the value singular in the lexical (upper) string is replaced by plural in the context of immediately following the attribute number. In the surface (lower) language, meanwhile, a set of composition operators takes care of the necessary orthographic changes, and finally, the plural suffix wt is concatenated to the end of the surface string.

The organization of the rule as a sequence of compositions may be misleading at first blush; in actuality, the rule does not specify a sequence of replacements. Rather, this rule compiles into a single finite-state transducer that encodes all the possible relation pairs licensed by the rule. Specifically, this transducer will license pairs such as xlwn–xlwnwt (the default case); tlwnh–tlwnwt (final h elided); clxt–clxwt and mpit–mpiwt (final t elided); kmwt–kmwiwt (wt changes to wi); and qniih–qniwt (iih changes to ih).

This rule is a good example of how a single phenomenon is factored out and accounted for independently of other phenomena: the rule refers to lexical information, such as ‘number’ or ‘plural’, but completely ignores irrelevant information such as, say, gender. However, it also hints at how information is manipulated by regular expressions. Since finite-state networks have no memory, save for the state, all information is encoded by strings that are manipulated by the rules. Thus, a simple operation such as changing the value of the number feature from singular to plural must be carried out by the same type of replace rules that account for the changes to the surface form. There is no way to structure such information or encapsulate it, as is common in programming languages; specifically, there is no obvious way to group together features that form a natural bundle, such as agreement features.

2.2 A direct implementation

The alternative to FST is a direct implementation of a morphological analyzer in some general purpose, high-level programming language. Recent proposals in this spirit include the Zen toolkit for morphological and phonological processing of natural languages (Huet Reference Huet2005), which inspired the better known paradigm of Functional Morphology (Forsberg and Ranta Reference Forsberg and Ranta2004). In both paradigms, rules are expressed in a functional programming languages (Objective Caml and Haskell, respectively), and their compilation yields a decorated trie that can be efficiently traversed at run-time, resulting in highly efficient lookup.

We directly reimplemented the HAMSAH grammar as a Java program; this is conceptually a variant of the functional morphology paradigm. We used the more common object-oriented programming paradigm, rather than the functional one. The method we used was analysis by generation: we first generate all the inflected forms induced by the lexicon and store them in a database; then, analysis is simply a database lookup. It is common to think that for languages with rich morphology such a method is impractical. While this may have been the case in the past, contemporary computers can efficiently store and retrieve millions of inflected forms. Of course, this method would break in the face of an infinite lexicon (which can easily be represented with FST), but for most practical purposes, it is safe to assume that natural language lexicons are finite. We note in passing that the same approach was used for the first morphological analyzer of Hebrew (Shapira and Choueka Reference Shapira and Choueka1964), and a similar idea (precompilation of all possible prefixes, stems, and suffixes, reducing analysis to a little more than lookup) is used in the current state-of-the-art analyzer of Arabic (Buckwalter Reference Buckwalter2004).

To separate linguistic knowledge from processing code as much as possible, our Java implementation uses a database of rules, which are simple string transductions intended to account for simple (mostly morpheme boundary) morphological and orthographic alterations. When generating inflected forms, the program identifies certain conditions (e.g., a plural suffix wt is to be attached to a noun). It then looks up this condition in the rule database and retrieves the action to apply, depending on the suffix of the input string. An example of the rule database, with alterations pertaining to the suffix wt(cf. Figure 2), is depicted in Figure 3. For many morphological processes, solutions such as this can accurately stand for linguistic rules of the form depicted in Figure 2.

Fig. 3.

Direct account of plural nouns.

Note that rules such as the one depicted in Figure 3 are generation rules, and must not be confused with the kind of ad hoc rules used at run-time, for example, stemming. They fully reflect the linguistic knowledge encoded in finite-state replace rules. Granted, the example rule is simplistic, and more complex phenomena require more complicated representations. For example, Hebrew inflectional morphology involves morpho-phonological alternations mostly along morpheme boundaries. In other languages, phenomena of vowel harmony that can spread across several morphemes may require more sophisticated solutions.

In addition, we preferred to formulate the grammar rules such that phonological (and orthographic) changes go hand in hand with morphological changes. It would have been possible to separate strictly phonological processes from affixation processes, and such an approach might have yielded a more compact grammar; in our approach, different affixation processes that trigger the same phonological or orthographic process have to duplicate the stipulation of the phonological change. The main reason for this is that this was how the finite-state grammar was designed, and the direct implementation attempted to be as faithful as possible to the original grammar. For our purposes, then, the rule database solution is a reasonable representation. Grammars for other languages may resort to a more sophisticated representation of the rules, either along the lines of functional morphology or as (simple) regular expressions.

The morphological analyzer was obtained by directly implementing the rules and applying them to the lexicon. The number of inflected forms (before attaching prefixes) is 473,880 (>300,000 of those are inflected nouns and close to 150,000 are inflected verb forms). In addition to inflected forms, the analyzer also allows as many as 174 different sequences of prefix particles to be attached to words; separation of prefixes from inflected forms is done at analysis time, since such combinations do not involve any morpho-phonological alternations. In principle, we could have generated all the possible surface forms (including prefixes) off-line, in which case analysis would strictly amount to lookup. The number of forms would then have been approximately 50 million (not all the prefixes combine with all word categories). While this would still be easily manageable with contemporary memory sizes, we acknowledge that for some languages, especially agglutinative ones, such a solution may not be adequate at present, although it may become feasible in the near future with the rapid decrease in the cost of memory.

The direct implementation is equivalent to the finite-state grammar: this was verified by exhaustively generating all the inflected forms with each of the systems and analyzing them with the other system.

3.1 Faithfulness

One of the assets of FST is that it allows for a very accurate implementation of linguistic rules. However, a good organization of the software can provide a clear separation between linguistic knowledge and processing in any programming environment, so that linguistic rules can be expressed concisely and declaratively, as exemplified in Figure 3. Our conclusion is that while for a linguistically accurate modeling of natural language phenomena, FST remains superior, from an engineering point of view, the two approaches are comparable.

3.2 Reversibility

A clear advantage of FST is that grammars are fully reversible. However, with the analysis by generation paradigm the same holds also for a direct implementation: the generator is directly implemented, and the analyzer is implemented as search in the database of generated forms.

3.3 Expressivity

Here, the disadvantages of FST as a programming environment are clear. Programming with FST is very different from programming in ordinary languages, mainly due to the highly constrained expressive power of regular relations (programmers sometimes feel that they are working with their hands tied behind their backs). Sometimes the expression of morphological phenomena requires more than regular power (as in the case of reduplication); more frequently, regular relations suffice, but grammar designers trained as programmers wish they had access to operators that are not regular. A typical example is the rule that doubles the final consonant of English verbs before some suffixes: one would want to express such a rule as ‘change a consonant C to CC when it is in the context of following a consonant and a vowel and preceding a vowel’. With regular expressions, this can only be done by stipulating all the consonants C and their doubled form.

3.4 Portability

XFST is a proprietary package with three versions available for three common operating systems. Other finite-state toolboxes are freer; FSA is open source, but as we noted earlier, it simply cannot cope with grammars the size of HAMSAH. FSM is available for a variety of Unix operating systems, as a binary only, whereas INTEX is distributed as a Windows executable. In contrast, a Java implementation can be delivered to users with all kinds of (contemporary) operating systems and hardware, and is optimally portable. The practical portability limitations directly hamper the utilization of FST in practical, commercial systems: this has been an issue both with the Hebrew HAMSAH and with a morphological grammar for Turkish (K. Oflazer, personal communication 2007)

3.5 Abstraction

Large-scale morphological grammars tend to be extremely non-modular. Each surface string is associated, during its processing, with a lexical counterpart that describes its structure. The lexical string is constantly rewritten by the rules, as in Figure 2. There are very limited facilities for grouping together related features, abstracting away from the actual representation, modularizing the grammar, etc.

Since information cannot be encapsulated and the language provides no abstraction mechanisms, collaborative development of finite-state grammars is difficult. All grammar developers must be aware of how information is represented at all times. Furthermore, since the only data type is strings, debugging becomes problematic: very few errors can be detected at compile time. In contrast, a direct implementation benefits from all the advantages of developing in a high-level programming environment.

An additional limitation of XFST is that it only provides two levels of representation, surface and lexical. Consequently, information pertaining to various strata of linguistic representation are coerced into two levels, and cleanup rules must be used as part of the grammar to eliminate intermediate layers that are less important for the final analysis. Consider Figures 1 and 2, which depict orthographic information (xlwn), morpho-syntactic features (number singular), exception features (plural wt), and full semantic glosses, all represented in two levels of strings.

3.6 Maintenance

A byproduct of the nonmodularity of FST grammars is that maintaining them is difficult and expensive. It is hard to find a single person who is knowledgeable in all aspects of the design, and any change in the grammar is painful. A direct implementation in a high-level language provides access to sophisticated debugging mechanisms that are missing altogether from FST frameworks, including XFST. This must be added to the poor compile-time performance (see below), which again hampers maintainability.

3.7 Compile-time efficiency

A major obstacle in the development of XFST grammars is the speed of compilation. Let us first recall a few theoretical (worst case) results. As is well known, many of the finite-state operators result in huge networks: theoretically, composition of networks of m and n states yields a network with O(m × n) states, and replace rules are implemented using composition. While automata can always be minimized, this is not the case for transducers (Mohri Reference Mohri2000). Theoretically, it is very easy to come up with very small regular expressions whose compilation is intractable. For any integer n > 2, there exists an n-state automaton A, such that any automaton that accepts the complement of L(A) needs at least 2^n-2 states (Holzer and Kutrib Reference Holzer and Kutrib2002). An example of an XFST expression whose compilation time is exponential in n is: ^~[ [a|b]* a [a|b]^n b [a|b]* ].

Of course, this worst case behavior is not worse than that of a direct implementation in an arbitrary programming language, where programmers are free to write arbitrary code. A more meaningful comparison must be in terms of actual performance. As it turns out, large-scale grammars such as HAMSAH yield temporary networks that are sometimes larger than the available memory, requiring disk access and thereby slowing compilation down dramatically. The complete Hebrew grammar is represented, in XFST, by a network of approximately 2 million states and 2.2 million transitions. Compiling the entire network takes more than 48 minutes and requires 3 Gb of memory. To verify that this was not an issue of limited machine memory, we repeated the experiment on a similar machine with 16 Gb of memory (compared with the 2.5 Gb used for all the experiments). This reduced compilation time to 25 minutes.

Compilation time is usually considered a negligible criterion for evaluating system performance. However, when developing a large-scale system, the ability to make minor changes and quickly remake the system is crucial. With XFST, modification of even a single lexical entry requires at least an intersection of (the XFST representation of) this entry with the network representing the rules that apply to it. As a concrete example, adding a single two-character proper name (which does not inflect) to the lexicon increased the size of the network by nine states and ten arcs, but took almost 3 minutes to compile. Adding a two-character adjective resulted in the addition of 27 states and 30 arcs, and took about the same time. A major contribution to this poor performance may be the fact that the features and glosses used for the analyses were all multi-character symbols, which increase the memory requirements of the compiled network.

In the direct implementation, modification of a single lexical entry requires generation of all inflected forms of this entry, which takes a fraction of a second; the time it takes to generate k lexical entries is proportional to k and is independent of the size of the remainder of the system. The analysis program is not altered.

To summarize the differences, Table 1 shows the time it takes to compile a network when k lexical entries are modified, for three values of k, corresponding to the number of adjectives, adverbs, and the size of the entire lexicon. This time is compared with the time it takes to generate all inflected forms of these sublexicons in the analysis by generation paradigm.Footnote ¹

Table 1.

Compilation/generation times (in minutes) when some lexical items change

3.8 Run-time efficiency

While finite-state automata guarantee linear recognition time, this is not the case with transducers, which cannot always be determinized (Mohri Reference Mohri1997). Even when a device can be determinized, the determinization algorithm is inefficient (theoretically, the size of the deterministic automaton can be exponential in the size of its nondeterministic counterpart).

As it turns out, storing a database of half a million inflected forms (along with their analyses) is inexpensive, and retrieving items from the database can be done very efficiently. We experimented with two versions: one uses MySQL as the database and the other loads the inflected forms into a hash table. In this latter version, most of the time is spent on loading the database, and retrieval time is negligible.

We compared the performance of the two systems on four tasks, analyzing text files of 10, 100, 1,000, and 10,000 tokens. The results are summarized in Table 2, and clearly demonstrate the superiority of the direct implementation. In terms of memory requirements, XFST requires approximately 57 Mb of memory, whereas the Java implementation uses no more than 10 Mb. This is not a significant issue with contemporary hardware.

Table 2.

Time performance of both analyzers (in seconds)