Log in

Relevant bibliographies by topics / Edit distance

Contents

Journal articles

Academic literature on the topic 'Edit distance'

Author: Grafiati

Published: 4 June 2021

Last updated: 13 June 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Edit distance.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Edit distance"

1

Petty, Taylor, Jan Hannig, Tunde I. Huszar, and Hari Iyer. "A New String Edit Distance and Applications." Algorithms 15, no. 7 (2022): 242. http://dx.doi.org/10.3390/a15070242.

Full text

Abstract:

String edit distances have been used for decades in applications ranging from spelling correction and web search suggestions to DNA analysis. Most string edit distances are variations of the Levenshtein distance and consider only single-character edits. In forensic applications polymorphic genetic markers such as short tandem repeats (STRs) are used. At these repetitive motifs the DNA copying errors consist of more than just single base differences. More often the phenomenon of “stutter” is observed, where the number of repeated units differs (by whole units) from the template. To adapt the Levenshtein distance to be suitable for forensic applications where DNA sequence similarity is of interest, a generalized string edit distance is defined that accommodates the addition or deletion of whole motifs in addition to single-nucleotide edits. A dynamic programming implementation is developed for computing this distance between sequences. The novelty of this algorithm is in handling the complex interactions that arise between multiple- and single-character edits. Forensic examples illustrate the purpose and use of the Restricted Forensic Levenshtein (RFL) distance measure, but applications extend to sequence alignment and string similarity in other biological areas, as well as dynamic programming algorithms more broadly.

APA, Harvard, Vancouver, ISO, and other styles

2

Akutsu, Tatsuya, Daiji Fukagawa, and Atsuhiro Takasu. "Approximating Tree Edit Distance through String Edit Distance." Algorithmica 57, no. 2 (2008): 325–48. http://dx.doi.org/10.1007/s00453-008-9213-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Hyyrö, Heikki, and Shunsuke Inenaga. "Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions." International Journal of Foundations of Computer Science 29, no. 04 (2018): 623–45. http://dx.doi.org/10.1142/s0129054118410083.

Full text

Abstract:

Kim and Park [A dynamic edit distance table, J. Disc. Algo., 2:302–312, 2004] proposed a method (KP) based on a “dynamic edit distance table” that allows one to efficiently maintain unit cost edit distance information between two strings [Formula: see text] of length [Formula: see text] and [Formula: see text] of length [Formula: see text] when the strings can be modified by single-character edits to their left or right ends. This type of computation is useful e.g. in cyclic string comparison. KP uses linear time, [Formula: see text], to update the distance representation after each single edit. Recently Hyyrö et al. [Incremental string comparison, J. Disc. Algo., 34:2-17, 2015] presented an efficient method for maintaining the dynamic edit distance table under general weighted edit distance, running in [Formula: see text] time per single edit, where [Formula: see text] is the maximum weight of the cost function. The work noted that the [Formula: see text] space requirement, and not the running time, may be the main bottleneck in using the dynamic edit distance table. In this paper we take the first steps towards reducing the space usage of the dynamic edit distance table by RLE compressing [Formula: see text] and [Formula: see text]. Let [Formula: see text] and [Formula: see text] be the lengths of RLE compressed versions of [Formula: see text] and [Formula: see text], respectively. We propose how to store the dynamic edit distance table using [Formula: see text] space while maintaining the same time complexity as the previous methods for uncompressed strings.

APA, Harvard, Vancouver, ISO, and other styles

4

Jie Wei. "Markov edit distance." IEEE Transactions on Pattern Analysis and Machine Intelligence 26, no. 3 (2004): 311–21. http://dx.doi.org/10.1109/tpami.2004.1262315.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Kim, HyunJin. "A k-mismatch string matching for generalized edit distance using diagonal skipping method." PLOS ONE 16, no. 5 (2021): e0251047. http://dx.doi.org/10.1371/journal.pone.0251047.

Full text

Abstract:

This paper proposes an approximate string matching with k-mismatches when calculating the generalized edit distance. When the edit distance is generalized, more sophisticated string matching can be provided. However, the execution time increases because of the bundle of complex computations for calculating complicated edit distances. The computational costs for finding which steps or edit distances are over k-mismatches cannot be significant in the generalized edit distance metric. Therefore, we can reduce the execution time by determining steps over k-mismatches and then skipping them. The diagonal step calculations using the pruning register skips unnecessary distance calculations over k-mismatches. The overhead of control statements and reordered memory accesses can be amortized by skipping multiple steps. Even though the proposed skipping method requires additional overhead, the proposed scheme’s practical embodiments show that the execution time of string matching is reduced significantly when k is small.

APA, Harvard, Vancouver, ISO, and other styles

6

McGrane, Martin, and Michael A. Charleston. "Biological Network Edit Distance." Journal of Computational Biology 23, no. 9 (2016): 776–88. http://dx.doi.org/10.1089/cmb.2016.0062.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Ristad, E. S., and P. N. Yianilos. "Learning string-edit distance." IEEE Transactions on Pattern Analysis and Machine Intelligence 20, no. 5 (1998): 522–32. http://dx.doi.org/10.1109/34.682181.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Myers, R., R. C. Wison, and E. R. Hancock. "Bayesian graph edit distance." IEEE Transactions on Pattern Analysis and Machine Intelligence 22, no. 6 (2000): 628–35. http://dx.doi.org/10.1109/34.862201.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Aratsu, Taku, Kouichi Hirata, and Tetsuji Kuboyama. "Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes." Fundamenta Informaticae 101, no. 3 (2010): 157–71. http://dx.doi.org/10.3233/fi-2010-282.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Cortés, Xavier, Donatello Conte, and Hubert Cardot. "Learning edit cost estimation models for graph edit distance." Pattern Recognition Letters 125 (July 2019): 256–63. http://dx.doi.org/10.1016/j.patrec.2019.05.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

More sources

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!