作成者 |
|
|
|
|
本文言語 |
|
出版者 |
|
発行日 |
|
収録物名 |
|
出版タイプ |
|
アクセス権 |
|
関連DOI |
|
|
関連URI |
|
|
関連情報 |
|
|
概要 |
Approximate string matching is a basic and important concept in many applications of information retrieval. This paper proposes an algorithm for the problem of approximate string matching. The algorit...hm solves the match-count problem as a preprocessing. For input strings of each length n, the time complexities of the approximate string matching problem and the match-count problem are O(n^2) and O(n log n), respectively. Therefore, the computation time of the algorithm is expected to be short when the scope of search is drastically restricted by the preprocessing. This paper makes clear the relation between the solutions of the two problems.続きを見る
|