Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Markov edit distance.

Jie Wei1

  • 1Department 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

IEEE Transactions on Pattern Analysis and Machine Intelligence
|September 21, 2004
PubMed
Summary

A new Markov edit distance (MED) enhances string matching by considering local patterns, unlike traditional context-free edit distances. This novel approach improves performance in applications requiring nuanced string comparison.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

[Close reduction for the treatment of inferior intra-articular dislocation of patella:a case report and literature review].

Zhongguo gu shang = China journal of orthopaedics and traumatology·2019
Same author

Analgesic efficacy and safety of ketamine after total knee or hip arthroplasty: a meta-analysis of randomised placebo-controlled studies.

BMJ open·2019
Same author

In situ Spectroscopic Insight into the Origin of the Enhanced Performance of Bimetallic Nanocatalysts towards the Oxygen Reduction Reaction (ORR).

Angewandte Chemie (International ed. in English)·2019
Same author

A novel method for estimating nail-tract bone density for intertrochanteric fractures.

Journal of orthopaedic translation·2019
Same author

Endophilin A2 attenuates cardiac hypertrophy induced by isoproterenol through the activation of autophagy.

American journal of translational research·2019
Same author

Expression and clinical significance of CPS1 in glioblastoma multiforme.

Current research in translational medicine·2019

Area of Science:

  • Computer Science
  • Computational Linguistics
  • Bioinformatics

Background:

  • Edit distance, a fundamental string metric, is computed efficiently using dynamic programming.
  • Normalized edit distance aims for more reasonable string comparisons.
  • Traditional edit distance lacks context-awareness, ignoring local string behaviors.

Purpose of the Study:

  • To introduce a novel context-aware edit distance measure.
  • To leverage local statistical dependencies for enhanced string matching.
  • To develop specialized edit distance variants for specific pattern matching challenges.

Main Methods:

  • Development of Markov edit distance (MED) within a dynamic programming framework.
  • Introduction of reshuffling MED for handling rearranged subpatterns.
  • Creation of coherence MED for local content-aware edits (insertion, deletion, substitution).

Main Results:

  • MED effectively utilizes local statistical dependencies for improved matching.
  • Reshuffling MED demonstrates efficacy in identifying rearranged subpatterns.
  • Coherence MED shows promise in local content-based string matching.
  • Encouraging empirical results observed in string matching applications.

Conclusions:

  • Markov edit distance offers a significant advancement over traditional context-free measures.
  • The specialized MED variants address specific limitations in pattern matching.
  • This research provides a powerful new tool for various string comparison tasks.

Related Experiment Videos