Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
A Preprocessing for Approximate String Matching
verfasst von : Kensuke Baba, Tetsuya Nakatoh, Yasuhiro Yamada, Daisuke Ikeda
Erschienen in: Informatics Engineering and Information Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
(
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.