English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The edit distance is a metric of dissimilarity between strings, widelyapplied in computational biology, speech recognition, and machine learning. Let$e_k(n)$ denote the average edit distance between random, independent stringsof $n$ characters from an alphabet of size $k$. For $k \geq 2$, it is an openproblem how to efficiently compute the exact value of $\alpha_{k}(n) =e_k(n)/n$ as well as of $\alpha_{k} = \lim_{n \to \infty} \alpha_{k}(n)$, alimit known to exist.  This paper shows that $\alpha_k(n)-Q(n) \leq \alpha_k \leq \alpha_k(n)$, fora specific $Q(n)=\Theta(\sqrt{\log n / n})$, a result which implies that$\alpha_k$ is computable. The exact computation of $\alpha_k(n)$ is explored,leading to an algorithm running in time $T=\mathcal{O}(n^2k\min(3^n,k^n))$, acomplexity that makes it of limited practical use.  An analysis of statistical estimates is proposed, based on McDiarmid'sinequality, showing how $\alpha_k(n)$ can be evaluated with good accuracy, highconfidence level, and reasonable computation time, for values of $n$ say up toa quarter million. Correspondingly, 99.9\% confidence intervals of widthapproximately $10^{-2}$ are obtained for $\alpha_k$.  Combinatorial arguments on edit scripts are exploited to analyticallycharacterize an efficiently computable lower bound $\beta_k^*$ to $\alpha_k$,such that $ \lim_{k \to \infty} \beta_k^*=1$. In general, $\beta_k^* \leq\alpha_k \leq 1-1/k$; for $k$ greater than a few dozens, computing $\beta_k^*$is much faster than generating good statistical estimates with confidenceintervals of width $1-1/k-\beta_k^*$.  The techniques developed in the paper yield improvements on most previouslypublished numerical values as well as results for alphabet sizes and stringlengths not reported before.

Computable Bounds and Monte Carlo Estimates of the Expected Edit Distance