POI資料壓縮與搜尋

POI Data Compression and Search

范家聲(Chia-Sheng Fan)

指導教授 ： 黃俊龍

國立交通大學/資訊學院/資訊學院資訊學程/碩士(2015年)

https://doi.org/10.6842/NCTU.2015.00208

摘要

隨著資訊科技的日益發達，資料量也隨之日益成長。因此，如何有效、快速地運用龐大的資料量，已是現今一個熱門的研究課題，其中資料的壓縮與搜尋正扮演著一個不可或缺的重要角色。雖然，已有許多關於資料壓縮和搜尋的研究，但由於行動裝置的興起，大量的應用程式也隨之產生，所使用的資料格式變得多樣化，實難找出一個可以有效兼顧資料壓縮和搜尋、且通用於各種資料格式的方法。本研究即是針對目前手機上最為常用的景點資料（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.

並列關鍵字

Point of Interest ； POI ； Compression ； Search

參考文獻

[10] Robert S. Boyer, and J. Strother Moore, "A fast string searching algorithm", Comm. ACM 20 (10): 762-772, Oct. 1977.

[12] David A. Huffman, "A method for the construction of minimum redundancy codes", in proceedings of Institute of Radio Engineers (IRE), 40(9):1098-1101, September 1952.

[13] De Moura, E.S., et al., "Direct pattern matching on compressed text", in proceedings of Processing and Information Retrieval: A South American Symposium. IEEE, September 1998.

[18] Terry Welch, "A technique for high-performance data compression", Computer 17 (6): 8-19, June 1984.

[21] Kang Jianchu, Liu Peng, and Zhu Tongyu. "Research on Navigation Terminal Oriented POI Compression and Retrieval", in proceedings of 2008 International Conference on Electric Technology and Civil Engineering (ICETCE), December 2008.