String-to-string correction problem
- String-to-string correction problem
Citation enhancement. Please you see. Any concerns? Please . The string-to-string correction problem refers to the minimum number of editoperations necessary to change one string into another. A single editoperation may be changing a single symbol of the string intoanother, deleting, or inserting a symbol. The length of the edit sequenceprovides a measure of the distance between the two strings.
Several algorithms exist to provide an efficient way to determine stringdistance and specify the minimum number of transformation operationsrequired. Such algorithms are particularly useful for delta creationoperations where something is stored as a set of differences relative to a baseversion. This allows several versions of a single object to be stored much moreefficiently than storing them separately. This holds true even for single versions of several objects if they do not differ greatly, or anything in between. Notably, such difference algorithms are used in
molecular biology to provide some measure of kinship between different kinds oforganisms based on the similarities of their macromolecules (such as proteins or
DNA).
See also
* Delta encoding
* Levenshtein distance
References
*cite journal | author=Robert A. Wagner and Michael J. Fischer | title= The String-to-String Correction Problem| journal= Journal of the ACM | volume=21 | issue=1 | year=1974 | pages=168–173 | doi= 10.1145/321796.321811
*cite journal | author=Walter F. Tichy | title= The string-to-string correction problem with block moves| journal= ACM Transactions on Computer Systems | volume=2 | issue=4 | year=1984 | pages=309–321 | doi= 10.1145/357401.357404
Wikimedia Foundation.
2010.
Look at other dictionaries:
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
Hierarchy problem — In theoretical physics, a hierarchy problem occurs when the fundamental parameters (couplings or masses) of some Lagrangian are vastly different (usually larger) than the parameters measured by experiment. This can happen because measured… … Wikipedia
Doublet-triplet splitting problem — In particle physics, the doublet triplet (splitting) problem is a problem of some Grand Unified Theories, such as SU(5), SO(10), E 6. Grand unified theories predict Higgs bosons (doublets of SU(2)) arise from representations of the unified group… … 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
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
Needleman–Wunsch algorithm — The Needleman–Wunsch algorithm performs a global alignment on two sequences (called A and B here). It is commonly used in bioinformatics to align protein or nucleotide sequences. The algorithm was published in 1970 by Saul B. Needleman and… … Wikipedia
Algorithme de Wagner-Fischer — L algorithme de Wagner Fisher est un algorithme de recherche de distance de Levenshtein. Il s agit du nombre minimum d opérations à effectuer pour passer d une chaine à une autre en n utilisant que 3 opérations : suppression d un caractère,… … Wikipédia en Français
Michael J. Fischer — Michael John Fischer (born 1942) is a computer scientist who works in the fields of distributed computing, parallel computing, cryptography, algorithms and data structures, and computational complexity. Contents 1 Career 2 Work 2.1 … Wikipedia
Gosling Emacs — (often shortened to Gosmacs or gmacs ) was an Emacs implementation written in 1981 by James Gosling in C. It was the first Emacs to run under Unix. Its extension language, Mocklisp, has a syntax that appears similar to Lisp, but Mocklisp has no… … Wikipedia
Delta encoding — Not to be confused with Elias delta coding. Delta encoding is a way of storing or transmitting data in the form of differences between sequential data rather than complete files; more generally this is known as data differencing. Delta encoding… … Wikipedia
