Speeding up Natural Language Text Search using Compression

Text search is a well-known problem in computer science where the valid shifts of a pattern P in a text string T are found. This paper shows how to speed up text search by searching for P in a compressed version of T. A fast compression algorithm was designed for this aim. This algorithm is based on the assumption that T is restricted to the letters of a single natural language. Relying on this assumption, a letter, in T or P, is encoded into a single byte instead of the two-byte unicode which shortens the string on which a text search algorithm works. The main disadvantage of this approach is the restriction of the alphabet of T to be from a single natural language. However, wide range of text documents comply to this assumption. Another issue is the overhead that is required to compress P and T, but it was found that the proposed compression algorithm is so fast such that its run-time can be paid for and still save text search time. Different approaches to store compressed T are also explored. The conducted experimental study showed that this approach does actually reduce the text search time.

@article{AbuSafiya2021,
  title     = {Speeding up Natural Language Text Search using Compression},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {12},
  number    = {4},
  year      = {2021},
  publisher = {The Science and Information Organization},
  author    = {Majed AbuSafiya},
  doi       = {10.14569/IJACSA.2021.0120452},
  url       = {https://doi.org/10.14569/IJACSA.2021.0120452}
}