Given a string over a finite alphabet, a set of minimal forbidden words (MFW) that do not appear in the string is called an antidictionary. A coding scheme used an antidictionary automaton was proposed by Crochemore in 2000. The antidictionary automaton represents the string symbol by symbol by using the antidictionary. In this article, we present an algorithm to build the antidictionary automaton for a given string. The proposed algorithm is fully based on array data structure. Computer simulation results show that the proposed algorithm has a linear time and memory complexities proportional to the length of the string and these complexities are significantly less than those of the conventional algorithm based on tree data structure.%有限アルファベット上の有限長の記号列に対して,その記号列に出現しない極小の部分記号列の集合を反辞書と呼ぶ.反辞書を用いた情報源符号化は2000年Chroshemoreらによって提案された.本稿は反辞書符号化法を実現するデータ構造を木から配列に移し替えて使用する計算量やメモリ土の削減を目的とするものである.
展开▼