History
Year:
-
Type:
Journal
Book
Article
Please fill in your query. A complete syntax description you will find on the General Help page.
Time warps, string edits, and macromolecules. Introduction by John Nerbonne. (English)
The David Hume Series of Philosophy and Cognitive Science Reissues. Stanford, CA: CSLI, Center for the Study of Language and Information. xxiv, 382 p. \sterling 13.95; \$ 22.95/pbk (1999).
[The articles of this volume will not be reviewed individually.] From the introduction: David Sankoff and Joseph Kruskal’s Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison (hereafter Time Warps) is a young (1983) classic which has inspired developments in computer science, pure and applied linguistics, computational biology, and even music and ethnology. CSLI Publications deserves the appreciation of all these scientific subfields for undertaking its republication. Because its first chapter, “Overview,” is Joseph Kruskal’s gentle introduction to Levenshtein distance (also known as sequence distance and edit distance), the book will be useful to students as well as researchers. The overview explores the concept of sequence distance first from the perspective of alignment ‒ finding the correspondence between sequences that minimizes distance. It goes on to introduce a dynamic programming algorithm which efficiently calculates the distance, and provide notes on the history of this and related concepts. Later chapters in Time Warps go on to explore several interesting extensions and applications in depth, including recognizing relatedness in DNA, matching speech input to lexical hypotheses, tracking the development of bird songs over time, and to error corrections (e.g., of keyboard input). Some of these chapters introduce significant refinements in order to handle transposed elements, continuous input (rather than sequences of discrete elements), and tree-structure.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!