TCS-TR-A-10-48

Date: Fri Nov 19 18:37:18 2010

Title: On Performance of Compressed Pattern Matching on VF Codes

Authors: Satoshi Yoshida and Takuya Kida

Contact:

First name: Takuya
Last name: Kida
Address: Division of Computer Science, Graduate School of Information Science and Technology, Hokkaido University, Kita 14-jo Nishi 9-chome, 060-0814 Sapporo, Japan
Email: kida@ist.hokudai.ac.jp

Abstract. This paper discusses about pattern matching on Variable-to-Fixed-length codes (VF codes). A VF code is a coding scheme whose codeword lengths are fixed, and thus it is suitable for comprssed pattern matching. However, there are few reports showing its efficiency so far. We present some experimental results about the compression ratios and encoding/decoding speeds besides pattern matching performance on Tunstall codes and STVF codes. We also present how an entropy coding affects to VF codes.