Per-Node Optimization of Finite-State Mechanisms for Natural Language

Abstract. Finite-state processing is typically based on structures that allow for efficient indexing and sequential search. However, this “rigid ” framework has several disadvantages when used in natural language processing, especially for non-alphabetical languages. The solution is to systematically introduce poly-morphic programming techniques that are adapted to particular cases. In this paper we describe the structure of a morphological dictionary implemented with finite-state automata using variable or polymorphic node formats. Each node is assigned a format from a predefined set reflecting its utility in corpora process-ing as measured by a number of graph theoretic metrics and statistics. Experi-mental results demonstrate that this approach permits a 52 % increase in the per-formance of dictionary look-up.