Výsledky vyhledávání - "Hjalte Wedel Vildhøj"

Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation

Autor: Hjalte Wedel Vildhøj, Søren Vind, Anders Roy Christiansen, Frederik Rye Skjoldjensen, Patrick Hagge Cording, Inge Li Gørtz, Philip Bille

Publikováno v: Bille, P, Christiansen, A R, Cording, P H, Gørtz, I L, Skjoldjensen, F R, Vildhøj, H W & Vind, S 2018, ' Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation ', Algorithmica, vol. 80, no. 11, pp. 3207-3224 . https://doi.org/10.1007/s00453-017-0380-7

Given a static reference string R and a source string S, a relative compression of S with respect to R is an encoding of S as a sequence of references to substrings of R. Relative compression schemes are a classic model of compression and have recent

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::df5a40c8e46e30e315d15cf619683274
https://doi.org/10.1007/s00453-017-0380-7

Zobrazit plný text záznamu

Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing

Autor: Hjalte Wedel Vildhøj, Philip Bille, Inge Li Gørtz, Mikko Berggren Ettienne

Publikováno v: Bille, P, Ettienne, M B, Gørtz, I L & Vildhøj, H W 2017, Time-space trade-offs for lempel-ziv compressed indexing . in Proceedings of 28th Annual Symposium on Combinatorial Pattern Matching . Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, 28th Annual Symposium on Combinatorial Pattern Matching, Warsaw, Poland, 04/07/2017 . https://doi.org/10.4230/LIPIcs.CPM.2017.16

Given a string S, the compressed indexing problem is to preprocess S into a compressed representation that supports fast substring queries. The goal is to use little space relative to the compressed size of S while supporting fast queries. We present

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5aaa3f3db3606a53ea2b26eef2a7452f

Zobrazit plný text záznamu

Dynamic and Approximate Pattern Matching in 2D

Autor: Raphaël Clifford, Tatiana Starikovskaya, Allyx Fontaine, Hjalte Wedel Vildhøj

Publikováno v: String Processing and Information Retrieval ISBN: 9783319460482
SPIRE

We consider dynamic and online variants of 2D pattern matching between an $m \times m$ pattern and an $n \times n$ text. All the algorithms we give are randomised and give correct outputs with at least constant probability.

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::b69d7df0cd6349f82cee28da187b8198
https://doi.org/10.1007/978-3-319-46049-9_13

Zobrazit plný text záznamu

Sparse Text Indexing in Small Space

Autor: Johannes Fischer, Benjamin Sach, Inge Li Gørtz, Tsvi Kopelowitz, Philip Bille, Hjalte Wedel Vildhøj

Publikováno v: Bille, P, Fischer, J, Gørtz, I L, Kopelowitz, T, Sach, B & Vildhøj, H W 2016, ' Sparse Text Indexing in Small Space ', A C M Transactions on Algorithms, vol. 12, no. 3, 39, pp. 1-19 . https://doi.org/10.1145/2836166

In this work, we present efficient algorithms for constructing sparse suffix trees, sparse suffix arrays, and sparse position heaps for b arbitrary positions of a text T of length n while using only O ( b ) words of space during the construction. Att

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8848063a5106225c8dbe42490e62b3ca
https://orbit.dtu.dk/en/publications/820ab6bf-15a4-4dc7-984d-757deb3d37dd

Zobrazit plný text záznamu

Longest Common Extensions in Sublinear Space

Autor: Inge Li Gørtz, Hjalte Wedel Vildhøj, Mathias Bæk Tejs Knudsen, Philip Bille, Moshe Lewenstein

Publikováno v: Combinatorial Pattern Matching ISBN: 9783319199283
CPM

The longest common extension problem (LCE problem) is to construct a data structure for an input string $T$ of length $n$ that supports ${\mathrm {LCE}}(i,j)$ queries. Such a query returns the length of the longest common prefix of the suffixes

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::019eb3db7744f02a3a16d9adaa763b28
https://doi.org/10.1007/978-3-319-19929-0_6

Zobrazit plný text záznamu

A Suffix Tree Or Not a Suffix Tree?

Autor: Tatiana Starikovskaya, Hjalte Wedel Vildhøj

Publikováno v: Lecture Notes in Computer Science ISBN: 9783319193144
IWOCA

In this paper we study the structure of suffix trees. Given an unlabeled tree $\tau $ on n nodes and suffix links of its internal nodes, we ask the question “Is $\tau $ a suffix tree?", i.e., is there a string S whose suffix tree has the same t

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::a98497b9adcacc6b49d0b04eb37e567b
https://doi.org/10.1007/978-3-319-19315-1_30

Zobrazit plný text záznamu

A Suffix Tree Or Not A Suffix Tree?

Autor: Hjalte Wedel Vildhøj, Tatiana Starikovskaya

Publikováno v: Starikovskaya, T A & Vildhøj, H W 2015, ' A suffix tree or not a suffix tree? ', Journal of Discrete Algorithms, vol. 32, pp. 14-23 . https://doi.org/10.1016/j.jda.2015.01.005

In this paper we study the structure of suffix trees. Given an unlabeled tree $\tau$ on $n$ nodes and suffix links of its internal nodes, we ask the question "Is $\tau$ a suffix tree?", i.e., is there a string $S$ whose suffix tree has the same topol

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::74b35eace94e6d8e0cc9d47fe8d30831
http://arxiv.org/abs/1403.1364

Zobrazit plný text záznamu

Time–space trade-offs for longest common extensions

Autor: Hjalte Wedel Vildhøj, Benjamin Sach, Philip Bille, Inge Li Gørtz

Publikováno v: Bille, P, Gørtz, I L, Sach, B & Vildhøj, H W 2014, ' Time–space trade-offs for longest common extensions ', Journal of Discrete Algorithms, vol. 25, pp. 42-50 . https://doi.org/10.1016/j.jda.2013.06.003

We revisit the longest common extension (LCE) problem, that is, preprocess a string T into a compact data structure that supports fast LCE queries. An LCE query takes a pair (i,j) of indices in T and returns the length of the longest common prefix of

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::af537d05ba2285d0ef1705fca2f16627
https://orbit.dtu.dk/en/publications/376dbefe-b2c1-4ece-973b-cc33f266d293

Zobrazit plný text záznamu

Time-Space Trade-Offs for the Longest Common Substring Problem

Autor: Tatiana Starikovskaya, Hjalte Wedel Vildhøj

Publikováno v: Combinatorial Pattern Matching ISBN: 9783642389047
CPM

The Longest Common Substring problem is to compute the longest substring which occurs in at least d ≥ 2 of m strings of total length n. In this paper we ask the question whether this problem allows a deterministic time-space trade-off using O(n 1 +

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::4cd7665d39034ed6bbb9a5e24c74d26d
https://doi.org/10.1007/978-3-642-38905-4_22

Zobrazit plný text záznamu

Sparse Suffix Tree Construction in Small Space

Autor: Johannes Fischer, Tsvi Kopelowitz, Inge Li Gørtz, Hjalte Wedel Vildhøj, Philip Bille, Benjamin Sach

Publikováno v: Automata, Languages, and Programming ISBN: 9783642392054
ICALP (1)

We consider the problem of constructing a sparse suffix tree (or suffix array) for b suffixes of a given text T of length n, using only O(b) words of space during construction. Attempts at breaking the naive bound of Ω(nb) time for this problem can

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::c2b0e866243d9235a4d0a5f2bb9f9161
https://doi.org/10.1007/978-3-642-39206-1_13

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání