Fast computation of normalized edit distances

IEEE Transactions on Pattern Analysis and Machine IntelligencePublished 1 January 1995

Enrique Vidal, Andrés Marzal, Pablo Aibar

DOI10.1109/34.406656

Source URL

Citations54

SJR quartileQ1

SJR score3.91

SNIP5.99

TL;DR

This work proposes here an algorithm that is observed to require in practice the same 0(mn) computing resources as the conventional unnormalized edit distance algorithm does.

Abstract

The normalized edit distance (NED) between two strings X and Y is defined as the minimum quotient between the sum of weights of the edit operations required to transform X into Y and the length of the editing path corresponding to these operations. An algorithm for computing the NED was introduced by Marzal and Vidal (1993) that exhibits 0(mn/sup 2/) computing complexity, where m and n are the lengths of X and Y. We propose here an algorithm that is observed to require in practice the same 0(mn) computing resources as the conventional unnormalized edit distance algorithm does. The performance of this algorithm is illustrated through computational experiments with synthetic data, as well as with real data consisting of OCR chain-coded strings.>

Keywords

Computer ScienceBiochemistry, Genetics and Molecular Biology

IEEE Transactions on Acoustics Speech and Signal ProcessingDynamic programming algorithm optimization for spoken word recognition

6,544 Citations1978Hiroaki Sakoe, Seibi Chiba

This paper reports on an optimum dynamic progxamming (DP) based time-normalization algorithm for spoken word recognition, in which the warping function slope is restricted so as to improve discrimination between words in different categories.

Management ScienceOn Nonlinear Fractional Programming

3,132 Citations1967Werner Dinkelbach

Journal of the ACMThe String-to-String Correction Problem

3,063 Citations1974Robert A. Wagner, Michael J. Fischer

An algorithm is presented which solves the string-to-string correction problem in time proportional to the product of the lengths of the two strings.

View PDF

IEEE Transactions on Pattern Analysis and Machine IntelligenceComputation of normalized edit distance and applications

327 Citations1993Andrés Marzal, Enrique Vidal

Experiments in hand-written digit recognition are presented, revealing that the normalized edit distance consistently provides better results than both unnormalized or post-normalized classical edit distances.

IRE Transactions on Communications SystemsIsolated and Connected Word Recognition--Theory and Selected Applications

229 Citations1981L. R. Rabiner, S. Levinson

This paper discusses word recognition as a classical pattern-recognition problem and shows how some fundamental concepts of signal processing, information theory, and computer science can be combined to give us the capability of robust recognition of isolated words and simple connected word sequences.

IEEE Transactions on Information TheoryAn inequality for rational functions with applications to some statistical estimation problems

198 Citations1991P.S. Gopalakrishnan, Dimitri Kanevsky +2 more

The well-known Baum-Eagon inequality provides an effective iterative scheme for finding a local maximum for homogeneous polynomials with positive coefficients over a domain of probability values.

Modelling (Sub)String Length Based Constraints through a Grammatical Inference Method

45 Citations1987H. Rulot, Enrique Vidal

The results of the application of the proposed Grammatical Inference method to a (simple) Automatic Speech Recognition task are presented, showing its capability of achieving recognition rates which are higher than those obtained with the automata constructed by hand by experienced speech researchers.

Dynamic Time Warping Algorithms for Isolated and Connected Word Recognition

16 Citations1985Joseph Di Martino

A new formulation of the dynamic programming recursive relations both for word and connected word recognition that permits relaxation of boundary conditions imposed on the warping paths, while preserving the optimal character of theynamic time warping algorithms.

IEEE Transactions on Acoustics Speech and Signal ProcessingLSI implementation of a pattern matching algorithm for speech recognition

8 Citations1985Y. Kitazume, Eiji Ohira +1 more

This integrated circuit has been designed to be suitable for both isolated word recognition and connected speech recognition and has been tested in a pilot isolated-word and connected-speech recognition system.