在網路普及和分散式多媒體運算的時代，資料量的成長一日千里。如何快速的存取資料，是當代迫切的需求。PAT tree 資料結構提供極快速的搜尋能力。藉由它的幫助，我們可以在O(log n)的時間內，執行任意的字首搜尋，不用受限於實際資料量的大小。事實上， 查詢字彙的長度通常小於 log n，所以真正在執行搜尋時，所耗費的時間是決定於查詢字彙的長度。雖然PAT tree 是如此的快速，我們認為它可以更快。我們憑藉PAT tree 的基礎，發展了DPAT tree。它的搜尋模式是隨機存取，不受限於查詢字彙的長度。DPAT tree 是一個trie 資料結構的變形，它能支援任何的語言索引功能，它同時也是一個雜湊表。我們使用了一個編碼程序來產生雜湊值，所有的搜尋都透過此雜湊值來查詢，來達到隨機存取的目的，確保查詢花費時間不會超過O(1)。在Cranfield II 資料測試集的實驗中，平均一個查詢花費25ms，相較於PAT tree 平均所花費的1443ms，它所提供的速度快上許多。 In the era of the Internet and distributed multimedia computing, data increasesrapidly in astonishing rate. How to retrieve data efficiently has become an urgentissue. The PAT tree is a data structure that allows very efficient searching withpreprocessing. We can do arbitrary prefix searching in O(log n) time with PAT tree,independent of the size of the answer. In practice, the length of the query is less thanO(log n), and the searching time is proportional to the query length. To improve thesearching efficiency, we have developed a modified PAT tree called decimal PAT tree(DPAT tree) with which the search could be done in a random access manner,regardless of the length of the query. The DPAT tree structure is a variation of triestructure that can support any language indexing functionality. It also is a hash tablethat maps every sistring to where it resides. We have employed an encoding procedureas the hash function to generate the hash values. The procedure is guaranteed to createa hash table, in which search can be done in random access manner. Thus searchingcould be done in no more than O(1). The experiment tests Cranfield II documentcollection and yields 25ms response time per query in average in contrast to 1443msresponse time per query in average in PAT tree retrieval.
