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 problem is a classical fundamental problem in computerscience in general, and in combinatorial pattern matching in particular. Thestandard dynamic programming solution for this problem computes theedit-distance between a pair of strings of total length O(N) in O(N^2) time. Tothis date, this quadratic upper-bound has never been substantially improved forgeneral strings. However, there are known techniques for breaking this bound incase the strings are known to compress well under a particular compressionscheme. The basic idea is to first compress the strings, and then to computethe edit distance between the compressed strings. As it turns out, practicallyall known o(N^2) edit-distance algorithms work, in some sense, under the sameparadigm described above. It is therefore natural to ask whether there is asingle edit-distance algorithm that works for strings which are compressedunder any compression scheme. A rephrasing of this question is to ask whether asingle algorithm can exploit the compressibility properties of strings underany compression method, even if each string is compressed using a differentcompression. In this paper we set out to answer this question by using straightline programs. These provide a generic platform for representing many popularcompression schemes including the LZ-family, Run-Length Encoding, Byte-PairEncoding, and dictionary methods. For two strings of total length N havingstraight-line program representations of total size n, we present an algorithmrunning in O(nN log(N/n)) time for computing the edit-distance of these twostrings under any rational scoring function, and an O(n^{2/3}N^{4/3}) timealgorithm for arbitrary scoring functions. Our new result, while providing asigni cant speed up for highly compressible strings, does not surpass thequadratic time bound even in the worst case scenario.

Unified Compression-Based Acceleration of Edit-Distance Computation