On the Implementation of Compact DAWG's

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F03%3A03088066" target="_blank" >RIV/68407700:21230/03:03088066 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

On the Implementation of Compact DAWG's

Original language description

There are several data structures that allow searching for a pattern P in a preprocessed text T in time dependent just on the length of P. In this paper we present an implementation of CDAWG's---Compact Direct Acyclic Word Graphs. While the previous implementations of CDAWG's required from 7n to 23n bytes of memory space, ours achieves 1.7n to 5n for a text T of length n. The implementation is suitable for large data files, since it minimizes the number of disk accesses. If disk accesses are not to be optimized, space requirements can be further decreased.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2003

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Implementation and Application of Automata

ISBN

3-540-40391-4

ISSN

—

e-ISSN

—

Number of pages

6

Pages from-to

289-294

Publisher name

Springer

Place of publication

Berlin

Event location

Tours

Event date

May 3, 2002

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—