Zobrazeno 1 - 10
of 35 230
pro vyhledávání: '"Edit Distance"'
Autor:
Nogler, Jakob, Polak, Adam, Saha, Barna, Williams, Virginia Vassilevska, Xu, Yinzhan, Ye, Christopher
The tree edit distance (TED) between two rooted ordered trees with $n$ nodes labeled from an alphabet $\Sigma$ is the minimum cost of transforming one tree into the other by a sequence of valid operations consisting of insertions, deletions and relab
Externí odkaz:
http://arxiv.org/abs/2411.06502
Several measures exist for string similarity, including notable ones like the edit distance and the indel distance. The former measures the count of insertions, deletions, and substitutions required to transform one string into another, while the lat
Externí odkaz:
http://arxiv.org/abs/2410.09877
Autor:
Baek, Ingyu
An exponent-string is an extension of traditional strings that can incorporate real-numbered exponents, indicating the quantity of characters. This novel representation overcomes the limitations of traditional discrete string by enabling precise data
Externí odkaz:
http://arxiv.org/abs/2408.12931
With the growing integration of AI in daily life, ensuring the robustness of systems to inference-time attacks is crucial. Among the approaches for certifying robustness to such adversarial examples, randomized smoothing has emerged as highly promisi
Externí odkaz:
http://arxiv.org/abs/2408.00728
Autor:
Rosenfeld, Matthieu
We study the average edit distance between two random strings. More precisely, we adapt a technique introduced by Lueker in the context of the average longest common subsequence of two random strings to improve the known upper bound on the average ed
Externí odkaz:
http://arxiv.org/abs/2407.18113
Publikováno v:
Advances in Neural Information Processing Systems, 38 (2024)
Graph Edit Distance (GED) measures the (dis-)similarity between two given graphs, in terms of the minimum-cost edit sequence that transforms one graph to the other. However, the exact computation of GED is NP-Hard, which has recently motivated the de
Externí odkaz:
http://arxiv.org/abs/2409.17687
Autor:
BOROUJENI, MAHDI1 safarnejad@ce.sharif.edu, EHSANI, SOHEIL2 ehsani@cs.umd.edu, GHODSI, MOHAMMAD3 ghodsi@sharif.edu, HAJIAGHAYI, MOHAMMADTAGHI2 hajiagha@cs.umd.edu, SEDDIGHIN, SAEED4 saeedreza.seddighin@ttic.edu
Publikováno v:
Journal of the ACM. May2021, Vol. 68 Issue 3, p1-41. 41p.
Autor:
Koucký, Michal, Saks, Michael
Edit distance is an important measure of string similarity. It counts the number of insertions, deletions and substitutions one has to make to a string $x$ to get a string $y$. In this paper we design an almost linear-size sketching scheme for comput
Externí odkaz:
http://arxiv.org/abs/2406.11225
Autor:
Gorbachev, Egor, Kociumaka, Tomasz
The edit distance of two strings is the minimum number of insertions, deletions, and substitutions needed to transform one string into the other. The textbook algorithm determines the edit distance of length-$n$ strings in $O(n^2)$ time, which is opt
Externí odkaz:
http://arxiv.org/abs/2404.06401