Fast approximate string matching in a dictionary

被引：35

作者：

Baeza-Yates, R ^{[1
]}

Navarro, G ^{[1
]}

机构：

[1] Univ Chile, Dept Comp Sci, Santiago, Chile

来源：

STRING PROCESSING AND INFORMATION RETRIEVAL - PROCEEDINGS: A SOUTH AMERICAN SYMPOSIUM | 1998年

关键词：

D O I：

10.1109/SPIRE.1998.712978

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A successful technique to search large textual databases allowing errors relies on an online search in the vocabulary of the text. To reduce the time of that online search, we index the vocabulary as a metric space. We show that with reasonable space overhead we can improve by a factor of two over the fastest online algorithms, when the tolerated error level is low (which is reasonable in text searching).

引用

页码：14 / 22

页数：9