Linked Life Data

15376879

Source:http://linkedlifedata.com/resource/pubmed/id/15376879

Statements in which the resource exists as a subject.
PredicateObject
rdf:type
lifeskim:mentions
pubmed:issue
3
pubmed:dateCreated
2004-9-20
pubmed:abstractText
Edit distance was originally developed by Levenstein several decades ago to measure the distance between two strings. It was found that this distance can be computed by an elegant dynamic programming procedure. The edit distance has played important roles in a wide array of applications due to its representational efficacy and computational efficiency. To effect a more reasonable distance measure, the normalized edit distance was proposed. Many algorithms and studies have been dedicated along this line with impressive performances in recent years. There is, however, a fundamental problem with the original definition of edit distance that has remained elusive: its context-free nature. In determining the possible actions, i.e., insertion, deletion, and substitution, no systematic consideration was given to the local behaviors of the string/pattern in question that indeed encompass great amount of useful information regarding its content. In this paper, inspired by the success of the Markov Random Field theory, a new edit distance called Markov edit distance (MED) within the dynamic programming framework is proposed to take full advantage of the local statistical dependencies in the pattern in order to arrive at enhanced matching performance. Within this framework, two specialized distance measures are developed: The reshuffling MED to handle cases where a subpattern in the target pattern is the reshuffles of that in the source pattern, and the coherence MED which is able to incur local content based substitution, insertion, and deletion. The applications based on these two MEDs in string matching are then explored, whereof encouraging empirical results have been observed.
pubmed:language
eng
pubmed:journal
pubmed:citationSubset
IM
pubmed:status
MEDLINE
pubmed:month
Mar
pubmed:issn
0162-8828
pubmed:author
pubmed:issnType
Print
pubmed:volume
26
pubmed:owner
NLM
pubmed:authorsComplete
Y
pubmed:pagination
311-21
pubmed:dateRevised
2006-11-15
pubmed:meshHeading
pubmed:year
2004
pubmed:articleTitle
Markov edit distance.
pubmed:affiliation
Department of Computer Science, The City College of the City University of New York, Convent Ave. @ 138th Street, New York, New York 10031, USA. wei@cs.ccny.cuny.edu
pubmed:publicationType
Journal Article, Comparative Study, Evaluation Studies