POI資料壓縮與搜尋

Abstract

隨著資訊科技的日益發達，資料量也隨之日益成長。因此，如何有效、快速地運用龐大的資料量，已是現今一個熱門的研究課題，其中資料的壓縮與搜尋正扮演著一個不可或缺的重要角色。雖然，已有許多關於資料壓縮和搜尋的研究，但由於行動裝置的興起，大量的應用程式也隨之產生，所使用的資料格式變得多樣化，實難找出一個可以有效兼顧資料壓縮和搜尋、且通用於各種資料格式的方法。本研究即是針對目前手機上最為常用的景點資料（POI）找出一個壓縮效果好且搜尋快速的方法。我們的實驗結果說明，本研究的方法比算術編碼法、霍夫曼系列的編碼法（Huffman encoding）的壓縮比高，可多壓縮2%～18%資料量；在搜尋方面，與Boyer-Moore演算法在未壓縮的文件上的搜尋速度相比要快上40%，在搜尋條件變多的情況下要快80%。

As information technology is developed rapidly, data volume grows bigger as well. Therefore, processing such enormous data in an efficient way has become a hot study topic. For this reason, data compression and search play a key role to this field. Although numerous studies about data compression and searching are revealed, when mobile is getting popular, a lot of software are developed and use various data formats. In this study, we implement a good compression and searchable method for POI（Point of Interest）, which is the most popular data used in mobile phones. Comparing with Arithmetic coding and Huffman family codings, the method gains 2~18% better in compression rate. In terms of searching, our method is 40% faster than the Boyer-Moore algorithm on plain text, and is 80% faster when searching criteria increase.