FFT-based algorithms for the string matching with mismatches problem

The string matching with mismatches problem requires finding the Hamming distance between a pattern P of length m and every length m substring of text T with length n. Fischer and Paterson's FFT-based algorithm solves the problem without error in O(σnlogm), where σ is the size of the alphabet Σ [SIAM–AMS Proc. 7 (1973) 113–125]. However, this in the worst case reduces to O(nmlogm). Atallah, Chyzak and Dumas used the idea of randomly mapping the letters of the alphabet to complex roots of unity to estimate the score vector in time O(nlogm) [Algorithmica 29 (2001) 468–486]. We show that the algorithm's score variance can be substantially lowered by using a bijective mapping, and specifically to zero in the case of binary and ternary alphabets. This result is extended via alphabet remappings to deterministically solve the string matching with mismatches problem with a constant factor of 2 improvement over Fischer–Paterson's method.     

Bit-parallel approximate string matching algorithms with transposition

Using bit-parallelism has resulted in fast and practical algorithms for approximate string matching under Levenshtein edit distance, which permits a single edit operation to insert, delete or substitute a character. Depending on the parameters of the search, currently the fastest non-filtering algorithms in practice are the O(km/wn) algorithm of Wu and Manber, the O((k+2)(m−k)/wn) algorithm of Baeza-Yates and Navarro, and the O(m/wn) algorithm of Myers, where m is the pattern length, n is the text length, k is the error threshold and w is the computer word size. In this paper we discuss a uniform way of modifying each of these algorithms to permit also a fourth type of edit operation: transposing two adjacent characters in the pattern. This type of edit distance is also known as Damerau edit distance. In the end we also present an experimental comparison of the resulting algorithms.     

匹配问题实例空间和解空间结构

本文通过研究匹配问题的实例空间，匈牙利算法和解空间三者之间的关系，指出S实例空间的数目与问题复杂度之间的关系既不是充分也不是必要的，而如何对问题的解空间进行合理的分解才能是问题的关键。     

Fold‐2‐covering triangular embeddings

For a graph G and a positive integer m, G_(m) is the graph obtained from G by replacing every vertex by an independent set of size m and every edge by m² edges joining all possible new pairs of ends. If G triangulates a surface, then it is easy to see from Euler's formula that G_(m) can, in principle, triangulate a surface. For m prime and at least 7, it has previously been shown that in fact G_(m) does triangulate a surface, and in fact does so as a “covering with folds” of the original triangulation. For m = 5, this would be a consequence of Tutte's 5‐Flow Conjecture. In this work, we investigate the case m = 2 and describe simple classes of triangulations G for which G₍₂₎ does have a triangulation that covers G “with folds,” as well as providing a simple infinite class of triangulations G of the sphere for which G₍₂₎ does not triangulate any surface. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 79–92, 2003     

全固态多波长飞秒脉冲激光系统

利用棱镜对引进频谱空间啁啾来补偿飞秒脉冲激光二次谐波产生中的相位失配,提高了倍频效率建立了一套全固态、多波长(1065nm, 532nm,823.1nm, 402nm)飞秒脉冲激光系统自制的Nd:YVO4激光器输出532nm绿光激光,最高平均功率可达5.6W当用2.5W绿光激光泵浦时,从自制的钛宝石激光器及经BBO倍频可分别输出中心波长为823.1nm和402nm,平均功率300mW和73mW,谱宽32.3nm和5.1nm,脉宽22fs和33.3fs、重复率108MHz的近红外和蓝光激光整个系统具有结构紧凑、倍频效率高、运行稳定的特点.     

Enumeration of perfect matchings of a type of Cartesian products of graphs

Let G be a graph and let Pm(G) denote the number of perfect matchings of G.We denote the path with m vertices by P_m and the Cartesian product of graphs G and H by G×H. In this paper, as the continuance of our paper [W. Yan, F. Zhang, Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians, Adv. Appl. Math. 32 (2004) 175-188], we enumerate perfect matchings in a type of Cartesian products of graphs by the Pfaffian method, which was discovered by Kasteleyn. Here are some of our results:1. Let T be a tree and let C_n denote the cycle with n vertices. Then Pm(C₄×T)=∏(2+α²), where the product ranges over all eigenvalues α of T. Moreover, we prove that Pm(C₄×T) is always a square or double a square.2. Let T be a tree. Then Pm(P₄×T)=∏(1+3α²+α⁴), where the product ranges over all non-negative eigenvalues α of T.3. Let T be a tree with a perfect matching. Then Pm(P₃×T)=∏(2+α²), where the product ranges over all positive eigenvalues α of T. Moreover, we prove that Pm(C₄×T)=[Pm(P₃×T)]².     

Indexing text using the Ziv–Lempel trie

Let a text of u characters over an alphabet of size σ be compressible to n phrases by the LZ78 algorithm. We show how to build a data structure based on the Ziv–Lempel trie, called the LZ-index, that takes 4nlog₂n(1+o(1)) bits of space (that is, 4 times the entropy of the text for ergodic sources) and reports the R occurrences of a pattern of length m in worst case time O(m³logσ+(m+R)logn). We present a practical implementation of the LZ-index, which is faster than current alternatives when we take into consideration the time to report the positions or text contexts of the occurrences found.     

Towards the Exact Minimization of BDDs—An Elitism-Based Distributed Evolutionary Algorithm

Binary Decision Diagrams (BDDs) are the state-of-the-art data structure for representation and manipulation of Boolean functions. In general, exact BDD minimization is NP-complete. For BDD-based technology, a small improvement in the number of nodes often simplifies the follow-up problem tremendously. This paper proposes an elitism-based evolutionary algorithm (EBEA) for BDD minimization. It can efficiently find the optimal orderings of variables for all LGSynth91 benchmark circuits with a known minimum size. Moreover, we develop a distributed model of EBEA, DEBEA, which obtains the best-ever variable orders for almost all benchmarks in the LGSynth91. Experimental results show that DEBEA is able to achieve super-linear performance compared to EBEA for some hard benchmarks.     

Practical algorithms for transposition-invariant string-matching

We consider the problems of (1) longest common subsequence (LCS) of two given strings in the case where the first may be shifted by some constant (that is, transposed) to match the second, and (2) transposition-invariant text searching using indel distance. These problems have applications in music comparison and retrieval. We introduce two novel techniques to solve these problems efficiently. The first is based on the branch and bound method, the second on bit-parallelism. Our branch and bound algorithm computes the longest common transposition-invariant subsequence (LCTS) in time O((m²+loglogσ)logσ) in the best case and O((m²+logσ)σ) in the worst case, where m and σ, respectively, are the length of the strings and the size of the alphabet. On the other hand, we show that the same problem can be solved by using bit-parallelism and thus obtain a speedup of O(w/logm) over the classical algorithms, where the computer word has w bits. The advantage of this latter algorithm over the present bit-parallel ones is that it allows the use of more complex distances, including general integer weights. Since our branch and bound method is very flexible, it can be further improved by combining it with other efficient algorithms such as our novel bit-parallel algorithm. We experiment on several combination possibilities and discuss which are the best settings for each of those combinations. Our algorithms are easily extended to other musically relevant cases, such as δ-matching and polyphony (where there are several parallel texts to be considered). We also show how our bit-parallel algorithm is adapted to text searching and illustrate its effectiveness in complex cases where the only known competing method is the use of brute force.     

单循环赛赛程安排的一个图论方法

利用图论的边着色理论建立了一个赛程安排的数学模型 .首先建立 n支球队与完全图 Kn的 n个顶点间的一一对应 ,把球队 Ai和 Aj间的比赛关系抽象成 Kn的顶点 i和 j间的边 ( i,j) .然后分别构造出了图K2 m- 1和 K2 m的正常 2 m-1边着色 .从而给出了各球队每两场比赛间得到的休整时间最均等 ,休整的间隔场次数达到上限值 n2 的一个赛程安排方案