Approximate dictionary matching (checking if a pattern occurs in a collection of strings) is a classic problem with applications in e.g. spellchecking, online catalogs, and web searchers. We present a simple solution called split index, which is based on the Dirichlet principle, for matching a keyword with few mismatches, and experimentally show that it offers competitive space-time tradeoffs. Our implementation in the C++ language is focused mostly on data compaction, which is beneficial for the search speed. We compare our solution with other algorithms and we show that it is faster when the Hamming distance is used. Query times in the order of 1 microsecond were reported for one mismatch for a few-megabyte natural language dictionary on a medium-end PC. We also demonstrate that a basic compression technique consisting in q-gram substitution can significantly reduce the index size (up to 50 % of the input text size for the DNA sequences).
Publié le : 2017-12-19
Classification:  other areas of Computing and Informatics,  Approximate dictionary matching, Hamming distance, k-mismatches problem, split index, text indexing,  68W32
@article{cai2017_5_1088,
     author = {Aleksander Cis\l ak; Warsaw University of Technology, Faculty of Mathematics and Information Science, 00-662 Warsaw and Szymon Grabowski; Lodz University of Technology, Institute of Applied Computer Science, 90-924  \L \'od\'z},
     title = {A Practical Index for Approximate Dictionary Matching with Few Mismatches},
     journal = {Computing and Informatics},
     volume = {35},
     number = {4},
     year = {2017},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai2017_5_1088}
}
Aleksander Cisłak; Warsaw University of Technology, Faculty of Mathematics and Information Science, 00-662 Warsaw; Szymon Grabowski; Lodz University of Technology, Institute of Applied Computer Science, 90-924  Łódź. A Practical Index for Approximate Dictionary Matching with Few Mismatches. Computing and Informatics, Tome 35 (2017) no. 4, . http://gdmltest.u-ga.fr/item/cai2017_5_1088/