Open AccessA new compression algorithm for fast text search
Author(s) -
Aydın Carus,
Altan Mesut
Publication year - 2016
Publication title -
turkish journal of electrical engineering and computer sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.225
H-Index - 30
eISSN - 1303-6203
pISSN - 1300-0632
DOI - 10.3906/elk-1407-178
Subject(s) - string searching algorithm , commentz walter algorithm , compression (physics) , computer science , string (physics) , data compression , algorithm , pattern matching , matching (statistics) , search algorithm , word (group theory) , approximate string matching , compression ratio , artificial intelligence , mathematics , engineering , geometry , automotive engineering , statistics , materials science , mathematical physics , internal combustion engine , composite material
We propose a new compression algorithm that compresses plain texts by using a dictionary-based model and a compressed string-matching approach that can be used with the compressed texts produced by this algorithm. The compression algorithm (CAFTS) can reduce the size of the texts to approximately 41% of their original sizes. The presented compressed string matching approach (SoCAFTS), which can be used with any of the known pattern matching algorithms, is compared with a powerful compressed string matching algorithm (ETDC) and a compressed string-matching tool (Lzgrep). Although the search speed of ETDC is very good in short patterns, it can only search for exact words and its compression performance differs from one natural language to another because of its word-based structure. Our experimental results show that SoCAFTS is a good solution when it is necessary to search for long patterns in a compressed document.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom