Pregled bibliografske jedinice broj: 35468
Ziv lempel compression of huge natural language data tries using suffix arrays
Ziv lempel compression of huge natural language data tries using suffix arrays // Combinatorial pattern matching, 10th annual symposium, CPM 99, Warwick University, UK, July 1999, Proceedings / Crochemore, Maxime ; Paterson Mike (ur.).
Berlin: Springer, 1999. str. 196-211
CROSBI ID: 35468 Za ispravke kontaktirajte CROSBI podršku putem web obrasca
Naslov
Ziv lempel compression of huge natural language data tries using suffix arrays
Autori
Ristov, Strahil ; Laporte, Eric
Vrsta, podvrsta i kategorija rada
Poglavlja u knjigama, znanstveni
Knjiga
Combinatorial pattern matching, 10th annual symposium, CPM 99, Warwick University, UK, July 1999, Proceedings
Urednik/ci
Crochemore, Maxime ; Paterson Mike
Izdavač
Springer
Grad
Berlin
Godina
1999
Raspon stranica
196-211
ISBN
3-540-66278-2
Sažetak
We present a very efficient, in terms of space and access speed, data structure for storing huge natural language data sets. The structure is described as LZ (Ziv Lempel) compressed linked list trie and is a step further beyond directed acyclic word graph in automata compression. We are using the structure to store DELAF, a huge French lexicon with syntactical, grammatical and lexical information associated with each word. The compressed structure can be produced in O(N) time using suffix trees for finding repetitions in trie, but for large data sets space requirements are more prohibitive than time so suffix arrays are used instead, with compression time complexity O(N log N) for all but for the largest data sets.
Izvorni jezik
Engleski
Znanstvena područja
Elektrotehnika
POVEZANOST RADA
