Search

Structure learning is the core of graph model Bayesian Network learning, and the current mainstream single search algorithm has problems such as poor learning effect, fuzzy initial network, and easy falling into local optimum. In this paper, we propose a heuristic learning algorithm HC-PSO combining the HC (Hill Climbing) algorithm and PSO (Particle Swarm Optimization) algorithm, which firstly uses HC algorithm to search for locally optimal network structures, takes these networks as the initial networks, then introduces mutation operator and crossover operator, and uses PSO algorithm for global search. Meanwhile, we use the DE (Differential Evolution) strategy to select the mutation operator and crossover operator. Finally, experiments are conducted in four different datasets to calculate BIC (Bayesian Information Criterion) and HD (Hamming Distance), and comparative analysis is made with other algorithms, the structure shows that the HC-PSO algorithm is superior in feasibility and accuracy. [ABSTRACT FROM AUTHOR]

Quantum approximate optimization algorithm (QAOA) is a promising hybrid quantum-classical algorithm to solve combinatorial optimization problems in the era of noisy intermediate-scale quantum computers. Recently it has been revealed that warm-start approaches can improve the performance of QAOA, where approximate solutions are obtained by classical algorithms in advance and incorporated into the initial state and/or unitary ansatz. In this work, we study in detail how the accuracy of approximate solutions affects the performance of the warm-start QAOA (WS-QAOA). We numerically find that in typical MAX-CUT problems, WS-QAOA achieves higher fidelity (probability that exact solutions are observed) and approximation ratio than QAOA as the Hamming distance of approximate solutions to the exact ones becomes smaller. We reveal that this could be quantitatively attributed to the initial state of the ansatz. We also solve MAX-CUT problems by WS-QAOA with approximate solutions obtained via QAOA, having higher fidelity and approximation ratio than QAOA especially when the circuit is relatively shallow. We believe that our study may deepen understanding of the performance of WS-QAOA and also provide a guide as to the necessary quality of approximate solutions. [ABSTRACT FROM AUTHOR]

Sequence motif discovery algorithms enhance the identification of novel deoxyribonucleic acid sequences with pivotal biological significance, especially transcription factor (TF)-binding motifs. The advent of assay for transposase-accessible chromatin using sequencing (ATAC-seq) has broadened the toolkit for motif characterization. Nonetheless, prevailing computational approaches have focused on delineating TF-binding footprints, with motif discovery receiving less attention. Herein, we present Cis rEgulatory Motif Influence using de Bruijn Graph (CEMIG), an algorithm leveraging de Bruijn and Hamming distance graph paradigms to predict and map motif sites. Assessment on 129 ATAC-seq datasets from the Cistrome Data Browser demonstrates CEMIG's exceptional performance, surpassing three established methodologies on four evaluative metrics. CEMIG accurately identifies both cell-type-specific and common TF motifs within GM12878 and K562 cell lines, demonstrating its comparative genomic capabilities in the identification of evolutionary conservation and cell-type specificity. In-depth transcriptional and functional genomic studies have validated the functional relevance of CEMIG-identified motifs across various cell types. CEMIG is available at https://github.com/OSU-BMBL/CEMIG , developed in C++ to ensure cross-platform compatibility with Linux, macOS and Windows operating systems. [ABSTRACT FROM AUTHOR]

While the theoretical analysis of evolutionary algorithms (EAs) has made significant progress for pseudo-Boolean optimization problems in the last 25 years, only sporadic theoretical results exist on how EAs solve permutation-based problems. To overcome the lack of permutation-based benchmark problems, we propose a general way to transfer the classic pseudo-Boolean benchmarks into benchmarks defined on sets of permutations. We then conduct a rigorous runtime analysis of the permutation-based (1 + 1) EA proposed by Scharnow et al. (J Math Model Algorithm 3:349–366, 2004) on the analogues of the LeadingOnes and Jump benchmarks. The latter shows that, different from bit-strings, it is not only the Hamming distance that determines how difficult it is to mutate a permutation σ into another one τ , but also the precise cycle structure of σ τ - 1 . For this reason, we also regard the more symmetric scramble mutation operator. We observe that it not only leads to simpler proofs, but also reduces the runtime on jump functions with odd jump size by a factor of Θ (n) . Finally, we show that a heavy-tailed version of the scramble operator, as in the bit-string case, leads to a speed-up of order m Θ (m) on jump functions with jump size m. A short empirical analysis confirms these findings, but also reveals that small implementation details like the rate of void mutations can make an important difference. [ABSTRACT FROM AUTHOR]

This paper presents a method for unsupervised classification of entities by a group of agents with unknown domains and levels of expertise. In contrast to the existing methods based on majority voting ("wisdom of the crowd") and their extensions by expectation-maximization procedures, the suggested method first determines the levels of the agents' expertise and then weights their opinions by their expertise level. In particular, we assume that agents will have relatively closer classifications in their field of expertise. Therefore, the expert agents are recognized by using a weighted Hamming distance between their classifications, and then the final classification of the group is determined from the agents' classifications by expectation-maximization techniques, with preference to the recognized experts. The algorithm was verified and tested on simulated and real-world datasets and benchmarked against known existing algorithms. We show that such a method reduces incorrect classifications and effectively solves the problem of unsupervised collaborative classification under uncertainty, while outperforming other known methods. [ABSTRACT FROM AUTHOR]

Modern applications of graph algorithms often involve the use of the output sets (usually, a subset of edges or vertices of the input graph) as inputs to other algorithms. Since the input graphs of interest are large and dynamic, it is desirable for an algorithm's output to not change drastically when a few random edges are removed from the input graph, so as to prevent issues in postprocessing. Alternately, having such a guarantee also means that one can revise the solution obtained by running the algorithm on the original graph in just a few places in order to obtain a solution for the new graph. We formalize this feature by introducing the notion of average sensitivity of graph algorithms, which is the average earth mover's distance between the output distributions of an algorithm on a graph and its subgraph obtained by removing an edge, where the average is over the edges removed and the distance between two outputs is the Hamming distance. In this work, we initiate a systematic study of average sensitivity of graph algorithms. After deriving basic properties of average sensitivity such as composition, we provide efficient approximation algorithms with low average sensitivities for concrete graph problems, including the minimum spanning forest problem, the global minimum cut problem, the minimum s-t cut problem, and the maximum matching problem. In addition, we prove that the average sensitivity of our global minimum cut algorithm is almost optimal, by showing a nearly matching lower bound. We also show that every algorithm for the 2-coloring problem has average sensitivity linear in the number of vertices. One of the main ideas involved in designing our algorithms with low average sensitivity is the following fact: if the presence of a vertex or an edge in the solution output by an algorithm can be decided locally, then the algorithm has a low average sensitivity, allowing us to reuse the analyses of known subline artime algorithms and local computation algorithms. Using this fact in conjunction with our average sensitivity lower bound for 2-coloring, we show that every local computation algorithm for 2-coloring has query complexity linear in the number of vertices, thereby answering an open question. [ABSTRACT FROM AUTHOR]

We thoroughly study a novel but basic combinatorial matrix completion problem: Given a binary incomplete matrix, fill in the missing entries so that every pair of rows in the resulting matrix has a Hamming distance within a specified range. We obtain an almost complete picture of the complexity landscape regarding the distance constraints and the maximum number of missing entries in any row. We develop polynomial-time algorithms for maximum diameter three based on Deza's theorem (1973) [11] from extremal set theory. We also prove NP-hardness for diameter at least four. For the number of missing entries per row, we show polynomial-time solvability when there is only one and NP-hardness when there can be at least two. In many of our algorithms, we heavily rely on Deza's theorem to identify sunflower structures. This paves the way towards polynomial-time algorithms which are based on finding graph factors and solving 2-SAT instances. [ABSTRACT FROM AUTHOR]

Motivation Comparing single-stranded nucleic acids (ssNAs) secondary structures is fundamental when investigating their function and evolution and predicting the effect of mutations on their structures. Many comparison metrics exist, although they are either too elaborate or not sensitive enough to distinguish close ssNAs structures. Results In this context, we developed AptaMat, a simple and sensitive algorithm for ssNAs secondary structures comparison based on matrices representing the ssNAs secondary structures and a metric built upon the Manhattan distance in the plane. We applied AptaMat to several examples and compared the results to those obtained by the most frequently used metrics, namely the Hamming distance and the RNAdistance, and by a recently developed image-based approach. We showed that AptaMat is able to discriminate between similar sequences, outperforming all the other here considered metrics. In addition, we showed that AptaMat was able to correctly classify 14 RFAM families within a clustering procedure. Availability and implementation The python code for AptaMat is available at https://github.com/GEC-git/AptaMat.git. Supplementary information Supplementary data are available at Bioinformatics online. [ABSTRACT FROM AUTHOR]

The affine scale-invariant feature transform (ASIFT) algorithm is a feature extraction algorithm with affinity and scale invariance, which is suitable for image feature matching using unmanned aerial vehicles (UAVs). However, there are many problems in the matching process, such as the low efficiency and mismatching. In order to improve the matching efficiency, this algorithm firstly simulates image distortion based on the position and orientation system (POS) information from real-time UAV measurements to reduce the number of simulated images. Then, the scale-invariant feature transform (SIFT) algorithm is used for feature point detection, and the extracted feature points are combined with the binary robust invariant scalable keypoints (BRISK) descriptor to generate the binary feature descriptor, which is matched using the Hamming distance. Finally, in order to improve the matching accuracy of the UAV images, based on the random sample consensus (RANSAC) a false matching eliminated algorithm is proposed. Through four groups of experiments, the proposed algorithm is compared with the SIFT and ASIFT. The results show that the algorithm can optimize the matching effect and improve the matching speed. [ABSTRACT FROM AUTHOR]

Trace reconstruction considers the task of recovering an unknown string $\mathbf {x}\in \{0,1\}^{n}$ given a number of independent “traces”, i.e., subsequences of $\mathbf {x}$ obtained by randomly and independently deleting every symbol of $\mathbf {x}$ with some probability $p$. The information-theoretic limit of the number of traces needed to recover a string of length $n$ is still unknown. This limit is essentially the same as the number of traces needed to determine, given strings $\mathbf {x}$ and $\mathbf {y}$ and traces of one of them, which string is the source. The most-studied class of algorithms for the worst-case version of the problem are “mean-based” algorithms. These are a restricted class of distinguishers that only use the mean value of each coordinate on the given samples. In this work we study limitations of mean-based algorithms on strings at small Hamming or edit distance. We show that, on the one hand, distinguishing strings that are nearby in Hamming distance is “easy” for such distinguishers. On the other hand, we show that distinguishing strings that are nearby in edit distance is “hard” for mean-based algorithms. Along the way, we also describe a connection to the famous Prouhet-Tarry-Escott (PTE) problem, which shows a barrier to finding explicit hard-to-distinguish strings: namely such strings would imply explicit short solutions to the PTE problem, a well-known difficult problem in number theory. Furthermore, we show that the converse is also true, thus, finding explicit solutions to the PTE problem is equivalent to the problem of finding explicit strings that are hard-to-distinguish by mean-based algorithms. Our techniques rely on complex analysis arguments that involve careful trigonometric estimates, and algebraic techniques that include applications of Descartes’ rule of signs for polynomials over the reals. [ABSTRACT FROM AUTHOR]

To solve the low accuracy of image feature matching in horticultural robot visual navigation, an innovative and effective image feature matching algorithm was proposed combining the improved Oriented FAST and Rotated BRIEF (ORB) and Lucas–Kanade (LK) optical flow algorithm. First, image feature points were extracted according to the adaptive threshold calculated using the Michelson contrast. Then, the extracted feature points were uniformed by the quadtree structure, which can reduce the calculated amount of feature matching, and the uniform ORB feature points were roughly matched to estimate the position of the feature points in the matched image using the improved LK optical flow. Finally, the Hamming distance between rough matching points was calculated for precise matching. Feature extraction and matching experiments were performed in four typical scenes: normal light, low light, high texture, and low texture. Compared with the traditional algorithm, the uniformity and accuracy of the feature points extracted by the proposed algorithm were enhanced by 0.22 and 50.47%, respectively. Meanwhile, the results revealed that the matching accuracy of the proposed algorithm increased by 14.59%, whereas the matching time and total time decreased by 39.18% and 44.79%, respectively. The proposed algorithm shows great potential for application in the visual simultaneous localization and mapping (V-SLAM) of horticultural robots to achieve higher accuracy of real-time positioning and map construction. [ABSTRACT FROM AUTHOR]

Smoke detection is an advance caution to the unforeseen great damage events. Therefore, it is required to identify the smoke in the course of initial stages for preventing fire events. A new technique is proposed to lessen the rate of incorrect alarm by identify the smoke and examine its distinctive texture attributes. Initially, the smoke-colored regions are segmented based on color at the YUV color locality. Then the tentative frame differencing is used to segment the candidate smoke region from the smoke-colored region. In the next phase, the candidate distinctive texture attributes in the smoke region are extracted using Co-occurrence of Hamming Distance based Local Binary pattern (CoHDLBP) and Co-occurrence of Local Binary pattern (CoLBP); these features include homogeneity, energy, correlation and contrast. Finally, the ELM classifier is proficient for the take-out features from the candidate smoke region, and then the decision has been taken with the assistance of a smoke alarm. Investigational outcomes proved that the suggested smoke recognition process executes better compared with all the usual smoke recognition methods by achieving better detection accuracy and processing time. [ABSTRACT FROM AUTHOR]

The rapid and accurate identification of photovoltaic (PV) model parameters is of great significance in solving practical engineering problems such as PV power prediction, maximum power point tracking and battery failure model recognition. Aiming at the shortcomings of low accuracy and poor reliability and being easy to fall into local optimization when standard intelligent optimization algorithms identify PV model parameters, a novel drunken adaptive walking chaotic wolf swarm algorithm is proposed, which is named DCWPA for short. The DCWPA uses the chaotic map sequence to initialize the population, thus to improve the diversity of the initial population. It adopts the walking direction mechanism based on the drunk walking model and the adaptive walking step size to increase the randomness of walking, enhance the individual's ability to explore and develop and improve the ability of algorithm optimization. It also designs the judgment conditions for half siege in order to accelerate the convergence of the algorithm and improve the speed of the algorithm. In the iterative process, according to the change of the optimal solution, the Hamming Distance is used to judge the similarity of individuals in the population, and the individuals in the population are constantly updated to avoid the algorithm from stopping evolution prematurely due to falling into local optimization. This paper firstly analyzes the time complexity of the algorithm, and then selects eight standard test functions (Benchmark) with different characteristics to verify the performance of the DCWPA algorithm for continuous optimization, and finally the improved algorithm is applied for parameter identification of PV models. The experiments show that the DCWPA has higher identification accuracy than other algorithms, and the results are more consistent with the measured data. Thus, the effectiveness and superiority of the improved algorithm in identifying solar cell parameters are verified, and the identification effect of the improved algorithm on solar cell parameters under different illumination is shown. This research provides a new idea and method for parameter identification of a PV module model. [ABSTRACT FROM AUTHOR]

An improved ORB feature point purification method has been proposed to address the problem of large feature point matching error and low image registration rate in the oriented FAST and rotated BRIEF (ORB) feature point color image matching algorithm. Pure virtual quaternions were used to represent the color image pixels in this method, and an improved FAST algorithm was used to detect the color feature points at first. The firework algorithm has been used to divide the detected feature points into key areas, auxiliary areas, and small influence areas, depending on the degree of attachment. The feature points of the key area and the subsidiary area are the required feature points. In order to further improve the efficiency of matching the color image feature points, the firework explosion radius formula and the explosion number formula in the firework algorithm have been improved, and an improved firework algorithm is proposed. This improved algorithm purifies the quaternion-represented color image feature points. For feature matching, the hamming distance was used. Experiments show that, when compared to the traditional ORB algorithm, the improved algorithm retains the key feature points of the color image with high accuracy, removes a large number of irrelevant feature points and noise points, and provides significantly higher accuracy and efficiency of color image matching. [ABSTRACT FROM AUTHOR]

Mining clusters from data is an important endeavor in many applications. The k‐means method is a popular, efficient, and distribution‐free approach for clustering numerical‐valued data, but does not apply for categorical‐valued observations. The k‐modes method addresses this lacuna by replacing the Euclidean with the Hamming distance and the means with the modes in the k‐means objective function. We provide a novel, computationally efficient implementation of k‐modes, called Optimal Transfer Quick Transfer (OTQT). We prove that OTQT finds updates to improve the objective function that are undetectable to existing k‐modes algorithms. Although slightly slower per iteration due to algorithmic complexity, OTQT is always more accurate and almost always faster (and only barely slower on some datasets) to the final optimum. Thus, we recommend OTQT as the preferred, default algorithm for k‐modes optimization. [ABSTRACT FROM AUTHOR]

Line-of-sight (LOS) is a critical requirement for mmWave wireless communications. In this work, we explore the use of access point (AP) infrastructure mobility to optimize indoor mmWave WiFi network performance based on the discovery of LOS connectivity to stations (STAs). We consider a ceiling-mounted mobile (CMM) AP as the infrastructure mobility framework. Within this framework, we propose two heuristic algorithms (basic and weighted) derived from Hamming distance computation and a machine learning (ML) solution fully exploiting available network state information to address the LOS discovery problem. Based on the ML solution, we then propose a systematic solution WiMove , which can decide if and where the AP should move to for optimizing network performance. Using both ns-3 based simulation and experimental prototype implementation, we show that the throughput and fairness performance of WiMove is up to 119% and 15% better compared with single static AP and brute force search. • We focus on line of sight discovery for mmWave WiFi with access point mobility. • We propose two heuristic algorithms and a machine learning (ML) solution. • Based on the ML solution, we provide a systematic solution called WiMove. • WiMove outperforms conventional methods (e.g., static AP and brute force). [ABSTRACT FROM AUTHOR]

Due to the advantage of capacity-achieving, polar codes have been extended to the block fading channel whereas most constructions involve complex iterative-calculation. In this paper, we establish a systematic framework to analyze the error performance of polar codes in the case of block mapping and random mapping. For both the mappings, by introducing the new concept, named split polar spectrum, we derive the upper bound on the error probability of polarized channel which explicitly reveals the relationship between the diversity order $L$ and the block-wise weight distribution of the codeword. For the special case $L=2$ in the block mapping, we design the enumeration algorithm to calculate the exact split polar spectrum based on the general MacWilliams identities. For arbitrary diversity order in the random mapping, with the help of uniform interleaving, we derive the approximate split polar spectrum by combining the polar spectrum and the probability of fading pattern for a specific weight. Furthermore, we propose the design criteria to construct polar codes over the block fading channel. The full diversity criterion is the primary target to achieve the diversity gain and the product distance criterion requires to maximize the product of the block-wise Hamming distance whereby obtain the coding gain. Guided by these design criteria, the construction metrics, respectively named polarized diversity weight (PDW) and simplified PDW (SPDW) are proposed to designpolar codes in both mappings. Such simple metrics can construct polar codes with similar or better performance over those based on traditional methods in block fading channel. [ABSTRACT FROM AUTHOR]

In order to satisfy the rapidly increasing demand for data volume, large data center networks (DCNs) have been proposed. In 2019, Zhang et al. proposed a new highly scalable DCN architecture named HSDC (Highly Scalable Data Center Network), which can achieve greater incremental scalability. In this paper, we give the definition of the logical graph of HSDC, named H n , which can be treated as a compound graph of hypercube and complete graph of the same dimension. First, we prove that the connectivity and tightly super connectivity of H n are both n. Then, we give an O(n) shortest unicast algorithm to find a shortest path between any two distinct nodes in H n , and prove the correctness of this algorithm. In fact, we also prove that the length of the shortest path constructed by this algorithm is no more than 2 d + 1 if d < n and at most 2d if d = n , where d is the Hamming distance between the start and end nodes, and the diameter of H n is 2n. [ABSTRACT FROM AUTHOR]

In an inverse combinatorial optimization problem, a feasible solution is given and is not optimal under the current parameters. The aim is to make the feasible solution optimal by modifying the current parameters as little as possible. The modification cost can be measured by different norms, such as weighted l 1 norm, weighted l 2 norm, weighted l ∞ norm, weighted Hamming distance and so on. In this paper, we focus on the constrained inverse minimum flow problems under the weighted Hamming distance. Three different models are considered: the general problem under the weighted bottleneck-type Hamming distance and two cases under the mixed of sum-type and bottleneck type. Strongly polynomial algorithms are presented for the models we studied. [ABSTRACT FROM AUTHOR]

The development of information technology has produced massive amounts of data, which has brought severe challenges to information storage. Traditional electronic storage media cannot keep up with the ever-increasing demand for data storage, but in its place DNA has emerged as a feasible storage medium with high density, large storage capacity and strong durability. In DNA data storage, many different approaches can be used to encode data into codewords. DNA coding is a key step in DNA storage and can directly affect storage performance and data integrity. However, since errors are prone to occur in DNA synthesis and sequencing, and non-specific hybridization is prone to occur in the solution, how to effectively encode DNA has become an urgent problem to be solved. In this article, we propose a DNA storage coding method based on the equilibrium optimization random search (EORS) algorithm, which meets the Hamming distance, GC content and no-runlength constraints and can reduce the error rate in storage. Simulation experiments have shown that the size of the DNA storage code set constructed by the EORS algorithm that meets the combination constraints has increased by an average of 11% compared with previous work. The increase in the code set means that shorter DNA chains can be used to store more data. [ABSTRACT FROM AUTHOR]

Graphs such as de Bruijn graphs and OLC (overlap-layout-consensus) graphs have been widely adopted for the de novo assembly of genomic short reads. This work studies another important problem in the field: how graphs can be used for high-performance compression of the large-scale sequencing data. We present a novel graph definition named Hamming-Shifting graph to address this problem. The definition originates from the technological characteristics of next-generation sequencing machines, aiming to link all pairs of distinct reads that have a small Hamming distance or a small shifting offset or both. We compute multiple lexicographically minimal k-mers to index the reads for an efficient search of the weight-lightest edges, and we prove a very high probability of successfully detecting these edges. The resulted graph creates a full mutual reference of the reads to cascade a code-minimized transfer of every child-read for an optimal compression. We conducted compression experiments on the minimum spanning forest of this extremely sparse graph, and achieved a 10 − 30% more file size reduction compared to the best compression results using existing algorithms. As future work, the separation and connectivity degrees of these giant graphs can be used as economical measurements or protocols for quick quality assessment of wet-lab machines, for sufficiency control of genomic library preparation, and for accurate de novo genome assembly. Author summary: We present a novel graph-based algorithm to compress next-generation short sequencing reads. The novelty of the algorithm is attributed to a new definition of genomic sequence graph named Hamming-Shifting graph. It consists of edges between distinct reads that have a small Hamming distance or a small shifting offset or both. Efficient construction of Hamming-Shifting graphs is challenging. We introduce a heuristic technique to detect the weight-lightest edges through multiple minimizers from each read, then search the minimum spanning trees and forests of the Hamming-Shifting graph for a high-performance compression of the reads. Our method achieves an additional 10 − 30% file size reduction compared to contemporary compression techniques. [ABSTRACT FROM AUTHOR]

This paper revisits the ordered statistics decoding (OSD). It provides a comprehensive analysis of the OSD algorithm by characterizing the statistical properties, evolution and the distribution of the Hamming distance and weighted Hamming distance from codeword estimates to the received sequence in the reprocessing stages of the OSD algorithm. We prove that the Hamming distance and weighted Hamming distance distributions can be characterized as mixture models capturing the decoding error probability and code weight enumerator. Simulation and numerical results show that our proposed statistical approaches can accurately describe the distance distributions. Based on these distributions and with the aim to reduce the decoding complexity, several techniques, including stopping rules and discarding rules, are proposed, and their decoding error performance and complexity are accordingly analyzed. Simulation results for decoding various eBCH codes demonstrate that the proposed techniques can significantly reduce the decoding complexity with a negligible loss in the decoding error performance. [ABSTRACT FROM AUTHOR]

Analogs of balls in n -dimensional Euclidean space are defined in the monoid of strings composed of letters of an alphabet if a metric is defined on the monoid. These analogs are not only balls in the monoid of strings but also regular languages. Since the Levenshtein distance, a reasonable metric between strings, was introduced in 1965, researchers have aimed to determine a formula for computing the volumes of balls of strings under this distance and their growth rate. However, this problem remains open. In this paper, we first derive a formula for the volumes of balls of strings under a metric obtained by extending the Hamming distance as a metric on the whole monoid and subsequently reveal the growth rate of balls of strings under the Levenshtein distance using this formula. Furthermore, we describe a conjecture on the formula for the volumes of spheres of strings under the Levenshtein distance. Next, we construct an efficient randomized algorithm that computes estimates of the volumes of the balls whose estimation errors are less than a given value with a probability greater than a specified value. Finally, we examine the validity of the proposed conjecture, using the (true) volumes obtained by exhaustive searches for small spheres and estimates of the volumes obtained by this algorithm for large ones. [ABSTRACT FROM AUTHOR]

Given a binary word relation τ onto A ⁎ and a finite language X ⊆ A ⁎ , a τ -Gray cycle over X consists in a permutation (w [ i ]) 0 ≤ i ≤ | X | − 1 of X such that each word w [ i ] is an image under τ of the previous word w [ i − 1 ]. We define the complexity measure λ A , τ (n) , equal to the largest cardinality of a language X having words of length at most n , and st. some τ -Gray cycle over X exists. The present paper is concerned with τ = σ k , the so-called k -character substitution, st. (u , v) ∈ σ k holds if, and only if, the Hamming distance of u and v is k. We present loopless (resp., constant amortized time) algorithms for computing specific maximum length σ k -Gray cycles. [ABSTRACT FROM AUTHOR]

In fact, compression and computation are two sides of the same coin, as they exploit the same underlying structure both for storing and operating on data. The study in [[4]] establishes new upper bounds and a conditional lower bound on the indexed regular expression matching problem and [[5]] improves existing analyses on the approximation ratios for common grammar-based compressors. As the production of massive data has outpaced Moore's law in many scientific areas, the very notion of algorithms is transforming. [Extracted from the article]

Image matching is one of the hot issues in recent years. Image matching determines the effect of image mosaic to a large extent. Therefore, a stable, accurate, and fast image matching algorithm is very important for the subsequent processing of image information. Most of the traditional image matching methods have the problems of high-error matching rate and difficulty in to eliminating false matching. To resolve the shortcomings listed here, an improved algorithm was proposed in which a combined measure of Hamming distance. Similarity measurement with Tanimoto similarity measurement was adopted to dispose binary feature vectors. In addition, as an important step in the process of image mosaics, the calculation of the best mosaics can eliminate the ghosting and ghosting that may appear in the mosaics. However, the traditional dynamic planning method is easy to pass through the obstacles and form obvious stitching traces when searching for stitching lines in images with large obstacles. In view of the aforementioned content, we propose a fast and robust method to search the image difference matrix and structure difference matrix of the overlapping area of the input image according to the search strategy to determine the pixel coordinates of the splicing line. Finally, from an optimal splicing line, the experimental results show that our algorithm performs well for eliminating error matching points. Compared with traditional algorithms, matching accuracy is improved by 25%. In terms of calculating the optimal splicing line, the method proposed is faster than the traditional method and has good robustness. [ABSTRACT FROM AUTHOR]

In stereo matching tasks, the matching effect is often very poor when the texture of the region is weak or repeated. To solve this problem, an improved Graph Cut stereo matching algorithm based on Census transform is proposed. The Hamming distance of the corresponding pixels in the left and right images after Census transform is introduced as the similarity measure in the data term of the energy function. In this way, the dependence on the pixel value is reduced. The stereo matching experiments are implemented on the standard images of Middlebury stereo benchmark and the real scene images, and it demonstrates that our algorithm is robust and can obtain better performance in weak texture or repeated texture region. • Optimizing the data term in the energy function of the traditional GC method. • Performing Census transform operation on the stereo image pairs. • Taking Hamming distance of the corresponding pixels as the similarity measure. • Reducing the effect of illumination and the dependence on the pixel value. • Improving the stereo matching performance in weak tor repeated texture region. [ABSTRACT FROM AUTHOR]