Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

A Dynamic Data Structure for Reverse Lexicographically Sorted Prefixes

Hidetoshi YokooContact Information

(6)  Department of Computer Science, Gunma University, Kiryu 376-8515, Japan
Abstract
This paper proposes a simple data structure, called a prefix list, which maintains all prefixes of a string in reverse lexicographic order. It can be on-line incrementally constructed in time and space linear in the string length. It is strongly related to sufix trees and sufix arrays, and may share applications with these existing structures. A sufix array can be built via the corresponding prefix list in linear time. Particular applications of the prefix list lie in source-coding problems that require on-line right-to-left string matching. We apply the prefix list to on-line estimation of source entropy and to context-based symbol-ranking text compression algorithms.
Partially supported by the Kayamori foundation of informational science advance- ment and by the Okawa foundation for information and telecommunications.

Contact Information Hidetoshi Yokoo
Email: yokoo@cs.gunma-u.ac.jp
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.106 • Server: mpweb08
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)