We present new algorithms for the k mismatches version of approximate string matching. Our algorithms utilize the SIMD (Single Instruction Multiple Data) instruction set extensions, particularly AVX2 and AVX-512 instructions. Our approach is an extension of an earlier algorithm for exact string matching with SSE2 and AVX2. In addition, we modify this exact string matching algorithm to work with AVX-512. We demonstrate the competitiveness of our solutions by practical experiments. Our algorithms outperform earlier algorithms for both exact and approximate string matching on various benchmark data sets. • New algorithms for the k mismatches version of approximate string matching. • We modify the exact string-matching algorithm to work with AVX-512. • Demonstrate the competitiveness of our solutions by practical experiments.

Abstract We present new algorithms for exact string matching of long patterns. Our algorithms read ‐grams at constant distances and are variations of the simplified BNDM algorithm. We demonstrate the competitiveness of our solutions through practical experiments. Many of our algorithms were faster than previous methods for English and DNA patterns between 400 and 50,000 in length. Our algorithms were still better when the preprocessing time was taken into account or when the patterns were taken from a different text of the same type.

Abstract We consider the $k$ mismatches version of approximate string matching for a single pattern and multiple patterns. For these problems, we present new algorithms utilizing the single instruction multiple data (SIMD) instruction set extensions for patterns of up to 32 characters. We apply SIMD computation in three ways: in counting of mismatches, in comparison of substrings and in calculation of fingerprints. We show the competitiveness of the new algorithms by practical experiments.

Summary The order‐preserving pattern matching problem has gained attention in recent years. It consists in finding all substrings in the text, which have the same length and relative order as the input pattern. Typically, the text and the pattern consist of numbers. Since recent times, there has been a tendency to utilize the ability of the word RAM model to increase the efficiency of string matching algorithms. This model works on computer words, reading and processing blocks of characters at once, so that usual arithmetic and logic operations on words can be performed in one unit of time. In this paper, we present a fast order‐preserving pattern matching algorithm, which uses specialized word‐size packed string matching instructions, grounded on the single instruction multiple data instruction set architecture. We show with experimental results that the new proposed algorithm is more efficient than the previous solutions. ©2016 The Authors. Software: Practice and Experience Published by John Wiley & Sons Ltd.

Summary More than 120 algorithms have been developed for exact string matching within the last 40 years. We show by experiments that the naïve algorithm exploiting SIMD instructions of modern CPUs (with symbols compared in a special order) is the fastest one for patterns of length up to about 50 symbols and extremely good for longer patterns and small alphabets. The algorithm compares 16 or 32 characters in parallel by applying SSE2 or AVX2 instructions, respectively. Moreover, it uses loop peeling to further speed up the searching phase. We tried several orders for comparisons of pattern symbols, and the increasing order of their probabilities in the text was the best.

The problem of order-preserving matching has gained attention lately. The text and the pattern consist of numbers. The task is to find all the substrings in the text which have the same length and relative order as the pattern. The problem has applications in analysis of time series. We present a new sublinear solution based on filtration. Any algorithm for exact string matching can be used as a filtering method. If the filtration algorithm is sublinear, the total method is sublinear on average. We show by practical experiments that the new solution is more efficient than earlier algorithms.

We develop bit-parallel algorithms for exact string matching.Our algorithms are variations of the BNDM and Shift-Or algorithms.At each alignment the algorithms read a q-gram before testing the state variable.In addition we apply reading a 2-gram in one instruction.Our experiments show that many of the new variations are substantially faster than any previous string matching algorithm on x86 processors for English and DNA data.

Based on results from the technologies for children with individual needs project and two case projects, we propose a new multidisciplinary framework for research between computer science, educational technology, and special education. The framework presents a way to conduct research that aims at developing new methods for technology-enhanced special education and for developing adaptable software and hardware tools for individual needs in educational settings.

We present a Boyer–Moore (BM) approach to string matching over LZ78 and LZW compressed text. The idea is to search the text directly in compressed form instead of decompressing and then searching it. We modify the BM approach so as to skip text using the characters explicitly represented in the LZ78/LZW formats, modifying the basic technique where the algorithm can choose which characters to inspect. We present and compare several solutions for single and multipattern searches. We show that our algorithms obtain speedups of up to 50% compared to the simple decompress-then-search approach. Finally, we present a public tool, LZgrep, which uses our algorithms to offer grep-like capabilities directly searching files compressed using Unix's Compress, a LZW compressor. LZgrep can also search files compressed with Unix gzip, using new decompress-then-search techniques we develop, which are faster than the current tools. This way, users can always keep their files in compressed form and still search them, uncompressing only when they want to see them. Copyright © 2005 John Wiley & Sons, Ltd.

Summary form only given. We consider string searching in compressed texts. We utilize a compression method related to static Huffman compression. Characters are encoded as variable length sequences of base symbols, which consist of a fixed number of bits. Because the length of a code as base symbols varies, we divide base symbols into stoppers and continuers in order to be able to recognize where a new code starts. Stoppers can only be used as the last base symbol of a code. All other base symbols are continuers which can be used anywhere but as the last base symbol of a code. Our searching algorithm is a variation of the Boyer-Moore-Horspool algorithm. The shift function is based on several base symbols in order to achieve longer jumps than the ordinary occurrence heuristic. If four bits are used for base symbols, we apply bytes of eight bits for shift calculation.

Concept learning belongs to the fundamental challenges of educational technology. Contrary to the current trend of designing and implementing contents for various web-based virtual courses, concept learning requires cognitive tools rather than digital materials. We introduce a novel scheme to generate computer games from concept maps made by a teacher or a learner herself. Concept gaming exceeds the potential of previous software packages for concept mapping in a significant feature: it adds excitement and tension to the process of building a meaningful composition of concepts related to each other. In addition, concept gaming supports learning at various levels, from memorizing up to open problem solving.

We present an applet-based system viewing concept maps on the Web. The input consists of a concept map written in a description language with optional style and layout definitions. The system has numerous applications, because many kinds of graphs, trees, and flowcharts written by humans or generated by other software can be shown in addition to traditional concept maps.

We consider methods for compressing parse trees, especially techniques based on statistical modeling. We regard a sequence of productions corresponding to a sum of the path from the root of a tree to a node x as the context of a node x. The contexts are augmented with branching information of the nodes. By applying the text compression algorithm PPMon such contexts we achieve good compression results. We compare experimentally the PPMapproach with other methods.

We consider how to create animations with Microsoft Excel. We present the capabilities of the drawing and auditing tools, dynamic graphs, and special effects of cells. Combining these features with the integrated Visual Basic programming language provides the user with an easy-to-use platform for versatile educational visualisations.

CLAP is a pedagogical approach for Computer Science education, applied here especially to laboratory courses. CLAP or Creative Lab with Active Participation provides an open learning environment, utilizing creative problem solving methods. For successful learning, CLAP emphasizes group processes. Pilot courses using CLAP were carried out during the Fall Semester of 1996 and the Spring Semester of 1997.

Understanding of fundamental algorithms and designing algorithms for a novel problem are basic skills in Computer Science. Animation is a useful aid in both these areas. We show how to animate algorithms with Microsoft Excel using data visualization and macro programming features of Excel. The user writes an algorithm using the Visual Basic programming language of Excel and defines charts visualizing dynamically the data structures of the algorithm. This approach is suitable especially for small-scale animation, e.g. for course assignments in Computer Science.

Searching for long DNA strings is studied. A q-gram variation of the Boyer–Moore algorithm is considered. An alphabet transformation with precomputed tables is utilized to reduce the processing time. Experimental results show that the new algorithm is efficient in practice. © 1997 John Wiley & Sons, Ltd.

Experimental comparisons of the running time of approximate string matching algorithms for the k differences problem are presented. Given a pattern string, a text string, and an integer k, the task is to find all approximate occurrences of the pattern in the text with at most k differences (insertions, deletions, changes). We consider seven algorithms based on different approaches including dynamic programming, Boyer–Moore string matching, suffix automata, and the distribution of characters. It turns out that none of the algorithms is the best for all values of the problem parameters, and the speed differences between the methods can be considerable.

The Boyer–Moore idea applied in exact string matching is generalized to approximate string matching. Two versions of the problem are considered. The k mismatches problem is to find all approximate occurrences of a pattern string (length m) in a text string (length n) with at most k mismatches. The generalized Boyer–Moore algorithm is shown (under a mild independence assumption) to solve the problem in expected time $O(kn({1 / {(m - k) + ({k / c})}}))$, where c is the size of the alphabet. A related algorithm is developed for the k differences problem, where the task is to find all approximate occurrences of a pattern in a text with $ \leqslant k$ differences (insertions, deletions, changes). Experimental evaluation of the algorithms is reported, showing that the new algorithms are often significantly faster than the old ones. Both algorithms are functionally equivalent with the Horspool version of the Boyer–Moore algorithm when $k = 0$.