Improving multikey Quicksort for sorting strings with many equal elements

Bentley and Sedgewick proposed multikey Quicksort with ‘split-end’ partitioning for sorting strings. But it can be slow in case of many equal elements because it adopted ‘split-end’ partitioning that moves equal elements to the ends and swaps back to the middle. We present ‘collect-center’ partitioning to improve multikey Quicksort in that case. It moves equal elements to the middle directly like the ‘Dutch National Flag Problem’ partitioning approach and it uses two inner loops like Bentley and McIlroy's. In case of many equal elements such as DNA sequences, HTML files, and English texts, multikey Quicksort with ‘collect-center’ partitioning is faster than multikey Quicksort with ‘split-end’ partitioning.     

Finding the longest common nonsuperstring in linear time

String inclusion and non-inclusion problems have been vigorously studied in such diverse fields as molecular biology, data compression, and computer security. Among the well-known string inclusion or non-inclusion notions, we are interested in the longest common nonsuperstring. Given a set of strings, the longest common nonsuperstring problem is finding the longest string that is not a superstring of any string in the given set. It is known that the longest common nonsuperstring problem is solvable in polynomial time.In this paper, we propose an efficient algorithm for the longest common nonsuperstring problem. The running time of our algorithm is linear with respect to the sum of the lengths of the strings in the given set, using generalized suffix trees.     

On some operations on strings suggested by gene assembly in ciliates

We define three operations on strings and languages suggested by the process of gene assembly in hypotrichous ciliates. This process is considered to be a prine example of DNA computing in vivo. This paper is devoted to some computational aspects of these operations from a formal language point of view. The closure of the classes of regular and context-free languages under these operations is settled. Then, we consider theld-macronuclear language of a given languageL, which consists of allld-macronuclear strings obtained from the strings ofL by iteratively applying the loop-direct repeat-excision. Finally, we discuss some open problems and further directions of research. Rudolf Freund: He received his master and doctor degree in computer science from the Vienna University of Technology, Austria, in 1980 and 1982, respectively. In 1986, he received his master degree in mathematics and physics from the University Vienna, Austria. In 1988 he joined the Vienna University of Technology in Austria, where he became an Associate Professor in September 1995. He has given various lectures in theoretical computer science, especially on formal languages and automata. His research interests include array and graph grammars, regulated rewritung, infinite words, syntactic pattern recognition, neural networks, and especially models and systems for biological computing. In these fields he is author of more than sixty scientific papers. Carlos Martín-Vide: He is Professor and Head of the Research Group on Mathematical Linguistics at Rovira i Virgili University, Tarragona, Spain. His specialities are formal language theory and mathematical linguistics. His last volume edited is Where Mathematics, Computer Science, Linguistics and Biology Meet (Kluwer, 2001, with V. Mitrana). He published 150 papers in conference proceedings and journals such as: Acta Informatica, BioSystems. Computational Linguistics, Computers and Artificial Intelligence, Information Processing Letters, Information Sciences, International Journal of Computer Mathematics, New Generation Computing, Publicationes Mathematicae Debrecen, and Theoretical Computer Science. He is the editor-in-chief of the journal Grammars (Kluwer), and the chairman of the 1st International PhD School in Formal Languages and Applications (2001–2003). Victor Mitrana, Ph.D.: He is Professor of Computer Science at the Faculty of Mathematics, University of Bucharest. He received his MSc and PhD from the University of Bucharest in 1986 and 1993, respectively. In 1999 he was awarded with the “Gheorghe Lazar” Prize for Mathematics of the Romanian Academy. His research interests include: formal language theory and applications, combinatorics on words, computational models inspired from biology, mathematical linguistics. In these areas, he published three books, more than 100 papers, and edited two books. He is an associate editor of “The Korean Journal of Computational and Applied Mathematics” and an editor of “Journal of Universal Computer Science”.     

The subsequence composition of a string

Words that appear as constrained subsequences in a text-string are considered as possible indicators of the host string structure, hence also as a possible means of sequence comparison and classification. The constraint consists of imposing a bound on the number ω$\omega$ of positions in the text that may intervene between any two consecutive characters of a subsequence. A subset of such ω$\omega$-sequences is then characterized that consists, in intuitive terms, of sequences that could not be enriched with more characters without losing some occurrence in the text. A compact spatial representation is then proposed for these representative sequences, within which a number of parameters can be defined and measured. In the final part of the paper, such parameters are empirically analyzed on a small collection of text-strings endowed with various degrees of structure.     

Construction of Aho Corasick automaton in linear time for integer alphabets

We present a new simple algorithm that constructs an Aho Corasick automaton for a set of patterns, P, of total length n, in O(n) time and space for integer alphabets. Processing a text of size m over an alphabet Σ with the automaton costs O(mlog|Σ|+k), where there are k occurrences of patterns in the text.A new, efficient implementation of nodes in the Aho Corasick automaton is introduced, which works for suffix trees as well.     

Computing by Floating Strings

We propose a biologically inspired system which computes on double structures of mobile strings by means of rewriting rules that have a biotechnological implementation, by resembling DNA computations. Its computational universality may be straight deduced from a few formal language theoretical results of one of the authors. Such a DNA-like computational device is naturally described by a membrane system which concludes the paper.     

Improving practical exact string matching

We present improved variations of the BNDM algorithm for exact string matching. At each alignment our bit-parallel algorithms process a q-gram before testing the state variable. In addition we apply reading a 2-gram in one instruction. Our point of view is practical efficiency of algorithms. Our experiments show that the new variations are faster than earlier algorithms in many cases.     

基于特征串的大规模中文网页快速去重算法研究

网页检索结果中,用户经常会得到内容相同的冗余页面,其中大量是由于网站之间的转载造成。它们不但浪费了存储资源,并给用户的检索带来诸多不便。本文依据冗余网页的特点引入模糊匹配的思想,利用网页文本的内容、结构信息,提出了基于特征串的中文网页的快速去重算法,同时对算法进行了优化处理。实验结果表明该算法是有效的,大规模开放测试的重复网页召回率达97.3% ,去重正确率达99.5%。     

On regular drawn symbolic picture languages

Drawn symbolic pictures are an extension of drawn pictures obtained by associating a symbol from an alphabet to each point of the picture. In the paper we will address some new interesting issues derived from the introduction of the symbols and we will identify the conditions, which ensure the preservation of properties holding for drawn pictures in the setting of the proposed extension.