LINGUIST List 11.1288

Thu Jun 8 2000

Books: Computational Linguistics

Editor for this issue: Scott Fults <scottlinguistlist.org>

Directory

1. Kim Lewis Brown, Computational Ling: Time Warps, String Edits & Macromolecules

Sankoff, David (University of Montreal); Kruskal, Joseph (Bell Labs); 
foreword by John Nerbonne; TIME WARPS, STRING EDITS AND 
MACROMOLECULES; paperback ISBN: 1575862174; 408 pages. CSLI 
Publications 2000: http://cslipublications.stanford.edu email 
pubscsli.stanford.edu.

Time Warps, String Edits and Macromolecules is a young classic in
computational science, scientific analysis from a computational
perspective, reissued with a foreword by John Nerbonne. The
computational perspective is that of sequence processing, in
particular the problem of recognizing related sequences. The book is
the first, and still best compilation of papers explaining how to
measure distance between sequences, and how to compute that measure
effectively. This is called string distance, Levenshtein distance, or
edit distance. The book contains lucid explanations of the basic
techniques; well-annotated examples of applications; mathematical
analysis of its computational (algorithmic) complexity; and extensive
discussion of the variants needed for weighted measures, timed
sequences (songs), applications to continuous data, comparison of
multiple sequences and extensions to tree-structures. In molecular
biology the sequences compared are the macromolecules DNA and RNA.
Sequence distance allows the recognition of homologies
(correspondences) between related molecules. One may interpret the
distance between molecular sequences in terms of the mutations
necessary for one molecule to evolve into another. A further
application explores methods of predicting the secondary structure
(chemical bonding) of RNA sequences. In speech recognition speech
input must be compared to stored patterns to find the most likely
interpretation (e.g., syllable). Because speech varies in tempo, part
of the comparison allows for temporal variation, and is known as
"time-warping". In dialectology Levenshtein distance allows analysis
of the learned variation in pronunication, its cultural component.
Levenshtein distance introduces a metric which allows more
sophisticated analysis than traditional dialectology's focus on
classes of alternative pronunciations. A similar application is the
study of bird song, where degrees of distance in song are seen to
correspond to the divergence of bird populations. A final application
area is software, where Levenshtein distance is employed to located
differing parts of different versions of computer files, and to
perform error correction.

For more information about this book, contact CSLI Publications at
pubscsli.stanford.edu or go to our website
http://cslipublications.stanford.edu.

To order this book, contact Cambridge University Press: order online
at http://www.cup.cam.ac.uk/ or http://www.cup.org/ or call their toll
free number 1-800-872-7423 (USA only).


*************************
CSLI Publications
Ventura Hall
Stanford University
Stanford, CA 94305-4115
Telephone (650) 723-1839
Fax (650) 725-2166
http://cslipublications.stanford.edu/