TY - GEN
T1 - A preprocessing for approximate string matching
AU - Baba, Kensuke
AU - Nakatoh, Tetsuya
AU - Yamada, Yasuhiro
AU - Ikeda, Daisuke
PY - 2011
Y1 - 2011
N2 - 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 algorithm 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(n2) and O(nlogn), 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.
AB - 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 algorithm 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(n2) and O(nlogn), 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.
KW - FFT
KW - algorithm
KW - approximate string matching
UR - http://www.scopus.com/inward/record.url?scp=82955176917&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=82955176917&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-25453-6_50
DO - 10.1007/978-3-642-25453-6_50
M3 - Conference contribution
AN - SCOPUS:82955176917
SN - 9783642254529
T3 - Communications in Computer and Information Science
SP - 610
EP - 615
BT - Informatics Engineering and Information Science - International Conference, ICIEIS 2011, Proceedings
T2 - International Conference on Informatics Engineering and Information Science, ICIEIS 2011
Y2 - 14 November 2011 through 16 November 2011
ER -