STSimon Rumle Tarnow

Simon Rumle Tarnow

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Simon Rumle Tarnow has a total of 4 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Tighter Bounds for Wheeler Determinization

    by Philip Bille, Inge Li Gørtz, Máximo Pérez-López, Simon R. Tarnow

  • Open Access

    Compressed Dictionary Matching on Run-Length Encoded Strings

    by Philip Bille, Inge Li Gørtz, Simon J. Puglisi, Simon Rumle Tarnow

    Given a set of pattern strings $$\mathcal {P}=\{P_1, P_2,\ldots P_k\}$$ P = { P 1 , P 2 , … P k } and a text string S , the classic dictionary matching problem is to report all occurrences of each pattern in S . We study the dictionary problem in the compressed setting, where the pattern strings and the text string are compressed using run-length encoding, and the goal is to solve the problem without decompression and achieve efficient time and space in the size of the compressed strings. Let m and n be the total length of the patterns $$\mathcal {P}$$ P and the length of the text string S , respectively, and let $$\overline{m}$$ m ¯ and $$\overline{n}$$ n ¯ be the total number of runs in the run-length encoding of the patterns in $$\mathcal {P}$$ P and S , respectively. Our main result is an algorithm that achieves $$O( (\overline{m} + \overline{n})\log \log m + \textrm{occ})$$ O ( ( m ¯ + n ¯ ) log log m + occ ) expected time, and $$O(\overline{m})$$ O ( m ¯ ) space, where $$\textrm{occ}$$ occ is the total number of occurrences of patterns in S . This is the first non-trivial solution to the problem. Since any solution must read the input, our time bound is optimal within a $$\log \log m$$ log log m factor. We introduce several new techniques to achieve our bounds, including a new compressed representation of the classic Aho-Corasick automaton and a new efficient string index that supports fast queries in run-length encoded strings.

  • Open Access

    Compressed Dictionary Matching on Run-Length Encoded Strings

    by Philip Bille, Inge Li Gørtz, Simon J. Puglisi, Simon Rumle Tarnow

    Given a set of pattern strings P = {P1, P2, . . . Pk} and a text string S, the classic dictionary matching problem is to report all occurrences of each pattern in S. We study the dictionary problem in the compressed setting, where the pattern strings and the text string are compressed using run-length encoding, and the goal is to solve the problem without decompression and achieve efficient time and space in the size of the compressed strings. Let m and n be the total length of the patterns P and the length of the text string S, respectively, and let m and n be the total number of runs in the run-length encoding of the patterns in P and S, respectively. Our main result is an algorithm that achieves O((m+n) log logm+occ) expected time, and O(m) space, where occ is the total number of occurrences of patterns in S. This is the first non-trivial solution to the problem. Since any solution must read the input, our time bound is optimal within an log logm factor. We introduce several new techniques to achieve our bounds, including a new compressed representation of the classic Aho-Corasick automaton and a new efficient string index that supports fast queries in runlength encoded strings.

  • Open Access

    Compressed Dictionary Matching on Run-Length Encoded Strings

    by Philip Bille, Inge Li Gørtz, Simon J. Puglisi, Simon R. Tarnow

    Given a set of pattern strings $\mathcal{P}=\{P_1, P_2,\ldots P_k\}$ and a text string $S$, the classic dictionary matching problem is to report all occurrences of each pattern in $S$. We study the dictionary problem in the compressed setting, where the pattern strings and the text string are compressed using run-length encoding, and the goal is to solve the problem without decompression and achieve efficient time and space in the size of the compressed strings. Let $m$ and $n$ be the total length of the patterns $\mathcal{P}$ and the length of the text string $S$, respectively, and let $\overline{m}$ and $\overline{n}$ be the total number of runs in the run-length encoding of the patterns in $\mathcal{P}$ and $S$, respectively. Our main result is an algorithm that achieves $O( (\overline{m} + \overline{n})\log \log m + \mathrm{occ})$ expected time, and $O(\overline{m})$ space, where $\mathrm{occ}$ is the total number of occurrences of patterns in $S$. This is the first non-trivial solution to the problem. Since any solution must read the input, our time bound is optimal within an $\log \log m$ factor. We introduce several new techniques to achieve our bounds, including a new compressed representation of the classic Aho-Corasick automaton and a new efficient string index that supports fast queries in run-length encoded strings.