An efficient deletion method for a minimal prefix double array

A minimal prefix (MP) double array is an efficient data structure for a trie. The MP double array only requires a small amount of space and enables fast retrieval. However, the space efficiency of the MP double array is degraded by deletion. This paper presents a fast and compact adaptive deletion method for the MP double array. The presented method is implemented with C. Simulation results for English and Japanese keys show that the adaptive method is faster than the conventional method and maintains higher space efficiency. Copyright © 2006 John Wiley & Sons, Ltd.     

An Efficient Trie Construction for Natural Language Dictionaries

A trie structure is frequently used for various applications, such as natural language dictionaries, database systems and compilers. However, the total number of nodes of the trie becomes large and it takes a lot of spaces for a huge set of keys. The space cost becomes a serious problem if long strings, or compound words, are stored in the trie. In order to resolve this disadvantage, this paper presents a compression method for these long strings by using trie arc for single words. The concept of the compression scheme to be presented is to replace long strings into the corresponding leaf node numbers of the trie. The double array structure is introduced because a fast backward tracing of the trie is required in this approach. The theoretical and experimental observations show that the method presented is more practical than existing ones.     

Fast insertion methods of a double‐array structure

A double‐array is a compact and fast data structure for a trie, but it degrades the speed of insertion for a large set of keys. In this paper, two kinds of methods for improving insertion are presented. The basic functions for retrieval, insertion and deletion are implemented in the C language. Comparing with the original double‐array for large sets of keys, the improved double‐array is about six to 320 times faster than that for insertion. Copyright © 2001 John Wiley & Sons, Ltd.     

Fast construction of space‐optimized recursive automaton

Finite‐state automata are important components in information retrieval and natural language processing software. A recursive automaton is the most compact representation of the acyclic deterministic finite‐state automata. It is based on merging not only the equivalent states but also the identical substructures in an automaton. The LZ trie variant is the state‐of‐the‐art in automata compression regarding space, but the time needed for its construction was, until now, quadratic, which has made it impractical for large inputs. In this paper, we present the first algorithm for LZ trie construction that runs in effectively linear time thereby making it an attractive choice for finite‐state automata implementation. We achieve this goal by adding a new functionality to the enhanced suffix array data structure. We present two variants of the construction procedure – an optimal method regarding the final size and a method that sacrifices some compression for low intermediate memory usage. We have made the implementation of our algorithms available in an open source software package LzLex.Copyright © 2014 John Wiley & Sons, Ltd.     

A new compression method of double array for compact dictionaries

Speed and storage capacity are very important issues in information retrieval system. In natural language analysis, double array is a well-known data structure to implement the trie, which is a widely used approach to retrieve strings in a dictionary. Moreover, double array helps for fast access in a matrix table with compactness of a list form. In order to realize quite compact structure for information retrieval, this paper presents a compression method by dividing the trie constructed into several pieces (pages). This compression method enables us to reduce the number of bits representing entries of the double array. The obtained trie must trace to the pages that cause slow retrieval time, because of a state connection. To solve this problem, this paper proposes a new trie construction method to compress and minimize the number of state connections. Experimental results applying for a large set of keys show that the storage capacity has been reduced to 50%. Moreover, our new approach has the same retrieval speed as the old one.     

A method of compressing trie structures

A trie structure can immediately determine whether a desired key is in a given key set or not, and can find its longest match easily. Thanks to these attractive properties, a trie structure is frequently used for various fields, such as natural language dictionaries, database systems and compilers. However, the total number of states of a trie becomes large, so space requirements are not good for a huge key set. To resolve this disadvantage a new structure which reduces the total number of states in a traditional trie, called a double-trie, is introduced in this paper. Insertion and deletion operations, as well as key retrieval for this double-trie, are presented. The efficiency of this method is shown by the results of simulations for various key sets.     

Practical rearrangement methods for dynamic double‐array dictionaries

Double‐array structures have been widely used to implement dictionaries with string keys. Although the space efficiency of dynamic double‐array dictionaries tends to decrease with key updates, we can still maintain high efficiency using existing methods. However, these methods have practical problems of time and functionality. This paper presents several efficient rearrangement methods to solve these problems. Through experiments using real‐world datasets, we demonstrate that the proposed rearrangement methods are much more practical than existing methods.     

Response‐correction‐based fault detection in small linear microstrip patch arrays using magnitude‐only far‐field pattern samples

We present a computationally efficient method for detecting faulty elements in a small linear microstrip patch array from samples of the array's far‐field magnitude radiation pattern (here represented by realistic EM simulations). Regardless of the array size, our method requires only one expensive full‐wave entire‐array simulation—compared to, e.g., the 696 required by the previous best method (Patnaik et al., IEEE Trans Antennas Propag 55 (2007), 775–777) for a 16‐element array. This one simulation gives the accurate far‐field magnitude pattern of the original defect‐free array, and is used in conjunction with the defect‐free array's analytical array factor to formulate a response correction function, which can then be used to construct an accurate approximation of the EM‐simulated pattern of any arbitrary faulty array at very low cost. The low cost and high accuracy of these approximations make possible an enumeration strategy for identifying the faulty elements, which would have been computationally prohibitive were EM‐simulated patterns to be used. Our method was robust in handling arrays of double the size considered in Patnaik et al., IEEE Trans Antennas Propag 55 (2007), 775–777, while expanding on (Patnaik et al., IEEE Trans Antennas Propag 55 (2007), 775–777) by also addressing partial faults and measurement noise. Accuracies in detecting up to three faults (including partial ones) in arrays of 16 and 32 elements exceeded 97% under noise‐free conditions, and were above 93% in the presence of 2 dB measurement noise. © 2016 Wiley Periodicals, Inc. Int J RF and Microwave CAE 26:683–689, 2016.     

Performance of a circular crossed‐dipole array for SDMA configuration adopting directivity and polarization control using particle swarm optimization algorithm

In this article, the performance of a circular crossed‐dipole array (CCDA) for space division multiple access (SDMA) configurations adopting directivity and polarization control is presented. The array consists of 12 dual‐polarized elements uniformly distributed in a circular configuration; each dual‐polarized element (crossed‐dipole) consists of two half‐wave dipoles in a ±45° slant configuration. The modified particle swarm optimization and moment of method (MPSO‐MOM) algorithm is used to calculate the complex weightings of the array elements in a mutual coupling environment for beamforming synthesis. In addition, the performance of the adaptive array using discrete feedings (1‐bit amplitude and 4‐bit phase shifters or only 4‐bit phase shifters) is studied. © 2008 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2009.     

一种基于决策信息系统的知识约简算法

差别矩阵方法作为求解粗糙集知识约简的关键技术之一,而差别矩阵中的元素个数将直接影响知识约简算法的计算效率,针对现有基于差别矩阵方法的知识约简算法的不足,并且当决策信息系统中样本量较大、决策类别数较少时,算法构造的差别矩阵中将存在大量空值元素。提出了一种新的差别矩阵构造方法,有效地剔除了差别矩阵中的空值元素,在此基础上,设计了一种决策信息系统的知识约简算法,由于算法能有效地利用核属性,进一步缩小了知识约简算法的效率,并通过算例分析说明了算法的可行性。     

Engineering scalable, cache and space efficient tries for strings

Storing and retrieving strings in main memory is a fundamental problem in computer science. The efficiency of string data structures used for this task is of paramount importance for applications such as in-memory databases, text-based search engines and dictionaries. The burst trie is a leading choice for such tasks, as it can provide fast sorted access to strings. The burst trie, however, uses linked lists as substructures which can result in poor use of CPU cache and main memory. Previous research addressed this issue by replacing linked lists with dynamic arrays forming a cache-conscious array burst trie. Though faster, this variant can incur high instruction costs which can hinder its efficiency. Thus, engineering a fast, compact, and scalable trie for strings remains an open problem. In this paper, we introduce a novel and practical solution that carefully combines a trie with a hash table, creating a variant of burst trie called HAT-trie. We provide a thorough experimental analysis which demonstrates that for large set of strings and on alternative computing architectures, the HAT-trie—and two novel variants engineered to achieve further space-efficiency—is currently the leading in-memory trie-based data structure offering rapid, compact, and scalable storage and retrieval of variable-length strings.     

Efficient implementation of Aho–Corasick pattern matching automata using Unicode

We study different efficient implementations of an Aho–Corasick pattern matching automaton when searching for patterns in Unicode text. Much of the previous research has been based on the assumption of a relatively small alphabet, for example the 7‐bit ASCII. Our aim is to examine the differences in performance arising from the use of a large alphabet, such as Unicode that is widely used today. The main concern is the representation of the transition function of the pattern matching automaton. We examine and compare array, linked list, hashing, balanced tree, perfect hashing, hybrid, triple‐array, and double‐array representations. For perfect hashing, we present an algorithm that constructs the hash tables in expected linear time and linear space. We implement the Aho–Corasick automaton in Java using the different transition function representations, and we evaluate their performance. Triple‐array and double‐array performed best in our experiments, with perfect hashing, hashing, and balanced tree coming next. We discovered that the array implementation has a slow preprocessing time when using the Unicode alphabet. It seems that the use of a large alphabet can slow down the preprocessing time of the automaton considerably depending on the transition function representation used. Copyright © 2006 John Wiley & Sons, Ltd.     

基于双十字链表存储的共享资源矩阵方法特性研究

针对共享资源矩阵法在系统隐蔽通道检测过程中存在的算法时间复杂度高的问题,提出了一种基于双十字链表存储的改进算法。首先,针对共享资源矩阵方法中的核心操作——传递闭包操作,将传统的数组存储改进为双十字链表存储;其次,针对共享资源矩阵方法建立了概率模型;最后,在该概率模型下,分析了改进算法的时间复杂度和共享资源矩阵方法的特性。理论分析和实验仿真表明:当共享资源矩阵为稀疏矩阵时,采用基于双十字链表存储的改进算法能够使共享资源矩阵法的时间效率相比传统的数组存储提高67%;当共享资源矩阵的规模较大时,传递闭包操作会使得共享资源矩阵中的元素快速填充,从而导致基于双十字链表存储改进算法相比传统数组存储的时间效率优势下降,并在概率模型下通过理论推导验证了传递闭包操作的这一特性。     

Simple compact tree storage of a multidimensional array

Algorithms are described for storing and retrieving an array having a large and variable number of indices, each of which takes on values which are usually small integers, but whose maximum size is unknown. Such arrays are extremely common in physical problems, where the indices may be quantum numbers (describing the electrons in a many-electron atom, for example) or point separations on a lattice (as in the case of lattice Green functions). Usual methods for storing such arrays are very wasteful of space, and the resulting large memory requirements are often the limiting factor in the quality of physical calculations. The “trie” structure described here is conservative of memory. We have written a set of FORTRAN subroutines which allow a user to store and retrieve array elements efficiently without a detailed understanding of the tree structure; these are described in an accompanying write-up.     

Broadband planar dipole array Antenna with double C‐shaped slit elements for digital TV broadcasting transmission

This research has proposed a planar rectangular dipole antenna enclosed in double C‐shaped parasitically slit elements (i.e., radiator element) on a double‐cornered reflector for bandwidth enhancement. In the study, simulations were first carried out to determine the optimal parameters of the radiator element and then a radiator element prototype was fabricated and mounted onto a double‐cornered aluminum reflector. The simulated and measured |S₁₁|<–10 dB of the antenna element covered the frequency ranges of 451–901 MHz (66.6%) and 455–886 MHz (64.3%), respectively. The gain was enhanced by the subsequent deployment of multiple radiator elements to fabricate a four‐element vertically array antenna on an elongated double‐cornered reflector. The simulated and measured |S₁₁|20 and 相似文献   

Untilted slot array antenna at the narrow wall of the waveguide using double‐ridge

In this article a novel array antenna composed of untilted slots in the narrow wall of the double‐ridge waveguide, with significantly improved cross‐polarization, is presented. In the first step, suitable radiating elements for designing a linear slot array antenna were created. An untilted slot which is created the narrow wall of the double‐ridge waveguide is suggested to be used as the radiating resonance slot. The concave and convex ridges are located under the untilted slots only. It is shown that the concave and convex double ridge waveguides can produce an orthogonal current distribution in the place of the slots. They are also placed successively to produce the required phase inversion between adjacent slots. The linear array consists of nine uniform resonant untilted slots in the double ridge waveguide and is designed at the frequency of 5 GHz using the normalized conductance of each radiating slot. Analyzing the simulation results shows that cross‐polarization of the designed array was significantly improved, it was also found that the cross‐polarization and the SLL were respectively about ?65 and ?16 dB. © 2010 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2010.     

Incremental Polygon Rendering on a SIMD Processor Array

We demonstrate how both area coherence and parallelism can be exploited in order to speed up rendering operations on a SIMD square array of processors. Our algorithms take advantage of the method of differences, in order to incrementally compute the values of a linear polynomial function at discrete intervals and thus implement area rendering operations efficiently. We discuss how filling of convex polygons, hidden surface elimination and smooth shading can be implemented on an N × N processor array that supports planar arithmetic, that is, arithmetic operations performed on N × N matrices in parallel for all matrix elements. A major attraction of the method we present is that it is based on a SIMD processor array; such machines are now recognised as highly general purpose given the wide range of applications successfully implemented on them.     

Safe,multiphase bounds check elimination in Java

As part of its type‐safety regime, Java's semantics require precise exceptions at runtime when programs attempt out‐of‐bound array accesses. This paper describes a Java implementation that utilizes a multiphase approach to identifying safe array accesses. This approach reduces runtime overhead by spreading the out‐of‐bounds checking effort across multiple phases of compilation and execution: production of mobile code from source code, just‐in‐time (JIT) compilation in the virtual machine, application method invocations, and the execution of individual array accesses. The code producer uses multiple passes (including common subexpression elimination, load elimination, induction variable substitution, speculation of dynamically verified invariants, and inequality constraint analysis) to identify unnecessary bounds checks and prove their redundancy. During class‐loading and JIT compilation, the virtual machine verifies the proofs, inserts code to dynamically validate speculated invariants, and generates code specialized under the assumption that the speculated invariants hold. During each runtime method invocation, the method parameters and other inputs are checked against the speculated invariants, and execution reverts to unoptimized code if the speculated invariants do not hold. The combined effect of the multiple phases is to shift the effort associated with bounds‐checking array access to phases that are executed earlier and less frequently, thus, reducing runtime overhead. Experimental results show that this approach is able to eliminate more bounds checks than prior approaches with minimal overhead during JIT compilation. These results also show the contribution of each of the passes to the overall elimination. Furthermore, this approach increased the speed at which the benchmarks executed by up to 16%. Copyright © 2010 John Wiley & Sons, Ltd.     

Multi‐layer Depth Peeling by Single‐Pass Rasterisation for Faster Isosurface Raytracing on GPUs

Empty‐space skipping is an essential acceleration technique for volume rendering. Image‐order empty‐space skipping is not well suited to GPU implementation, since it must perform checks on, essentially, a per‐sample basis, as in kd‐tree traversal, which can lead to a great deal of divergent branching at runtime, which is very expensive in a modern GPU pipeline. In contrast, object‐order empty‐space skipping is extremely fast on a GPU and has negligible overheads compared with approaches without empty‐space skipping, since it employs the hardware unit for rasterisation. However, previous object‐order algorithms have been able to skip only exterior empty space and not the interior empty space that lies inside or between volume objects. In this paper, we address these issues by proposing a multi‐layer depth‐peeling approach that can obtain all of the depth layers of the tight‐fitting bounding geometry of the isosurface by a single rasterising pass. The maximum count of layers peeled by our approach can be up to thousands, while maintaining 32‐bit float‐point accuracy, which was not possible previously. By raytracing only the valid ray segments between each consecutive pair of depth layers, we can skip both the interior and exterior empty space efficiently. In comparisons with 3 state‐of‐the‐art GPU isosurface rendering algorithms, this technique achieved much faster rendering across a variety of data sets.     

A new hierarchical packet classification algorithm

Packet classification is one of the most challenging functions in Internet routers since it involves a multi-dimensional search that should be performed at wire-speed. Hierarchical packet classification is an effective solution which reduces the search space significantly whenever a field search is completed. However, the hierarchical approach using binary tries has two intrinsic problems: back-tracking and empty internal nodes. To avoid back-tracking, the hierarchical set-pruning trie applies rule copy, and the grid-of-tries uses pre-computed switch pointers. However, none of the known hierarchical algorithms simultaneously avoids empty internal nodes and back-tracking. This paper describes various packet classification algorithms and proposes a new efficient packet classification algorithm using the hierarchical approach. In the proposed algorithm, a hierarchical binary search tree, which does not involve empty internal nodes, is constructed for the pruned set of rules. Hence, both back-tracking and empty internal nodes are avoided in the proposed algorithm. Two refinement techniques are also proposed; one for reducing the rule copy caused by the set-pruning and the other for avoiding rule copy. Simulation results show that the proposed algorithm provides an improvement in search performance without increasing the memory requirement compared with other existing hierarchical algorithms.