望月 久稔

LR 構文解析は，C 言語や Pascal などのプログラミング言語，SQL などの問合せ言語，XML パーサ，プロトコルパーサなどの様々な場面で利用されており，時間的，領域的に効率的な LR 構文解析表の実現が求められる．本論文では，ダブル配列の遷移を拡張して LR 構文解析表を実現し，解析時の状態遷移に要する計算量を抑制することで，LR 構文解析に要する時間を短縮する手法を提案する．実験の結果，提案手法は構文解析器生成系の一種である Bison と比較して LR 構文解析に要する時間を 10～23% 削減した．LR parsers are used widely, such as programing language compilers, SQL parsers, XML parsers, and protocol parsers. So it is important to implement efficient LR parsing tables. In this paper, we present an efficient implementation of LR parsing table with Double-Array that is extended transition function. Our experiment show that proposal method can decrease the parsing time about 10～23% in comparison with parser generator Bison.

自然言語処理における辞書構造として，トライ法が広く用いられているが，日本語のように分かち書きされていない言語のテキストからキーワードを検出するためには，解析対象となるテキストのあらゆる位置から探索する必要がある．より高速に形態素解析を行うため，複数のキーワードをテキストから線形時間で検出する AC 法を用いる手法が提案されているが，AC 法はトライ法よりも使用する記憶領域が大きい．本論文では，AC マシンにおける遷移のうち，多分岐の節点における遷移をダブル配列に，1 方向分岐の節点における遷移をダブル配列と異なる配列にそれぞれ定義することで，照合時に必要な記憶領域を抑制し，高速性とコンパクト性をあわせ持つ AC マシンを実現する手法を提案する．日本語形態素 40 万語を登録した実験で，提案手法はトライを用いた辞書システム Darts とほぼ同等の記憶領域で対象テキストを 60～87% の時間で照合した．Trie structure is used widely, such as dictionary for natural language processing. However, it is not so effective using a trie structure for the morphological analysis of languages without explicit word boundaries like Japanese because we have to perform dictionary lookup for all possible substrings of the text. This paper proposes an efficient dictionary structure that is Aho-Corasick Machine using Double-array defining multi-way branch and different arrays defining oneway branch. Our experiments show that the matching time of the proposal machine decreased to about 60%-87% against other structures.

An extendible hashing scheme resolves bucket overflows by reorganizing the hash function and file structure locally, so it is very suitable for fast key retrievals of dynamic key sets. However, it cannot search keys that contain a given string as substrings efficiently. In this paper, in order to design this substring search in extendible hashing, sig nature vectors are introduced as hash values, and a trie structure as an extendible hash table, where each vector is composed by a bit stream. Pseudo signature vectors are defined to identify the buckets, and a constrained depth-fir st search is presented to traverse the arcs of the trie structure. To construct a compact trie despite an increase in the number of keys, uniform signature treetops are introduced, and the method for an incremental expansion of the hash table is proposed. This approach can restrict the size of the bit stream for each key, making constrained depth-first search efficient. From simulation results, by applying the presented schemes to Japanese and English key sets, it was shown that the number of accessed buckets decreased from 40% to 10% in comparison with traditional extendible hashing for which only descriptors were used. In addition, the search time cost of the presented approach is 2-10 times faster. (C) 1998 Elsevier Science Inc. All rights reserved.

In accordance with the diffusion of applications, such as the Desk Top Publishing system, the Document Formatting system and the Document Editing system, it is easy to make a document by using a computer. However, as for allocating the diagrams(figures and tables), there are few document processing systems able to allocate diagrams on the appropriate places automatically. In a document processing system it is a very important issue to allocate diagrams on the most suitable places. This paper defines the criteria for allocating diagrams on the suitable positions by investigating published papers. These criteria concern 1) the order of diagrams to be allocated, 2) the stability of the diagram allocations, 3) the distance between the diagram and the location of the corresponding first reference in the text, 4) the allocation balance of diagrams in a text, 5) the restricted areas where diagrams shouldn't be allocated, 6) the allocation priorities between diagrams of different width. Moreover, this paper proposes a method for deciding the diagram allocations satisfying the above criteria automatically and fast on document formatting systems. In this case we have limited its application to one type of documents, which is papers. Especially, this method can skillfully allocate diagrams of different width on the page by reallocating the diagrams and texts within it, and can allocate diagrams over the document uniformly. But, this method doesn't have to reallocate diagrams, which have been already allocated, beyond the page. From the experimental results using various published papers (50 papers including 556 diagrams), 94.7 percent of the diagrams in these published papers satisfy the criteria defined in this paper, and so we confirmed the validity of the criteria. And, it has been shown that, by using this method, 99.8 percent of the diagrams satisfy the criteria. Furthermore, it has been shown that 82 percent of diagrams are allocated on the same place and 98 percent on the same page of the published paper. As for the execution time of the proposed method, it takes less than 1 second.

This paper presents a new method of LR parsing based oil the distinction of stack states and non-stack stales. Non-slack states are states which do not need to be pushed into the LR parsing stack. and slack stales are stales to be pushed into it. By using some properties based oil the stack-controlling LR parser defined here, the parsing speed and tile size of parsing tables call remarkably improved and tile improvement includes tile traditional method eliminating unit productions. By empirical observations for variety of programming languages, the efficiency is verified. Extending it to tile generalized LR parsers for natural language is also discussed.

In many applications, information retrieval is a very important research field in several key strategies, the binary trie is famous as a fast access method to be able to retrieve keys in order. However, if the binary trie is implemented, the greater the number of the registered keys, the larger storage in secondary memory is required In order to solve this problem, Jonge et al. proposed the method to change the binary trie into a compact bit stream (called the pre-order bit stream). However, searching and updating a key takes a lot of time in large key sets. This paper proposes an efficient binary digital search algorithm by introducing a new hierarchical structure. The algorithms for retrieval, insertion and deletion of keys using this new method are introduced through examples. The theoretical and experimental results, using 50,000 Japanese nouns and 50,000 English words, show that this method provides faster access than the traditional method. Retrieval is 18 similar to 20 times, the insertion is 11 similar to 13 times aid the deletion is 4 similar to 6 times faster.

A trie structure is frequently used for various applications, such as natural language dictionaries, database systems and compilers. However, the total number of states (and transitions between them) of a trie becomes large so that space cost may not be acceptable for a huge key set. In order to resolve this disadvantage, this paper presents a new scheme, called ''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 determine uniquely information corresponding to keys while a DAWG cannot. For an efficient implementation of the two-trie, two types of data structures are introduced. The theoretical and experimental observations show that the method presented is more practical than existing ones considering the use of dynamic key sets, storing information of keys and compression of transitions.

The selection of an appropriate key search algorithm for a specific application field is an important issue in application systems development. This is because data retrieval is the most time-consuming part of many application programs. An automatic selection method for key search algorithms is presented in this paper. The methodology has been implemented in a system called KESE2 (KEy-SEarch ALgorithm SElection). Key search algorithms are selected according to the user's requirements through interaction with KESE2 which bases its inferences on an evaluation table. This evaluation table contains values rating the performance of each key search algorithm for the different searching properties, or characteristics. The selection algorithm presented is based on step by step reduction of unsuitable key search algorithms and searching properties. The paper also proposes assistance facilities that consist of both a support function and a program synthesis function. Experimental results show that the appropriate key search algorithms are effectively selected, and that the necessary number of questions asked, to select the appropriate algorithm, is reduced to less than half of the total number of possible questions. The support function is useful for the user during the selection process and the program synthesis function fully translates a selected key search algorithm into high level language in an average of less than 1 hour.

An efficient algorithm for deciding on the allocation of diagram (DAD) on automatic document layout is described. The document style is the double column setting with two columns in each page. The conditions that the allocation of the diagrams need to satisfy are highlighted. As future improvement, the allocation method for the diagram of halfway size, which is between the single and the double column diagram, should be designed.