Teaching computer programming has become common in high schools, and often students' programming work needs to be assessed formally. In Aotearoa New Zealand this formal assessment happens primarily in the last three years of high school, and is currently carried out manually by teachers. Here we explore the possibility of automating this assessment with the goal of decreasing teacher workload, and increasing fairness and transparency. To do this, we first report on a multi-part survey of teachers in New Zealand schools. The first part of the survey identifies the range of languages that need to be supported. The second part of the survey, in conjunction with a literature review of automated assessment, gives us a range of tools that are designed to automatically assess programming. We evaluate this group of assessment tools based on a wide range of criteria gathered from the survey of schools and the literature review. This includes the programming languages these tools can check, with a priority given to programming languages teachers are already using in the classroom. We also consider their resilience to common programming mistakes (such as infinite while loops), whether the tools can check style and quality, whether they include gamification, whether they use closure to encourage students, what kinds of programming constraints we can put on questions, and if they are open source. Based on this analysis, CodeRunner was the contender that most strongly stood out for our context, and is the tool we will move forward with in implementing automated assessment in a New Zealand high school environment.

Randomization is a technique that can be used with programming assessments to discourage academic misconduct by making it unlikely for two colluding students to get the exact same questions. Previous research about randomization has shown it to be an effective tool for addressing academic misconduct, but this work often focuses on randomization broadly, with few considering specific techniques. In contrast, we consider different randomization techniques and the contexts that they are best suited to. In addition, we investigate the effectiveness of randomization techniques against emerging AI technologies. This is done by exploring randomization in the context of an online quiz system that evaluates student responses to pro-gramming challenges, specifically the CodeRunner system for the Moodle learning management system. We provide a classification of techniques, and discuss the benefits of each. This classification starts with simpler techniques, such as shuffling question order, shuffling multi-choice question options, and question pooling. We then move on to more advanced techniques, including simple substitution, altering expected output, switching logic, and steganography. We also investigate two approaches to generating randomized questions, considering the benefits and drawbacks of each. These approaches are generating the questions beforehand (pre-generation) and generating the questions when the quiz is started (on-the-fly generation). We then identify four categories of assessment based on assessment that is formative/summative, and proctored/non-proctored, then identify which randomization techniques are suited for each category. Finally, we test randomized questions against OpenAI's Codex, to see if these techniques could prevent this new opportunity for academic dishonesty. We found that there are some types of questions that Codex currently performs poorly on, such as program reasoning, and creating complex classes, but overall randomization was not effective in defeating it, with Codex scoring 79.7% on questions that were created after it was trained, and 85.3 % on questions that could have been available to it when it was trained.

In learning to program and understanding how a programming language controls a computer, learners develop both insights and misconceptions whilst their mental models are gradually refined. It is important that the learner is able to distinguish the different elements and roles of a computer (compiler, interpreter, memory, etc.), which novice programmers may find difficult to comprehend. Forming accurate mental models is one of the potential sources of difficulty inextricably linked to mastering computing concepts and processes, and for learning computer programming. It is common to use some form of representation (e.g., an abstract machine or a Computational Agent (CA)) to support technical or pedagogic explanations. The Notional Machine (NM) is a pedagogical device that entails one or more computational concepts, originally described as an idealised computer operating with the constructs of a particular programming language. It can be used to support specific or general learning goals and will typically have some concrete representation that can be referred to. Computational Thinking (CT), which is defined as a way of thinking that is used for [computational] problem solving, is often presented as using a CA to carry out information processing presented by a solution. In CT, where the typical goal is to produce an algorithm or a computer program, the CA seemingly serves a purpose very similar to an NM. Although it changes through the different stages of development (of the learner and of the curriculum), the roles of CAs and NMs can be seen as versatile tools that connect a learner’s mental model with the conceptual model of a program. In this article, we look at this relationship between CAs and NMs, and indicate how they would look at different stages of learning. We traverse the range of definitions and usages of these concepts, and articulate models that clarify how these are viewed in the literature. This includes exploring the nature of machines and agents, and how historical views of these relate to modern pedagogy for computation. We argue that the CA can be seen as an abstract, simplified variant of an NM that provides a useful perspective to the learner to support them to form robust mental models of NMs more efficiently and effectively. We propose that teaching programming should make use of the idea of a CA at different stages of learning, as a link that connects a learner’s mental model to a full NM.

Programming plays a paramount role in many educational policies and initiatives. However, the current focus on coding skills poses a risk of giving pupils an over simplistic and impoverished idea of what programming means and involves. Their experiences would be much more significant if learning were aimed at understanding the richness of the nature of programs. In fact, programs are strange creatures that escape simple definitions. They are real, in that they affect our real lives; they are abstract, in that they process abstract entities; and they are concrete, in that they take up space in digital devices memory, and can be copied, transferred, corrupted. Thus, understanding the multifaceted nature of programs is crucial knowledge for all citizens of the digital era, and a fundamental component of such an understanding is getting a sense of how programs are created and work (i.e., the programming process). To the best of our knowledge, there is no Nature of Programs framework (e.g., a set of statements that describe what the nature of programs is), that teachers and policy makers can use to shape their practice and targets. The goal of the WG is developing such a framework, by collecting and organizing contributions from CER, CS experts, and educators.

This Full Paper in the Research Category identifies and evaluates teaching resources suitable for teaching younger students using the Scratch and Python programming languages. Choosing suitable resources to introduce programming to children is a balance between making sure they are appropriate to their skills such as literacy and numeracy, and are motivating in their social context. Resources need to strike a balance between allow early success, but also introduce genuine programming skills, so that students can progress their programming skills rather than repeating simple tasks over and over. An important element is the choice of teaching resources used to support students' learning. We propose using elementary programming patterns as a measure of how comprehensive a teaching resource for programming is. Note that this doesn't mean advocating that students should be pressed to learn advanced patterns quickly, but it does provide a measure of how deeply a particular resource covers general programming concepts. We identify a set of patterns that are relevant to basic programming practice, and have analyzed some recommended online teaching resources and a small sample of introductory programming books for Scratch and Python against this set of patterns. The use of given set of patterns was relatively low, but some resources did introduce a range of patterns, and some new patterns emerged from the analysis that seemed to be used frequently in Scratch.

As new computing curricula are rolled out around the world, teachers are having to adjust to teaching new topics, finding new resources, and even working in a different style in the classroom. For some, this is a long-awaited change that they are more than ready for, but for many, particularly in primary school, it is unfamiliar territory and a foreign language, and it might even appear to threaten deeply-held values they have about what their learners need. Because the curriculum is new, it is unlikely to have been part of their own education or their preparation for being a teacher.

The 32 chapters of the 2019 Cambridge Handbook of Computing Education Research synthesize the existing research in computing education and propose new directions for future research. An author from each chapter will summarize their chapter with auto-advancing slides. Attendees will be introduced to the breadth of content in the new handbook and can identify chapters of interest. This fits uniquely as a special session, and will likely be informative, inspiring, and overwhelming.

This Full Paper in the Research Category evaluates the use of remixing in Scratch. A feature of the Scratch programming environment is that it supports students to share their code and “remix” (modify) other students' code. Remixing in Scratch has garnered much attention by the research community as use of collaboration for learning was one of the main ideas behind Scratch. It can provide opportunities to read others' code, learn how features can be implemented using the Scratch language, and contribute to the program. It can also prevent students from engaging with the code if they copy an existing program that does what they are trying to do without needing modification. The literature shows mixed results regarding use of remixes in Scratch. We have investigated at a large scale what happens in practice by analysing thousands of student programs shared through the Scratch online repository. As well as replicating prior work on a larger scale to show the impact of remixing on learning programming skills through Lines of Code (LOC) and repertoire of block usage, we also measure the use of elementary patterns (common combinations of commands). We track the progress of each project through its remixes and compare the results between the root version and the final version.

In this Work in Progress paper in the Research Category we report on existing concerns about Scratch programming, and introduce patterns as a possible solution. Scratch is a popular language for introducing students to programming, but there is a concern that the students might not be exposed to all the key elements of programming when the development environment tempts them to explore elements such as the range of sprites available. We propose the use of programming patterns as a measure of the sophistication of student work. To understand the importance of patterns we report on our initial work that analyzes a large number of projects from the public Scratch repository to evaluate how extensively the basic patterns appear in student work. This can help inform the improvement of teaching methods to include use of broader range of patterns.

Computer Science is seen in many different ways in society; some may consider it to be an esoteric collection of jargon-laden skills, while others view it as an essential topic of study for all citizens. Many of us are very passionate about sharing our enthusiasm for the subject with others, and we are at a time in history where much of the hard work to get the public to understand that it is something special is starting to bear fruit, as we see Computer Science and Computational thinking appearing in K-12 curricula around the world. But what is it about Computer Science that makes it so important and exciting? Is it a subject in its own right that deserves space in the curriculum? We will explore the reasons that young students should become engaged with the subject, illustrated using an Unplugged perspective.

Study abroad offers students the opportunity to experience other cultures, languages, and environments while obtaining credits toward their degree. Students are also taught to appreciate the diversity of people and culture, such that they may dismiss stereotypes and learn to communicate and collaborate cross-culturally in a global economy. Unfortunately, few universities offer study abroad programs directed specifically to computer science and particularly in combining student technical learning with service learning for broadening participation in computing throughout the world. In this paper, we describe a service-learning-based model for computer science students and other university students with minimal prior computer science experience to engage and inspire themselves and the next generation of computational thinkers through learning, teaching and creating web-based learning games along with local children and teachers in a foreign country. We describe the model focusing on learning objectives, curriculum, field component, planning, and partnership building. We describe the products that undergraduates were able to create in four weeks and their CS education service learning field experiences. Finally, we investigate the impact of the study abroad model on undergraduates' content knowledge, and their career and personal development.

We propose a root stemmer for the Modern Standard Arabic (MSA) language in an attempt to enhance the performance of Arabic Information Retrieval (AIR). The new Simple Arabic Stemmer (SAS) is based on the Quran morphology, since the Quran was a key source for the derivation of Arabic morphological rules. The stemmer is developed by decomposing all of the Quran words and studying their internal morphological structure including the roots, the patterns, and the affixes employed in the generation process. We were able to construct a relatively small lexicon capable of finding the root for most of the MSA vocabulary. Using the TREC corpus and queries, we test our approach against two well-known root stemmers, Khoja and Sebawai. The results show that SAS gives an improvement in terms of precision.

For many years computing in New Zealand schools was focused on teaching students how to use computers, and there was little opportunity for students to learn about programming and computer science as formal subjects. In this article we review a series of initiatives that occurred from 2007 to 2009 that led to programming and computer science being made available formally as part of the National Certificate in Educational Achievement (NCEA), the main school-leaving assessment, in 2011. The changes were phased in from 2011 to 2013, and we review this process using the Darmstadt model, including describing the context of the school system, the socio-cultural factors in play before, during and after the changes, the nature of the new standards, the reactions and roles of the various stakeholders, and the teaching materials and methods that developed. The changes occurred very quickly, and we discuss the advantages and disadvantages of having such a rapid process. In all these changes, teachers have emerged as having a central role, as they have been key in instigating and implementing change.

You've been asked to talk to an elementary or high school class about Computer Science, but how can you ensure that the talk is engaging? Or perhaps you're trying to introduce a concept from Computer Science to a school group, but you want a fun way to get the class engaged. This workshop is a hands-on introduction to Computer Science Unplugged (www.csunplugged.org), a widely used set of kinesthetic, fun activities that cover many core areas of computer science without using high technology. We will explore how to use the activities in a variety of situations, including using them with robotics activities, school outreach, and computer clubs. Attendees will receive a CD with a copy of a handbook for teachers and a collection of videos demonstrating the activities. Laptops are optional.

In 2011 New Zealand introduced computer science into high schools after a long period when computing was mainly focussed on training students to be users. The transition was rapid, and teachers had little time to upskill to prepare for the new topics, and yet there was widespread voluntary adoption of the new standards. The role of teachers and the national teachers' organisation in making the change has been pivotal, and this paper reviews the changes from the teachers' perspective. This story is intended to inform those planning similar changes in other countries, and provide a context for the next steps in NZ. The discussion centres around a survey of 91~teachers, which reveals strong intrinsic motivation from teachers to make the changes, a mixture of prior knowledge and skills that teachers shared with each other through peer support and online communication, a low level of confidence as teachers of computer science, and a need for further professional development.

Computer science became available as a nationally assessed topic in NZ schools for the first time in 2011. We review the introduction of computer science as a formal topic, including the level of adoption, issues that have arisen in the process of introducing it, and work that has been undertaken to address those issues.

Outreach activities including Computer Science Unplugged demonstrate computer science concepts at schools and public venues based around kinesthetic activities rather than hands-on computer use. Computer Science Unplugged is a global project that has shared many such activities for children to adults using no technology, including how binary numbers represent words, images and sound, routing and deadlock, public/private key encryption, and others. These and other effective outreach programs can combat the idea that computer science = programming or, worse, keyboarding; and can educate the public, interest students, and recruit majors. Many people have used these activities, and adapted them for their own culture or outreach purposes. Come share your outreach ideas and experiences with such activities. Employers, researchers and teachers have noted the need for effective outreach to ensure that students and the public be exposed to, and understand what Computer Science is. CS Unplugged is a collection of activities that are accessible to a general audience, need no technology, are fun, and cover many core areas of computer science. The focus of this session will be discussing activities that introduce computer science concepts and way of thinking, and that are consistent with Jeanette Wing's Computational Thinking [Wing06]. The session is intended to allow exchanging ideas about effective outreach in the community, in K-12, and even non-major classes. There are many variations of these activities, and it is valuable to get practitioners together to share their successes - and not-so-successful events - so that others can benefit from them.

You've been asked to talk to an elementary or high school class about Computer Science, but how can you ensure that the talk is engaging? Or perhaps you're trying to introduce a concept from Computer Science to a school group, but you want a fun way to get the class engaged. This workshop is a hands-on introduction to Computer Science Unplugged (www.csunplugged.org), a widely used set of kinesthetic, fun activities that cover many core areas of computer science without using high technology. We will explore how to use the activities in a variety of situations, including combining them with robotics activities, and explore some novel applications. Attendees will receive a CD with a copy of a handbook for teachers and a collection of videos demonstrating the activities.

We examine five outreach programmes that introduce school students to Computer Science. All downplay programming as a pre-requisite skill for engaging with Computer Science, yet they use a wide variety of formats for reaching students, including contests, shows, magazine articles, and resources for teachers. We classify these different approaches, identifying the different ways they have been adapted to their target audience, and drawing out the common elements to provide guidance for similar initiatives.

This paper offers an exercise for revisiting the main sorting algorithms after they have been taught to students. This is done in a way that emphasizes the relationships between them, and shows how considering abstraction and extreme cases can lead to the generation of new algorithms. A number of authors (including textbook authors) have noted particular relationships between algorithms, such as an uneven split in merge sort being equivalent to insertion sort. In this paper we use a flexible priority queue, the d-heap, to derive three common sorting algorithms. We combine this with using a BST as a priority queue, plus prior observations in the literature, to show strong relationships between the main sorting algorithms that appear in textbooks. In the process students are able to revisit a number of algorithms and data structures and explore elegant relationships between them. This approach can also lead to exercises and exam questions that go beyond desk-checking to evaluate students' understanding of these algorithms.

This paper describes the design, implementation, and evaluation of a course teaching Computer Science majors about teaching Computer Science. The course was designed to address the need for teachers and resources to support rapid changes in topics being taught in high schools. It also helped prepare students for research in Computer Science Education, and for careers involving computing and education. The course is described in detail, and is evaluated based on student feedback and the outcomes from the course.

We describe the experiences of three University projects that use a style of physical, non-computer based activity to enthuse and teach school students computer science concepts. We show that this kind of activity is effective as an outreach and teaching resource even when reused across different age/ability ranges, in lecture and workshop formats and for delivery by different people. We introduce the concept of a Reusable Outreach Object (ROO) that extends Reusable Learning Objects. and argue for a community effort in developing a repository of such objects.

"Computer Science (CS) Unplugged" is an educational method for introducing non-specialists to concepts of CS through hands-on activities that don't require the use of a computer. Often the deeper concepts of CS have been considered as being too difficult for elementary and middle school students, and many educators teaching "IT" are not even aware of the richness of the topic. CS Unplugged methods have been used successfully with students of a wide range of ages. In this paper, we analyze the structure of CS Unplugged activities to identify the elements that make them work well. Based on the analysis, we propose a design pattern which will be useful as a guideline for developing new activities, and to revise existing ones. We also describe our experience developing original teaching material, using the pattern as a benchmark for evaluation.

The rapid rate of the development of computer technology raises the issue of how to reform Computer Science education in elementary and middle schools. In Korea the government has taken this issue seriously, and the Ministry of Education & Human Resources Development has announced substantial revisions to its computing curricula, leading to a new curriculum in Informatics to be introduced for middle schools in 2010, and for high schools in 2011. There is a proposal that the elementary school curriculum will be linked to these, and with a stronger focus on not just learning how to operate computers and software, but understanding the methods and algorithms behind Computer Science.

Groupware communicates by sending messages across the network, and groupware programmers use a variety of formats for these messages, such as XML, plain text, or serialized objects. Although these formats have many advantages, they are often so verbose that they overload the system's network resources. Groupware programmers could improve efficiency by using more compact formats, but this efficiency comes at the cost of increased complexity, reduced convenience, and reduced readability. In this paper we propose an alternate approach for improving efficiency -- an automatic compression system that transparently minimizes verbose formats. Our general message compressor -- GMC -- automatically finds and removes redundancy in message streams, without any knowledge of the contents or structure of the message, and without any need for the programmer to change the way they work. In tests with realistic message traces, GMC reduced text messages to 20% of their original size, XML messages to 8% of the original, and serialized objects to 9%. Although not as compact as a hand-coded representation, GMC provides most of the compression benefits with almost none of the work -- it allows groupware programmers to use convenient message formats without compromising transport efficiency.

Recently a number of algorithms have been developed to search files compressed with the Burrows-Wheeler Transform (BWT) without the need for full decompression first. This allows the storage requirement of data to be reduced through the exceptionally good compression offered by BWT, while allowing fast access to the information for searching by taking advantage of the sorted nature of BWT files. We provide a detailed description of five of these algorithms: BWT-based Boyer-Moore, Binary Search, Suffix Arrays, q-grams and the FM-index, and also present results from a set of extensive experiments that were performed to evaluate and compare the algorithms. Furthermore, we introduce a technique to improve the search times of Binary Search, Suffix Arrays and q-grams by 22% on average, as well as reduce the memory requirement of the latter two by 40% and 31%, respectively. Our results indicate that, while the compressed files of the FM-index are larger than those of the other approaches, it is able to perform searches with considerably less memory. Additionally, when only counting the occurrences of a pattern, or when locating the positions of a small number of matches, it is the fastest algorithm. For larger searches, Binary Search provides the fastest results. Comparative results with non-BWT based search methods are also included. Copyright © 2005 John Wiley & Sons, Ltd.

Summary form only given. The approximate pattern matching on the text transformed by the Burrows-Wheeler transform (BWT) was considered. This is an important first step towards developing a compressed pattern matching algorithm for the BWT based compression system. Algorithms are proposed to solve the K-mismatch problem. Tests were performed on different pattern lengths using 133 selected files from the Canterbury, Calgary, and TREC corpus. The results on the K-mismatch pattern matching show that the running time and storage are superior to the fast suffix tree approach. Thus, once the index arrays are created, for repeated pattern search operations and for long patterns, the proposed algorithms perform significantly better than the agrep and ngrep. Using DFA verification, the search time is almost constant. The amortized cost is lower for multiple patterns search operations.

Abstract Optical music recognition (OMR) systems are used to convert music scanned from paper into a format suitable for playing or editing on a computer. These systems generally have two phases: recognizing the graphical symbols (such as note‐heads and lines) and determining the musical meaning and relationships of the symbols (such as the pitch and rhythm of the notes). In this paper we explore the second phase and give a two‐step approach that admits an economical representation of the parsing rules for the system. The approach is flexible and allows the system to be extended to new notations with little effort—the current system can parse common music notation, Sacred Harp notation and plainsong. It is based on a string grammar and a customizable graph that specifies relationships between musical objects. We observe that this graph can be related to printing as well as recognizing music notation, bringing the opportunity for cross‐fertilization between the two areas of research. Copyright © 2003 John Wiley & Sons, Ltd.

Summary form only given. The compressed pattern matching problem is to locate the occurrence(s) of a pattern P in a text string T using a compressed representation of T, with minimal (or no) decompression. The BWT performs a permutation of the characters in the text, such that characters in lexically similar contexts will be near to each other. The motivation for our approach is the observation that the BWT provides a lexicographic ordering of the input text as part of its inverse transformation process.

This paper explores two techniques for on-line exact pattern matching in files that have been compressed using the Burrows-Wheeler transform. We investigate two approaches. The first is an application of the Boyer-Moore algorithm (1977) to a transformed string. The second approach is based on the observation that the transform effectively contains a sorted list of all substrings of the original text, which can be exploited for very rapid searching using a variant of binary search. Both methods are faster than a decompress-and-search approach for small numbers of queries, and binary search is much faster even for large numbers of queries.

This correspondence considers the compression of matrices where the majority of the entries are a fixed constant (most typically zero), usually referred to as sparse matrices. We show that using Golomb or Rice encoding requires significantly less space than previous approaches. Furthermore, compared to arithmetic coding, the space requirements are only slightly increased but access is ten times faster for both Golomb and Rice encoding. By blocking the data, the access time can be kept constant as only a single block needs to be decoded to access any element. Although such blocking increases the space overheads, this is marginal until the block sizes become so small that only a few nonzero values will be found in a block. We provide formulas giving the space overhead of blocked Rice encoding and validate these empirically.

The compression of matrices where the majority of the entries are a fixed constant (most typically zero), usually referred to as sparse matrices, has received much attention. We evaluate the performance of existing methods, and consider how arithmetic coding can be applied to the problem to achieve better compression. The result is a method that gives better compression than existing methods, and still allows constant-time access to individual elements if required. Although for concreteness we express our method in terms of two-dimensional matrices where the majority of the values are zero, it is equally applicable to matrices of any number of dimensions and where the fixed known constant is any value. We assume that the number of dimensions and their ranges are known, but will not assume that any information is available externally regarding the number of non-zero entries.

A number of authors have used the Calgary corpus of texts to provide empirical results for lossless compression algorithms. This corpus was collected in 1987, although it was not published until 1990. The advances with compression algorithms have been achieving relatively small improvements in compression, measured using the Calgary corpus. There is a concern that algorithms are being fine-tuned to this corpus, and that small improvements measured in this way may not apply to other files. Furthermore, the corpus is almost ten years old, and over this period there have been changes in the kinds of files that are compressed, particularly with the development of the Internet, and the rapid growth of high-capacity secondary storage for personal computers. We explore the issues raised above, and develop a principled technique for collecting a corpus of test data for compression methods. A corpus, called the Canterbury corpus, is developed using this technique, and we report the performance of a collection of compression methods using the new corpus.

Text compression schemes have sometimes been divided into two classes: symbolwise methods, which form a source model, typically using a finite context to predict symbols; and dictionary methods, which replace phrases (groups of symbols) in the input with a code. It is possible to decompose some dictionary methods into equivalent symbolwise methods. The decomposed method gives identical compression performance, but is slower because more coded symbols are transmitted. This decomposition is of interest primarily because it is helpful in making comparisons of the two methods. The authors explore a hybrid approach based on the opposite of this decomposition: the predictions of a symbolwise method are grouped together so that several characters can be coded at once. The objective is to combine the good compression of symbolwise methods with the high speed of dictionary methods. The hybrid allows tradeoffs to be made in terms of compression speed, compression performance, and memory usage. More importantly, investigating a hybrid method gives extra insights into the relationship between dictionary and symbolwise methods, and reveals that they are more closely related than might be expected.>

The complementary paradigms of text compression and image compression suggest that there may be potential for applying methods developed for one domain to the other. In image coding, lossy techniques yield compression factors that are vastly superior to those of the best lossless schemes and we show that this is also the case for text. This paper investigates the resulting trade-off between subjective quality of the transmission and its compression factor. Two different methods are described, which can be combined into an extremely effective technique that provides far better compression than the present state of the art and yet preserves a reasonable degree of perceived match between the original and received text. The major challenge for lossy text compression is the quantitative evaluation of the quality of this match.

Text compression methods can be divided into two classes: symbolwise and parsing . Symbolwise methods assign codes to individual symbols, while parsing methods assign codes to groups of consecutive symbols (phrases). The set of phrases available to a parsing method is referred to as a dictionary . The vast majority of parsing methods in the literature use greedy parsing (including nearly all variations of the popular Ziv-Lempel methods). When greedy parsing is used, the coder processes a string from left to right, at each step encoding as many symbols as possible with a phrase from the dictionary. This parsing strategy is not optimal, but an optimal method cannot guarantee a bounded coding delay. An important problem in compression research has been to establish the relationship between symbolwise methods and parsing methods. This paper extends prior work that shows that there are symbolwise methods that simulate a subset of greedy parsing methods. We provide a more general algorithm that takes any nonadaptive greedy parsing method and constructs a symbolwise method that achieves exactly the same compression. Combined with the existence of symbolwise equivalents for two of the most significant adaptive parsing methods, this result gives added weight to the idea that research aimed at increasing compression should concentrate on symbolwise methods, while parsing methods should be chosen for speed or temporary storage considerations.

A two-stage method for compressing bilevel images is described that is particularly effective for images containing repeated subimages, notably text. In the first stage, connected groups of pixels, corresponding approximately to individual characters, are extracted from the image. These are matched against an adaptively constructed library of patterns seen so far, and the resulting sequence of symbol identification numbers is coded and transmitted. From this information, along with the library itself and the offset from one mark to the next, an approximate image can be reconstructed. The result is a lossy method of compression that outperforms other schemes. The second stage employs the reconstructed image as an aid for encoding the original image using a statistical context-based compression technique. This yields a total bandwidth for exact transmission appreciably undercutting that required by other lossless binary image compression methods. Taken together, the lossy, and lossless methods provide an effective two-stage progressive transmission capability for textual images which has application for legal, medical, and historical purposes, and to archiving in general.>

The authors examine the resource requirements and compression efficiency of the coding phase, concentrating on applications with medium and large alphabets. When semi-static two-pass encoding can be used, Huffman coding is two to four times faster than arithmetic coding, and sometimes results in superior compression. When an adaptive coder is required the difference in speed is smaller, but Gallager's implementation of dynamic Huffman coding is still faster than arithmetic coding in most situations. The compression loss through the use of Huffman codes is negligible in all but extreme circumstances. Where very high speed is necessary splay coding is also worth considering, although it yields poorer compression.>

article Free Access Share on Getting research students started: a tale of two courses Authors: Ian H. Witten Department of Computer Science, University of Waikato, Hamilton, New Zealand Department of Computer Science, University of Waikato, Hamilton, New ZealandView Profile , Timothy C. Bell Department of Computer Science, University of Canterbury, Christchurch, New Zealand Department of Computer Science, University of Canterbury, Christchurch, New ZealandView Profile Authors Info & Claims ACM SIGCSE BulletinVolume 25Issue 1March 1993 pp 165–169https://doi.org/10.1145/169073.169385Online:01 March 1993Publication History 10citation480DownloadsMetricsTotal Citations10Total Downloads480Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

When data compression is applied to full-text retrieval systems, intricate relationships emerge between the amount of compression, access speed, and computing resources required. We propose compression methods, and explore corresponding tradeoffs, for all components of static full-text systems such as text databases on CD-ROM. These components include lexical indexes, inverted files, bitmaps, signature files, and the main text itself. Results are reported on the application of the methods to several substantial full-text databases, and show that a large, unindexed text can be stored, along with indexes that facilitate fast searching, in less than half its original size—at some appreciable cost in primary memory requirements. © 1993 John Wiley & Sons, Inc.

Abstract Ziv‐Lempel coding is currently one of the more practical data compression schemes. It operates by replacing a substring of a text with a pointer to its longest previous occurrence in the input, for each coding step. Decoding a compressed file is very fast, but encoding involves searching at each coding step to find the longest match for the next few characters. This paper presents eight data structures that can be used to accelerate the searching, including adaptations of four methods normally used for exact matching searching. The algorithms are evaluated analytically and empirically, indicating the trade‐offs available between compression speed and memory consumption. Two of the algorithms are well‐known methods of finding the longest match—the time‐consuming linear search, and the storage‐intensive trie (digital search tree). The trie is adapted along the lines of a PATRICIA tree to operate economically. Hashing, binary search trees, splay trees and the Boyer‐Moore searching algorithm are traditionally used to search for exact matches, but we show how these can be adapted to find longest matches. In addition, two data structures specifically designed for the application are presented.

The authors describe a method for lossless compression of images that contain predominantly typed or typeset text-they call these textual images. An increasingly popular application is document archiving, where documents are scanned by a computer and stored electronically for later retrieval. Their project was motivated by such an application: Trinity College in Dublin, Ireland, are archiving their 1872 printed library catalogues onto disk, and in order to preserve the exact form of the original document, pages are being stored as scanned images rather than being converted to text. The test images are taken from this catalogue. These typeset documents have a rather old-fashioned look, and contain a wide variety of symbols from several different typefaces-the five test images used contain text in English, Flemish, Latin and Greek, and include italics and small capitals as well as roman letters. The catalogue also contains Hebrew, Syriac, and Russian text.>

This paper explores the application of arithmetic coding to systems involving the storage of a large body of text, along with a lexicon that lists the words and a concordance that indicates the exact locations at which each word can be found. A typical query might seek all sentences that contain a particular word or combination of words. The random-access requirement means that many current compression techniques are not directly applicable-particularly those using adaptive modelling. However, the static nature of the text and the existence of a lexicon give help that is not available in other compression scenarios. A number of different kinds of model developed for different parts of a full-text retrieval system are presented and evaluated.>

Approaches to the zero-frequency problem in adaptive text compression are discussed. This problem relates to the estimation of the likelihood of a novel event occurring. Although several methods have been used, their suitability has been on empirical evaluation rather than a well-founded model. The authors propose the application of a Poisson process model of novelty. Its ability to predict novel tokens is evaluated, and it consistently outperforms existing methods. It is applied to a practical statistical coding scheme, where a slight modification is required to avoid divergence. The result is a well-founded zero-frequency model that explains observed differences in the performance of existing methods, and offers a small improvement in the coding efficiency of text compression over the best method previously known.>

Abstract Hashing is so commonly used in computing that one might expect hash functions to be well understood, and that choosing a suitable function should not be difficult. The results of investigations into the performance of some widely used hashing algorithms are presented and it is shown that some of these algorithms are far from optimal. Recommendations are made for choosing a hashing algorithm and measuring its performance.

An OPM/L data compression scheme suggested by Ziv and Lempel, LZ77, is applied to text compression. A slightly modified version suggested by Storer and Szymanski, LZSS, is found to achieve compression ratios as good as most existing schemes for a wide range of texts. LZSS decoding is very fast, and comparatively little memory is required for encoding and decoding. Although the time complexity of LZ77 and LZSS encoding isO(M)for a text ofMcharacters, straightforward implementations are very slow. The time consuming step of these algorithms is a search for the longest string match. Here a binary search tree is used to find the longest string match, and experiments show that this results in a dramatic increase in encoding speed. The binary tree algorithm can be used to speed up other OPM/L schemes, and other applications where a longest string match is required. Although the LZSS scheme imposes a limit on the length of a match, the binary tree algorithm will work without any limit.