A k-mismatch string matching for generalized edit distance using diagonal skipping method.

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 calc...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	HyunJin Kim
Formato:	article
Lenguaje:	EN
Publicado:	Public Library of Science (PLoS) 2021
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/8d105c73a6d94b1aa57f78c737f12d3a
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:8d105c73a6d94b1aa57f78c737f12d3a
record_format	dspace
spelling	oai:doaj.org-article:8d105c73a6d94b1aa57f78c737f12d3a2021-11-25T06:19:22ZA k-mismatch string matching for generalized edit distance using diagonal skipping method.1932-620310.1371/journal.pone.0251047https://doaj.org/article/8d105c73a6d94b1aa57f78c737f12d3a2021-01-01T00:00:00Zhttps://doi.org/10.1371/journal.pone.0251047https://doaj.org/toc/1932-6203This 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.HyunJin KimPublic Library of Science (PLoS)articleMedicineRScienceQENPLoS ONE, Vol 16, Iss 5, p e0251047 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q HyunJin Kim A k-mismatch string matching for generalized edit distance using diagonal skipping method.
description	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.
format	article
author	HyunJin Kim
author_facet	HyunJin Kim
author_sort	HyunJin Kim
title	A k-mismatch string matching for generalized edit distance using diagonal skipping method.
title_short	A k-mismatch string matching for generalized edit distance using diagonal skipping method.
title_full	A k-mismatch string matching for generalized edit distance using diagonal skipping method.
title_fullStr	A k-mismatch string matching for generalized edit distance using diagonal skipping method.
title_full_unstemmed	A k-mismatch string matching for generalized edit distance using diagonal skipping method.
title_sort	k-mismatch string matching for generalized edit distance using diagonal skipping method.
publisher	Public Library of Science (PLoS)
publishDate	2021
url	https://doaj.org/article/8d105c73a6d94b1aa57f78c737f12d3a
work_keys_str_mv	AT hyunjinkim akmismatchstringmatchingforgeneralizededitdistanceusingdiagonalskippingmethod AT hyunjinkim kmismatchstringmatchingforgeneralizededitdistanceusingdiagonalskippingmethod
_version_	1718413876362477568

A k-mismatch string matching for generalized edit distance using diagonal skipping method.

Ejemplares similares