LINGUIST List 11.1288

Thu Jun 8 2000

Books: Computational Linguistics

Editor for this issue: Scott Fults <>

Links to the websites of all LINGUIST's supporting publishers are available at the end of this issue.


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

Message 1: Computational Ling: Time Warps, String Edits & Macromolecules

Date: Tue, 6 Jun 2000 09:25:41 -0700
From: Kim Lewis Brown <kimcsli.Stanford.EDU>
Subject: 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: email

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 or go to our website

To order this book, contact Cambridge University Press: order online
at or 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
Mail to author|Respond to list|Read more issues|LINGUIST home page|Top of issue

----------------- Major Supporters ----------------

Academic Press

Arnold Publishers

Athelstan Publications

Blackwell Publishers

Cambridge UP -USA

Cascadilla Press

Elsevier Science Ltd.

John Benjamins

Kluwer Academic Publishers

Lernout & Hauspie

Lincom Europa

MIT Press

Mouton de Gruyter

Multilingual Matters

Oxford UP


St. Jerome Publishers

---------Other Supporting Publishers-------------

Finno-Ugrian Society

Graduate Linguistic Students' Assoc., Umass

IULC Publications

Kingston Press Ltd.

Linguistic Assoc. of Finland

Linguistic Society of Southern Africa (LSSA)

Orientalia et Africana Gothoburgensia

Pacific Linguistics

U. of Antwerp, Dept of Germanic Languages

U. of Arizona Press

U. of Huelva

U. of Marburg & Max Hueber Verlag

Utrecht Institute of Linguistics

Vaxjo: Acta Wexionesia

Virittaja Aikakauslehti
First Previous Next Last