2015 | OriginalPaper | Buchkapitel
Transforming XML Streams with References
verfasst von : Sebastian Maneth, Alberto Ordóñez, Helmut Seidl
Erschienen in: String Processing and Information Retrieval
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Many useful
xml
transformations can be formulated through deterministic top-down tree transducers. If transducers process parts of the input repeatedly or in non-document order, then they cannot be realized over the
xml
stream with constant or even depth-bounded memory. We show that by enriching streams by
forward references
both in the input and in the output, every such transformation can be compiled into a stream processor with a space consumption depending only on the transducer and the depth of the
xml
document. References allow to produce DAG-compressed output that is guaranteed to be linear in the size of the input (up to the space required for labels). Our model is designed so that without decompression, the output may again serve as the input of a subsequent transducer.