Abstract

We aim to speed up approximate keyword matching with the use of a lightweight, fixed-size block of data for each string, called a fingerprint. These work in a similar way to hash values; however, they can be also used for matching with errors. They store information regarding symbol occurrences using individual bits, and they can be compared against each other with a constant number of bitwise operations. In this way, certain strings can be deduced to be at least within the distance k from each other (using Hamming or Levenshtein distance) without performing an explicit verification. We show experimentally that for a preprocessed collection of strings, fingerprints can provide substantial speedups for k = 1, namely over 2.5 times for the Hamming distance and over 30 times for the Levenshtein distance. Tests were conducted on synthetic and real-world English and URL data.

Keywords

MSC

68W32

Cite this article

@article{cai-4140,
  author  = {Aleksander Cisłak and Szymon Grabowski},
  title   = {Lightweight Fingerprints for Fast Approximate Keyword Matching Using Bitwise Operations},
  journal = {Computing and Informatics},
  volume  = {38},
  number  = {2},
  pages   = {367--389},
  year    = {2019},
  issn    = {1335-9150},
  doi     = {10.31577/cai_2019_2_367}
}
Download .bib