Directed Replacement

Directed Replacement Lauri Karttunen Rank Xerox Research Centre Grenoble 6, chemin de Maupertuis F-38240 MEYLAN~ FRANCE lauri, karttunen@xerox, fr Abstract This paper introduces to the finite-state calculus a family of directed replace op- erators. In contrast to the simple re- place expression, UPPER -> LOWER, defined in Karttunen (1995), the new directed ver- sion, UPPER ©-> LOWER, yields an unam- biguous transducer if the lower language consists of a single string. It transduces the input string from left to right, mak- ing only the longest possible replacement at each point. A new type of replacement expression, UPPER @-> PREFIX ... SUFFIX, yields a transducer that inserts text around strings that are instances of UPPER. The symbol ... denotes the matching part of the input which itself remains unchanged. PREFIX and SUFFIX are regular expressions describ- ing the insertions. Expressions of the type UPPER @-> PI~EFIX •.. SUFFIX may be used to compose a de- terministic parser for a "local grammar" in the sense of Gross (1989). Other useful ap- plications of directed replacement include tokenization and filtering of text streams. 1 Introduction Transducers compiled from simple replace expres- sions UPPER -> LOWER (Karttunen 1995, Kempe and Karttunen 1996) are generally nondeterministic in the sense that they may yield multiple results even if the lower language consists of a single string. For example, let us consider the transducer in Figure 1, representing a b I b I b a I a b a-> x. 1 1The regular expression formalism and other nota- tional cdnventions used in the paper are explained in the Appendix at the end. a:x b:O b:x a:x Figure 1: a b I b I b a I a b a-> x . The four paths with "aba" on the upper side are: <0 a 0 b:x 2 a 0>, <0 a 0 b:x 2 a:0 0>, <0 a:x 1 b:0 2 a 0>, and <0 a:x 1 b:0 2 a:0 0>. The application of this transducer to the input "aba" produces four alternate results, "axa", "ax", "xa", and "x", as shown in Figure 1, since there are four paths in the network that contain "aba" on the upper side with different strings on the lower side. This nondeterminism arises in two ways. First of all, a replacement can start at any point. Thus we get different results for the "aba" depending on whether we start at the beginning of the string or in the middle at the "b". Secondly, there may be alter- native replacements with the same starting point. In the beginning of "aba", we can replace either "ab" or "aba". Starting in the middle, we can replace ei- ther "b" or "ba". The underlining in Figure 2 shows aba aba aba aba a X a a X X a X Figure 2: Four factorizations of "aba". the four alternate factorizations of the input string, that is, the four alternate ways to partition the string "aba" with respect to the upper language of the re- placement expression. …

Content truncated to 500 words