Abstract Field‐association (FA) terms give us the knowledge to identify document fields using a limited set of discriminating terms. Although many earlier methods tried to extract automatically relevant FA terms to build a comprehensive dictionary, the problem lies in the lack of an effective method to extract automatically relevant FA terms to build a comprehensive dictionary. Moreover, all previous studies are based on FA terms in English and Japanese, and the extension of FA terms to other languages such as Arabic could benefit future research in the field. We present a new method to build a comprehensive Arabic dictionary using part‐of‐speech, pattern rules, and corpora in Arabic language. Experimental evaluation is carried out for various fields using 251 MB of domain‐specific corpora obtained from Arabic Wikipedia dumps and Alhayah news selected average of 2,825 FA terms (single and compound) per field. From the experimental results, recall and precision are 84% and 79%, respectively. We propose amended text classification methodology based on field association terms. Our approach is compared with Nave Bayes (NB) and kNN classifiers on 5,959 documents from Wikipedia dumps and Alhayah news. The new approach achieved a precision of 80.65% followed by NB (72.79%) and kNN (36.15%).

Abstract 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.

Full-text search is widely used for various services of the Internet. A more high-speed and a more efficient full-text search technology are necessary because of the amount of increasing handled document and corresponding document data every day. This work proposes an adaptive block management algorithm that is efficient for dynamic, data management method. This algorithm is applied for inverted file searching. The new method is speeding up character string retrieval by first making the full-text search of Uni-gram and by the full-text search of Bi-gram. This work proposes a method of enhancing the static full-text search system of Bi-gram to the dynamic full-text search system of Bi-gram. Moreover, This work presents an efficient achievement method of the dynamic full-text search system of Bi-gram using effectiveness of the adaptive block management structure.

Although there are many text classification techniques depending on vector spaces, it is difficult to detect the meaning, which are relating to the user's intension (complaint, encouragement, request, invitation, etc.). The intension discussed in This work is very useful for understanding focus points in conversation. This paper presents a method of determining the speaker's intention for sentences in conversation. The intension association expressions are introduced, and the formal rule descriptions using these expressions are defined to build intention classification knowledge. A set pattern-matching algorithm is proposed to determine the intension class efficiently. From simulation results for 5,859 conversations, the presented set pattern-matching algorithm is about 44.5 times faster than Aho and Corasick method. Precision and recall of intension classifications are 90% and 95%. Moreover, precision and recall of unnecessary sentences extraction are 96% and 97%.

Although E-mail systems are one of the most useful communication tools for business, education, etc., missing important E-mail messages becomes very serious problems. It is very useful filtering supports for users to pick up important messages or to neglect unnecessary messages. This work presents a method of determining the time priority for E-mail messages. Multiattribute rules are defined to detect complex time expressions and a set pattern-matching machine is proposed. It enables us to protect missing messages with important time information because the presented method can classify and rank them according to time priority measurement automatically. From the simulation results of determining time priority, it turned out that the presented pattern-matching method is from about 4 times faster than the traditional string pattern-matching method. From the results of filtering 5,172 sentences, it is verified that precision and recall of the presented method becomes 95% and 96%, respectively. From the experimental results of determining 10 highest messages among 100 E-mail, it is verified that filtering time by the proposed measurement is from 9.7 to 16.6 faster than that of a nonfiltering method.

Abstract A double‐array is a well‐known data structure to implement the trie. However, the space efficiency of the double‐array degrades with the number of key deletions because the double‐array keeps empty elements produced by the key deletion. This paper presents a fast and compact elimination method of empty elements using properties of the trie nodes that have no siblings. The present elimination method is implemented by C language. From simulation results for large sets of keys, the present elimination method is about 30–330 times faster than the conventional elimination method and maintains high space efficiency. Copyright © 2003 John Wiley & Sons, Ltd.

The final purpose of the authors is to achieve indicative summarization for retrieved text. The paper examines the effectiveness of a method of automatically deriving Japanese compound keywords based on rules of dependency relationship and restrictions on them. Then, an importance measure of derived keywords is discussed. The derivation method can derive more significant Japanese compound keywords that do not appear in the original text.

Speed and storage capacity are big issues in information retrieval system. For natural language analysis, a double array is one of a data structure of trie, which is a well-known approach to retrieve strings in a dictionary, and helps very fast access in a matrix table with compactness of a list form. In order to realize quite compact structure, this paper presents a compression method by dividing the trie constructed into several pieces (blocks). It enables us to reduce the number of bits representing entries of the double arrays. The trie obtained must trace to the blocks and this causes that retrieval time might be slow because of a state connection. To solve this problem, we propose a new trie construction method to compress and minimize the number of state connections. After applying to a large set of keys, experimental result shows that the storage capacity has been reduced to 50% even though the approach we present has the same retrieval speed.

In many information retrieval applications, it is necessary to be able to adopt a trie search for looking at the input character by character. As a fast and compact data structure for a trie, a double-array is presented. However, the insertion time is not faster than other dynamic retrieval methods because the double-array is a semi-static retrieval method that cannot treat high frequency updating. Further, the space efficiency of the double-array degrades with the number of deletions because it keeps empty elements produced by deletion. The paper presents two algorithms to establish the double-array as a dynamic retrieval method. From the simulation results for 100 thousand keys, it turned out that the insertion time and the space efficiency are remarkably improved.

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.

Proposes an efficient dictionary access method for morphological analysis of oriental languages by extending Aho and Corasick's (1990) pattern matching machine. The proposed method is a simple and efficient algorithm to find all possible substrings in an input sentence and during a single pass. It stores the relations of grammatical connectivity of adjacent words into the output functions. Therefore, the costs of checking connections between the adjacent words can be reduced by using the connectivity relations. Furthermore, the method of constructing the grammatical connectivity relations is described. Finally, the proposed method is verified by theoretical analysis and an experimental estimation is supported by a computer simulation with a 100,000-word dictionary. From the simulation results, it turns out that the proposed method is 49.9% faster (in CPU time) than the traditional trie approach. In addition, the number of candidates for checking connections was 25.5% less than that of the original morphological analysis.

Storing and retrieving a useful example sentence efficiently is an important task in document management systems because text retrieval is the most time-consuming part of them. Inverted filing is a well-known approach, but there are some problems when storing a huge number of sentences. They arise when the intersection is computed or large postings indexed by terms, or keywords. Moreover, disk access for postings also takes a lot of time in this situation. This paper presents a technique for the storing of multi-stages of postings and retrieving them partly in order to compute efficiently the intersection between postings for the requested terms. From the simulation results, it is shown that the presented algorithm is 3 to 19 times faster than the traditional approach.

Hierarchical classification is very comprehensive for human and a useful representation for many applications, such as selection of word translation of machine translation systems, semantic representation of natural language analysis, and so on. Especially, for the case structures, the case slot is generally restricted by hierarchical concepts. Case structures are a typical semantic representation for natural language understanding and it has semantic constraints, or roles, for noun phrases in the slot for a verb. Generally, semantic constraints are confirmed by hierarchical relationships between concepts of nouns and the input concepts. With growing hierarchical structures, the number of concepts increases and the length of numerical codes representing concepts becomes long. The frequency of determinations is very high for complex sentences. Multiple concepts correspond to one word. From these reasons, it costs a lot to determine whether a concept for a given word is a sub-concept for concepts of the case slot or not. This paper presents a fast method for determining the hierarchical relationships by introducing trie structures instead of a sequential storage of concept codes. The worst-case time complexity of the determination process by the presented method remarkably improves the one of the sequential storage, which depends on the number of concepts in the slot. The trie structures can be compressed by merging common transitions into one trie. From the simulation results, it is shown that the presented algorithm is 6 to 25 times faster than the sequential storage while keeping a smaller size of tries.

This paper proposes a method for understanding time expressions. For components of which time expressions consist, 31 concepts are defined. We provide formal representations for these concepts and proposed an algorithm to analyse the meaning of time expressions. The representation includes both conceptual and quantitative aspects. Experiments for about 2,000 time expressions extracted from actual documents show that the proposed method yields correct interpretation in about 93% of the cases.

Word relation is primitive knowledge and it is very useful for natural language processing systems. In the traditional systems, although each knowledge dictionary is constructed separately, recent natural language applications become more complex by integrating the above multi-attribute relationships. This paper presents an efficient data structure by introducing a trie that can define the linkage among leaves. The linkage enables us to share the basic words required for multi-attribute relations. Theoretical observations show that the worst-case time complexity of retrieving multi-attribute relations is a constant. From the simulation results, it is shown that the presented method is about 1/3 smaller than that of the competitive methods.

In the current natural language interface system, it is impossible to understand erroneous sentences. In order to realize the superior one, the automatic error recovery for erroneous sentences is one of the problems to be solved. The method to apply the LR parsing strategies is one of the famous approaches, however it takes many time to parse the sentence. This paper shows the method to improve the time efficiency keeping the accuracy of the traditional method.

A trie structure is frequently used for various applications, such as natural language dictionaries, database systems and compilers. However, the total number of states of a trie (and transitions between them) becomes large, so that the space cost may not be acceptable for a huge key set. In order to resolve this disadvantage, this paper presents a new scheme, called a "two-trie", that enables us to perform efficient retrievals, insertions and deletions for the key sets. The essential idea is to construct two tries for both front and rear compressions of keys, which is similar to a DAWG (directed acyclic word-graph). The approach differs from a DAWG in that the two-trie approach presented can uniquely determine information corresponding to keys while a DAWG cannot. For an efficient implementation of the two-trie, two types of data structures are introduced. Theoretical and experimental observations show that the method presented is more practical than existing ones considering the use of dynamic key sets, information storage of keys and compression of transitions.

Abstract Among the different processes that entail unification‐based grammar parsing, the unification of feature structures is by far the most expensive one in terms of execution time. Unification of the feature structures of a given sentence typically takes between 85 and 98 per cent of the total elapsed time during parsing, thus the need to develop faster unification methods. The approach presented in this paper is based on the fact that, in general, between 60 and 85 per cent of unifications attempted in a typical parse result in failure. Our claim is that the efficient treatment of such unification failures reduces unification time significantly. In this paper we present what we call a unification filter or U‐filter, that preprocesses the feature structures to be unified. If the U‐filter succeeds, unification is then skipped because the attempt to unify the involved structures would result in failure. On the other hand, when the U‐filter does not succeed it is not possible to determine at that moment whether or not the structures unify, so unification is performed. The U‐filter stops around 87 per cent of unification failures, and speeds up unification time by an average of around 29 per cent over quasi‐destructive graph unification, the fastest unification method known so far.

Abstract 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.

Abstract A new internal array structure, called a double‐array, implementing a trie structure is presented. The double‐array combines the fast access of a matrix form with the compactness of a list form. The algorithms for retrieval, insertion and deletion are introduced through examples. Although insertion is rather slow, it is still practical, and both the deletion and the retrieval time can be improved from the list form. From the comparison with the list for various large sets of keys, it is shown that the size of the double‐array can be about 17 per cent smaller than that of the list, and that the retrieval speed of the double‐array can be from 3–1 to 5–1 times faster than that of the list.

A decimal notation satisfies many simple mathematical properties and it is a useful tool in the analysis of trees. A practical method is presented that compresses the decimal codes while maintaining the fast determination of relations (e.g. ancestor, descendant, brother, etc.). A special node, called a kernel node, including many common subcodes of the other codes, is defined and a compact data structure is presented using the kernel nodes. For the case where n(m) is the number of the total (kernel) nodes, it is proved that encoding a decimal code is a constant time, that the worst-case time complexity of compressing the decimal codes is O(n+m/sup 2/), and that the size of the data structure is proportional to m. From the experimental results for some hierarchical semantic primitives for natural language processing, it is shown that the ratio m/n is extremely small, ranging from 0.047 to 0.13.>

A technique for implementing a static transition table of a string pattern matching machine which locates all occurrences of a finite number of keywords in a string is described. The approach is based on S.C. Johnson's (1975) storage and retrieval method of the transition table of a finite-state machine. By restricting the transition table of the finite-state machine to that of the string pattern-matching machine, triple arrays of Johnsons's data structure can be reduced to two arrays. The retrieval program of the reduced data structure can be speeded up by a finite straight program without loops.>

An efficient digital search algorithm that is based on an internal array structure called a double array, which combines the fast access of a matrix form with the compactness of a list form, is presented. Each arc of a digital search tree, called a DS-tree, can be computed from the double array in 0(1) time; that is to say, the worst-case time complexity for retrieving a key becomes 0(k) for the length k of that key. The double array is modified to make the size compact while maintaining fast access, and algorithms for retrieval, insertion, and deletion are presented. If the size of the double array is n+cm, where n is the number of nodes of the DS-tree, m is the number of input symbols, and c is a constant particular to each double array, then it is theoretically proved that the worst-case times of deletion and insertion are proportional to cm and cm/sup 2/, respectively, and are independent of n. Experimental results of building the double array incrementally for various sets of keys show that c has an extremely small value, ranging from 0.17 to 1.13.>

An efficient digital search algorithm is presented by introducing a new data structure, called a double-array, which combines the fast access of a matrix form with the compactness of a list form. Each transition of the search tree can be computed from the double-array in O(1) time; in other words, the worst-case time for retrieving a key becomes O(k) for the length k of that key. It is theoretically verified that each worst-case time of insertion and deletion is O(m) and O(m*e+e/sup 2/), respectively, where m is the number of redundant-state numbers in the double-array and e is the density of the transition labels. Simulation results are discussed.>

The authors describe a contextual machine translation system from Japanese documents to English skeleton expressions. In this system, an analyzer performs syntax, semantic, anaphoral, and coherent analyses to obtain a contextual representation concerning the input text. A generator produces conversationally the translation results of the skeleton, detail, and diagrammatic forms. Semantic and contextual analysers based on world knowledge are presented for the system.>

Arithmetic AN codes are useful for error correction in both arithmetic operations and digital data transmission. This paper presents a theoretical approach to a new class of nonbinary arithmetic AN codes using symmetric R-ary expressions and Lee-type arithmetic distance.

This correspondence describes an efficient string pattern matching machine to locate all occurrences of any of a finite number of keywords and phrases in an arbitrary text string. Some conditions are defined on the states of the machine in order to improve the speed and size of the machine by Aho and Corasick [1]. The pattern matching algorithm is partitioned into various cases by combining these conditions. Finally, the correspondence illustrates the proposed approach by applying it to the analysis of the machines for a simple search.

This paper presents a practical method for constructing a more compact matrix structure of the precedence information used in a new weak precedence parsing. The parsing algorithm differs from the conventional weak precedence algorithm in that the precedence relation .> signals a sequence of reduce actions, not just one. The method can be used for any weak precedence grammars without degrading the good error detection capability of the traditional weak precedence parsers. It is shown by the empirical results that the obtained matrices are the very reasonable size and that the presented parsing algorithm is very efficient.