Name
Abstract | ||
|---|---|---|
We propose a new algorithm for computing the edit distance of an uncompressed string against a run-length-encoded string. For an uncompressed string of length n and a compressed string with M runs, the algorithm computes their edit distance in time O(Mn). This result directly implies an O(min{mN,Mn}) time algorithm for strings of lengths m and n with M and N runs, respectively. It improves the previous best known time bound O(mN+Mn). |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.ipl.2007.07.006 | Inf. Process. Lett. |
Keywords | Field | DocType |
lengths m,length n,time o,uncompressed string,time algorithm,new algorithm,run-length-encoded string,algorithms,compression algorithm,edit distance,run length encoding | Edit distance,Discrete mathematics,Combinatorics,Run-length encoding,Rabin–Karp algorithm,Approximate string matching,Mathematics,Uncompressed video | Journal |
Volume | Issue | ISSN |
105 | 1 | 0020-0190 |
Citations | PageRank | References |
11 | 0.67 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| jia liu | 1 | 74 | 6.27 |
| G. S. Huang | 2 | 11 | 0.67 |
| Y. L. Wang | 3 | 11 | 0.67 |
| R. C. T. Lee | 4 | 11 | 0.67 |