New methods for compression of MP double array by compact management of suffixes

Minimal Prefix (MP) double array is an efficient data structure for a trie. However, its space efficiency is degraded by the non-compact management of suffixes. This paper presents three methods to compress the MP double array. The first two methods compress the MP double array by accommodating short suffixes inside the leaf nodes, and pruning leaf nodes corresponding to the end marker symbol. These methods achieve size reduction of up to 20%, making insertion and deletion faster at the same time while maintaining the retrieval time of O(1). The third method eliminates empty spaces in the array that holds suffixes, and improves the maximum size reduction further by about 5% at the cost of increased insertion time. Compared to a Ternary Search Tree, the key retrieval of the compressed MP double array is 50% faster and its size is 3–5 times smaller.     

A fast retrieving algorithm of hierarchical relationships using trie structures

Case structures are useful for natural language systems, such as word selection of machine translation systems, query understanding of natural language interfaces, meaning disambiguation of sentences and context analyses and so on. The case slot is generally constrained by hierarchical concepts because they are simple knowledge representations. With growing hierarchical structures, they are deeper and the number of concepts to be corresponded to one word increases. From these reasons, it takes a lot of cost to determine whether a concept for a given word is a sub-concept for concepting the case slot or not. This paper presents a faster method to determine the hierarchical relationships by using trie structures. The worst-case time complexity of determining relationships by the presented method could be remarkably improved for the one of linear (or sequential) searching, which depends on the number of concepts in the slot. From the simulation result, it is shown that the presented algorithm is 6 to 30 times faster than linear searching, while keeping the smaller size of tries.     

Social class differences on the Boehm test of basic concepts: Are they due to bias?

One of Jensen's internal criteria for the detection of bias was applied to the standardization data for the Boehm Test of Basic Concepts (BTBC). Despite sizable social class differences in mean scores, differences in the rank orders of item difficulties were negligible. Thus, by this one criterion, there was little evidence of test bias. Instead, the findings suggest that children of different socioeconomic levels master basic concepts in about the same temporal order, differing only in the rate at which they do so.     

Construction of mathematical knowledge through whole-class discussion

A word problem that requires addition of fractions with different denominators was presented to 11 classes of 4th- or 5th-graders, 10 years of age. It had three answer alternatives: adding the denominators and numerators separately, transforming fractions into decimals before adding them, and the standard, most appropriate solution. Students in each class were required to choose an alternative themselves, state their reason for the choice, and discuss which alternative would be right. After whole-class discussion, they were asked to choose an alternative again and nominate the student who had offered the most plausible idea. Then students in six classes were informed which alternative was the most appropriate, whereas those in five classes were not. Finally, the students, irrespective of the presence/absence of feedback, were required to solve the initial problem without the alternatives as the post-test, and two new problems as the transfer test.The results showed that (a) the students could offer more or less plausible arguments for or against each alternative, which in most classes included the correct explanation; (b) both vocal and silent students could write a mathematical expression for the post-test problem and manipulated it correctly, incorporating other students' ideas presented during the discussion, with or without the teacher's feedback, though their generalization was rather limited; and (c) the students could recognize and memorize reasonable explanations offered by other students in the discussion.