Zobrazeno 1 - 10
of 316
pro vyhledávání: '"Gørtz P"'
A 'degenerate string' is a sequence of subsets of some alphabet; it represents any string obtainable by selecting one character from each set from left to right. Recently, Alanko et al. generalized the rank-select problem to degenerate strings, where
Externí odkaz:
http://arxiv.org/abs/2310.19702
Autor:
Gæde, Emil Toftegaard, Gørtz, Inge Li, van der Hoog, Ivor, Krogh, Christoffer, Rotenberg, Eva
The convex hull of a data set $P$ is the smallest convex set that contains $P$. In this work, we present a new data structure for convex hull, that allows for efficient dynamic updates. In a dynamic convex hull implementation, the following traits ar
Externí odkaz:
http://arxiv.org/abs/2310.18068
We revisit the popular \emph{delayed deterministic finite automaton} (\ddfa{}) compression algorithm introduced by Kumar~et~al.~[SIGCOMM 2006] for compressing deterministic finite automata (DFAs) used in intrusion detection systems. This compression
Externí odkaz:
http://arxiv.org/abs/2306.12771
Autor:
Bille, Philip, Fischer, Johannes, Gørtz, Inge Li, Pedersen, Max Rishøj, Stordalen, Tord Joakim
Given a string $S$ over an alphabet $\Sigma$, the 'string indexing problem' is to preprocess $S$ to subsequently support efficient pattern matching queries, i.e., given a pattern string $P$ report all the occurrences of $P$ in $S$. In this paper we s
Externí odkaz:
http://arxiv.org/abs/2301.09477
Autor:
Bille, Philip, Gørtz, Inge Li, Lewenstein, Moshe, Pissis, Solon P., Rotenberg, Eva, Steiner, Teresa Anna
In Gapped String Indexing, the goal is to compactly represent a string $S$ of length $n$ such that for any query consisting of two strings $P_1$ and $P_2$, called patterns, and an integer interval $[\alpha, \beta]$, called gap range, we can quickly f
Externí odkaz:
http://arxiv.org/abs/2211.16860
Relative Lempel-Ziv (RLZ) parsing is a dictionary compression method in which a string $S$ is compressed relative to a second string $R$ (called the reference) by parsing $S$ into a sequence of substrings that occur in $R$. RLZ is particularly effect
Externí odkaz:
http://arxiv.org/abs/2208.11371
Let $S$ be a string of length $n$ over an alphabet $\Sigma$ and let $Q$ be a subset of $\Sigma$ of size $q \geq 2$. The 'co-occurrence problem' is to construct a compact data structure that supports the following query: given an integer $w$ return th
Externí odkaz:
http://arxiv.org/abs/2206.10383
We consider the predecessor problem on the ultra-wide word RAM model of computation, which extends the word RAM model with 'ultrawords' consisting of $w^2$ bits [TAMC, 2015]. The model supports arithmetic and boolean operations on ultrawords, in addi
Externí odkaz:
http://arxiv.org/abs/2201.11550
Given two strings $S$ and $P$, the Episode Matching problem is to find the shortest substring of $S$ that contains $P$ as a subsequence. The best known upper bound for this problem is $\tilde O(nm)$ by Das et al. (1997) , where $n,m$ are the lengths
Externí odkaz:
http://arxiv.org/abs/2108.08613
The classic string indexing problem is to preprocess a string S into a compact data structure that supports efficient pattern matching queries. Typical queries include existential queries (decide if the pattern occurs in S), reporting queries (return
Externí odkaz:
http://arxiv.org/abs/2102.02505