سال انتشار: ۱۳۸۴

محل انتشار: یازدهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۶

نویسنده(ها):

Thomas Bj ¨ orklund – Lule°a University of Technology S971 87 Lule° a, Sweden
Andrej Brodnik – University of Primorska Cankarjeva 5 6000 Koper, Slovenia
Johan Nordlander – Lule°a University of Technology S971 87 Lule° a, Sweden

چکیده:

In this paper we present a variant of the path and level com- pressed trie that can store non pre x-free sets of strings.We also study how to limit the height of it, while main- taining optimal size. The ability to limit the height is particularly important since it also limits the number of memory accesses needed for a search operation. The min- imum height is proportional to the length of the longest chain of pre xes in the set to be represented. If this can be bounded, the data structure can be e ciently implemented in a pipelined hardware architecture, where the length of the pipeline puts a hard limit on the height of the trie. We also discuss a simple language for describing path and level compressed tries, and use it to describe an algorithm to control the height of a trie while maintaining optimal size. The algorithm uses dynamic programming and runs in O