Edit distance

Edit distance

In information theory and computer science, the edit distance between two strings of characters is the number of operations required to transform one of them into the other. There are several different algorithms to define or calculate this metric:

*Hamming distance
*Levenshtein distance
*Damerau-Levenshtein distance
*Jaro-Winkler distance
*Wagner-Fischer edit distance
*Ukkonen
*Hirschberg's algorithm

ee also

* Fuzzy string searching

External links

* [http://search.cpan.org/dist/Text-WagnerFischer Text::WagnerFischer] , a Perl implementation of the Wagner-Fischer edit distance


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • edit distance — noun A string distance …   Wiktionary

  • Édit de Pîtres — Denier de Charles le Chauve frappé à Tours 843 864 L Édit de Pîtres ou de Pistres (latin Edictun Pistense) est un capitulaire promulgué par Charles II le Chauve à la deuxième des quatre assemblées (conciles) réunies à Pîtres sous son règne entre… …   Wikipédia en Français

  • Damerau–Levenshtein distance — In information theory and computer science, the Damerau–Levenshtein distance (named after Frederick J. Damerau and Vladimir I. Levenshtein) is a distance (string metric) between two strings, i.e., finite sequence of symbols, given by counting the …   Wikipedia

  • Levenshtein distance — In information theory and computer science, the Levenshtein distance is a string metric for measuring the amount of difference between two sequences. The term edit distance is often used to refer specifically to Levenshtein distance. The… …   Wikipedia

  • Hirschberg's algorithm — Hirschberg s algorithm, named after its inventor, Dan Hirschberg, is a dynamic programming algorithm that finds the least cost sequence alignment between two strings, where cost is measured as Levenshtein edit distance, defined to be the sumof… …   Wikipedia

  • Fuzzy string searching — Approximate string search is the name that is used for a category of techniques for finding strings that approximately match some given pattern string. It may also be known as approximate or inexact matching. Approximate string searching has two… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • diff — This article is about the file comparison utility. For other uses, see DIFF (disambiguation). Diffs redirects here. For the American punk rock group, see The Diffs. In computing, diff is a file comparison utility that outputs the differences… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”