A novel string-to-string distance measure with applications to machine translation evaluati.pdf

A Novel String-to-String Distance Measure With Applications to Machine Translation Evaluation Gregor Leusch, Nicola Uef?ng, Hermann Ney Lehrstuhl f ¨ur Informatik VI RWTHAachen – University of Technology D-52056 Aachen, Germany, {leusch,ueffing,ney}***@- Abstract We introduce a string-to-string distance measure which extends the edit distance by block transpositions as con- stant cost edit operation. An algorithm for the calculation of this distance measure in polynomial time is pre- sented. We then showhowthis distance measure can be used as an evaluation criterion in machine translation. Its correlation with human judgment is pared with that of other automatic evaluation measures on two translation tasks. 1 Introduction One basic task in natural language processing (NLP), as well as other disciplines puta- tional biology (Waterman, 1995), paring se- quences of symbols with each other, deciding about their similarity. In NLP, sequences are designated as sentences, consisting ofwords. mon sense, sentences are considered to be the more similar the more words they share and the more their word orders resemble each other. Whereas for applications in speech recognition or optical character recognition reordering is of no con- sideration, there are applications where one expects reordering of single words and blocks between two sentences, like ?Grammar induc