Zobrazeno 1 - 10
of 49
pro vyhledávání: '"Kimmo Fredriksson"'
Publikováno v:
COMPUTING AND INFORMATICS; Vol. 38 No. 3 (2019): Computing and Informatics; 555-574
The suffix array is a classic full-text index, combining effectiveness with simplicity. We discuss three approaches aiming to improve its efficiency even more: changes to the navigation, data layout and adding extra data. In short, we show that i) th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::dfbce3d7696267779cd70d1c1a14e6f8
https://doi.org/10.31577/cai_2019_3_555
https://doi.org/10.31577/cai_2019_3_555
Publikováno v:
COMPUTING AND INFORMATICS; Vol. 38 No. 4 (2019): Computing and Informatics; 937-962
We consider the classical exact multiple string matching problem. The proposed solution is based on a combination of a few ideas: using q-grams instead of single characters, pattern superimposition, bit-parallelism and alphabet size reduction. We dis
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::343318775baf2e165dde4d7aab5fede6
https://www.cai.sk/ojs/index.php/cai/article/view/2019_4_937
https://www.cai.sk/ojs/index.php/cai/article/view/2019_4_937
Autor:
Pekka Kilpeläinen, Kimmo Fredriksson
Publikováno v:
Software: Practice and Experience. 46:435-467
Initialization of an array, out of which only a small initially unknown portion will eventually be used, is a frequent need in programming. A folklore solution for initializing an array of n entries in constant time uses 2ni¾?log2ni¾? extra bits to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d8162c235fdbf6ed9c879a9443fa431e
https://doi.org/10.1002/spe.2314
https://doi.org/10.1002/spe.2314
Publikováno v:
Theoretical Computer Science. 548:1-13
We present new algorithms for the problem of multiple string matching of gapped patterns, where a gapped pattern is a sequence of strings such that there is a gap of fixed length between each two consecutive strings. The problem has applications in t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2f9a8df886f19b3c46a63320b01b069f
https://doi.org/10.1016/j.tcs.2014.06.032
https://doi.org/10.1016/j.tcs.2014.06.032
Publikováno v:
Information Processing Letters. 113:693-697
Given strings $P$ of length $m$ and $T$ of length $n$ over an alphabet of size $\sigma$, the string matching with $k$-mismatches problem is to find the positions of all the substrings in $T$ that are at Hamming distance at most $k$ from $P$. If $T$ c
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d4565d59414bde6741792e13e8e85c2e
https://doi.org/10.1016/j.ipl.2013.07.002
https://doi.org/10.1016/j.ipl.2013.07.002
Autor:
Kimmo Fredriksson, Szymon Grabowski
Publikováno v:
European Journal of Combinatorics. 34:38-51
We develop a method for performing convolutions efficiently in a word RAM model of computation, having a word size of w = ? ( log n ) bits, where n is the input size. The basic?idea?is to pack several elements of the input vector into a single comput
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9906077cd87cba424ba3008a26a3ec06
https://doi.org/10.1016/j.ejc.2012.07.013
https://doi.org/10.1016/j.ejc.2012.07.013
Autor:
Kimmo Fredriksson
Publikováno v:
Information Processing Letters. 110:1093-1098
We address the problem of building an index for a set $D$ of $n$ strings, where each string location is a subset of some finite integer alphabet of size $\sigma$, so that we can answer efficiently if a given simple query string (where each string loc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9746197b546131ff78516883aaaefc2d
https://doi.org/10.1016/j.ipl.2010.09.014
https://doi.org/10.1016/j.ipl.2010.09.014
Autor:
Szymon Grabowski, Kimmo Fredriksson
Publikováno v:
Journal of Discrete Algorithms. 7:579-594
The exact string matching problem is to find the occurrences of a pattern of length m from a text of length n symbols. We develop a novel and unorthodox filtering technique for this problem. Our method is based on transforming the problem into multip
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::94cc6162ec30dbb640cf57789e44c444
https://doi.org/10.1016/j.jda.2008.09.001
https://doi.org/10.1016/j.jda.2008.09.001
Autor:
Kimmo Fredriksson, Fedor Nikitin
Publikováno v:
Fundamenta Informaticae. 92:63-81
Given a sequence S of n symbols over some alphabet Σ of size σ, we develop new compression methods that are (i) very simple to implement; (ii) provide O(1) time random access to any symbol (or short substring) of the original sequence. Our simplest
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6e02ab70b08cba53d0151d017513591f
https://doi.org/10.3233/fi-2009-0066
https://doi.org/10.3233/fi-2009-0066
Autor:
Szymon Grabowski, Kimmo Fredriksson
Publikováno v:
Information Retrieval. 11:335-357
We develop efficient dynamic programming algorithms for pattern matching with general gaps and character classes. We consider patterns of the form p 0 g(a 0,b 0)p 1 g(a 1,b 1)?p m?1, where p i ? Σ, Σ is some finite alphabet, and g(a i ,b i ) denote
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5e104e5cd91553494559a362bdbdc0a3
https://doi.org/10.1007/s10791-008-9054-z
https://doi.org/10.1007/s10791-008-9054-z