| 講演抄録／キーワード |
| 講演名 |
2005-07-22 10:50
Suffix Treeを用いた反辞書の生成法について
○太田隆博（長野県工科短大）・森田啓義（電通大） |
| 抄録 |
（和） |
バイナリ系列に対する反辞書の構築については，suffix trieと呼ばれるデータ構造を用いた手法が提案されている．この手法は，suffix trie上の全てのノードに対して探索を行う手法であるために，入力系列長の2乗に比例した計算量を必要とする問題点がある．
本報告では，反辞書に登録される記号列の性質を用いて，suffix treeを利用した線形計算量で反辞書の構築が可能な手法を提案する． |
| （英） |
An antidictionary is a set of shortest words that never appear in a binary string. To construct the antidictionary for a given string, a method used suffix trie has been known. But the complexity of the method is quadratic in both of time and space.
In this article, we present an algorithm to construct antidictionary of a given string, based on suffix tree representation of the string. The proposed algorithm needs linear computational time and space with respect to the sequence length. |
| キーワード |
（和） |
反辞書 / 最小禁止句 / 接尾辞木 / 線形 / 計算量 / / / |
| （英） |
antidictionary / minimal forbidden word / suffix tree / linear / computational complexity / / / |
| 文献情報 |
信学技報, vol. 105, no. 191, IT2005-43, pp. 9-14, 2005年7月. |
| 資料番号 |
IT2005-43 |
| 発行日 |
2005-07-15 (IT) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|