Browse

Space-efficient implementation of a compressed trie
공간효율적인 트라이 구현

Cited 0 time in Web of Science Cited 0 time in Scopus
Authors
Jeongsoo Shin
Advisor
Srinivasa Rao Satti
Major
공과대학 컴퓨터공학부
Issue Date
2016-02
Publisher
서울대학교 대학원
Keywords
TrieArray representationSuccinct representationCompression algorithm
Description
학위논문 (석사)-- 서울대학교 대학원 : 컴퓨터공학부, 2016. 2. Srinivasa Rao Satti.
Abstract
Trie is the typical data structure for keyword searching algorithms. The algorithms are classified into two ways. One is the array representation, the other one is the succinct representation. In array representation, one can access the child node using the one dimensional array which stores the pointers from the node to its child. This shows fast lookup time, but takes a lot of space. In succinct representation, one separates a tree structure and index array, and represents a tree structure by succinct representation. This shows slower query time than array representation, but takes less space. In this thesis, we first use the degree sequence and its variants to implement the space-efficient trie on the small fixed alphabet. The experimental result shows that for small alphabet (
Σ
≤10), our implementation gives fast query time and less space usage compared to the exist implementations.
Language
English
URI
http://hdl.handle.net/10371/122659
Files in This Item:
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Computer Science and Engineering (컴퓨터공학부)Theses (Master's Degree_컴퓨터공학부)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse