担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Let ST(k) denote the set of distinct substrings of length k in a string T, then its cardinality | ST(k) | is called the k-th substring complexity of T. Recently, δ= max { | ST(k) | / k: k≥ 1 } has been shown to be a good compressibility measure of highly-repetitive strings. In this paper, given T of length n in the run-length compressed form of size ρ, we show that δ can be computed in Csort(ρ, n) time and O(ρ) space, where Csort(ρ, n) = O(min (ρlg lg ρ, ρlg ρn) ) is the time complexity for sorting ρ integers with O(lg n) bits each in O(ρ) space in the Word-RAM model with word size Ω(lg n).

DOI： 10.1007/978-3-031-20643-6_10

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85142675895&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

For the feature selection problem, we propose an efficient privacy-preserving algorithm. Let D, F, and C be data, feature, and class sets, respectively, where the feature value x(Fi) and the class label x(C) are given for each x ∈ D and Fi ∈ F. For a triple (D, F, C), the feature selection problem is to find a consistent and minimal subset F′ ⊆ F, where ‘consistent’ means that, for any x, y ∈ D, x(C) = y(C) if x(Fi) = y(Fi) for Fi ∈ F′, and ‘minimal’ means that any proper subset of F′ is no longer consistent. On distributed datasets, we consider feature selection as a privacy-preserving problem: assume that semi-honest parties A and B have their own personal DA and DB. The goal is to solve the feature selection problem for DA ∪ DB without sacrificing their privacy. In this paper, we propose a secure and efficient algorithm based on fully homomorphic encryption, and we implement our algorithm to show its effectiveness for various practical data. The proposed algorithm is the first one that can directly simulate the CWC (Combination of Weakest Components) algorithm on ciphertext, which is one of the best performers for the feature selection problem on the plaintext.

DOI： 10.3390/a15070229

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85133509105&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

We study succinct variants of B trees in the word RAM model that require s+ o(s) bits of space, where s is the number of bits essentially needed for storing keys and possibly other satellite values. Assuming that elements are sorted by keys (not necessarily in the order of their integer representations), our B trees support standard operations such as searching, insertion and deletion of elements. In some applications it is useful to associate a satellite value to each element, and to support aggregate operations such as computing the sum of values, the minimum/maximum value in a given range, or search operations based on those values. We propose a B tree representation storing n elements in s+ O(s/ lg n) bits of space and supporting all mentioned operations in O(lg n) time.

DOI： 10.1007/978-3-031-06678-8_24

DOI： 10.1007/978-3-031-06678-8_24

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85131937834&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

In this study, we propose a simple and effective preprocessing method for subword segmentation based on a data compression algorithm. Compression-based subword segmentation has recently attracted significant attention as a preprocessing method for training data in neural machine translation. Among them, BPE/BPE-dropout is one of the fastest and most effective methods compared to conventional approaches; however, compression-based approaches have a drawback in that generating multiple segmentations is difficult due to the determinism. To overcome this difficulty, we focus on a stochastic string algorithm, called locally consistent parsing (LCP), that has been applied to achieve optimum compression. Employing the stochastic parsing mechanism of LCP, we propose LCP-dropout for multiple subword segmentation that improves BPE/BPE-dropout, and we show that it outperforms various baselines in learning from especially small training data.

DOI： 10.3390/electronics11071014

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85126910361&origin=inward

担当区分：最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Since highly repetitive strings, which can be compressed greatly, are ubiquitous nowadays, algorithms working on compressed space have gained much more attention. In particular, converting one compressed format to another without explicit decompression is of great interest as we can take advantage of various compressed formats with small cost of space. In this paper, we consider algorithms to convert run-length encoded Burrows-Wheeler Transform (RLBWT) to Lempel-Ziv 77 (LZ77). We implement a simplified version of the algorithm proposed by Nishimoto and Tabei and propose a two-pass algorithm to reduce its peak memory usage in practice. Experimental results show that the two-pass algorithm uses 23% to 37% less space with up to 10% increase of computational time when we use 8 threads in the second pass.

DOI： 10.1109/DCC52660.2022.00032

DOI： 10.1109/DCC52660.2022.00032

Scopus

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85134417981&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Computing the matching statistics of patterns with respect to a text is a fundamental task in bioinformatics, but a formidable one when the text is a highly compressed genomic database. Bannai et al. gave an efficient solution for this case, which Rossi et al. recently implemented, but it uses two passes over the patterns and buffers a pointer for each character during the first pass. In this paper, we simplify their solution and make it streaming, at the cost of slowing it down slightly. This means that, first, we can compute the matching statistics of several long patterns (such as whole human chromosomes) in parallel while still using a reasonable amount of RAM; second, we can compute matching statistics online with low latency and thus quickly recognize when a pattern becomes incompressible relative to the database. Our code is available at http://github.com/koeppl/phoni.

DOI： 10.1109/DCC50243.2021.00027

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85106006610&origin=inward

担当区分：筆頭著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

We prove that for n≥ 2, the size b(tn) of the smallest bidirectional scheme for the nth Thue–Morse word tn is n+ 2. Since Kutsukake et al. [SPIRE 2020] show that the size γ(tn) of the smallest string attractor for tn is 4 for n≥ 4, this shows for the first time that there is a separation between the size of the smallest string attractor γ and the size of the smallest bidirectional scheme b, i.e., there exist string families such that γ= o(b).

DOI： 10.1007/978-3-030-86692-1_14

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85116783139&origin=inward

担当区分：筆頭著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Given a text T of length n, the sparse suffix sorting problem asks for the lexicographic order of suffixes starting at m selectable text positions P. The suffix binary search tree [Irving and Love, JDA’03] is a dynamic data structure that can answer this problem dynamically in the sense that insertions and deletions of positions in P are allowed. While a standard binary search tree on strings needs to store two longest-common prefix (LCP) values per node for providing the same query bounds, each suffix binary search tree node only stores a single LCP value and a bit flag. Its tree topology induces the sorting of the m suffixes by an Euler tour in O(m) time. However, it has not been addressed how to compute the lengths of the longest common prefixes of two suffixes with neighboring ranks with this data structure. We show that we can compute these lengths again by an Euler tour in O(m) time.

DOI： 10.1007/978-3-030-86692-1_12

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85116834863&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

Re-Pairis a grammar compression scheme with favorably good compression rates. The computation of Re-Pair comes with the cost of maintaining large frequency tables, which makes it hard to compute Re-Pair on large-scale data sets. As a solution for this problem, we present, given a text of length n whose characters are drawn from an integer alphabet with size σ = nO(1), an O(min(n2, n2 lg logτ n lg lg lg n/ logτ n)) time algorithm computing Re-Pair with max((n/c) lg n, n⌈lg τ⌉) + O(lg n) bits of working space including the text space, where c ≥ 1 is a fixed user-defined constant and τ is the sum of σ and the number of non-terminals. We give variants of our solution working in parallel or in the external memory model. Unfortunately, the algorithm seems not practical since a preliminary version already needs roughly one hour for computing Re-Pair on one megabyte of text.

DOI： 10.3390/a14010005

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85099168551&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Grammar-based compression is a popular and powerful approach to compressing repetitive texts but until recently its relatively poor time-space trade-offs during real-life construction made it impractical for truly massive datasets such as genomic databases. In a recent paper (SPIRE 2019) we showed how simple pre-processing can dramatically improve those trade-offs, and in this paper we turn our attention to one of the features that make grammar-based compression so attractive: the possibility of supporting fast random access. This is an essential primitive in many algorithms that process grammar-compressed texts without decompressing them and so many theoretical bounds have been published about it, but experimentation has lagged behind. We give a new encoding of grammars that is about as small as the practical state of the art (Maruyama et al., SPIRE 2013) but with significantly faster queries.

DOI： 10.1007/978-3-030-59212-7_16

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85092111359&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

記述言語：英語   掲載種別：研究論文（学術雑誌）

Given a text T of length n, we propose a deterministic online algorithm computing the sparse suffix array and the sparse longest common prefix array of T in O(c g lg n + m lg m lg n lg∗ n) time with O(m) words of space under the premise that the space of T is rewritable, where m ≤ n is the number of suffixes to be sorted (provided online and arbitrarily), and c is the number of characters with m ≤ c ≤ n that must be compared for distinguishing the designated suffixes.

DOI： 10.1145/3398681

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85025816771&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2019 Elsevier B.V. Gagie, Navarro and Prezza's r-index (SODA, 2018) promises to speed up DNA alignment and variation calling by allowing us to index entire genomic databases, provided certain obstacles can be overcome. In this paper we first strengthen and simplify Policriti and Prezza's Toehold Lemma (DCC '16; Algorithmica, 2017), which inspired the r-index and plays an important role in its implementation. We then show how to update the r-index efficiently after adding a new genome to the database, which is likely to be vital in practice. As a by-product of this result, we obtain an online version of Policriti and Prezza's algorithm for constructing the LZ77 parse from a run-length compressed Burrows-Wheeler Transform. Our experiments demonstrate the practicality of all three of these results. Finally, we show how to augment the r-index such that, given a new genome and fast random access to the database, we can quickly compute the matching statistics and maximal exact matches of the new genome with respect to the database.

DOI： 10.1016/j.tcs.2019.08.005

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85070385571&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2019 Elsevier B.V. In this paper, we propose a new dynamic compressed index of O(w) space for a dynamic text T, where w=O(min(zlogNlog∗M,N)) is the size of the signature encoding of T, z is the size of the Lempel–Ziv77 (LZ77) factorization of T, N is the length of T, and M≥N is the maximum length of T. Our index supports searching for a pattern P in T in O(|P|fA+logwlog|P|log∗M(logN+log|P|log∗M)+occlogN) time and insertion/deletion of a substring of length y in O((y+logNlog∗M)logwlogNlog∗M) time, where occ is the number of occurrences of P in T and [Formula presented]. Also, we propose a new space-efficient LZ77 factorization algorithm for a given text T, which runs in O(NfA+zlogwlog3N(log∗N)2) time with O(w) working space.

DOI： 10.1016/j.dam.2019.01.014

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85061439333&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Re-Pair is a grammar compression scheme with favorably good compression rates. The computation of Re-Pair comes with the cost of maintaining large frequency tables, which makes it hard to compute Re-Pair on large scale data sets. As a solution for this problem we present, given a text of length n whose characters are drawn from an integer alphabet, an O(n^2) time algorithm computing Re-Pair in n lg max(n, τ) bits of working space including the text space, where τ is the number of terminals and non-terminals.

DOI： 10.1109/DCC47342.2020.00092

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85086859811&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Springer Nature Switzerland AG 2020. We consider an efficient two-party protocol for securely computing the similarity of strings w.r.t. an extended edit distance measure. Here, two parties possessing strings x and y, respectively, want to jointly compute an approximate value for EDM(x, y), the minimum number of edit operations including substring moves needed to transform x into y, without revealing any private information. Recently, the first secure two-party protocol for this was proposed, based on homomorphic encryption, but this approach is not suitable for long strings due to its high communication and round complexities. In this paper, we propose an improved algorithm that significantly reduces the round complexity without sacrificing its cryptographic strength. We examine the performance of our algorithm for DNA sequences compared to previous one.

DOI： 10.1007/978-3-030-39881-1_26

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85080940455&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© 2019, Springer Nature Switzerland AG. Data compression is a powerful tool for managing massive but repetitive datasets, especially schemes such as grammar-based compression that support computation over the data without decompressing it. In the best case such a scheme takes a dataset so big that it must be stored on disk and shrinks it enough that it can be stored and processed in internal memory. Even then, however, the scheme is essentially useless unless it can be built on the original dataset reasonably quickly while keeping the dataset on disk. In this paper we show how we can preprocess such datasets with context-triggered piecewise hashing such that afterwards we can apply RePair and other grammar-based compressors more easily. We first give our algorithm, then show how a variant of it can be used to approximate the LZ77 parse, then leverage that to prove theoretical bounds on compression, and finally give experimental evidence that our approach is competitive in practice.

DOI： 10.1007/978-3-030-32686-9_3

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85075670034&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© 2019 IEEE. Given a string T of length N, the goal of grammar compression is to construct a small context-free grammar generating only T. Among existing grammar compression methods, RePair (recursive paring) [Larsson and Moffat, 1999] is notable for achieving good compression ratios in practice. In this paper, we propose the first RePair algorithm working in compressed space, i.e., potentially o(N) space for highly compressible texts. The key idea is to give a new way to restructure an arbitrary (context-free) grammar S for T into RePair(T) in compressed space and time. We propose an algorithm for RePair(T) running in O(min(N, nm log N)) space and expected O(min(N, nm log N) m) time or O(min(N, nm log N) log log N) time, where n is the size of S and m is the number of variables in RePair(T). We implemented our O(min(N, nm log N) m)-time algorithm and show it can actually run in compressed space. We also present a new approach to reduce the peak memory usage of existing RePair algorithms combining with our algorithms, and show that the new approach outperforms, both in computation time and space, the most space efficient linear-time RePair implementation to date.

DOI： 10.1109/DCC.2019.00060

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85066320396&origin=inward

担当区分：筆頭著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2018 Elsevier B.V. We show that the number of all maximal α-gapped repeats and palindromes of a word of length n is at most 3(π2/6+5/2)αn and 7(π2/6+1/2)αn−3n−1, respectively.

DOI： 10.1016/j.tcs.2018.06.033

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85049535167&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Two strings of equal length are called k-Abelian equivalent, if they share the same multi-set of factors of length at most k. Ehlers et al. [JDA, 2015] considered the k-Abelian pattern matching problem, where the task is to find all factors in a text T that are k-Abelian equivalent to a pattern P. They claimed a number of algorithmic results for the off-line and on-line versions of the k-Abelian pattern matching problem. In this paper, we first argue that some of the claimed results by Ehlers et al. [JDA, 2015] contain major errors, and then we present a new algorithm that correctly solves the offline version of the problem within the same bounds claimed by Ehlers et al., in O(n + m) time and O(m) space, where n = |T| and m = |P|. We also show how to correct errors in their online algorithm, and errors in their real-time algorithms for a slightly different problem called the extended k-Abelian pattern matching problem.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85086064946&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2018 The Authors Run-length encoded Burrows–Wheeler Transformed strings, resulting in Run-Length BWT (RLBWT), is a powerful tool for processing highly repetitive strings. We propose a new algorithm for online RLBWT working in run-compressed space, which runs in O(nlg⁡r) time and O(rlg⁡n) bits of space, where n is the length of input string S received so far and r is the number of runs in the BWT of the reversed S. We improve the state-of-the-art algorithm for online RLBWT in terms of empirical construction time. Adopting the dynamic list for maintaining a total order, we can replace rank queries in a dynamic wavelet tree on a run-length compressed string by the direct comparison of labels in a dynamic list. Enlisting the proposed online RLBWT, we can efficiently compute the LZ77 factorization in run-compressed space. The empirical results show the efficiencies of both our online RLBWT and LZ77 parsing, especially for highly repetitive strings.

DOI： 10.1016/j.jda.2018.11.002

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85056312105&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2017, Springer Science+Business Media, LLC. We show that both the Lempel–Ziv-77 and the Lempel–Ziv-78 factorization of a text of length n on an integer alphabet of size σ can be computed in O(n) time with either O(nlg σ) bits of working space, or (1 + ϵ) nlg n+ O(n) bits (for a constant ϵ> 0) of working space (including the space for the output, but not the text).

DOI： 10.1007/s00453-017-0333-1

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85025816771&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© 2018 Yoshifumi Sakai; licensed under Creative Commons License CC-BY. An Elastic-Degenerate String [Iliopoulus et al., LATA 2017] is a sequence of sets of strings, which was recently proposed as a way to model a set of similar sequences. We give an online algorithm for the Elastic-Degenerate String Matching (EDSM) problem that runs in O(nm √mlogm+ N) time and O(m) working space, where n is the number of elastic degenerate segments of the text, N is the total length of all strings in the text, and m is the length of the pattern. This improves the previous algorithm by Grossi et al. [CPM 2017] that runs in O(nm2 + N) time.

DOI： 10.4230/LIPIcs.CPM.2018.9

Scopus

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85048268511&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© 2018 Yoshifumi Sakai; licensed under Creative Commons License CC-BY. We revisit the problem of computing the Lyndon factorization of a string w of length N which is given as a straight line program (SLP) of size n. For this problem, we show a new algorithm which runs in O(P(n,N) + Q(n,N)n log logN) time and O(n logN + S(n,N)) space where P(n,N), S(n,N), Q(n,N) are respectively the pre-processing time, space, and query time of a data structure for longest common extensions (LCE) on SLPs. Our algorithm improves the algorithm proposed by I et al. (TCS '17), and can be more efficient than the O(N)-time solution by Duval (J. Algorithms '83) when w is highly compressible.

DOI： 10.4230/LIPIcs.CPM.2018.24

Scopus

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85048271134&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© 2018 Yoshifumi Sakai; licensed under Creative Commons License CC-BY. Lempel-Ziv 1977 (LZ77) parsing, matching statistics and the Burrows-Wheeler Transform (BWT) are all fundamental elements of stringology. In a series of recent papers, Policriti and Prezza (DCC 2016 and Algorithmica, CPM 2017) showed how we can use an augmented run-length compressed BWT (RLBWT) of the reverse TR of a text T, to compute offline the LZ77 parse of T in O(n log r) time and O(r) space, where n is the length of T and r is the number of runs in the BWT of TR. In this paper we first extend a well-known technique for updating an unaugmented RLBWT when a character is prepended to a text, to work with Policriti and Prezza's augmented RLBWT. This immediately implies that we can build online the LZ77 parse of T while still using O(n log r) time and O(r) space; it also seems likely to be of independent interest. Our experiments, using an extension of Ohno, Takabatake, I and Sakamoto's (IWOCA 2017) implementation of updating, show our approach is both time- and space-efficient for repetitive strings. We then show how to augment the RLBWT further -albeit making it static again and increasing its space by a factor proportional to the size of the alphabet -such that later, given another string S and O(log log n)-time random access to T, we can compute the matching statistics of S with respect to T in O(|S| log log n) time.

DOI： 10.4230/LIPIcs.CPM.2018.7

Scopus

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85048304169&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2017, The Author(s). An α-gapped repeat (α ≥ 1) in a word w is a factor uvu of w such that |uv| ≤ α|u|; the two occurrences of u are called arms of this α-gapped repeat. An α-gapped repeat is called maximal if its arms cannot be extended simultaneously with the same character to the right nor to the left. We show that the number of all maximal α-gapped repeats occurring in words of length n is upper bounded by 18αn. In the case of α-gapped palindromes, i.e., factors uvu⊺ with |uv|≤ α|u|, we show that the number of all maximal α-gapped palindromes occurring in words of length n is upper bounded by 28αn + 7n. Both upper bounds allow us to construct algorithms finding all maximal α-gapped repeats and/or all maximal α-gapped palindromes of a word of length n on an integer alphabet of size nO(1) in O(αn) time. The presented running times are optimal since there are words that have Θ(αn) maximal α-gapped repeats/palindromes.

DOI： 10.1007/s00224-017-9794-5

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85028529401&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing AG, part of Springer Nature 2018. Run-length encoding Burrows-Wheeler Transformed strings, resulting in Run-Length BWT (RLBWT), is a powerful tool for processing highly repetitive strings. We propose a new algorithm for online RLBWT working in run-compressed space, which runs in O(n lg r) time and O(r lg n) bits of space, where n is the length of input string S received so far and r is the number of runs in the BWT of the reversed S. We improve the state-of-the-art algorithm for online RLBWT in terms of empirical construction time. Adopting the dynamic list for maintaining a total order, we can replace rank queries in a dynamic wavelet tree on a run-length compressed string by the direct comparison of labels in a dynamic list. The empirical result for various benchmarks show the efficiency of our algorithm, especially for highly repetitive strings.

DOI： 10.1007/978-3-319-78825-8_33

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85046002496&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Springer Nature Switzerland AG 2018. We study a new generalization of palindromes and gapped palindromes called block palindromes. A block palindrome is a string that becomes a palindrome when identical substrings are replaced with a distinct character. We investigate several properties of block palindromes and in particular, study substrings of a string which are block palindromes. In so doing, we introduce the notion of a maximal block palindrome, which leads to a compact representation of all block palindromes that occur in a string. We also propose an algorithm which enumerates all maximal block palindromes that appear in a given string T in O(|T|+||MBP(T)||) time, where ||MBP(T)|| is the output size, which is optimal unless all the maximal block palindromes can be represented in a more compact way.

DOI： 10.1007/978-3-030-00479-8_15

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85054822428&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

<p>A grammar compression is a restricted context-free grammar (CFG) that derives a single string deterministically. The goal of a grammar compression algorithm is to develop a smaller CFG by finding and removing duplicate patterns, which is simply a frequent pattern discovery process. Any frequent pattern can be obtained in linear time; however, a huge working space is required for longer patterns, and the entire string must be preloaded into memory. We propose an <i>online</i> algorithm to address this problem approximately within compressed space. For an input sequence of symbols, <i>a</i>₁,<i>a</i>₂,..., let <i>G_i</i> be a grammar compression for the string <i>a</i>₁<i>a</i>₂…<i>a_i</i>. In this study, an online algorithm is considered one that can compute <i>G</i>_<i>i</i>+1 from (<i>G_i</i>,<i>a</i>_<i>i</i>+1) without explicitly decompressing <i>G_i</i>. Here, let <i>G</i> be a grammar compression for string <i>S</i>. We say that variable <i>X</i> approximates a substring <i>P</i> of <i>S</i> within approximation ratio <i>δ</i> iff for any interval [<i>i</i>,<i>j</i>] with <i>P</i>=<i>S</i>[<i>i</i>,<i>j</i>], the parse tree of <i>G</i> has a node labeled with <i>X</i> that derives <i>S</i>[<i>l</i>,<i>r</i>] for a subinterval [<i>l</i>,<i>r</i>] of [<i>i</i>,<i>j</i>] satisfying |[<i>l</i>,<i>r</i>]|≥<i>δ</i>|[<i>i</i>,<i>j</i>]|. Then, <i>G</i> solves the frequent pattern discovery problem approximately within <i>δ</i> iff for any frequent pattern <i>P</i> of <i>S</i>, there exists a variable that approximates <i>P</i> within <i>δ</i>. Here, <i>δ</i> is called the approximation ratio of <i>G</i> for <i>S</i>. Previously, the best approximation ratio obtained by a polynomial time algorithm was Ω(1/lg²|<i>P</i>|). The main contribution of this work is to present a new lower bound Ω(1/<^*|<i>S</i>|lg|<i>P</i>|) that is smaller than the previous bound when lg^*|<i>S</i>|<lg|<i>P</i>|. Experimental results demonstrate that the proposed algorithm extracts sufficiently long frequent patterns and significantly reduces memory consumption compared to the offline algorithm in the previous work.</p>

DOI： 10.1587/transinf.2017FCP0010

CiNii Article

その他リンク： https://ci.nii.ac.jp/naid/130006414054

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing AG, part of Springer Nature 2018. We propose a new LZ78-style grammar compression algorithm, named LZ-ABT, which is a simple online algorithm to create, given a string of length N over an alphabet of size σ, an α -balanced grammar in O(N logN log σ) time and O(n) space in addition to the input string, where n is the grammar size to output. LZ-ABT can avoid the lower-bound of Ω(N5/4) time of the naive algorithms for LZMW and LZD, other LZ78-style compression algorithms, which was observed in [Badkobeh et al. SPIRE 2017, pp. 51–67]. We also show that the algorithm can be executed in compressed space, i.e., without storing the whole input string explicitly in memory: in O(N log2 N log σ) time and O(n) space, or O(N logN log σ) time and O(n log* N) space. We implement LZ-ABT running in O(N logN log σ) time and O(N) space and empirically show that its performance is competitive to LZD. This is the first practical implementation of α -balanced grammar compression to the best of our knowledge.

DOI： 10.1007/978-3-319-94667-2_27

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85049890021&origin=inward

担当区分：筆頭著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© 2018, Springer Nature Switzerland AG. Repetitions in a string are fundamental properties the string possesses, which have been extensively studied in word combinatorics and utilized in many efficient string processing algorithms. Particularly maximal repetitions, also known as runs, are useful for representing all the repetitions in the string. Since it was shown that the number of runs in a string of length n is upper bounded by O(n) [Kolpakov and Kucherov, FOCS, pp. 596–604, 1999], the following conjecture (known as the “runs” conjecture) have been attracting the attention of many researchers: The number of runs in a string of length n is upper bounded by n. This conjecture was recently solved affirmatively using a characterization based on Lyndon words [Bannai et al., SIAM J Comput, pp. 1501–1514, 2017]. The characterization not only gives a surprisingly simple proof to the 15-years open problem but also provides completely new insights on how repetitions are packed into a string. In this article, we will briefly review the runs theorem and some related topics.

DOI： 10.1007/978-3-319-98654-8_2

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85053865754&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© 2018, Springer Nature Switzerland AG. We propose the first two-party protocol for securely computing an extended edit distance. The parties possessing their respective strings x and y want to securely compute the edit distance with move operations (EDM), that is, the minimum number of insertions, deletions, renaming of symbols, or substring moves required to transform x to y. Although computing the exact EDM is NP-hard, there exits an almost linear-time algorithm within the approximation ratio *NN for. We extend this algorithm to the privacy-preserving computation enlisting the homomorphic encryption scheme so that the party can obtain the approximate EDM without revealing their privacy under the semi-honest model.

DOI： 10.1007/978-3-030-02224-2_18

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85055117003&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

A grammar compression is a context-free grammar (CFG) deriving a single string deterministically. For an input string of length N over an alphabet of size σ, the smallest CFG is O(lgN)-Approximable in the offline setting and O(lgN lg∗ N)-Approximable in the online setting. In addition, an information-Theoretic lower bound for representing a CFG in Chomsky normal form of n variables is lg(n!/nσ) + n + o(n) bits. Although there is an online grammar compression algorithm that directly computes the succinct encoding of its output CFG with O(lgN lg∗ N) approximation guarantee, the problem of optimizing its working space has remained open. We propose a fully-online algorithm that requires the fewest bits of working space asymptotically equal to the lower bound in O(N lg lg n) compression time. In addition we propose several techniques to boost grammar compression and show their efficiency by computational experiments.

DOI： 10.4230/LIPIcs.ESA.2017.67

Scopus

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85030564164&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2017 Elsevier B.V. The Lyndon factorization of a string w is a unique factorization ℓ1p1,…,ℓmpm of w such that ℓ1,…,ℓm is a sequence of Lyndon words that is monotonically decreasing in lexicographic order. In this paper, we consider the reverse-engineering problem on Lyndon factorization: Given a sequence S=((s1,p1),…,(sm,pm)) of ordered pairs of positive integers, find a string w whose Lyndon factorization corresponds to the input sequence S, i.e., the Lyndon factorization of w is in a form of ℓ1p1,…,ℓmpm with |ℓi|=si for all 1≤i≤m. Firstly, we show that there exists a simple O(n)-time algorithm if the size of the alphabet is unbounded, where n is the length of the output string. Secondly, we present an O(n)-time algorithm to compute a string over an alphabet of the smallest size. Thirdly, we show how to compute only the size of the smallest alphabet in O(m) time. Fourthly, we give an O(m)-time algorithm to compute an O(m)-size representation of a string over an alphabet of the smallest size. Finally, we propose an efficient algorithm to enumerate all strings whose Lyndon factorizations correspond to S.

DOI： 10.1016/j.tcs.2017.05.038

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85020825934&origin=inward

担当区分：筆頭著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Tomohiro I. Given two positions i and j in a string T of length N, a longest common extension (LCE) query asks for the length of the longest common prefix between suffixes beginning at i and j. A compressed LCE data structure stores T in a compressed form while supporting fast LCE queries. In this article we show that the recompression technique is a powerful tool for compressed LCE data structures. We present a new compressed LCE data structure of size O(z lg(N/z)) that supports LCE queries in O(lg N) time, where z is the size of Lempel-Ziv 77 factorization without self-reference of T. Given T as an uncompressed form, we show how to build our data structure in O(N) time and space. Given T as a grammar compressed form, i.e., a straight-line program of size n generating T, we show how to build our data structure in O(nlg(N/n)) time and O(n + z lg(N/z)) space. Our algorithms are deterministic and always return correct answers.

DOI： 10.4230/LIPIcs.CPM.2017.18

Scopus

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85027268431&origin=inward

担当区分：筆頭著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2016 Elsevier B.V. We present two efficient algorithms which, given a compressed representation of a string w of length N, compute the Lyndon factorization of w. Given a straight line program (SLP) S of size n that describes w, the first algorithm runs in O(n2+P(n,N)+Q(n,N)nlog⁡n) time and O(n2+S(n,N)) space, where P(n,N), S(n,N), Q(n,N) are respectively the pre-processing time, space, and query time of a data structure for longest common extensions (LCE) on SLPs. Given the Lempel–Ziv 78 encoding of size s for w, the second algorithm runs in O(slog⁡s) time and space.

DOI： 10.1016/j.tcs.2016.03.005

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84961175476&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2016 Elsevier B.V. A closed string is a string with a proper substring that occurs in the string as a prefix and a suffix, but not elsewhere. Closed strings were introduced by Fici (2011) as objects of combinatorial interest in the study of Trapezoidal and Sturmian words. In this paper we present algorithms for computing closed factors (substrings) in strings. First, we consider the problem of greedily factorizing a string into a sequence of longest closed factors. We describe an algorithm for this problem that uses linear time and space. We then consider the related problem of computing, for every position in the string, the longest closed factor starting at that position. We describe a simple algorithm for the problem that runs in O(nlogn/loglogn) time, where n is the length of the string. This also leads to an algorithm to compute the maximal closed factor containing (i.e. covering) each position in the string in O(nlogn/loglogn) time. We also present linear time algorithms to factorize a string into a sequence of shortest closed factors of length at least two, to compute the shortest closed factor of length at least two starting at each position of the string, and to compute a minimal closed factor of length at least two containing each position of the string.

DOI： 10.1016/j.dam.2016.04.009

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84967167017&origin=inward

記述言語：日本語   掲載種別：研究論文（学術雑誌）

DOI： 10.11517/jsaifpai.101.0_06

CiNii Article

CiNii Research

その他リンク： http://id.ndl.go.jp/bib/027587749

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. A Longest Common Extension (LCE) query on a text T of length N asks for the length of the longest common prefix of suffixes starting at given two positions. We show that the signature encoding G of size w = O(min(z logN log∗M,N)) [Mehlhorn et al., Algorithmica 17(2):183- 198, 1997] of T, which can be seen as a compressed representation of T, has a capability to support LCE queries in O(logN + log ℓ log∗M) time, where ℓ is the answer to the query, z is the size of the Lempel-Ziv77 (LZ77) factorization of T, and M ≥ 4N is an integer that can be handled in constant time under word RAM model. In compressed space, this is the fastest deterministic LCE data structure in many cases. Moreover, G can be enhanced to support efficient update operations: After processing G in O(wfA) time, we can insert/delete any (sub)string of length y into/from an arbitrary position of T in O((y + logN log∗M)fA) time, where fA = O(min{log log M log log w/log log log M, √log w/log log w}). This yields the first fully dynamic LCE data structure working in compressed space. We also present efficient construction algorithms from various types of inputs: We can construct G in O(NfA) time from uncompressed string T; in O(n log log(n log∗M) logN log∗M) time from grammar-compressed string T represented by a straight-line program of size n; and in O(zfA logN log∗M) time from LZ77-compressed string T with z factors. On top of the above contributions, we show several applications of our data structures which improve previous best known results on grammar-compressed string processing.

DOI： 10.4230/LIPIcs.MFCS.2016.72

Scopus

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85012885943&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Yuka Tanimura, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Simon J. Puglisi, and Masayuki Takeda. Given a string S of n symbols, a longest common extension query LCE(i, j) asks for the length of the longest common prefix of the ith and jth suffixes of S. LCE queries have several important applications in string processing, perhaps most notably to suffix sorting. Recently, Bille et al. (J. Discrete Algorithms 25:42-50, 2014, Proc. CPM 2015:65-76) described several data structures for answering LCE queries that offers a trade-off between data structure size and query time. In particular, for a parameter 1 ≤ τ ≤ n, their best deterministic solution is a data structure of size O(n/τ) which allows LCE queries to be answered in O(τ) time. However, the construction time for all deterministic versions of their data structure is quadratic in n. In this paper, we propose a deterministic solution that achieves a similar space-time trade-off of O(τ min{log τ, log n/τ}) query time using O(n/τ) space, but we significantly improve the construction time to O(nτ).

DOI： 10.4230/LIPIcs.CPM.2016.1

Scopus

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85011977600&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, and Florin Manea; licensed under Creative Commons License CC-BY. For α ≥ 1, an α-gapped repeat in a word w is a factor uvu of w such that |uv| ≤ α|u|; the two occurrences of a factor u in such a repeat are called arms. Such a repeat is called maximal if its arms cannot be extended simultaneously with the same symbol to the right nor to the left. We show that the number of all maximal α-gapped repeats occurring in words of length n is upper bounded by 18αn, allowing us to construct an algorithm finding all maximal α-gapped repeats of a word on an integer alphabet of size nO(1); in O(αn) time. This result is optimal as there are words that have Θ(αn) maximal α-gapped repeats. Our techniques can be extended to get comparable results in the case of α-gapped palindromes, i.e., factors uvuT with |uv| ≤ α|u|.

DOI： 10.4230/LIPIcs.STACS.2016.39

Scopus

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84961615105&origin=inward

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

In this paper, we propose a new dynamic compressed index of O(w) space for a dynamic text T, where w = O(min(z logN log-M,N)) is the size of the signature encoding of T, z is the size of the Lempel-Ziv77 (LZ77) factorization of T, N is the length of T, and M ≥ 4N is an integer that can be handled in constant time under word RAM model. Our index supports searching for a pattern P in T in O(|P|fA + log w log |P| log-M(logN + log |P| log-M) + occ logN) time and insertion/deletion of a substring of length y in O((y + logN log-M) log w logN log-M) time, where fA = O(min{log logM log log w log log logM , √ log w log log w}). Also, we propose a new spaceefficient LZ77 factorization algorithm for a given text of length N, which runs in O(NfA + z log w log3 N(log- N)2) time with O(w) working space.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85027267678&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Springer-Verlag Berlin Heidelberg 2016. Given a rewritable text T of length n on an alphabet of size σ, we propose an online algorithm computing the sparse suffix array and the sparse longest common prefix array of T in (formula presented) time by using the text space and O(m) additional working space, where m ≤ n is the number of suffixes to be sorted (provided online and arbitrarily), and c ≥ m is the number of characters that must be compared for distinguishing the designated suffixes.

DOI： 10.1007/978-3-662-49529-2_36

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84961711921&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2015 Elsevier B.V. We present the first worst-case linear-time algorithm to compute the Lempel-Ziv 78 factorization of a given string over an integer alphabet. Our algorithm is based on nearest marked ancestor queries on the suffix tree of the given string. We also show that the same technique can be used to construct the position heap of a set of strings in worst-case linear time, when the set of strings is given as a trie.

DOI： 10.1016/j.ipl.2015.04.002

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84927723236&origin=inward

記述言語：英語   掲載種別：研究論文（学術雑誌）

© 2015 Elsevier B.V.. We address a variant of the dictionary matching problem where the dictionary is represented by a straight line program (SLP). For a given SLP-compressed dictionary D of size n and height h representing m patterns of total length N, we present an O(n2log N)-size representation of Aho-Corasick automaton which recognizes all occurrences of the patterns in D in amortized O(h+m) running time per character. We also propose an algorithm to construct this compressed Aho-Corasick automaton in O(n3log n log N) time and O(n2log N) space. In a spacial case where D represents only a single pattern, we present an O(n log N)-size representation of the Morris-Pratt automaton which permits us to find all occurrences of the pattern in amortized O(h) running time per character, and we show how to construct this representation in O(n3log n log N) time with O(n2log N) working space.

DOI： 10.1016/j.tcs.2015.01.019

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84951866541&origin=inward

担当区分：筆頭著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© 2014 Elsevier Inc. All rights reserved. We address the problems of detecting and counting various forms of regularities in a string represented as a straight-line program (SLP) which is essentially a context free grammar in the Chomsky normal form. Given an SLP of size n that represents a string s of length N, our algorithm computes all runs and squares in s in O(n3h) time and O(n2) space, where h is the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in O(n3h + gnh log N) time and O(n2) space, where g is the length of the gap. As one of the main components of the above solution, we propose a new technique called approximate doubling which seems to be a useful tool for a wide range of algorithms on SLPs. Indeed, we show that the technique can be used to compute the periods and covers of the string in O(n2h) time and O(nh(n + log2 N)) time, respectively.

DOI： 10.1016/j.ic.2014.09.009

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85027953511&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

Copyright © 2015 by the Society for Industrial and Applied Mathmatics. We give a new characterization of maximal repetitions (or runs) in strings, using a tree defined on recursive standard factorizations of Lyndon words, called the Lyndon tree. The characterization leads to a remarkably simple novel proof of the linearity of the maximum number of runs p(n) in a string of length n. Furthermore, we show an upper bound of p(n) < 1.5n, which improves on the best upper bound 1.6n (Crochemore & Hie 2008) that does not rely on computational verification. The proof also gives rise to a new, conceptually simple linear-time algorithm for computing all the runs in a string. A notable characteristic of our algorithm is that, unlike all existing linear-time algorithms, it does not utilize the Lempel-Ziv factorization of the string.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84938221386&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing Switzerland 2015. In [3], a short and elegant proof was presented showing that a word of length n contains at most n - 3 runs. Here we show, using the same technique and a computer search, that the number of runs in a binary word of length n is at most 22/23n < 0.957n.

DOI： 10.1007/978-3-319-23826-5_27

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84944682455&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing Switzerland 2015. We study the sequence of Fibonacci words and some of its derivatives with respect to their suffix array, inverse suffix array and Burrows-Wheeler transform based on the respective suffix array.We show that the suffix array is a rotation of its inverse under certain conditions, and that the factors of the LZ77 factorization of any Fibonacci word yield again similar characteristics.

DOI： 10.1007/978-3-319-23660-5_12

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84945955196&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing Switzerland 2015. A string x = uvu with both u, v being non-empty is called a gapped repeat with period p = |uv|, and is denoted by pair (x, p). If p ≤ α(|x| − p) with α > 1, then (x, p) is called an α-gapped repeat. An occurrence [i, i+|x|−1] of an α-gapped repeat (x, p) in a string w is called a maximal α-gapped repeat of w, if it cannot be extended either to the left or to the right in w with the same period p. Kolpakov et al. (CPM 2014) showed that, given a string of length n over a constant alphabet, all the occurrences of maximal α-gapped repeats in the string can be computed in O(α2n+occ) time, where occ is the number of occurrences. In this paper, we propose a faster O(αn + occ)-time algorithm to solve this problem, improving the result of Kolpakov et al. by a factor of α.

DOI： 10.1007/978-3-319-23826-5_13

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84944682942&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Springer-Verlag Berlin Heidelberg 2015. Strings u, v are said to be Abelian equivalent if u is a permutation of the characters appearing in v. A string w is said to have a full Abelian period p if w = w1 …wk, where all wi’s are of length p each and are all Abelian equivalent. This paper studies reverse-engineering problems on full Abelian periods. Given a positive integer n and a set D of divisors of n, we show how to compute in O(n) time the lexicographically smallest string of length n which has all elements of D as its full Abelian periods and has the minimum number of full Abelian periods not in D. Moreover, we give an algorithm to enumerate all such strings in amortized constant time per output after O(n)-time preprocessing. Also, we show how to enumerate the strings which have all elements of D as its full Abelian periods in amortized constant time per output after O(n)-time preprocessing.

DOI： 10.1007/978-3-662-48971-0_64

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84951950947&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing Switzerland 2015. We present a compact semi-dynamic text index which allows us to find short patterns efficiently. For parameters k ≤ q ≤ logσ n − logσ logσ n and alphabet size σ = O(polylog(n)), all occ occurrences of a pattern of length at most q−k+1 can be obtained in O(k×occ +logσ n) time, where n is the length of the text. Adding characters to the end of the text is supported in amortized constant time. Our index requires (n/k) log(n/k) + n log σ + o(n) bits of space, which is compact (i.e., O(n log σ)) when k = Θ(logσ n). As a byproduct, we present a succinct van Emde Boas tree which supports insertion, deletion, predecessor, and successor on a dynamic set of integers over the universe [0,m − 1] in O(log logm) time and requires only m + o(m) bits of space.

DOI： 10.1007/978-3-319-19929-0_30

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84948993636&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Springer International Publishing Switzerland 2015. For both the Lempel Ziv 77- and 78-factorization we propose factorization algorithms using (1 + ε)n lg n + O(n) bits (for any positive constant ε ≤ 1) working space (including the space for the output) for any text of size n over an integer alphabet in O(n/ε2) time.

DOI： 10.1007/978-3-319-19929-0_15

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84948952875&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Jun'ichi Yamamoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda. We present a new on-line algorithm for computing the Lempel-Ziv factorization of a string that runs in O(N logN) time and uses only O(N log σ) bits of working space, where N is the length of the string and σ is the size of the alphabet. This is a notable improvement compared to the performance of previous on-line algorithms using the same order of working space but running in either O(N log3N) time (Okanohara & Sadakane 2009) or O(N log2N) time (Starikovskaya 2012). The key to our new algorithm is in the utilization of an elegant but less popular index structure called Directed Acyclic Word Graphs, or DAWGs (Blumer et al. 1985). We also present an opportunistic variant of our algorithm, which, given the run length encoding of size m of a string of length N, computes the Lempel-Ziv factorization of the string on-line, in O (m · min{n (log logm)(log logN)/log log logN , √ logm/log logm o})time and O(mlogN) bits of space.

DOI： 10.4230/LIPIcs.STACS.2014.675

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84907858098&origin=inward

担当区分：筆頭著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Tomohiro I, Juha Kärkkäinen, and Dominik Kempa. The sparse suffix sorting problem is to sort b = o(n) arbitrary suffixes of a string of length n using o(n) words of space in addition to the string. We present an O(n) time Monte Carlo algorithm using O(b log b) space and an O(n log b) time Las Vegas algorithm using O(b) space. This is a significant improvement over the best prior solutions by Bille et al. (ICALP 2013): a Monte Carlo algorithm running in O(n log b) time and O(b1+ε) space or O(n log2b) time and O(b) space, and a Las Vegas algorithm running in O(n log2b+b2log b) time and O(b) space. All the above results are obtained with high probability not just in expectation.

DOI： 10.4230/LIPIcs.STACS.2014.386

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84907811406&origin=inward

担当区分：筆頭著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

A suffix tree, which provides us with a linear space full-text index of a given string, is a fundamental data structure for string processing and information retrieval. In this paper we consider the reverse engineering problem on suffix trees: given an unlabeled ordered rooted tree T accompanied with a node-to-node transition function f, infer a string whose suffix tree and its suffix links for inner nodes are isomorphic to T and f, respectively. Also, we consider the enumeration problem in which we enumerate all strings corresponding to an input tree and links. By introducing new characterizations of suffix trees, we show that the reverse engineering problem and the enumeration problem on suffix trees on a binary alphabet can be solved in optimal time. © 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2013.02.033

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84889665144&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

The Lyndon factorization of a string w is a unique factorization ℓp11,⋯, ℓpmm of w s.t. ℓ1,⋯, ℓm is a sequence of Lyndon words that is monotonically decreasing in lexicographic order. In this paper, we consider the reverse-engineering problem on Lyndon factorization: Given a sequence S = ((s1, p1),⋯, (sm, p m)) of ordered pairs of positive integers, find a string w whose Lyndon factorization corresponds to the input sequence S, i.e., the Lyndon factorization of w is in a form of ℓp11,⋯, ℓpmm with |ℓi| = si for all 1 ≤ i ≤ m. Firstly, we show that there exists a simple O(n)-time algorithm if the size of the alphabet is unbounded, where n is the length of the output string. Secondly, we present an O(n)-time algorithm to compute a string over an alphabet of the smallest size. Thirdly, we show how to compute only the size of the smallest alphabet in O(m) time. Fourthly, we give an O(m)-time algorithm to compute an O(m)-size representation of a string over an alphabet of the smallest size. Finally, we propose an efficient algorithm to enumerate all strings whose Lyndon factorizations correspond to S. © 2014 Springer-Verlag Berlin Heidelberg.

DOI： 10.1007/978-3-662-44465-8_48

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84906230308&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

A palindromic factorization of a string w is a factorization of w consisting only of palindromic substrings of w. In this paper, we present an on-line O(n logn)-time O(n)-space algorithm to compute smallest palindromic factorizations of all prefixes of w, where n is the length of a given string w. We then show how to extend this algorithm to compute smallest maximal palindromic factorizations of all prefixes of w, consisting only of maximal palindromes (non-extensible palindromic substring) of each prefix, in O(n logn) time and O(n) space, in an on-line manner. We also present an on-line O(n)-time O(n)-space algorithm to compute a smallest palindromic cover of w. © 2014 Springer International Publishing Switzerland.

DOI： 10.1007/978-3-319-07566-2_16

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84958527699&origin=inward

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

© Czech Technical University in Prague, Czech Republic. A closed string is a string with a proper substring that occurs in the string as a prefix and a suffix, but not elsewhere. Closed strings were introduced by Fici (Proc. WORDS, 2011) as objects of combinatorial interest in the study of Trapezoidal and Sturmian words. In this paper we consider algorithms for computing closed factors (substrings) in strings, and in particular for greedily factorizing a string into a sequence of longest closed factors. We describe an algorithm for this problem that uses linear time and space. We then consider the related problem of computing, for every position in the string, the longest closed factor starting at that position. We describe a simple algorithm for the problem that runs in O(n log n/ log log n) time.

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84928791807&origin=inward