The Pattern Matching problem with Swaps consists in finding all occurrences of a, pattern P in a text T, when disjoint local swaps in the pattern are allowed. In the Approximate Pattern Matching problem with Swaps one...
详细信息
ISBN:
(纸本)9783540958901
The Pattern Matching problem with Swaps consists in finding all occurrences of a, pattern P in a text T, when disjoint local swaps in the pattern are allowed. In the Approximate Pattern Matching problem with Swaps one seeks, for every text location with a swapped match of P, the number of swaps necessary to obtain a match at the location. In this paper, we present a new approach for solving both the Swap Matching problem and the Approximate Swap Matching problem in linear time, in the case of short, patterns. In particular, we devise a O(nm) general algorithm, named CROSS-SAMPLINGING, and show an efficient implementation of it, based on bit-parallelism, which achieves O(n) worst-case time and O(sigma)-space complexity, with patterns whose length is comparable to the word-size of the target machine.
A new bottom-up distance measure for labeled trees, which is based on the largest common forest of the trees and has the threefold advantage of independence of particular edit costs, low complexity, and coverage of or...
详细信息
ISBN:
(纸本)0769511937
A new bottom-up distance measure for labeled trees, which is based on the largest common forest of the trees and has the threefold advantage of independence of particular edit costs, low complexity, and coverage of ordered and unordered trees, is introduced and related in this paper with other distance measures published in the literature. algorithms for computing the bottom-up distance in time linear in the number of nodes are given in full detail.
Repetitive substructures in two-dimensional arrays emerge in speeding up searches and have been recently studied also independently in an attempt to parallel some of the classical derivations concerning repetitions in...
详细信息
Repetitive substructures in two-dimensional arrays emerge in speeding up searches and have been recently studied also independently in an attempt to parallel some of the classical derivations concerning repetitions in strings. The present paper focuses on repetitions in two dimensions that manifest themselves in form of two "tandem" occurrences of a same primitive rectangular pattern W where the two replicas touch each other with either one side or corner. Being primitive here means that W cannot be expressed in turn by repeated tiling of another array. The main result of the paper is an O(n(3) log n) algorithm for detecting all "side-sharing" repetitions in an n x n array. This is optimal, based on bounds on the number of such repetitions established in previous work. With easy adaptations, these constructions lead to an equally optimal, O(n(4)) algorithm for repetitions of the second type. (c) 2005 Elsevier B.V. All rights reserved.
Recent work shows that sampling algorithms can be an effective tool for graph visualization. This paper extends prior work by applying edge sampling algorithms to speed up the spring force calculation in force-directe...
详细信息
ISBN:
(纸本)9781728126050
Recent work shows that sampling algorithms can be an effective tool for graph visualization. This paper extends prior work by applying edge sampling algorithms to speed up the spring force calculation in force-directed graph layout algorithms. An experiment on 72 graphs finds that some sampling algorithms achieve comparable quality as no sampling. This result is confirmed with visualizations of the graph layout results. However, runtime improvements are small, especially for graphs with 10,000 vertices or fewer, indicating that the runtime savings might not be worth the risk to layout quality. Therefore, this paper suggests that accurate spring forces may be more important to force-directed graph layout algorithms than accurate electric forces. A copy of this paper plus the code and data to reproduce the results are available at https://***/4ja29/
In transfusion medicine, the process of preparing or separating blood components from the whole blood is essential because the indication for the use of unfractionated whole blood almost does not exist nowadays. Since...
详细信息
ISBN:
(纸本)9781424423835
In transfusion medicine, the process of preparing or separating blood components from the whole blood is essential because the indication for the use of unfractionated whole blood almost does not exist nowadays. Since blood is uneasily-collected and easily-perished, a blood center or a hospital blood bank might as well aggressively manage the volume of each blood component. so as to decrease any waste. We assume that the process of blood component preparation can be underlaid by a so-called blood component tree, where each vertex representing a blood component with a certain value is derived from its parent vertex. Initially given a certain amount of the root blood component in a blood component tree (noticing that the amount of every other blood component is zero initially), the blood component preparation problem is concerned with finding the assignment of amount of each blood component such that the total value is maximized while satisfying the demand limit of every blood component. In this paper, we propose a linear time algorithm (in the size of vertices) for efficiently coping with the concerned problem, which also can be modeled as a linear program. Some theoretical analyses are included in this paper.
Image capturing in different indoor and outdoor environment requires high quality and sensing camera devices. Image capture in fog, night, rainy atmosphere, etc., can face an unequal contrast problem. Visibility is th...
详细信息
ISBN:
(纸本)9789811065446;9789811065439
Image capturing in different indoor and outdoor environment requires high quality and sensing camera devices. Image capture in fog, night, rainy atmosphere, etc., can face an unequal contrast problem. Visibility is the primary concern for any image processing application to extract the content information and features accurately. In this paper, a ring segment based block feature evaluation method is provided to setup the enhancement individually in each segmented region. In this model, an intelligent method is applied to raw image to locate the regions with extreme visibility difference. The ring specific geographical mapping is applied to locate these regions. Three blocks from the region are evaluated based on visibility, entropy and frequency parameters. The comparative evaluation on block content strength is applied to get the referenced block blocks with maximum containment. Finally, each region block is mapped to this reference block to stabilize the contrast unbalancing. The proposed method is applied in real time captured images with different lighting effects. The comparative evaluation against histogram equalization method is applied for the PSNR and MSE parameters. The evaluation results show that the proposed method enhanced the visible quality and error robustness of dark, dull and faded images.
The problem of extracting a basis of irredundant motifs from a sequence is considered. In previous work such bases were built incrementally for all suffixes of the input string s in O(n(3)), where n is the length of s...
详细信息
ISBN:
(纸本)9783540735441
The problem of extracting a basis of irredundant motifs from a sequence is considered. In previous work such bases were built incrementally for all suffixes of the input string s in O(n(3)), where n is the length of s. Faster, non-incremental algorithms have been based on the landmark approach to string searching due to Fischer and Paterson, and exhibit respective time bounds of O(n(2) logn log|Sigma|) and O(|Sigma|n(2) log(2) n log log n), with Z denoting the alphabet. The algorithm by Fischer and Paterson makes crucial use of the FFT, which is impractical with long sequences. The algorithm presented in the present paper does not need to resort to the FFT and yet is asymptotically faster than previously available ones. Specifically, an off-line algorithm is presented taking time O(|Sigma|n(2)), which is optimal for finite Z.
The tree pattern matching problem over labeled trees is addressed in this paper Several tree pattern matching algorithms are known which are based on the decomposition of the pattern into strings, with each string rep...
详细信息
ISBN:
(纸本)0769521606
The tree pattern matching problem over labeled trees is addressed in this paper Several tree pattern matching algorithms are known which are based on the decomposition of the pattern into strings, with each string representing a root-to-leaf path. Among these, Alfs T. Berztiss gave a simple tree pattern matching algorithm which remained unknown to the research community. In this paper the tree pattern matching algorithm of Berztiss is reviewed, its correctness is established, and its complexity is shown to be O(mn) time and space in the worst case and O(n) on the average, where n is the text size and m is the pattern size.
Chordal bipartite graphs axe introduced to analyze non-symmetric matrices, and form a large class of perfect graphs. There are several problems, which can be solved efficiently on the class using the characterization ...
详细信息
ISBN:
(纸本)3540438645
Chordal bipartite graphs axe introduced to analyze non-symmetric matrices, and form a large class of perfect graphs. There are several problems, which can be solved efficiently on the class using the characterization by the doubly lexical ordering of the bipartite adjacency matrix. However, the best known algorithm for computing the ordering runs in O(min{m log n,n(2)}), which is the bottleneck of the problems. We show a linear time algorithm that computes the ordering of a given chordal bipartite graph. The result improves the upper bounds of several problems, including recognition problem, from O(min{m log n, n(2)}) to linear time. Strongly chordal graphs are well-studied subclass of chordal graphs, and that have similar characterization. The upper bounds of several problems on a given strongly chordal graph are also improved from O(min {m log n, n(2)}) to linear time.
The Pattern Matching problem with Swaps consists in finding all occurrences of a pattern P in a text;T, when disjoint local swaps in the pattern are allowed. In this paper, we present a new efficient algorithm for the...
详细信息
ISBN:
(纸本)9783642102165
The Pattern Matching problem with Swaps consists in finding all occurrences of a pattern P in a text;T, when disjoint local swaps in the pattern are allowed. In this paper, we present a new efficient algorithm for the Swap Matching problem with short patterns. In particular, we devise a O(nm(2)) general algorithm, named BACKWARD-CROSS-SAMPLING, and show an efficient implementation of it, based on bit-parallelism, which achieves O(nm) worst-case time and O(sigma)-space complexity, with patterns whose length m is comparable to the word-size of the target machine (n and sigma are respectively the size of the text and of the alphabet). From an extensive comparison with some of the most recent and effective algorithms for the swap matching problem, it turns out that our algorithm is very flexible and achieves very good results in practice.
暂无评论