Search

We refine and extend Ziv's model and results regarding perfectly secure encryption of individual sequences. According to this model, the encrypter and the legitimate decrypter share a common secret key that is not shared with the unauthorized eavesdropper. The eavesdropper is aware of the encryption scheme and has some prior knowledge concerning the individual plaintext source sequence. This prior knowledge, combined with the cryptogram, is harnessed by the eavesdropper, who implements a finite-state machine as a mechanism for accepting or rejecting attempted guesses of the plaintext source. The encryption is considered perfectly secure if the cryptogram does not provide any new information to the eavesdropper that may enhance their knowledge concerning the plaintext beyond their prior knowledge. Ziv has shown that the key rate needed for perfect secrecy is essentially lower bounded by the finite-state compressibility of the plaintext sequence, a bound that is clearly asymptotically attained through Lempel–Ziv compression followed by one-time pad encryption. In this work, we consider some more general classes of finite-state eavesdroppers and derive the respective lower bounds on the key rates needed for perfect secrecy. These bounds are tighter and more refined than Ziv's bound, and they are attained using encryption schemes that are based on different universal lossless compression schemes. We also extend our findings to the case where side information is available to the eavesdropper and the legitimate decrypter but may or may not be available to the encrypter. [ABSTRACT FROM AUTHOR]

We refine and extend Ziv’s model and results regarding perfectly secure encryption of individual sequences. According to this model, the encrypter and the legitimate decrypter share a common secret key that is not shared with the unauthorized eavesdropper. The eavesdropper is aware of the encryption scheme and has some prior knowledge concerning the individual plaintext source sequence. This prior knowledge, combined with the cryptogram, is harnessed by the eavesdropper, who implements a finite-state machine as a mechanism for accepting or rejecting attempted guesses of the plaintext source. The encryption is considered perfectly secure if the cryptogram does not provide any new information to the eavesdropper that may enhance their knowledge concerning the plaintext beyond their prior knowledge. Ziv has shown that the key rate needed for perfect secrecy is essentially lower bounded by the finite-state compressibility of the plaintext sequence, a bound that is clearly asymptotically attained through Lempel–Ziv compression followed by one-time pad encryption. In this work, we consider some more general classes of finite-state eavesdroppers and derive the respective lower bounds on the key rates needed for perfect secrecy. These bounds are tighter and more refined than Ziv’s bound, and they are attained using encryption schemes that are based on different universal lossless compression schemes. We also extend our findings to the case where side information is available to the eavesdropper and the legitimate decrypter but may or may not be available to the encrypter.

Load forecasting has significant implications on optimizing the operation of air conditioning systems for industrial mushroom houses and energy saving. This research paper presents a novel approach for short-term load forecasting in mushroom houses, which face challenges in accurately modeling cold and heat loads due to the complex interplay of various factors, including climatic conditions, mushroom growth, and equipment operation. The proposed method combines empirical wavelet transform (EWT), hybrid autoregressive integrated moving average (ARIMA), convolutional neural network (CNN), and bi-directional long short-term memory (BiLSTM) with an attention mechanism (CNN-BiLSTM-Attention) to address these challenges. The first step of this method was to select input features via the Boruta algorithm. Then, the EWT method was used to decompose the load data of mushroom houses into four modal components. Subsequently, the Lempel–Ziv method was introduced to classify the modal components into high-frequency and low-frequency classes. CNN-BiLSTM-Attention and ARIMA prediction models were constructed for these two classes, respectively. Finally, the predictions from both classes were combined and reconstructed to obtain the final load forecasting value. The experimental results show that the Boruta algorithm selects key influential feature factors effectively. Compared to the Spearman and Pearson correlation coefficient methods, the mean absolute error (MAE) of the prediction results is reduced by 14.72% and 3.75%, respectively. Compared to the ensemble empirical mode decomposition (EEMD) method, the EWT method can reduce the decomposition reconstruction error by an order of magnitude of 10 3 , effectively improving the accuracy of the prediction model. The proposed model in this paper exhibits significant advantages in prediction performance compared to the single neural network model, with the MAE, root mean square error (RMSE), and mean absolute percentage error (MAPE) of the prediction results reduced by 31.06%, 26.52%, and 39.27%, respectively. [ABSTRACT FROM AUTHOR]

The increasing volume of airport flights inevitably brings about the increase of airport delay level during peak hours, so the scientific prediction of airport delay level is of great significance to ensure the efficiency of airport operation. Firstly an airport queuing network model was established based on aircraft operation characteristics. Then the Lempel-Ziv algorithm was used to calculate the complexity of flight time series at different time scales, the small time scale was determined to portray flight delays. Thus, the queuing network model parameters were determined and verified by example. Finally, the AirTop simulation software was used to simulate the trend of airport delay level with the average delay of the whole day and the average delay of the peak hour as the key indicators. By comparing the simulated data with the calculated results, it is found that the airport queuing network model can better reflect the real airport delays. And the small time scale of 15 min is chosen for the calculation of airport queuing network model parameters, the results are closer to the real airport delay level. [ABSTRACT FROM AUTHOR]

Crude oil markets have become increasingly uncertain. To study them, we first employ the decomposition-ensemble framework based on the variational mode decomposition (VMD) and Lempel–Ziv algorithms to assess the crude oil dual attributes. Three steps are involved: 1) conditional autoregressive value at risk measures the crude oil risk; 2) they are decomposed by the VMD algorithm into submodes; 3) the Lempel–Ziv algorithm is applied to analyze the crude oil risk for each, thereby identifying the oil commodity or oil financial risks. The results of the empirical analysis reveal significantly different amplitudes for the high- and low-frequency crude oil risk. By summarizing the crude oil risk components, we also conclude that the mean value for the oil commodity risk is 0.04, while that for the oil financial risk is 0. What is more, the oil commodity risk is highly related to downward trends in oil prices, while the oil financial risk exerts the same clustering effect as oil returns.

The utility of rodents for research related to atrial fibrillation (AF) is growing exponentially. However, the obtained arrhythmic waveforms are often mixed with ventricular signals and the ability to analyze regularity and complexity of such events is limited. Recently, we introduced an implantable quadripolar electrode adapted for advanced atrial electrophysiology in ambulatory rats. Notably, we have found that the implantation itself leads to progressive atrial remodeling, presumably because of mechanical loading of the atria. In the present study, we developed an algorithm to clean the atrial signals from ventricular mixing and thereafter quantify the AF substrate in an objective manner based on waveform complexity. Rats were sequentially examined 1-, 4-, and 8-wk postelectrode implantation using a standard AF triggering protocol. Preburst ventricular mixing was sampled and automatically subtracted based on QRS detection in the ECG. Thereafter, the "pure" atrial signals were analyzed by Lempel-Ziv complexity algorithm and a complexity ratio (CR) was defined for each signal by normalizing the postburst to the preburst values. Receiver operating characteristic (ROC) curve analysis indicated an optimal CR cutoff of 1.236 that detected irregular arrhythmic events with high sensitivity (94.5%), specificity (93.1%), and area under the curve (AUC) (0.96, 95% confidence interval, 0.945-0.976). Automated and unbiased analysis indicated a gradual increase in signal complexity over time with augmentation of high frequencies in power spectrum analysis. Our findings indicate that CR algorithm detects irregularity in a highly efficient manner and can also detect the atrial remodeling induced by electrode implantation. Thus, CR analysis can strongly facilitate standardized AF research in rodents. [ABSTRACT FROM AUTHOR]

Crude oil markets have become increasingly uncertain. To study them, we first employ the decomposition-ensemble framework based on the variational mode decomposition (VMD) and Lempel–Ziv algorithms to assess the crude oil dual attributes. Three steps are involved: 1) conditional autoregressive value at risk measures the crude oil risk; 2) they are decomposed by the VMD algorithm into submodes; 3) the Lempel–Ziv algorithm is applied to analyze the crude oil risk for each, thereby identifying the oil commodity or oil financial risks. The results of the empirical analysis reveal significantly different amplitudes for the high- and low-frequency crude oil risk. By summarizing the crude oil risk components, we also conclude that the mean value for the oil commodity risk is 0.04, while that for the oil financial risk is 0. What is more, the oil commodity risk is highly related to downward trends in oil prices, while the oil financial risk exerts the same clustering effect as oil returns. [ABSTRACT FROM AUTHOR]

In this paper, we propose a compression-based anomaly detection method for time series and sequence data using a pattern dictionary. The proposed method is capable of learning complex patterns in a training data sequence, using these learned patterns to detect potentially anomalous patterns in a test data sequence. The proposed pattern dictionary method uses a measure of complexity of the test sequence as an anomaly score that can be used to perform stand-alone anomaly detection. We also show that when combined with a universal source coder, the proposed pattern dictionary yields a powerful atypicality detector that is equally applicable to anomaly detection. The pattern dictionary-based atypicality detector uses an anomaly score defined as the difference between the complexity of the test sequence data encoded by the trained pattern dictionary (typical) encoder and the universal (atypical) encoder, respectively. We consider two complexity measures: the number of parsed phrases in the sequence, and the length of the encoded sequence (codelength). Specializing to a particular type of universal encoder, the Tree-Structured Lempel–Ziv (LZ78), we obtain a novel non-asymptotic upper bound, in terms of the Lambert W function, on the number of distinct phrases resulting from the LZ78 parser. This non-asymptotic bound determines the range of anomaly score. As a concrete application, we illustrate the pattern dictionary framework for constructing a baseline of health against which anomalous deviations can be detected. [ABSTRACT FROM AUTHOR]

In this paper, we propose a compression-based anomaly detection method for time series and sequence data using a pattern dictionary. The proposed method is capable of learning complex patterns in a training data sequence, using these learned patterns to detect potentially anomalous patterns in a test data sequence. The proposed pattern dictionary method uses a measure of complexity of the test sequence as an anomaly score that can be used to perform stand-alone anomaly detection. We also show that when combined with a universal source coder, the proposed pattern dictionary yields a powerful atypicality detector that is equally applicable to anomaly detection. The pattern dictionary-based atypicality detector uses an anomaly score defined as the difference between the complexity of the test sequence data encoded by the trained pattern dictionary (typical) encoder and the universal (atypical) encoder, respectively. We consider two complexity measures: the number of parsed phrases in the sequence, and the length of the encoded sequence (codelength). Specializing to a particular type of universal encoder, the Tree-Structured Lempel–Ziv (LZ78), we obtain a novel non-asymptotic upper bound, in terms of the Lambert W function, on the number of distinct phrases resulting from the LZ78 parser. This non-asymptotic bound determines the range of anomaly score. As a concrete application, we illustrate the pattern dictionary framework for constructing a baseline of health against which anomalous deviations can be detected.

We consider the problem of encoding a deterministic source sequence (i.e., individual sequence) for the degraded wiretap channel by means of an encoder and decoder that can both be implemented as finite-state machines. Our first main result is a necessary condition for both reliable and secure transmission in terms of the given source sequence, the bandwidth expansion factor, the secrecy capacity, the number of states of the encoder and the number of states of the decoder. Equivalently, this necessary condition can be presented as a converse bound (i.e., a lower bound) on the smallest achievable bandwidth expansion factor. The bound is asymptotically achievable by Lempel–Ziv compression followed by good channel coding for the wiretap channel. Given that the lower bound is saturated, we also derive a lower bound on the minimum necessary rate of purely random bits needed for local randomness at the encoder in order to meet the security constraint. This bound too is achieved by the same achievability scheme. Finally, we extend the main results to the case where the legitimate decoder has access to a side information sequence, which is another individual sequence that may be related to the source sequence, and a noisy version of the side information sequence leaks to the wiretapper.

Motivated by earlier results on universal randomized guessing, we consider an individual–sequence approach to the guessing problem: in this setting, the goal is to guess a secret, individual (deterministic) vector $x^{n}=(x_{1},\ldots,x_{n})$ , by using a finite–state machine that sequentially generates randomized guesses from a stream of purely random bits. We define the finite–state guessing exponent as the asymptotic normalized logarithm of the minimum achievable moment of the number of randomized guesses, generated by any finite–state machine, until $x^{n}$ is guessed successfully. We show that the finite–state guessing exponent of any sequence is intimately related to its finite–state compressibility (due to Lempel and Ziv), and it is asymptotically achieved by the decoder of (a certain modified version of) the 1978 Lempel–Ziv data compression algorithm (a.k.a. the LZ78 algorithm), fed by purely random bits. The results are also extended to the case where the guessing machine has access to a side information sequence, $y^{n}=(y_{1},\ldots,y_{n})$ , which is also an individual sequence. [ABSTRACT FROM AUTHOR]

The article discusses critique of Giuliano Pascucci's attribution methods rely on entropy, compression, and authorial style including BCL authorial authorship algorithm. Topics include criticizing the use of Lempel-Ziv-derived compression algorithms as a proxy for entropy; Brotli compression algorithm obtains over 20 percent better results in compressing typical web content than the LZ77-derived DEFLATE algorithm used in the zlib library.

Consider the problem of guessing the realization of a random vector ${X}$ by repeatedly submitting queries (guesses) of the form “Is ${X}$ equal to ${x}$ ?” until an affirmative answer is obtained. In this setup, a key figure of merit is the number of queries required until the right vector is identified, a number that is termed the guesswork. Typically, one wishes to devise a guessing strategy which minimizes a certain guesswork moment. In this work, we study a universal, decentralized scenario where the guesser does not know the distribution of ${X}$ , and is not allowed to use a strategy which prepares a list of words to be guessed in advance, or even remember which words were already used. Such a scenario is useful, for example, if bots within a Botnet carry out a brute–force attack in order to guess a password or decrypt a message, yet cannot coordinate the guesses between them or even know how many bots actually participate in the attack. We devise universal decentralized guessing strategies, first, for memoryless sources, and then generalize them for finite–state sources. In each case, we derive the guessing exponent, and then prove its asymptotic optimality by deriving a compatible converse bound. The strategies are based on randomized guessing using a universal distribution. We also extend the results to guessing with side information. Finally, for all above scenarios, we design efficient algorithms in order to sample from the universal distributions, resulting in strategies which do not depend on the source distribution, are efficient to implement, and can be used asynchronously by multiple agents. [ABSTRACT FROM AUTHOR]

In this work, we aim to investigate whether information based metrics of neural activity are a useful tool for the quantification of consciousness before and shortly after birth. Neural activity is measured using fetal magnetoencephalography (fMEG) in human fetuses and neonates. Based on recent theories on consciousness, information-based metrics are established to measure brain complexity and to assess different levels of consciousness. Different metrics (measures of entropy, compressibility and fractality) are, thus, explored in a reference population and their usability is evaluated. For comparative analysis, two fMEG channels were selected: one where brain activity was previously detected and one at least 15 cm away, that represented a control channel. The usability of each metric was evaluated and results from the brain and control channel were compared. Concerning the ease of use with fMEG data, Lempel-Ziv-Complexity (LZC) was evaluated as best, as it is unequivocal and needs low computational effort. The fractality measures have a high number of parameters that need to be adjusted prior to analysis and therefore forfeit comparability, while entropy measures require a higher computational effort and more parameters to adjust compared to LZC. Comparison of a channel with brain activity and a control channel in neonatal recordings showed significant differences in most complexity metrics. This clear difference can be seen as proof of concept for the usability of complexity metrics in fMEG. For fetal data, this comparison produced less clear results which can be related to leftover maternal signals included in the control channel. Further work is necessary to conclusively interpret results from the analysis of fetal recordings. Yet this study shows that complexity metrics can be used for fMEG data on early consciousness and the evaluation gives a guidance for future work. The inconsistency of results from different metrics highlights the challenges of working with complexity metrics as neural correlates of consciousness, as well as the caution one should apply to interpret them. [ABSTRACT FROM AUTHOR]

Irreducible grammars are a class of context-free grammars with well-known representatives, such as Repair (with a few tweaks), Longest Match, Greedy, and Sequential. We show that a grammar-based compression method described by Kieffer and Yang (2000) is upper bounded by the high-order empirical entropy of the string when the underlying grammar is irreducible. Specifically, given a string $S$ over an alphabet of size $\sigma $ , we prove that if the underlying grammar is irreducible, then the length of the binary code output by this grammar-based compression method is bounded by $|S|H_{k}(S) + o(|S|\log \sigma)$ for any $k\in o(\log _\sigma |S|)$ , where $H_{k}(S)$ is the $k$ -order empirical entropy of $S$. This is the first bound encompassing the whole class of irreducible grammars in terms of the high-order empirical entropy, with coefficient 1. [ABSTRACT FROM AUTHOR]

A financial price dynamics is developed based on the voter interacting system, in an attempt to investigate and reproduce the complex similarity and the fluctuation dynamics of financial markets. The complexity-invariance distance (CID) is applied to study the similarity of each stock pairs. A simple classification of seven real indexes and the simulated data is obtained according to the CID values for each stock pairs. The corresponding multiscale dynamical behaviors of CID values are also studied by combining CID with the multiscale method. Further, the similarity of the newest data and the historical data of the returns is investigated by a novel auto-CID analysis, and a corresponding exponent relationship is exhibited. Moveover, the cross correlation function (CCF) is applied to study the correlation of each stock pairs and the causalities of these stock pairs are investigated by the Granger causality method. Besides, the complexity and the randomness of fluctuations of returns, surrogate returns, shuffled returns and intrinsic mode functions (derived from empirical mode decomposition) are also explored at different thresholds with Lempel–Ziv complexity. The empirical study shows complex similarity and similar random property between the proposed price model and the real stock markets, which exhibits that the proposed model is feasible to some extent. [ABSTRACT FROM AUTHOR]

Aiming at the misdiagnosis caused by extracting the non-fault features using Lempel-Ziv algorithm, a quantitative trend fault diagnosis method of a rolling bearing based on Sparsogram and Lempel-Ziv is proposed in this paper. The approximate linear relationships between Lempel-Ziv and the fault sizes of inner and outer races are simulated with a theoretical model of rolling bearings. Then, the fault characteristic of experimental signal of bearing inner and outer race in different severity is extracted by Sparsogram algorithm, and the frequency band is selected which reflects the fault characteristic mostly, and the Lempel-Ziv complexity index of the frequency band is calculated. This method can avoid the misdiagnosis caused by extracting non-fault features. Comparing with direct calculation of Lempel-Ziv value, the performance is much better on the quantitative diagnosis of a defective bearing. The experimental results show that the proposed method can realize the quantitative trend diagnosis on defective bearings. [ABSTRACT FROM AUTHOR]

Introduction: Patients with schizophrenia show cognitive deficits that are evident both behaviourally and with EEG recordings. Recent studies have suggested that non-linear analyses of EEG might more adequately reflect the complex, irregular, non-stationary behavior of neural processes than more traditional ERP measures. Non-linear analyses have been mainly applied to EEGs from patients at rest, whereas differences in complexity might be more evident during task performance. Objective: We aimed to investigate changes in non-linear brain dynamics of patients with schizophrenia during cognitive processing. Method: 18 patients and 17 matched healthy controls were asked to name pictures. EEG data were collected at rest and while they were performing a naming task. EEGs were analyzed with the classical Lempel-Ziv Complexity (LZC) and with the Multiscale LZC. Electrodes were grouped in seven regions of interest (ROI). Results: As expected, controls had fewer naming errors than patients. Regarding EEG complexity, the interaction between Group, Task and ROI indicated that patients showed higher complexity values in right frontal regions only at rest, where no differences in complexity between patients and controls were found during the naming task. EEG complexity increased from rest to task in controls in left temporal-parietal regions, while no changes from rest to task were observed in patients. Finally, differences in complexity between patients and controls depended on the frequency bands: higher values of complexity in patients at rest were only observed in fast bands, indicating greater heterogeneity in patients in local dynamics of neuronal assemblies. Conclusion: Consistent with previous studies, schizophrenic patients showed higher complexity than controls in frontal regions at rest. Interestingly, we found different modulations of brain complexity during a simple cognitive task between patients and controls. These data can be interpreted as indicating schizophrenia-related failures to adapt brain functioning to the task, which is reflected in poorer behavioral performance. Highlights: - We measured classical and multiscale Lempel-Ziv Complexity (LZCN and MLZC) of the EEG signal of patients with schizophrenia and controls at rest and while performing a cognitive task. - We found that patients and controls showed a different pattern of brain complexity depending on their cognitive state (at rest or under cognitive challenge). - Our results illustrate the value of the MLZC in the characterization of the pattern of brain complexity in schizophrenia on function of frequency bands. - Nonlinear methodologies of EEG analysis can help to characterize brain dysfunction in schizophrenia. [ABSTRACT FROM AUTHOR]

The report entitled “L. Liu, D. Li, F. Bai, A relative Lempel-Ziv complexity: Application to comparing biological sequences, Chem. Phys. Lett. 530 (2012) 107–112” mentions on the powerful construction of phylogenetic trees based on Lempel-Ziv algorithm. On the other hand, the method explained in the paper does not give promising result on the data set on invasive Caulerpa taxifolia in the Mediterranean Sea. The phylogenetic trees are obtained by the proposed method of the aforementioned paper in this short note. [ABSTRACT FROM AUTHOR]

In this work, we developed two novel approaches to characterize dynamical properties of brain electrical activity, based on cross-prediction errors analysis. The first, a test called γ -sets, provides an efficient way to classify the data generator mechanism. The second, the μ -index, considers relevant changes in the dynamics through stationarity checking. These measures are defined by two basic properties of chaotic time series: a set of dense orbits and the similarity between its parts. The accuracy was verified for simulated signals with different dynamical properties and by the relation with other descriptive measures, Lempel–Ziv complexity and Lyapunov exponents. We applied these measures to local field potentials data, acquired from the cerebral cortex of a Wistar rat during a sleep-wake cycle, and point out evidence of deterministic components in the brain electrical activity even if it exhibits a nonstationary signature. [ABSTRACT FROM AUTHOR]

Dispersion entropy (DispEn) is a recently introduced entropymetric to quantify the uncertainty of time series. It is fast and, so far, it has demonstrated very good performance in the characterisation of time series. It includes a mapping step, but the effect of different mappings has not been studied yet. Here, we investigate the effect of linear and nonlinear mapping approaches in DispEn. We also inspect the sensitivity of different parameters of DispEn to noise. Moreover, we develop fluctuation-based DispEn (FDispEn) as ameasure to deal with only the fluctuations of time series. Furthermore, the original and fluctuation-based forbidden dispersion patterns are introduced to discriminate deterministic from stochastic time series. Finally, we compare the performance of DispEn, FDispEn, permutation entropy, sample entropy, and Lempel-Ziv complexity on two physiological datasets. The results show that DispEn is the most consistent technique to distinguish various dynamics of the biomedical signals. Due to their advantages over existing entropy methods, DispEn and FDispEn are expected to be broadly used for the characterization of a wide variety of real-world time series. [ABSTRACT FROM AUTHOR]

The measure of complexity of Lempel-Ziv (LZC) is used for the analysis of time series generated by dynamic systems with the objective of determining its complexity. This work measures LZC of different series coming from periodic functions, probabilistic functions, and chaotic systems. Later, these metrics of complexity are applied to the average of the number of parts in the waiting line in a manufacturing workshop. The results demonstrate the efficiency of the LZC to establish the level of the dynamic behavior of the manufacturing systems, through the time series. [ABSTRACT FROM AUTHOR]

In previously published work (Jordon and Moser, 2020), notions of finite-state-depth and pushdown-depth were presented. These were based on finite-state transducers and information lossless pushdown compressors. Unfortunately, a complete separation between the two notions was not established. This paper introduces a new formulation of pushdown-depth based on restricting how fast a pushdown compressor's stack can grow. This allows us to do a full comparison by demonstrating the existence of sequences with high finite-state-depth and low pushdown-depth, and vice-versa. A new notion based on the Lempel-Ziv 78 algorithm is also presented. Its difference from finite-state-depth is shown by a Lempel-Ziv deep sequence that is not finite-state deep, and vice versa. Lempel-Ziv-depth's difference from pushdown-depth is shown by building sequences that have a pushdown-depth of roughly 1/2 but low Lempel-Ziv depth, and by a sequence with high Lempel-Ziv depth but low pushdown-depth. Properties of all three notions are also studied. [ABSTRACT FROM AUTHOR]

We give a one-step construction of de Bruijn sequences of general alphabet size and with order $$n+k$$ , given a de Bruijn sequence of order n and any integer $$k>1$$ . This is achieved by using an appropriate class of graph homomorphisms between de Bruijn digraphs whose orders differ by an integer k. The method starts with a lower order de Bruijn cycle, finds its inverse cycles in the higher order digraph, which are then cross-joined into one full cycle. Therefore, this generalizes the Lempel's binary construction and the Alhakim-Akinwande construction for non-binary alphabets and a wide class of homomorphisms. [ABSTRACT FROM AUTHOR]

In an attempt to investigate the nonlinear complex evolution of financial dynamics, a new financial price model — the multitype range-intensity contact (MRIC) financial model, is developed based on the multitype range-intensity interacting contact system, in which the interaction and transmission of different types of investment attitudes in a stock market are simulated by viruses spreading. Two new random visibility graph (VG) based analyses and Lempel-Ziv complexity (LZC) are applied to study the complex behaviors of return time series and the corresponding random sorted series. The VG method is the complex network theory, and the LZC is a non-parametric measure of complexity reflecting the rate of new pattern generation of a series. In this work, the real stock market indices are considered to be comparatively studied with the simulation data of the proposed model. Further, the numerical empirical study shows the similar complexity behaviors between the model and the real markets, the research confirms that the financial model is reasonable to some extent. [ABSTRACT FROM AUTHOR]

Precipitation is an important part of the hydrologic cycle, and its complexity is closely related to surface runoff and changing groundwater dynamics, which in turn influences the accuracy of precipitation forecasts. In this study, we used the Lempel-Ziv algorithm (LZA) and a multi-scaling approach to assess precipitation complexity for 1958-2011 by analyzing time series data from 28 gauging stations located throughout Jilin province, China. The spatial distribution of normalized precipitation complexity was measured by LZA, a symbolic dynamics algorithm, and by a multi-scaling approach, which is described by fractals. In addition, the advantages and limitations of these two methods were investigated. The results indicate that both methods are applicable and consistent for calculating precipitation complexity, and that the degree of relief is a primary factor controlling precipitation complexity in the mountainous area; in the plain terrain, however, the prominent influencing factor is climate. [ABSTRACT FROM AUTHOR]

The properties of one-dimensional photonic quasicrystals ultimately rely on their nontrivial long-range order, a hallmark that can be quantified in many ways depending on the specific aspects to be studied. Here, we assess the quasicrystal structural features in terms of the Lempel-Ziv complexity. This is an easily calculable quantity that has proven to be useful for describing patterns in a variety of systems. One feature of great practical relevance is that it provides a reliable measure of how hard it is to create the structure. Using the generalized Fibonacci quasicrystals as our thread, we give analytical fitting formulas for the dependence of the optical response with the complexity. [ABSTRACT FROM AUTHOR]

We provide an automata-theoretic approach to analyzing an abstract channel modeled by a transducer and to characterizing its lossy rates. In particular, we look at related decision problems and show the boundaries between the decidable and undecidable cases. We conduct experiments on several channels and use Lempel-Ziv algorithms to estimate lossy rates of these channels. [ABSTRACT FROM AUTHOR]

Broadcasting a message from one to many processors in a network corresponds to concurrent reading on a random access shared memory parallel machine. Computing the trees of a forest, the level of each node in its tree and the path between two nodes are problems that can easily be solved with concurrent reading in a time logarithmic in the maximum height of a tree. Solving such problems with exclusive reading requires a time logarithmic in the number of nodes, implying message passing between disjoint pairs of processors on a distributed system. Allowing concurrent reading in parallel algorithm design for distributed computing might be advantageous in practice if these problems are faced on shallow trees with some specific constraints. We show an application to LZC (Lempel-Ziv-Compress)-compressed file decoding, whose parallelization employs these computations on such trees for realistic data. On the other hand, zipped files do not have this advantage, since they are compressed by the Lempel-Ziv sliding window technique. [ABSTRACT FROM AUTHOR]

An improved lossless group compression algorithm is proposed for decreasing the size of SEG-Y files to relieve the enormous burden associated with the transmission and storage of large amounts of seismic exploration data. Because each data point is represented by 4 bytes in SEG-Y files, the file is broken down into 4 subgroups, and the Gini coefficient is employed to analyze the distribution of the overall data and each of the 4 data subgroups within the range [0,255]. The results show that each subgroup comprises characteristic frequency distributions suited to distinct compression algorithms. Therefore, the data of each subgroup was compressed using its best suited algorithm. After comparing the compression ratios obtained for each data subgroup using different algorithms, the Lempel-Ziv-Markov chain algorithm (LZMA) was selected for the compression of the first two subgroups and the Deflate algorithm for the latter two subgroups. The compression ratios and decompression times obtained with the improved algorithm were compared with those obtained with commonly employed compression algorithms for SEG-Y files with different sizes. The experimental results show that the improved algorithm provides a compression ratio of 75–80%, which is more effective than compression algorithms presently applied to SEG-Y files. In addition, the proposed algorithm is applied to the miniSEED format used in natural earthquake monitoring, and the results compared with those obtained using the Steim2 compression algorithm, the results again show that the proposed algorithm provides better data compression. [ABSTRACT FROM AUTHOR]

The analysis of electroencephalograms (EEGs) of patients with Alzheimer's disease (AD) could contribute to the diagnosis of this dementia. In this study, a new non-linear signal processing metric, distance-based Lempel-Ziv complexity (dLZC), is introduced to characterise changes between pairs of electrodes in EEGs in AD. When complexity in each signal arises from different sub-sequences, dLZC would be greater than when similar sub-sequences are present in each signal. EEGs from 11 AD patients and 11 age-matched control subjects were analysed. The dLZC values for AD patients were lower than for control subjects for most electrode pairs, with statistically significant differences (p < 0.01, Student's t-test) in 17 electrode pairs in the distant left, local posterior left, and interhemispheric regions. Maximum diagnostic accuracies with leave-one-out cross-validation were 77.27% for subject-based classification and 78.25% for epoch-based classification. These findings suggest not only that EEGs from AD patients are less complex than those from controls, but also that the richness of the information contained in pairs of EEGs from patients is also lower than in age-matched controls. The analysis of EEGs in AD with dLZC may increase the insight into brain dysfunction, providing complementary information to that obtained with other complexity and synchrony methods. [ABSTRACT FROM AUTHOR]

We make an approach on investigating the fluctuation behaviors of financial volatility duration dynamics. A new concept of volatility two-component range intensity (VTRI) is developed, which constitutes the maximal variation range of volatility intensity and shortest passage time of duration, and can quantify the investment risk in financial markets. In an attempt to study and describe the nonlinear complex properties of VTRI, a random agent-based financial price model is developed by the finite-range interacting biased voter system. The autocorrelation behaviors and the powerlaw scaling behaviors of return time series and VTRI series are investigated. Then, the complexity of VTRI series of the real markets and the proposed model is analyzed by Fuzzy entropy (FuzzyEn) and Lempel-Ziv complexity. In this process, we apply the cross-Fuzzy entropy (C-FuzzyEn) to study the asynchrony of pairs of VTRI series. The empirical results reveal that the proposed model has the similar complex behaviors with the actual markets and indicate that the proposed stock VTRI series analysis and the financial model are meaningful and feasible to some extent. [ABSTRACT FROM AUTHOR]

The quantitative diagnosis of rolling bearing fault severity is particularly crucial to realize a proper maintenance decision. Aiming at the fault feature of rolling bearing, a novel double-dictionary matching pursuit (DDMP) for fault extent evaluation of rolling bearing based on the Lempel-Ziv complexity (LZC) index is proposed in this paper. In order to match the features of rolling bearing fault, the impulse time-frequency dictionary and modulation dictionary are constructed to form the double-dictionary by using the method of parameterized function model. Then a novel matching pursuit method is proposed based on the new double-dictionary. For rolling bearing vibration signals with different fault sizes, the signals are decomposed and reconstructed by the DDMP. After the noise reduced and signals reconstructed, the LZC index is introduced to realize the fault extent evaluation. The applications of this method to the fault experimental signals of bearing outer race and inner race with different degree of injury have shown that the proposed method can effectively realize the fault extent evaluation. [ABSTRACT FROM AUTHOR]

Indexing highly repetitive collections has become a relevant problem with the emergence of large repositories of versioned documents, among other applications. These collections may reach huge sizes, but are formed mostly of documents that are near-copies of others. Traditional techniques for indexing these collections fail to properly exploit their regularities in order to reduce space. We introduce new techniques for compressing inverted indexes that exploit this near-copy regularity. They are based on run-length, Lempel–Ziv, or grammar compression of the differential inverted lists, instead of the usual practice of gap-encoding them. We show that, in this highly repetitive setting, our compression methods significantly reduce the space obtained with classical techniques, at the price of moderate slowdowns. Moreover, our best methods are universal, that is, they do not need to know the versioning structure of the collection, nor that a clear versioning structure even exists. We also introduce compressed self-indexes in the comparison. These are designed for general strings (not only natural language texts) and represent the text collection plus the index structure (not an inverted index) in integrated form. We show that these techniques can compress much further, using a small fraction of the space required by our new inverted indexes. Yet, they are orders of magnitude slower. [ABSTRACT FROM AUTHOR]

Background and objective The Lempel–Ziv (LZ) complexity and its variants have been extensively used to analyze the irregularity of physiological time series. To date, these measures cannot explicitly discern between the irregularity and the chaotic characteristics of physiological time series. Our study compared the performance of an encoding LZ (ELZ) complexity algorithm, a novel variant of the LZ complexity algorithm, with those of the classic LZ (CLZ) and multistate LZ (MLZ) complexity algorithms. Methods and results Simulation experiments on Gaussian noise, logistic chaotic, and periodic time series showed that only the ELZ algorithm monotonically declined with the reduction in irregularity in time series, whereas the CLZ and MLZ approaches yielded overlapped values for chaotic time series and time series mixed with Gaussian noise, demonstrating the accuracy of the proposed ELZ algorithm in capturing the irregularity, rather than the complexity, of physiological time series. In addition, the effect of sequence length on the ELZ algorithm was more stable compared with those on CLZ and MLZ, especially when the sequence length was longer than 300. A sensitivity analysis for all three LZ algorithms revealed that both the MLZ and the ELZ algorithms could respond to the change in time sequences, whereas the CLZ approach could not. Cardiac interbeat (RR) interval time series from the MIT-BIH database were also evaluated, and the results showed that the ELZ algorithm could accurately measure the inherent irregularity of the RR interval time series, as indicated by lower LZ values yielded from a congestive heart failure group versus those yielded from a normal sinus rhythm group ( p  < 0.01). [ABSTRACT FROM AUTHOR]

Computing the Lempel-Ziv factorization (LZ77) of a string is a key step in many applications. However, at the same time, it constitutes a bottleneck of the entire computation. The investigation of time and space efficient computation of the LZ77 has become an important topic. In this paper, we present a lightweight linear-time algorithm called LZone for computing the LZ77, which is designed by improvements on the existing linear-time space efficient LZ77 algorithm BGone for speed acceleration. For an input string T[1.. n] over a constant alphabet size of O(1), LZone requires only n words of workspace in addition to the input string and the output factorization, ⌈log n⌉ bits per word. This is the same space requirement for the algorithm BGone. LZone has two versions, LZoneT and LZoneSA, corresponding to BGoneT and BGoneSA, respectively. Our experimental results show that for computing the LZ77 from an input string T, LZoneT and LZoneSA run at around 26 % and 57 %, respectively, faster than their counterparts in BGone. Moreover, for computing the LZ77 from the suffix array of T, the speed of LZoneSA is on average twice that of BGoneSA. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Consciousness is thought to scale with brain complexity, and it may be diminished in anesthesia. Lempel-Ziv complexity (LZC) of field potentials has been shown to be a promising measure of the level of consciousness in anesthetized human subjects, neurological patients, and across the sleep-wake states in rats. Whether this relationship holds for intrinsic networks obtained by functional brain imaging has not been tested. To fill this gap of knowledge, we estimated LZC from large-scale dynamic analysis of functional magnetic resonance images (fMRI) in conscious sedated and unconscious anesthetized rats. Blood oxygen dependent (BOLD) signals were obtained from 30-min whole-brain resting-state scans while the anesthetic propofol was infused intravenously at constant infusion rates of 20 mg/kg/h (conscious sedated) and 40 mg/kg/h (unconscious). Dynamic brain networks were defined at voxel level by sliding window analysis of regional homogeneity (ReHo) of the BOLD signal. From scans performed at low to high propofol dose, the LZC was significantly reduced by 110%. The results suggest that the difference in LZC between conscious sedated and anesthetized unconscious subjects is conserved in rats and this effect is detectable in large-scale brain network obtained from fMRI. [ABSTRACT FROM AUTHOR]

The information sources using logistic maps have been studied in this article. We use a particular symmetric binary function to generate the binary sequences due to the generating partition of the logistic maps, which can reflect the dynamics of chaotic real-valued sequences. Using this binary function, we will establish a binary description of the logistic maps, and prove that this description is equivalent with the logistic maps. The probability of all the possible binary sequences generated by this symmetric binary function has been calculated according to this description. Furthermore, the cryptographic complexity of these binary sequences is evaluated theoretically and experimentally, including the correlation functions, the linear complexity, the nonlinear complexity, the Lempel-Ziv complexity and the approximate entropy. Such results show that the logistic binary sequences have good properties of cryptography. © 2015 Wiley Periodicals, Inc. Complexity 21: 121-129, 2016 [ABSTRACT FROM AUTHOR]

Sleep is characterized by a loss of behavioral responsiveness. However, recent research has shown that the sleeping brain is not completely disconnected from its environment. How neural activity constrains the ability to process sensory information while asleep is yet unclear. Here, we instructed human volunteers to classify words with lateralized hand responses while falling asleep. Using an electroencephalographic (EEG) marker of motor preparation, we show how responsiveness is modulated across sleep. These modulations are tracked using classic event-related potential analyses complemented by Lempel-Ziv complexity (LZc), a measure shown to track arousal in sleep and anesthesia. Neural activity related to the semantic content of stimuli was conserved in light non-rapid eye movement (NREM) sleep. However, these processes were suppressed in deep NREM sleep and, importantly, also in REM sleep, despite the recovery of wake-like neural activity in the latter. In NREM sleep, sensory activations were counterbalanced by evoked down states, which, when present, blocked further processing of external information. In addition, responsiveness markers correlated positively with baseline complexity, which could be related to modulation in sleep depth. In REM sleep, however, this relationship was reversed. We therefore propose that, in REM sleep, endogenously generated processes compete with the processing of external input. Sleep can thus be seen as a self-regulated process in which external information can be processed in lighter stages but suppressed in deeper stages. Last, our results suggest drastically different gating mechanisms in NREM and REM sleep. [ABSTRACT FROM AUTHOR]

Ischemic thalamus stroke has become a serious cardiovascular and cerebral disease in recent years. To date the existing researches mostly concentrated on the power spectral density (PSD) in several frequency bands. In this paper, we investigated the nonlinear features of EEG and brain functional connectivity in patients with acute thalamic ischemic stroke and healthy subjects. Electroencephalography (EEG) in resting condition with eyes closed was recorded for 12 stroke patients and 11 healthy subjects as control group. Lempel-Ziv complexity (LZC), Sample Entropy (SampEn), and brain network using partial directed coherence (PDC) were calculated for feature extraction. Results showed that patients had increased mean LZC and SampEn than the controls, which implied the stroke group has higher EEG complexity. For the brain network, the stroke group displayed a trend of weaker cortical connectivity, which suggests a functional impairment of information transmission in cortical connections in stroke patients. These findings suggest that nonlinear analysis and brain network could provide essential information for better understanding the brain dysfunction in the stroke and assisting monitoring or prognostication of stroke evolution. [ABSTRACT FROM AUTHOR]

This paper presents a new methodology for degradation assessment in bearings with outer race fault. The novelty of the paper is the application of the Lempel-Ziv complexity (LZC) to the node of maximal energy from the wavelet package transform of the raw vibration signal. The objective of the paper is to develop a methodology for outer race fault bearing severity assessment and to show how the extracted feature LZC follows monotonically the bearing degradation. The proposed methodology is compared with LZC and kurtosis extracted from the raw vibration signal and with kurtosis extracted from the node with maximal energy. [ABSTRACT FROM AUTHOR]

Complexity measures have been enormously used in schizophrenia patients to estimate brain dynamics. However, the conflicting results in terms of both increased and reduced complexity values have been reported in these studies depending on the patients' clinical status or symptom severity or medication and age status. The objective of this study is to investigate the nonlinear brain dynamics of chronic and medicated schizophrenia patients using distinct complexity estimators. EEG data were collected from 22 relaxed eyes-closed patients and age-matched healthy controls. A single-trial EEG series of 2min was partitioned into identical epochs of 20s intervals. The EEG complexity of participants were investigated and compared using approximate entropy (ApEn), Shannon entropy (ShEn), Kolmogorov complexity (KC) and Lempel-Ziv complexity (LZC). Lower complexity values were obtained in schizophrenia patients. The most significant complexity differences between patients and controls were obtained in especially left frontal (F3) and parietal (P3) regions of the brain when all complexity measures were applied individually. Significantly, we found that KC was more sensitive for detecting EEG complexity of patients than other estimators in all investigated brain regions. Moreover, significant inter-hemispheric complexity differences were found in the frontal and parietal areas of schizophrenics' brain. Our findings demonstrate that the utilizing of sensitive complexity estimators to analyze brain dynamics of patients might be a useful discriminative tool for diagnostic purposes. Therefore, we expect that nonlinear analysis will give us deeper understanding of schizophrenics' brain. [ABSTRACT FROM AUTHOR]

In this study we investigate how bankruptcy affects the market behaviour of prices of stocks on Warsaw's Stock Exchange. As the behaviour of prices can be seen in a myriad of ways, we investigate a particular aspect of this behaviour, namely the predictability of these price formation processes. We approximate their predictability as the structural complexity of logarithmic returns. This method of analysing predictability of price formation processes using information theory follows closely the mathematical definition of predictability, and is equal to the degree to which redundancy is present in the time series describing stock returns. We use Shannon's entropy rate (approximating Kolmogorov-Sinai entropy) to measure this redundancy, and estimate it using the Lempel-Ziv algorithm, computing it with a running window approach over the entire price history of 50 companies listed on the Warsaw market which have gone bankrupt in the last few years. This enables us not only to compare the differences between predictability of price formation processes before and aft er their filing for bankruptcy, but also to compare the changes in predictability over time, as well as divided into different categories of companies and bankruptcies. There exists a large body of research analysing the efficiency of the whole market and the predictability of price changes en large, but only a few detailed studies analysing the influence of external stimuli on the efficiency of price formation processes. This study fills this gap in the knowledge of financial markets, and their response to extreme external events. [ABSTRACT FROM AUTHOR]

In this paper, we generalize the permutation entropy (PE) measure to binary sequences, which is based on Shannon's entropy, and theoretically analyze this measure for random binary sequences. We deduce the theoretical value of PE for random binary sequences, which can be used to measure the randomness of binary sequences. We also reveal the relationship between this PE measure with other randomness measures, such as Shannon's entropy and Lempel-Ziv complexity. The results show that PE is consistent with these two measures. Furthermore, we use PE as one of the randomness measures to evaluate the randomness of chaotic binary sequences. [ABSTRACT FROM AUTHOR]

Vibration analysis is the most used technique for defect monitoring failures of industrial gearboxes. Detection and diagnosis of gear defects are thus crucial to avoid catastrophic failures. It is therefore important to detect early fault symptoms. This paper introduces signal processing methods based on approximate entropy (ApEn), sample entropy (SampEn), and Lempel-Ziv Complexity (LZC) for detection of gears defects. These methods are based on statistical measurements exploring the regularity of vibratory signals. Applied to gear signals, the parameter selection of ApEn, SampEn, and LZC calculation is first numerically investigated, and appropriate parameters are suggested. Finally, an experimental study is presented to investigate the effectiveness of these indicators and a comparative study with traditional time domain indicators is presented. The results demonstrate that ApEn, SampEn, and LZC provide alternative features for signal processing. A new methodology is presented combining both Kurtosis and LZC for early detection of faults. The results show that this proposed method may be used as an effective tool for early detection of gear faults. [ABSTRACT FROM AUTHOR]

The relaxed Hilberg conjecture states that the mutual information between two adjacent blocks of text in natural language grows as a power of the block length. The present paper reviews recent results concerning this conjecture. First, the relaxed Hilberg conjecture occurs when the texts repeatedly describe a random reality and Herdan’s law for facts repeatedly described in the texts is obeyed. Second, the relaxed Hilberg conjecture implies Herdan’s law for set phrases, which can be associated with the better known Herdan law for words. Third, the relaxed Hilberg conjecture is positively tested, using the Lempel-Ziv universal code, on a selection of texts in English, German, and French. Hence the relaxed Hilberg conjecture seems to be a likely and important hypothesis concerning natural language. [ABSTRACT FROM PUBLISHER]

The Synchrosqueezing is a special case of the reassignment method and concentrates the timefrequency representation (TFR) in a scale dimension. Compared to other TFR enhancement methods, the synchrosqueezing offers better adaptability, less deformation for IF profile and an exact reconstruction formula for constituent components. This paper deals with the investigation of descriptors based on the combination of the synchrosqueezing transform (SST) and Lempel-Ziv complexity methods. This last one transforms the analyzed signal into a data sequence. In the first part, the vibration signal components are extracted by using the synchrosqueezing transform and the reconstruction method. Afterward, the Lempel- Ziv complexity values are calculated. Since the complexity values are not dependent on the magnitude of the measured signal, the proposed method is less sensitive to the data sets measured under different data acquisition conditions. This approach is applied for monitoring and diagnosing the defects during a fatigue test on a first gear reducer and also when varying the load on a second gear reducer by using the recorded vibration signals. It can also provide a new way for feature extraction and recognition of gear system faults. [ABSTRACT FROM AUTHOR]

We have used the Kolmogorov complexity ( KC) and three suggested complexity measures to describe the complexity of spatial distribution of precipitation in Bosnia and Herzegovina, for the period 1960-1984. In particular, we have examined the monthly precipitation amount time series from 23 stations and then calculated the KC using the Lempel-Ziv Algorithm ( LZA), Kolmogorov complexity spectrum ( KCS), Kolmogorov complexity spectrum highest value ( KCM) and overall Kolmogorov complexity ( OKC) values for each time series. Our results indicate that the difference in complexity of spatial distribution of precipitation may be attributed to influence of Adriatic Sea, relief and Pannonian Basin. [ABSTRACT FROM AUTHOR]