A dynamic edit distance table |
| |
| Authors: | Sung-Ryul Kim Kunsoo Park |
| |
| Institution: | a Division of Internet & Media and Multidisciplinary Aerospace System Design Team, Konkuk University, Seoul 143-701, South Korea;b School of Computer Science and Engineering, Seoul National University, Seoul 151-742, South Korea |
| |
| Abstract: | In this paper we consider the incremental/decremental version of the edit distance problem: given a solution to the edit distance between two strings A and B, find a solution to the edit distance between A and B′ where B′=aB (incremental) or bB′=B (decremental). As a solution for the edit distance between A and B, we define the difference representation of the D-table, which leads to a simple and intuitive algorithm for the incremental/decremental edit distance problem. |
| |
| Keywords: | String matching Edit distance Incremental/decremental edit distance |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
