2,374 research outputs found
Lyndon Arrays Simplified
No full textA Lyndon word is a string that is lexicographically smaller than all of its proper suffixes (e.g., "airbus" is a Lyndon word; "amtrak" is not a Lyndon word because its suffix "ak" is lexicographically smaller than "amtrak"). The Lyndon array (sometimes called Lyndon table) identifies the longest Lyndon prefix of each suffix of a string. It is well known that the Lyndon array of a length-n string can be computed in O(n) time. However, most of the existing algorithms require the suffix array, which has theoretical and practical disadvantages. The only known algorithms that compute the Lyndon array in O(n) time without the suffix array (or similar data structures) do so in a particularly space efficient way (Bille et al., ICALP 2020), or in an online manner (Badkobeh et al., CPM 2022). Due to the additional goals of space efficiency and online computation, these algorithms are complicated in technical detail. Using the main ideas of the aforementioned algorithms, we provide a simpler and easier to understand algorithm that computes the Lyndon array in O(n) time
Linear Time Runs Over General Ordered Alphabets
No full textA run in a string is a maximal periodic substring. For example, the string bananatree contains the runs anana = (an)^{5/2} and ee = e². There are less than n runs in any length-n string, and computing all runs for a string over a linearly-sortable alphabet takes (n) time (Bannai et al., SIAM J. Comput. 2017). Kosolobov conjectured that there also exists a linear time runs algorithm for general ordered alphabets (Inf. Process. Lett. 2016). The conjecture was almost proven by Crochemore et al., who presented an (nα(n)) time algorithm (where α(n) is the extremely slowly growing inverse Ackermann function). We show how to achieve (n) time by exploiting combinatorial properties of the Lyndon array, thus proving Kosolobov’s conjecture. This also positively answers the at least 29-year-old question whether square-freeness can be tested in linear time over general ordered alphabets (Breslauer, PhD thesis, Columbia University 1992)
Lyndon Arrays in Sublinear Time
No full textA Lyndon word is a string that is lexicographically smaller than all of its non-trivial suffixes. For example, airbus is a Lyndon word, but amtrak is not a Lyndon word due to its suffix ak. The Lyndon array stores the length of the longest Lyndon prefix of each suffix of a string. For a length-n string over a general ordered alphabet, the array can be computed in O(n) time (Bille et al., ICALP 2020). However, on a word-RAM of word-width w ≥ log₂ n, linear time is not optimal if the string is over integer alphabet {0, … , σ} with σ ≪ n. In this case, the string can be stored in O(n log σ) bits (or O(n / log_σ n) words) of memory, and reading it takes only O(n / log_σ n) time. We show that O(n / log_σ n) time and words of space suffice to compute the succinct 2n-bit version of the Lyndon array. The time is optimal for w = O(log n). The algorithm uses precomputed lookup tables to perform significant parts of the computation in constant time. This is possible due to properties of periodic substrings, which we carefully analyze to achieve the desired result. We envision that the algorithm has applications in the computation of runs (maximal periodic substrings), where the Lyndon array plays a central role in both theoretically and practically fast algorithms
Minimal Generators in Optimal Time
No full textA walk of length n on a string S of length m is a function f : {1, … , n} → {1, … , m} such that ∀ i ∈ {2, … , n} : |f(i) - f(i - 1)| ≤ 1. The walk generates the string T of length n defined by {∀ i ∈ {1, … , n} : T[i] = S[f(i)]}. Intuitively, this can be seen as walking n steps in S and outputting the encountered symbols, where in each step we either remain at the same position, or move one position to the left or to the right. The minimal generator of a string T is the shortest string S such that a walk on S generates T. Recently, it was shown that each string admits exactly one (up to reversal) minimal generator (Pratt-Hartmann, CPM 2024). However, no efficient algorithm for computing the minimal generator was known. We provide an optimal algorithm for this task, taking {O}(n) time for a string of length n over general unordered alphabet, i.e., accessing the string only by equality comparisons of symbols. The main challenge is to detect substrings of the form axbx̃axb and replace them with axb, where a,b are symbols and x is a string with reversal x̃. We solve this problem with a non-trivial adaptation of Manacher’s classic algorithm for computing maximal palindromic substrings (Manacher, J. ACM 1975). To obtain the final algorithm, we solve small subinstances of the problem in optimal time by adapting the "Four Russians" technique to strings over general unordered alphabet, which may be of independent interest
Lyndon Words Accelerate Suffix Sorting
No full textSuffix sorting is arguably the most fundamental building block in string algorithmics, like regular sorting in the broader field of algorithms. It is thus not surprising that the literature is full of algorithms for suffix sorting, in particular focusing on their practicality. However, the advances on practical suffix sorting stalled with the emergence of the DivSufSort algorithm more than 10 years ago, which, up to date, has remained the fastest suffix sorter. This article shows how properties of Lyndon words can be exploited algorithmically to accelerate suffix sorting again. Our new algorithm is 6-19% faster than DivSufSort on real-world texts, and up to three times as fast on artificial repetitive texts. It can also be parallelized, where similar speedups can be observed. Thus, we make the first advances in practical suffix sorting after more than a decade of standstill
A Parallel Framework for Approximate Max-Dicut in Partitionable Graphs
No full textComputing a maximum cut in undirected and weighted graphs is a well studied problem and has many practical solutions that also scale well in shared memory (despite its NP-completeness). For its counterpart in directed graphs, however, we are not aware of practical solutions that also utilize parallelism. We engineer a framework that computes a high quality approximate cut in directed and weighted graphs by using a graph partitioning approach. The general idea is to partition a graph into k subgraphs using a parallel partitioning algorithm of our choice (the first ingredient of our framework). Then, for each subgraph in parallel, we compute a cut using any polynomial time approximation algorithm (the second ingredient). In a final step, we merge the locally computed solutions using a high-quality or exact parallel Max-Dicut algorithm (the third ingredient). On graphs that can be partitioned well, the quality of the computed cut is significantly better than the best cut achieved by any linear time algorithm. This is particularly relevant for large graphs, where linear time algorithms used to be the only feasible option
Bidirectional Text Compression in External Memory
No full textBidirectional compression algorithms work by substituting repeated substrings by references that, unlike in the famous LZ77-scheme, can point to either direction. We present such an algorithm that is particularly suited for an external memory implementation. We evaluate it experimentally on large data sets of size up to 128 GiB (using only 16 GiB of RAM) and show that it is significantly faster than all known LZ77 compressors, while producing a roughly similar number of factors. We also introduce an external memory decompressor for texts compressed with any uni- or bidirectional compression scheme
Accentuation of Jonas Rėza's Psalter of 1625
No full textStraipsnyje trumpai apžvelgiama dabartinių kalbų kirčio ženklų istorija – nuo Antikos kalbininko Aristofano Bizantiečio žymėtų akūto, gravio ir cirkumflekso iki Mažvydo Katekizme pažymėto į riestinį cirkumfleksą panašaus ženklo, Baltramiejaus Vilento raštų, D. Kleino gramatikos, J. Rėzos psalmyno ,,Psalteras Dowido“ kirčio ženklų. Išsamiau straipsnyje analizuojamas 1625 m. J. Rėzos psalmyno kirčiavimas, iš graikų perimti kirčio ženklai, paties autoriaus įsivestas kirčio ženklas. Straipsnyje taip pat aptariama Rėzos psalmyne vartotų kirčio ženklų funkcijos, kirčio ženklų vartojimo įvairavimas, sąsajos tarp psalmyno kirčiavimo ir D. Kleino gramatikos Reikšminiai žodžiai: Akūtas; Gravis; Cirkumfleksas; Psalmynas; Lietuvių kalbos istorija; KirčiavimasThis article gives a brief overview of the history of the accent marks of languages from Antiquity linguist Aristophanes of Byzantium marked the acute accent, grave accent and circumflex accent until the sign similar to a tilde-shaped circumflex marked in Mažvydas’ Catechism, and accent signs of Baltramiejus Vilentas’ writings, Daniel Klein‘s grammer, and Jonas Rhesa’s Psalter of David. The article gives a comprehensive analysis of the accentuation made by Jonas Rhesa in the psalter, accent marks taken from Greek, and an accent mark developed by the author himself. The article also discusses the functions of the accent marks used in Rhesa’s psalter, the variation of the usage of accent marks and the interaction between the accentuation of the psalter and D. Klein’s grammer
Jonas, Hobbes e le forme della paura
No full textThis essay aims at clarifying the concept of Jonas’s heuristic of fear. Although it has been severely criticized, fear remains an aspect of his thought which has drawn little attention, particularly regarding the role it plays in the elaboration of the imperative of responsibility. Jonas elaborates a new concept of fear, moulded by the particular form of uncertainty brought about by the technological age. Although critics have interpreted Jonas’ attempt as an ethics founded on irrationality and emotion, the present analysis shows that Jonas affirms a cognitivist theory of fear. The concept of fear he discusses in The Imperative of Responsibility is not an emotion as an immediate physical and psychological reaction, but a form of evaluative thinking that is part of responsibility. In order to illustrate form and function of fear in Jonas thought, I will refer to the meanings of fear in Hobbes, an author Jonas himself refers to
Jonas, Hobbes e le forme della paura
No full textThis essay aims at clarifying the concept of Jonas’s heuristic of fear. Although it has been severely criticized, fear remains an aspect of his thought which has drawn little attention, particularly regarding the role it plays in the elaboration of the imperative of responsibility. Jonas elaborates a new concept of fear, moulded by the particular form of uncertainty brought about by the technological age. Although critics have interpreted Jonas’ attempt as an ethics founded on irrationality and emotion, the present analysis shows that Jonas affirms a cognitivist theory of fear. The concept of fear he discusses in The Imperative of Responsibility is not an emotion as an immediate physical and psychological reaction, but a form of evaluative thinking that is part of responsibility. In order to illustrate form and function of fear in Jonas thought, I will refer to the meanings of fear in Hobbes, an author Jonas himself refers to
- …
