反辞書の
効率的な構築手法に 関する研究
Study on Efficient Algorithms for Construction of an Antidictionary.
深江 裕忠
電気通信大学大学院 情報システム学研究科
博士（工学）の学位申請論文
2014 年 3 月
反辞書の
効率的な構築手法に 関する研究
Study on Efficient Algorithms for Construction of an Antidictionary.
博 士 論 文 審 査 委 員 会 審 査 主 査： 森 田 啓 義 教 授 審 査 委 員： 長 岡 浩 司 教 授 審 査 委 員： 笠 井 裕 之 准 教 授 審 査 委 員： 古 賀 久 志 准 教 授 審 査 委 員： 多 田 好 克 教 授
著 作 権 所 有 者：深 江 裕 忠, 2014
Abstract
An antidictionary is a data structure to represent minimal forbidden words which never appear on a given string but its proper substrings do appear on it.
Since Crochemore et al. originally introduced an antidictionary for a lossless data compression in 2000, it has been widely applied as a useful tool to many applications, data compression of ECG, frame-synchronization, branch prediction, and so on.
Although a na¨ıve method for constructing an antidictionary takes time and mem- ory complexity which is a quadratic proportional to length of a string, some algo- rithms with linear time and memory complexity for construction of an antidictionary have been proposed so far.
However, in spite of their liner complexity, those conventional algorithms con- sume a huge amount of computational time and space resources to construct an antidictionary in practical applications.
In this thesis, we discuss efficient algorithms to construct an antidictionary.
First we propose an off-line algorithm by using two array structures, that is, suffix array and L-array. A suffix array is a sorted list of the suffixes of a given string while an L-array is a list of length of the longest common prefix between adjacent pairs of suffixes on the suffix array.
Computer simulation shows that time and space complexities of the proposed algorithm are about 1/20 and 1/2.5 lower than a conventional linear construction algorithm, respectively.
Next, we consider a problem how to construct dynamically an antidictionary au- tomaton which accepts minimum forbidden words of a given string.
Each time a new symbol of the string is entered into the system, we update the antidictionary automaton to fit the intermediate input data. By identifying which minimum forbidden word is deleted from or added to the current automaton, we obtain an on-line algorithm to construct an antidictionary automaton of a given string.
概要
情 報 技 術 の 発 展 に よ り，近 年 で は 様々な 機 器 に セ ン サ ー が 搭 載 さ れ ，セ ン サーで検知したデータに従って動作する機器が多くなってきた．センサーは，
温度，振動，超音波，電波など様々なものがあるが，取得するデータは数値の 系 列 で あ る ．こ の 数 値 の 系 列（ 入 力 系 列 ）に 対 し て ，検 出 や 解 析 を 行 う た め に ，入 力 系 列 に 出 現 す る 全 て の 部 分 系 列 を 登 録 し た デ ー タ ベ ー ス(こ こ で は 辞 書 と 呼 ぶ)が よ く 使 わ れ る ．
本論文で研究対象にしている反辞書とは，従来の一般的な辞書とは異なり，
入 力 系 列 に 出 現 し な い 系 列（ 極 小 禁 止 語 ）を 登 録 す る 辞 書 で あ る ．極 小 禁 止 語 と は ，そ れ 自 身 は 入 力 系 列 に 出 現 し な い が ，極 小 禁 止 語 の 真 の 部 分 系 列 は 全 て 入 力 系 列 に 出 現 す る 系 列 で あ る ．す な わ ち ，入力 系 列 に 出 現 し な い 系 列 の 中 で 極 小 性 を も つ ．反 辞 書 は ，全 て の 部 分 系 列 を 登 録 す る 辞 書 よ り も ，登 録 す る 系 列 が 少 な い と い う 性 質 を も つ ．また ，反 辞 書 を 構 成 す る デ ー タ 構 造 と し て ，極 小 禁 止 語 を 受 理 す る オ ー ト マ ト ン や ，接尾 辞 木 を 拡 張 し て 極 小 禁 止 語 の ノ ー ド を 追 加 す る な ど 効 率 的 な 検 索 方 法 が 提 案 さ れ て い る ．
反辞書は，Crochemoreらが2000年に提案した無歪みデータ圧縮法に初めて 用 い ら れ ，符号 化 で 使 用 さ れ る 確 率 モ デ ル の 作 成 に お い て ，そ の 有 効 性 が 示 さ れ た ．デ ー タ 圧 縮 以 外 に も ，反 辞 書 は ，分 岐 予 測 ，同 期 符 号 ，不 整 脈 検 出 な ど へ 応 用 さ れ て い る ．
し か し ，反 辞 書 を 構 築 す る に は ，計 算 量 が 入 力 系 列 長 に 比 例 す る こ と が 知 られているが，実用上は，膨大な記憶量と計算時間を必要とする．例えば，太 田・森田によって提案された接尾辞木を用いた反辞書構築手法では，アルファ ベットサイズが多値の場合，記憶量が膨大になる．計算機実験では，アルファ ベット サ イ ズ が256の 場 合 ，入 力 系 列 長 の 約1万 倍 の 記 憶 量 を 必 要 と し た ．
そ こ で ，本 論 文 で は ，記 憶 量 と 計 算 時 間 を 改 善 す る 新 し い 反 辞 書 構 築 手 法 を 二 つ 提 案 す る ．
一 つ 目 は ，入 力 系 列 を 全 て 入 力 後 に 反 辞 書 を 構 築 す る 静 的 な 手 法 で あ る ． 二 つ 目 は ，入力 系 列 を 逐 次 的 に 読 み 込 み な が ら ，反辞 書 を 変 化 さ せ て い く 動 的 な 手 法 で あ る ．構 築 手 法 を 考 え る 場 合 ，一 般 的 に は ，動 的 な 手 法 よ り も 静
的な手法の方が簡単である．そこで，最初に静的な手法について検討を行い，
そ の 成 果 を 動 的 な 手 法 へ 活 用 す る ．
静 的 な 手 法 で は ，新 し い 反 辞 書 の 別 表 現 を 提 案 す る ．こ の 別 表 現 で は ，極 小 禁 止 語 を ，先 頭 記 号 と 後 続 す る 系 列 に 分 け て 考 え る こ と に よ り，あ と1記 号先頭に加えることで極小禁止語になる系列が，入力系列の接尾辞配列なら び に 高 さ 配 列（ 本 論 文 で はL配 列 と 呼 ぶ ）に よって 特 徴 づ け ら れ る こ と ，す な わ ち ，先 頭 に １ 記 号 加 え れ ば 極 小 禁 止 語 に な る 系 列 は ，接尾 辞 配 列 上 の 接 尾 辞 の 先 頭 部 分 に 存 在 し ，そ の 長 さ はL配 列 で 求 め る こ と が で き る こ と を 示 す．こ こ でL配 列 と は ，接 尾 辞 配 列 上 で 隣 接 し た 二 つ の 接 尾 辞 に 共 通 す る 最 長 接 頭 辞 の 長 さ の 配 列 で あ る ．
さ ら に ，本 論 文 で は ，被 覆 集 合 を 提 案 す る ．被 覆 集 合 と は ，入 力 系 列 の 任 意の部分系列が，接尾辞配列上の接尾辞の先頭部分に存在している範囲を表 現する集合である．接尾辞配列上の接尾辞は辞書式順序昇順で整列している の で ，被覆 集 合 の 範 囲 を 比 較 す る こ と で ，入 力 系 列 の 部 分 系 列 同 士 の 辞 書 式 順 序 昇 順 の 大 小 関 係 を 判 別 で き る ．す な わ ち ，こ の2つ の 系 列 の 先 頭 か ら 順 に 記 号 を 比 較 す る 必 要 が な く，定 数 時 間 で 系 列 の 比 較 が 行 え る よ う に な る ． こ の 反 辞 書 の 別 表 現 と 被 覆 集 合 を 用 い る こ と で ，接 尾 辞 配 列 ，L配 列 を そ れ ぞ れ3回 走 査 す る だ け で ，先 頭 に １ 記 号 加 え れ ば 極 小 禁 止 語 に な る 系 列 を す べ て 含 む 高々2n+2個（nは 入 力 系 列 長 ）の 系 列 を 辞 書 式 順 序 昇 順 で 求 め ら れ る 算 法 を 提 案 す る ．提 案 方 法 に お い て は ，極 小 禁 止 語 は ，利 用 し た 被 覆 集 合 の 範 囲 を そ の ま ま 活 用 し て ，被 覆 集 合 の 範 囲 と 系 列 長 ，そ し て ，先 頭 に 加 え る 記 号 を 要 素 に 持 つ 配 列 で 表 現 さ れ る ．本 論 文 で は ，こ の 極 小 禁 止 語 の 配 列 表 現 を 反 辞 書 配 列 と 呼 ん で い る ．
そ し て ，計 算 機 実 験 に よって 提 案 し た 算 法 の 有 効 性 を 確 か め た と こ ろ ，接 尾辞木を用いた従来手法と比較して，計算時間が約20分の1，記憶量が約2.5 分 の1に 改 善 さ れ る こ と が 分 かった ．
動 的 な 手 法 で は ，反 辞 書 そ の も の で は な く，反 辞 書 オ ー ト マ ト ン ，す な わ ち ，反 辞 書 に 含 ま れ る 極 小 禁 止 語 を 受 理 す る オ ー ト マ ト ン を ，入力 系 列 を 逐 次 的 に 読 み 込 み な が ら 動 的 に 構 築 す る 手 法 を 提 案 す る ．
ま ず，す で に 読 み 込 ま れ た 入 力 系 列 の 末 尾 に 新 た な 記 号 が 加 わ る こ と に よ り，反 辞 書 が ど の よ う に 更 新 さ れ る か を 明 ら か に し た ．申 請 者 が 修 士 論 文 で 得 た 知 見 で あ る ，反 辞 書 の 更 新 に お い て ，あ る 特 定 の 極 小 禁 止 語 が 一 つ 削 除 さ れ る こ と と ，新 た に 加 わ る 極 小 禁 止 語（ 新 規 極 小 禁 止 語 ）は ，そ の 両 端 の ど ち ら か 一 方 に 削 除 さ れ る 極 小 禁 止 語 を 含 む ，と い う 二 つ の 性 質 に 加 え ，本 論文では，新規極小禁止語の長さを削除される極小禁止語の長さで上と下か
ら 評 価 し た ．
つぎに，反辞書の別表現と同様に，あと1記号加えることで新規極小禁止語 に な る 系 列 を ，入 力 系 列 の 末 尾 か ら 探 索 す る ．さ ら に ，更 新 前 の 反 辞 書 オ ー トマトンを用いて，探索した系列を新規極小禁止語にするために加える記号 を 求 め る ．
こ れ ら の 結 果 を 用 い る こ と に よって ，反 辞 書 オ ー ト マ ト ン の 構 築 す る た め に ，従 来 の 手 法 で は ，接尾 辞 を 表 す 木 構 造 や オ ー ト マ ト ン を 経 由 し て 作 成 す る 必 要 が あった の が ，そ の 手 間 を 省 い て ，入 力 系 列 か ら 直 接 構 築 す る 手 法 を 提 案 す る ．
目 次
第1章 はじめに 12
1.1 研 究 背 景 . . . . 12
1.2 研 究 の ね ら い . . . . 13
第2章 定義とデータ構造 15 2.1 有 限 ア ル ファベット 集 合 と 系 列 . . . . 15
2.2 辞 書 . . . . 15
2.3 接 尾 辞 と 接 頭 辞 . . . . 16
2.4 極 小 禁 止 語 と 反 辞 書 . . . . 17
2.5 辞 書 式 順 序 比 較 . . . . 17
2.6 接 尾 辞 配 列 . . . . 18
2.7 共 通 接 頭 辞 の 最 大 長 . . . . 19
2.8 L配 列 . . . . 19
2.9 被 覆 集 合 . . . . 20
2.10 接 頭 記 号 と 接 尾 記 号 . . . . 21
第3章 接尾辞木を用いた反辞書構築 23 3.1 反 辞 書 構 築 の ア プ ロ ー チ . . . . 23
3.2 接 尾 辞 木 . . . . 24
3.3 suffix linkとMF–link . . . . 26
3.4 反 辞 書 の 構 築 . . . . 27
3.4.1 タ イ プIの 極 小 禁 止 語 の 追 加 . . . . 27
3.4.2 タ イ プIIの 極 小 禁 止 語 の 追 加 . . . . 28
第4章 配列を用いた静的反辞書構築の提案 30 4.1 接 尾 辞 木 を 用 い た 反 辞 書 構 築 手 法 の 記 憶 量 の 内 訳 . . . . 30
4.2 反 辞 書 の 別 表 現 . . . . 30
4.3 極 小 禁 止 語 の 先 頭 文 字 を 削 除 し た 系 列 . . . . 31
4.4 提 案 手 法 の 概 要 . . . . 34
4.5 系 列 の 表 現 . . . . 35
4.6 Step 3の ア ル ゴ リ ズ ム . . . . 37
4.7 Step 4の ア ル ゴ リ ズ ム . . . . 40
4.8 計 算 時 間 の 評 価 . . . . 44
4.9 記 憶 量 の 評 価 . . . . 45
4.10 計 算 機 実 験 . . . . 47
第5章 動的反辞書構築の提案 51 5.1 静 的 反 辞 書 構 築 と 動 的 反 辞 書 構 築 . . . . 51
5.2 表 記 の 拡 張 . . . . 51
5.3 反 辞 書 オ ー ト マ ト ン . . . . 52
5.4 既 知 の 結 果 . . . . 54
5.5 新 し く 加 わ る 極 小 禁 止 語 の 長 さ . . . . 56
5.6 反 辞 書 の 変 化 と 提 案 ア ル ゴ リ ズ ム . . . . 58
第6章 おわりに 61
図 目 次
2.1 x=MISSISSIPPIの と き の 接 尾 辞 配 列 . . . . 18
2.2 x=MISSISSIPPIの と き のL配 列 . . . . 19
2.3 x=MISSISSIPPIの と き のSの 被 覆 集 合 . . . . 20
2.4 x=MISSISSIPPIの と き のSの 接 尾 辞 配 列 と 接 頭 記 号 . . . . 22
3.1 こ れ ま で の 反 辞 書 の 構 築 方 法 . . . . 23
3.2 x=aababacbcbの と き の 接 尾 辞 ト ラ イ(上)と 接 尾 辞 木(下) . . . . 25
3.3 接 尾 辞 のsuffix link（ 実 線 矢 印 ）とMF–link（ 点 線 矢 印 ） . . . . . 26
3.4 接 尾 辞 木 へ の タ イ プIの 反 辞 書 の 追 加 例 . . . . 28
3.5 接 尾 辞 木 へ の タ イ プIIの 反 辞 書 の 追 加 例 . . . . 29
4.1 計 算 時 間 の 比 較（ 実 線：提 案 手 法 ，点 線：接 尾 辞 木 を 用 い た 手 法 ） . . 48
4.2 記 憶 量 の 比 較（ 実 線：提 案 手 法 ，点 線：接 尾 辞 木 を 用 い た 手 法 ） . . . 48
4.3 ア ル ファベット サ イ ズmご と の 計 算 時 間 . . . . 50
4.4 ア ル ファベット サ イ ズmご と の 記 憶 量 . . . . 50
5.1 x10 = abcaababacの 反 辞 書 オ ー ト マ ト ン ．黒 丸 の ノ ー ド が 極 小 禁 止 語 を 示 す． . . . . 53
表 目 次
4.1 x=ababbの と き のt¯iと¯bi（¯biの—は ，存 在 し な い 事 を 示 す ）． . 33
記法一覧
X 有 限 ア ル ファベット 集 合 ．. . . p.15 xji 系 列xixi+1· · ·xj．. . . p.15 λ 空 系 列 ．. . . p.15 x 長 さnの 系 列x1x2· · ·xn（ 第4章 ま で の 記 法 ）．. . . p.15 xn 長 さnの 系 列x1x2· · ·xn（ 第5章 以 降 の 記 法 ）．. . . p.52 D(xn) 系 列xnの 辞 書 ．. . . p.15 S(xn) 系 列xnの 全 て の 接 尾 辞 の 集 合 ．. . . p.16 σ(xn) 系 列xnの 先 頭 記 号 を 削 る 接 尾 辞 演 算 子 ．. . . p.16 σk(xn) 接 尾 辞 演 算 子 を 系 列xnにk回 繰 り 返 し ほ ど こ す．. . . p.16 P(xn) 系 列xnの 全 て の 接 頭 辞 の 集 合 ．. . . p.16 π(xn) 系 列xnの 末 尾 記 号 を 削 る 接 頭 辞 演 算 子 ．. . . p.16 πk(xn) 接 頭 辞 演 算 子 を 系 列xnにk回 繰 り 返 し ほ ど こ す．. . . p.16 A(xn) 系 列xnの 反 辞 書 ．. . . p.17 v≺w 辞 書 式 順 序 昇 順 で の 大 小 関 係 ．vの 方 がwよ り 小 さ い ．. . p.17 ri 辞 書 式 順 序 昇 順 でi番 目 の 接 尾 辞 ．な お ，r0 =λで あ る ． p.18 S 系 列xnの 接 尾 辞 配 列 ．. . . p.18 S[i] 系 列xnの 接 尾 辞 配 列 のi (0≤i≤n)番 目 の 要 素 ．. . . p.18
⊥ 接 尾 辞 配 列 の 境 界 を 示 す 仮 想 記 号 ．. . . p.18 lcp (v,w) 系 列vとwの 共 通 接 頭 辞 の 最 大 の 系 列 長 ．. . . p.19
L 系 列xnのL配 列 ．. . . p.19 L[i] 系 列xnのL配 列 のi (−1≤i≤n)番 目 の 要 素 ．. . . p.19 C(u) 系 列xnの 部 分 系 列uの 被 覆 集 合 ．. . . p.20 XH(u) 系 列xnの 部 分 系 列uの 接 頭 記 号 の 全 て の 集 合（ 第4章 ま で の 記 法 ）．. . . p.21 XnH(u) 系 列xnの 部 分 系 列uの 接 頭 記 号 の 全 て の 集 合（ 第5章 以 降 の 記 法 ）．. . . p.52 XT(u) 系 列xnの 部 分 系 列uの 接 尾 記 号 の 全 て の 集 合（ 第4章 ま で の 記 法 ）．. . . p.21 XnT(u) 系 列xnの 部 分 系 列uの 接 尾 記 号 の 全 て の 集 合（ 第5章 以 降 の 記 法 ）．. . . p.52 N(v) 系 列vの ロ ー カ ス. . . p.26 L(p) ノ ー ドpの ラ ベ ル 列 ．. . . .p.26 S(p) ノ ー ドpのsuffix link先 ノ ー ド．. . . .p.26 H(u) 系 列xnの 部 分 系 列uに 対 す る ，π(u)とuの 全 接 頭 記 号 集 合 の 差 集 合（ 第4章 ま で の 記 法 ）．. . . p.30 Hn(u) 系 列xnの 部 分 系 列uに 対 す る ，π(u)とuの 全 接 頭 記 号 集 合 の 差 集 合. . . p.52 T(u) 系 列xnの 部 分 系 列uに 対 す る ，σ(u)とuの 全 接 尾 記 号 集 合 の 差 集 合（ 第4章 ま で の 記 法 ）．. . . p.31 Tn(u) 系 列xnの 部 分 系 列uに 対 す る ，σ(u)とuの 全 接 尾 記 号 集 合 の 差 集 合. . . p.52 GH 系列xnの全ての極小禁止語の先頭文字を削除した系列の集合．
p.31
t¯i 系 列xnの 極 小 禁 止 語 の 先 頭 文 字 を 削 除 し た 系 列 の 候 補 ．長 さ をL[i−1]で 求 め て い る ．. . . p.33
¯bi 系 列xnの 極 小 禁 止 語 の 先 頭 文 字 を 削 除 し た 系 列 の 候 補 ．長 さ をL[i]で 求 め て い る ．. . . p.33 G 全 て のt¯iとb¯iの 集 合 ．GHを 含 ん で い る ．. . . p.34 GT 全 て のt¯iの 集 合 ．. . . p.37 GB 全 て のb¯iの 集 合 ．. . . p.37 ti 集合GTの要素を辞書式順序昇順に整列したときのi(0≤i≤n) 番 目 の 系 列 ．. . . p.37 bi 集 合GBの 要 素 を 辞 書 式 順 序 昇 順 に 整 列 し た と き のi (0 ≤ i ≤
|GB| −1)番 目 の 系 列 ．. . . p.37 gi 集 合Gの 要 素 を 辞 書 式 順 序 昇 順 に 整 列 し た と き のi (0 ≤ i ≤
|G| −1)番 目 の 系 列 ．. . . p.37
第 1 章 はじめに
1.1 研究背景
反 辞 書 と は ，従 来 の 一 般 的 な 辞 書 と は 異 な り，入 力 系 列 に 出 現 し な い 系 列
（極小禁止語）を登録する辞書である．Crochemoreらが2000年に提案した反辞 書法[5]で，歪みのないデータ圧縮に有効であることが明らかにされた．デー タ圧縮以外にも，分岐予測[6]，同期符号[7]，不整脈検出[8]などの応用が提案 さ れ て い る ．
反辞書を利用するには，反辞書から構築した反辞書オートマトンを用いる．
例 え ば ，反 辞 書 法 の 場 合 ，符 号 側 で は ，入 力 系 列 に し た がって オ ー ト マ ト ン の状態を遷移していき，遷移先が一意に定まるときは記号を削除することで デ ー タ を 圧 縮 す る ．そ し て ，復 号 側 で は ，符 号 側 か ら 反 辞 書 と 生 成 し た 圧 縮 デ ー タ が 与 え ら れ る ．与 え ら れ た 反 辞 書 か ら 反 辞 書 オ ー ト マ ト ン を 生 成 し ， 圧縮 デ ータ に し たがって反辞 書 オ ート マ ト ンを 遷 移 する こ と でデ ー タ を復 元 す る ．こ の と き ，符 号 側 で 削 除 し た 記 号 は 遷 移 先 が 一 意 に 決 ま る の で ，デ ー タ は 完 全 に 復 元 さ れ る ．
す なわ ち ，反辞書 法 は 符 号化 側 と 復 号側 の 処 理 がオ ー ト マ トン を 遷 移 する だ け な の で ，計 算 機 へ の 負 荷 が 少 な い と い う 利 点 が あ る ．こ の 利 点 は ，組 込 み機器などの資源が限られ，記憶量と通信路容量を十分確保できない環境下 に お い て ，優 れ た 圧 縮 手 法 と な る 可 能 性 を 秘 め て い る ．ま た ，反 辞 書 法 以 外 に つ い て も ，反 辞 書 オ ー ト マ ト ン を 用 い る の で 計 算 機 へ の 負 荷 が 少 な い ．
反 辞 書 の 構 築 は ，太 田・森 田 に よって ，入 力 系 列 長 に 比 例 す る ，す な わ ち ， 線 形 の 計 算 時 間 と 記 憶 量 で 構 築 す る 手 法[9]が 提 案 さ れ て い る ．こ の 手 法 で は ，入 力 記 号 系 列 の 接 尾 辞 を 木 構 造 で 表 現 し た 接 尾 辞 木 を 用 い る ．接尾 辞 木
へMF–linkと呼ばれる特別なリンクを追加して反辞書を構築する．ただし，ア
ル ファベットが 多 値 の 場 合 ，記憶 量 が 膨 大 に な る と い う 問 題 が あ る ．これ は ，
MF–linkが使用する記憶量は線形だが，アルファベットサイズにも比例するた
め に 係 数 が 大 き く な る の が 原 因 で あ る ．
そ こで ，本論 文で は よ り 少な い 計 算 時間 と 記 憶 量で 反 辞 書 を構 築 す る こと
を 検 討 す る ．
1.2 研究のねらい
本 論 文 で は ，記 憶 量 と 計 算 時 間 を 改 善 す る 新 し い 反 辞 書 構 築 手 法 を2つ 提 案 す る ．1つ 目 は ，入 力 系 列 を 全 て 入 力 後 に 反 辞 書 を 構 築 す る 静 的 な 手 法 で あ る ．2つ 目 は ，入 力 系 列 を 逐 次 的 に 読 み 込 み な が ら ，反 辞 書 を 変 化 さ せ て い く 動 的 な 手 法 で あ る ．構 築 手 法 を 考 え る 場 合 ，一 般 的 に は ，動 的 な 手 法 よ り も 静 的 な 手 法 の ほ う が 簡 単 で あ る ．そ こ で ，最 初 に 静 的 な 手 法 に つ い て 検 討 を 行 い ，そ の 成 果 を 動 的 な 手 法 へ 活 用 す る ．
1つ 目 の 静 的 手 法 で は ，接 尾 辞 を 配 列 で 表 現 す る 接 尾 辞 配 列[10]に 注 目 す る ．た だ し ，単 純 に 接 尾 辞 木 の 代 わ り に 接 尾 辞 配 列 を 用 い る と ，記 憶 量 は 削 減 で き る が ，入 力 系 列 長nに 対 し て ，n2 に 比 例 す る 計 算 時 間 を 必 要 と す る ． また ，接尾辞 配列 に 高さ 配 列[11],[12]（本 論文 で はL配列 と 呼ぶ ）を利用 し た 方 法 で も 平 均 し てnlognに 比 例 す る 計 算 時 間 を 必 要 と す る 問 題 が あ る ．こ こ でL配 列 と は ，接 尾 辞 配 列 上 で 隣 接 し た 二 つ の 接 尾 辞 に 共 通 す る 最 長 接 頭 辞 の 長 さ の 配 列 で あ る ．
そ こ で ，本 論 文 で は 計 算 時 間 を 線 形 と す る た め に ，あ と1記 号 を 先 頭 に 加 えると反辞書の要素になる系列を接尾辞配列から探索し，反辞書を構築する 手 法 を 提 案 す る ．
そ の た め に ，極 小 禁 止 語 を 先 頭 記 号 と 後 続 す る 系 列 に 分 け て 考 え る ，反 辞 書 の 新 し い 別 表 現 を 提 案 す る ．そ し て ，あ と1記 号 先 頭 に 加 え る こ と で 極 小 禁 止 語 に な る 系 列 が ，入 力 系 列 の 接 尾 辞 配 列 な ら び にL配 列 に よって 特 徴 づ けられること，すなわち，先頭に1記号加えれば極小禁止語になる系列は，接 尾 辞 配 列 上 の 接 尾 辞 の 先 頭 部 分 に 存 在 し ，そ の 長 さ はL配 列 で 求 め る こ と が で き る こ と を 示 す．
さ ら に ，本 論 文 で は ，被 覆 集 合 を 提 案 す る ．被 覆 集 合 と は ，入 力 系 列 の 任 意の部分系列が，接尾辞配列上の接尾辞の先頭部分に存在している範囲を表 現する集合である．接尾辞配列上の接尾辞は辞書式順序昇順で整列している の で ，被覆 集 合 の 範 囲 を 比 較 す る こ と で ，入 力 系 列 の 部 分 系 列 同 士 の 辞 書 式 順 序 昇 順 の 大 小 関 係 を 判 別 で き る ．す な わ ち ，こ の2つ の 系 列 の 先 頭 か ら 順 に 記 号 を 比 較 す る 必 要 が な く，定 数 時 間 で 系 列 の 比 較 が 行 え る よ う に な る ． こ の 反 辞 書 の 別 表 現 と 被 覆 集 合 を 用 い る こ と で ，接 尾 辞 配 列 ，L配 列 を そ れ ぞ れ3回 走 査 す る だ け で ，先 頭 に1記 号 加 え れ ば 極 小 禁 止 語 に な る 系 列 を す べ て 含 む 高々2n+ 2個 の 系 列 を 辞 書 式 順 序 昇 順 で 求 め ら れ る 算 法 を 提 案 す
る ．提 案 方 法 に お い て は ，極 小 禁 止 語 は ，利 用 し た 被 覆 集 合 の 範 囲 を そ の ま ま 活 用 し て ，被 覆 集 合 の 範 囲 と 系 列 長 ，そ し て ，先 頭 に 加 え る 記 号 を 要 素 に 持 つ 配 列 で 表 現 さ れ る ．本論 文 で は ，こ の 極 小 禁 止 語 の 配 列 表 現 を 反 辞 書 配 列 と 呼 ん で い る ．
ま た ，計 算 機 実 験 を 行 い ，接 尾 辞 木 を 用 い た 従 来 手 法 と 比 較 し て ，計 算 時 間 が 約20分 の1，記 憶 量 が 約2.5分 の1に 改 善 さ れ る こ と を 示 す．
2つ 目 の 動 的 な 手 法 で は ，反 辞 書 そ の も の で は な く，反 辞 書 オ ー ト マ ト ン ， す な わ ち ，反辞 書 に 含 ま れ る 極 小 禁 止 語 を 受 理 す る オ ー ト マ ト ン を ，入 力 系 列 を 逐 次 的 に 読 み 込 み な が ら 動 的 に 構 築 す る 手 法 を 提 案 す る ．
そ のた め に ，入力 系 列 の 末尾 に 新 た な記 号 が 加 わる こ と で 反辞 書 が ど のよ う に 更 新 す る の か を 検 討 す る ．
こ れ ま で の 研 究 で ，反 辞 書 が 変 化 す る と き に ，削 除 さ れ る 極 小 禁 止 語 と 新 たに加える極小禁止語（新規極小禁止語）は明らかになっている．しかし，効 率的に求めることができない問題があった．本論文では，さらに検討を進め，
新 た に 加 わ る 極 小 禁 止 語 の 長 さ を 評 価 す る ．
つぎに，反辞書の別表現と同様に，あと1記号加えることで新規極小禁止語 に な る 系 列 を ，入 力 系 列 の 末 尾 か ら 探 索 す る ．さ ら に ，更 新 前 の 反 辞 書 オ ー トマトンを用いて，探索した系列を新規極小禁止語にするために加える記号 を 求 め る ．
こ れ ら の 結 果 を 用 い る こ と に よって ，反 辞 書 オ ー ト マ ト ン の 構 築 す る た め に ，従 来 の 手 法 で は ，接尾 辞 を 表 す 木 構 造 や オ ー ト マ ト ン を 経 由 し て 作 成 す る 必 要 が あった の が ，そ の 手 間 を 省 い て ，入 力 系 列 か ら 直 接 構 築 す る 手 法 を 提 案 す る ．
第 2 章 定義とデータ構造
2.1 有限アルファベット集合と系列
有 限 ア ル ファベット 集 合 を
X ={ξ1, ξ2, . . . , ξm} (ξ1 < ξ2 <· · ·< ξm, m ≥2) と お き ，X 上 の 系 列 を ，
xji =xixi+1· · ·xj (xk ∈ X,1≤i≤k ≤j) と す る ．
こ こ で ，集 合 の サ イ ズ と 系 列 長 は| · |で 表 記 す る ．例 え ば ，|X | = m,|xji| = j−i+ 1で あ る ．な お ，系 列 長0を 空 系 列 と し ，λと 表 記 す る ．便 宜 上 ，i > j の と きxji =λと す る ．ま た ，系 列 長n(≥1)の 系 列xn1 をxと 表 記 す る ．
2.2 辞書
辞書(dictionary) D(x)とは，x上に出現する部分系列の全ての集合であり，
D(x) = {xji|1≤i≤j ≤n} ∪ {λ}
と す る ．な お ，D(λ) = {λ}で あ る こ と を 注 記 す る ． 例 1 系 列x=abbcaの 辞 書 は ，
D(x) = {a,b,c,ab,bb,bc,ca,abb,bbc,bca,abbc,bbca,abbca, λ} と な る ．
2.3 接尾辞と接頭辞
系 列x = xnに 対 し てxの 接 尾 辞(suffix)と は ，xni (1 ≤ i ≤ n)に 空 系 列λを 加 え た も の で あ る ．こ こ で ，xの 全 て の 接 尾 辞 か ら な る 集 合S(x)は ，
S(x) ={xni|1≤i≤n} ∪ {λ}
と表される．さらに，接尾辞演算子σをσ(x) =xn2と定義する．xにσをk(≥1) 回 繰 り 返 し 施 す と ，
σk(x) = xn1+k
と な る ．す な わ ち ，σk(x)は ，xの 先 頭 か らk記 号 分 削 除 し た 系 列 で あ る ． ま た ，xi1 (1≤ i ≤n)と 空 系 列λをxの 接 頭 辞(prefix)と 呼 ぶ ．こ こ で は ，x の 全 て の 接 頭 辞 か ら な る 集 合P(x)は ，
P(x) ={xi1|1≤i≤n} ∪ {λ}
と 表 さ れ る ．さ ら に ，接 頭 辞 演 算 子π をπ(x) = xn1−1 と 定 義 す る ．xにπを k (≥1)回 繰 り 返 し 施 す と ，
πk(x) = xn1−k
と な る ．す な わ ち ，πk(x)は ，xの 末 尾 か らk記 号 分 削 除 し た 系 列 で あ る ． な お ，σ(λ) = λ, π(λ) = λで あ る こ と を 注 記 す る ．
例 2 系列x=abbcaの全ての接尾辞の集合S(x)と，全ての接頭辞の集合P(x) は ，
S(x) = {abbca,bbca,bca,ca,a, λ}, P(x) = {abbca,abbc,abb,ab,a, λ} と な る ．
ま た ，
σ(x) = bbca, σ2(x) =bca, π(x) = abbc, π2(x) =abb と な る ．
2.4 極小禁止語と反辞書
系 列x上 に 出 現 し な い 系 列 を 禁 止 語 と よ ぶ ．そ し て ，系 列v が 次 の(2.1), (2.2), (2.3)のすべてを満すとき，vはxの極小禁止語(Minimal Forbidden Word) で あ る ．
v ̸∈ D(x), (2.1)
π(v) ∈ D(x), (2.2)
σ(v) ∈ D(x). (2.3)
し た がって ，極 小 禁 止 語 はx上 に 出 現 し な い が ，極 小 禁 止 語 の 端 を 削 除 し た 系 列 はx上 に 出 現 し て い る ．
反 辞 書(antidictionary) A(x)と は ，系 列xに 対 す る 極 小 禁 止 語 の す べ て の 集 合 で あ る ．す な わ ち ，
A(x) = {v ̸∈ D(x)|π(v)∈ D(x), σ(v)∈ D(x)} と な る ．
例 3 有 限 ア ル ファベット 集 合X ={a,b,c}，系 列x=abbcaの 反 辞 書 は ， A(x) = {aa,ac,ba,cb,cc,abc,bbb,cab}
と な る ．
2.5 辞書式順序比較
系列v,wの辞書式順序昇順での大小関係を，比較記号≺で示すことにする．
v≺wは ，
(v1 < w1)∨(v1 =w1)∧(σ(v)≺σ(w)) と 定 義 す る ．便 宜 上 ，λ < ξ1と す る ．
例 4 次 の5つ の 系 列bb,aca,c,abba,abbの 辞 書 式 順 序 昇 順 で の 大 小 関 係 は ， abb≺abba≺aca≺bb ≺c
と な る ．
2.6 接尾辞配列
系列xの全ての接尾辞を辞書式順序昇順で並べたとき，i(0≤i≤n)番目の 接 尾 辞 を ラ ン クiの 接 尾 辞 と 呼 び ，riと 表 記 す る ．す な わ ち ，r0 =λと な り，
i >0の と き は ，
ri = min{v ∈ S(x)|ri−1 ≺v} (2.4)
と な る ．
系 列xの 接 尾 辞 配 列(suffix array) Sと は ，Sのi番 目 の 要 素 が S[i] =n− |ri|+ 1
で 与 え ら れ る 配 列 で あ る ．こ のS[i]は 接 尾 辞riのx上 に お け る イ ン デック ス を 表 す．よって ，xの 左 端 か らS[i]−1個 の 記 号 を 削 る と ，riに な る の で ，
ri =σj(x) (j =S[i]−1) が 成 り 立 つ ．
な お ，便 宜 上 ，本 論 で は 境 界 を 示 す た め に ，X に 属 さ な い 記 号⊥を 用 い て r−1 =rn+1 =⊥と お く．
例 5 図2.1に ，x=MISSISSIPPI（ 系 列 長11）の 接 尾 辞 配 列 の 概 要 を 示 す．
最初に，xの全ての接尾辞を辞書式順昇順で整列する．整列後の並びでi(0≤ i≤11)番目の接尾辞がriである．また，riのx上の開始インデックスがS[i]の 値 と な る ．
図 2.1: x=MISSISSIPPIの と き の 接 尾 辞 配 列
2.7 共通接頭辞の最大長
2つ の 任 意 の 系 列v,w ∈ X∗に は ，共 通 接 頭 辞u ∈ P(v)∩ P(w)が あ る ．こ の 共 通 接 頭 辞 の 最 大 の 系 列 長 を
lcp (v,w) = max{|u||u∈ P(v)∩ P(w)}
と す る ．記 号⊥はX に 属 さ な い の で ，vと の 共 通 接 頭 辞 は 存 在 し な い ．そ こ で 便 宜 上 ，lcp (⊥,v) = lcp (v,⊥) =−1と す る ．
2.8 L 配列
L配 列 は 高 さ 配 列[11],[12]と も 呼 ば れ ，2つ の 接 尾 辞ri,ri+1 (−1 ≤i ≤ n)の 最 長 共 通 接 頭 辞 の 系 列 長 を 配 列 で 表 現 し た も の で あ る ．
す な わ ち ，xのL配 列Lと は ，Lのi番 目 の 要 素 が
L[i] = lcp (ri,ri+1) (2.5)
で与えられる配列である．なお，L[−1] =L[n] =−1で,Lの長さがn+ 2である こ と を 注 記 す る ．
例 6 図2.2に ，x=MISSISSIPPI（ 系 列 長11）のL配 列 の 概 要 を 示 す．
r3とr4の最 長共通接頭辞はISSIで，系列 長は4である ．よって，L[3] = 4と な る ．便 宜 上 ，L[−1] = L[n] =−1は 境 界 を 示 す た め に 存 在 す る ．
図 2.2: x=MISSISSIPPIの と き のL配 列
2.9 被覆集合
系 列x上 の 任 意 の 部 分 系 列u ∈ D(x)に 対 し て ，uを 接 頭 辞 に も つ 接 尾 辞 が 必 ず 存 在 す る ．そ こ で ，
C(u) ={i|u∈ P(ri),0≤i≤n} (2.6)
を 定 義 し ，被 覆 集 合(cover set)と 呼 ぶ こ と に す る ．接 尾 辞 が 整 列 し て い る か ら ，C(u)は 連 続 し た 整 数 か ら な る 集 合 で あ る ．す な わ ち ，
C(u).min = min{i|i∈ C(u)}, (2.7)
C(u).max = max{i|i∈ C(u)} (2.8)
と す る と ，
C(u) ={i|C(u).min≤i≤ C(u).max} (2.9)
と表 せ る ．な お ，被覆 集 合 は ，文 献[12]のrank intervalを 整 数 の 集 合 で 表 現 し たものである．ここで，|C(u)|はuがx上に出現する数に等しく，また，C(λ) = {0,1,2, . . . , n}で あ る こ と を 注 記 す る ．
例 7 図2.3に ，x=MISSISSIPPI（ 系 列 長11）の 被 覆 集 合 の 概 要 を 示 す．
部分系列Sの被覆集合を求めるとき，接尾辞の先頭部分にSがあるものを探 す．この場合，接尾辞r8,r9,r10,r11が該当する．したがって，C(S) ={8,9,10,11} と な る ．
図 2.3: x=MISSISSIPPIの と き のSの 被 覆 集 合
2.10 接頭記号と接尾記号
系 列u∈ D(x)と 任 意 の 記 号α ∈ X に 対 し て ，x上 にαuが 出 現 す る な ら ，α をuの接 頭 記 号(head symbol)と 呼 ぶ こ と に す る ．さ ら に ，uの 接 頭 記 号 の 全 て の 集 合 を ，uの全 接 頭 記 号 集 合と 呼 ぶ こ と に し ，XH(u)と 表 記 す る ．す な わ ち ，
XH(u) = {α∈ X |αu ∈ D(x)} (2.10)
で あ る ．
さ ら に ，XH(u)は ，接 尾 辞 配 列Sと 被 覆 集 合C(u)を 用 い て
XH(u) ={xi|i=S[k]−1, k∈C(u), i≥1} (2.11) と 表 す こ と も で き る ．
また，x上にuβが出現するなら，βをuの接尾記号(tail symbol)と呼ぶこと にする．さらに，uの接尾記号の全ての集合を，uの全接尾記号集合と呼ぶこ と に し ，XT(u)と 表 記 す る ．す な わ ち ，
XT(u) ={β ∈ X |uβ ∈ D(x)} (2.12)
で あ る ．
な お ，XH(λ)とXT(λ)はx上 に 出 現 す る 全 て の 記 号 で あ る こ と を 注 記 す る ． ま た ，uがx上 に1箇 所 の み 出 現 し ，u ∈ P(x)の と き は ，XH(u) = ϕで あ る ． 同じく，uがx上に1箇所のみ出現し，u∈ S(x)のときは，XT(u) = ϕである．
例 8 図2.4に，x=MISSISSIPPIの接尾辞配列と接頭記号に関する概要を示す．
接 尾 辞r3 =ISSIPPIのx上 に お け る 開 始 イ ン デック ス はS[3] = 5で あ る ．す なわち，記号xS[3]−1 =Sは，r3の接頭記号である．さらに，r3の接頭辞につい ても，開始インデックスは変わらないので，記号xS[3]−1は，r3の接頭辞の接頭 記 号 で あ る ．
全 接頭 記 号 集 合は ，被覆 集合 を 使 う こと で 接 尾 辞配 列 か ら 求め る こ と がで き る ．部 分 系 列Sの 被 覆 集 合 は ，C(S) = {8,9,10,11}な の で ，r8,r9,r10,r11の 接 頭 記 号 を 集 め た も の が 全 接 頭 記 号 集 合XH(S)に な る ．
図 2.4: x=MISSISSIPPIの と き のSの 接 尾 辞 配 列 と 接 頭 記 号
第 3 章 接尾辞木を用いた反辞書構築
3.1 反辞書構築のアプローチ
反 辞書 構 築 の 従来 手 法 で は，入力 系 列か ら 直 接 反辞 書 を 構 築す る の で はな く，一 度 接 尾 辞 を 用 い た デ ー タ 構 造 を 構 築 し ，そ こ か ら 反 辞 書 を 構 築 し て い る ．ま た ，入 力 系 列 を 全 て 入 力 し て か ら 反 辞 書 を 構 築 す る 静 的 構 築 と ，入 力 系 列 を1記 号 ず つ 読 み 込 み な が ら 逐 次 的 に 反 辞 書 を 変 化 さ せ て 構 築 す る 動 的 構 築 の2種 類 が あ る（ 図3.1）．
図 3.1: こ れ ま で の 反 辞 書 の 構 築 方 法
接 尾 辞 を 用 い た デ ー タ 構 造 の 多 く は 入 力 系 列 を す べ て 読 み 込 み 終 わって か ら 構 築 す る ア ル ゴ リ ズ ム が 多 い た め ，反 辞 書 を 静 的 に 構 築 す る 場 合 に は ，こ れ ら の デ ー タ 構 造 を 活 用 で き る 利 点 が あ る ．ただ し ，デー タ 圧 縮 な ど に 応 用 するときには，構築した反辞書を復号側に送るなどのオーバヘッドが生じる．
一 方 ，反 辞 書 を 動 的 に 構 築 す る 場 合 に は ，入 力 記 号 に 合 わ せ な が ら 反 辞 書 を変化させていくので，オーバーヘッドを無くすことができる．また，1記号 読 み 込 ん だ 後 の 反 辞 書 の 変 化 が 少 な い 場 合 ，第4章 の 提 案 手 法 よ り も 効 率 が よ く な る 可 能 性 が あ る ．
第4章 と 第5章 で は ，静 的 構 築 と 動 的 構 築 の 両 方 で 入 力 系 列 長 に 対 し て 線 形 の 計 算 量 を 達 成 し て い る ，太 田・森 田 に よって 提 案 さ れ た 接 尾 辞 木 を 用 い た 反 辞 書 構 築 手 法[9]を 参 考 に し て ，新 し い 構 築 手 法 を 提 案 し た ．
そ こ で ，こ の 章 で は 接 尾 辞 木 を 用 い た 反 辞 書 構 築 手 法 に つ い て 述 べ る ．
3.2 接尾辞木
系 列 の 集 合 を 木 構 造 で 表 現 し た も の と し て ，ト ラ イ(trie)[13]が あ る ．ト ラ イ の 枝 に は ラ ベ ル が 付 け ら れ ，記 号 が1つ 割 り 振 ら れ て い る ．そ し て ，与 え られた系列xの全ての接尾辞の集合S(n)をトライで表現した木を接尾辞トラ イ と 呼 ぶ ．枝 の ラ ベ ル に は ，接 尾 辞 上 の 記 号 が1つ 割 り 振 ら れ て い る ．
一 方 ，接 尾 辞 木(Suffix tree)[14]も 同 様 に ，S(n)を 木 構 造 で 表 現 し た も の で あ る ．接 尾 辞 ト ラ イ と 異 な る の は ，ラ ベ ル に はxの 部 分 系 列 を 割 り 振って い る こ と で あ る ．こ こ で ，接 尾 辞 ト ラ イ の ノ ー ド の う ち ，子 ノ ー ド を1つ だ け 持 つ ノ ー ド を 陰 ノ ー ド，子 ノ ー ド を2つ 以 上 持 つ ノ ー ド を 陽 ノ ー ド と 呼 ぶ こ とにする．任意の陰ノードをp，pの親ノードをq,pの子ノードをr とし，pと qを 接 続 す る 枝 の ラ ベ ル をα，pとr を 接 続 す る 枝 の ラ ベ ル をβと す る ．こ の と き ，系 列αβはxの 部 分 系 列 で あ る ．し た がって ，枝 にxの 部 分 系 列 を 割 り 振 れ る の な ら ば ，pを な く し て ，q とr を1本 の 枝（ ラ ベ ル はαβ）に ま と め る こ と が で き る ．こ の よ う に し て ，接 尾 辞 ト ラ イ の 陰 ノ ー ド を1本 の 枝 に ま と め ，接 尾 辞 ト ラ イ を コ ン パ ク ト に 表 現 し た も の が 接 尾 辞 木 で あ る ．
と こ ろ で ，接 尾 辞 木 の 枝 の ラ ベ ル の 長 さ が2以 上 の 時 ，枝 を 記 号 単 位 で 分 割した区切り位置に仮想のノードがあると考えれば接尾辞トライと等価な木 に な る ．こ の と き ，こ の 仮 想 ノ ー ド は 接 尾 辞 ト ラ イ の 陰 ノ ー ド に 対 応 し ，接 尾 辞 木 の 中 間 ノ ー ド は 接 尾 辞 ト ラ イ の 陽 ノ ー ド に 対 応 す る ．本 論 文 で は ，接 尾 辞 木 に お い て ，上 記 の 仮 想 ノ ー ド を 扱 う こ と が あ る の で ，こ の 仮 想 ノ ー ド を 陰 ノ ー ド と 呼 ぶ こ と に す る ．
ま た ，陽 ノ ー ド か ら 子 ノ ー ド に 向 かって ，枝 が 伸 び て い る ．こ れ ら の 枝 の ラ ベ ル の 先 頭 記 号 は ，各々異 な る 記 号 で あ る ．そ こ で ，陽 ノ ー ド か ら 子 ノ ー ド へ 記 号αを 先 頭 に 持 つ ラ ベ ル の 枝 が 伸 び て い る と き ，αが 発 芽 す る と 呼 ぶ こ と に す る ．
図3.2にx=aababacbcbの 接 尾 辞 ト ラ イ と 接 尾 辞 木 を 示 す．
b
c c
b
c c
c
ba
b cb
cb c b
c b
cb cb c b
c b
cb
図 3.2: x=aababacbcbの と き の 接 尾 辞 ト ラ イ(上)と 接 尾 辞 木(下)
本 論 文 で は ，xの 接 尾 辞 木 をTと 表 記 す る ．
ま た ，任 意 の 系 列v ∈ X∗に 対 し て ，接 尾 辞 木Tの 根 か ら 葉 ノ ー ド に 向 かっ てvと一致するようにラベルをたどることで到達したノードをローカスと呼 び ，N(v)と 表 記 す る ．系 列vに よって は ，N(v)は 陰 ノ ー ド だった り，存 在 し な い こ と も あ り え る ．N(v)が 存 在 す る と き は ，v ∈ D(x)で あ る ．
さらに，陰ノードを含む任意のノードpに対して，木の根からpまでのラベ ル を 順 に つ な い だ 記 号 列 を ラ ベ ル 列 と 呼 び ，L(p)と 表 記 す る ．
3.3 suffix link と MF–link
接 尾 辞 木 を 線 形 時 間 で 構 築 す る 手 法 と し て ，Ukkonenの 構 築 手 法[15]が あ る．この手法では，接尾辞木の陽ノードにsuffix linkを用いている．suffix link とは ，接尾 辞 木Tの陽 ノ ー ドpに対 し て ，σ(L(p))のラ ベ ル 列 を 持 つ ノ ー ド へ の リ ン ク で あ る ．suffix link先 の ノ ー ド をS(p)と 表 記 す る ．
また，太田らは，接尾辞木を用いて反辞書を作成するために，MF–linkを定 義 し た[9]．こ れ は ，ノ ー ドpの 逆suffix linkで あ る ．す な わ ち ，ノ ー ドmの ラ ベル 列L(m)がσ(L(m)) =L(p)を 満た す と き ，pからmへMF–linkが張 ら れ る ． な お ，mは 陽 ノ ー ド だ け で な く 陰 ノ ー ド の も の も あ る こ と を 注 記 す る ．
図3.3に ，x = abbcaの 接 尾 辞 木 とsuffix link, MF–linkの 例 を 示 す．白 丸 の ノ ー ド が 接 尾 辞 木 の 陽 ノ ー ド，小 さ な 黒 丸 が 陰 ノ ー ド，四 角 が 葉 ノ ー ド で あ る ．suffix linkは ，実 線 の 矢 印 で 示 し て い る ．MF–linkは ，点 線 矢 印 で 示 し て い る ．
図 3.3: 接 尾 辞 のsuffix link（ 実 線 矢 印 ）とMF–link（ 点 線 矢 印 ）
3.4 反辞書の構築
接尾辞木を用いた反辞書構築手法では，極小禁止語をラベル列に持つMFW ノードを接尾辞木に追加する．そして，MFWノードを追加する位置によって，
極 小 禁 止 語 を2種 類 に 分 け て い る ．
• 葉 ノ ー ド にMFWノ ー ド を 追 加 す る 極 小 禁 止 語（ タ イ プI）．
• 葉 ノ ー ド 以 外 にMFWノ ー ド を 追 加 す る 極 小 禁 止 語（ タ イ プII）．
Ukkonenの接尾辞木の構築手法では，1記号づつ読み込みながら接尾辞木を
変化させて いる．1記号の 読み込み につき，葉ノー ドと陽ノー ドが高々1つ増 える．したがって，接尾辞木の変化に追従しながら，上記の2種類の極小禁止 語 を 求 め て い く こ と で ，反 辞 書 を 構 築 す る ．
3.4.1 タイプ I の極小禁止語の追加
タイプIの極小禁止語の場合，接尾辞木の葉ノードにMFWノードを追加す る ．す な わ ち ，葉 ノ ー ド をqと お い た と き ，極 小 禁 止 語 はL(q)β (β∈ X)と な る ．こ の と き ，L(q) ∈ D(x) な の で ，極 小 禁 止 語 の3つ の 条 件 の う ち ，(2.2) を満た してい る．さらに，qは葉ノ ード なので ，どん なβでも ，L(q)β ̸∈ D(x) と な り，極 小 禁 止 語 の3条 件 の う ち ，(2.1)を 満 た す．よって ，(2.3)を 満 た すβ を 求 め れ ば よ い ．
ここで，βはqのsuffix linkを用いて求める．qのsuffix link先S(q)のラベル列 はσ(L(q))である．すなわち，S(q)から発芽する記号をβとすれば，σ(L(q))β∈ D(x)と な り，(2.3)を 満 た す．
こうして，ノードqから，求めたβを枝のラベルにしてMFWノードを伸ば し て 追 加 す る ．
なお，ラベル列が最短でない葉ノードのsuffix link先は，別の葉ノードであ る．したがって，suffix link先で発芽する記号はない．言い換えると，タイプI の極小禁止語のMFWノードは，ラベル列が最短の葉ノードだけに追加する．
例 9 図3.4に ，x =abbcaの タ イ プIのMFWノ ー ド を 追 加 す る と き の 様 子 を 示 す．図 の 白 丸 の ノ ー ド が 接 尾 辞 木 の 陽 ノ ー ド，四 角 の ノ ー ド が 接 尾 辞 木 の 葉 ノ ー ド で あ る ．三 角 の ノ ー ド が 追 加 す るMFWノ ー ド で あ る ．
ラ ベ ル 列 が 最 短 の 葉 ノ ー ド をq と す る と ，L(q) = caで あ る ．す な わ ち ，タ イ プIの 極 小 禁 止 語 はcaβ (β ∈ X)と お け る ．
ここで，qのsuffix link先S(q)のラベル列は，aである．また，S(q)からは，b が発芽して いるので，ab ∈ D(x)である．よって，βがbのときは，cabが極小 禁 止 語 の3条 件 を 満 た す の で ，葉 ノ ー ドqか らMFWノ ー ド を 伸 ば し て い る ．
図 3.4: 接 尾 辞 木 へ の タ イ プIの 反 辞 書 の 追 加 例
3.4.2 タイプ II の極小禁止語の追加
タ イ プIIの 極 小 禁 止 語 の 場 合 ，接 尾 辞 木 の 葉 ノ ー ド 以 外 の ノ ー ド，つ ま り 陽 ノ ー ド や 陰 ノ ー ド にMFWノ ー ド を 追 加 す る ．追 加 す る 位 置 は ，陽 ノ ー ド pから張られているMF–link先mである．すなわち，極小禁止語はL(m)βとな る ．こ の と き ，L(m)∈ D(x), な の で ，極 小 禁 止 語 の3つ の 条 件 の う ち ，(2.2) を 満 た し て い る ．よって ，(2.1)と(2.3)を 満 た すβを 求 め れ ば よ い ．
こ こ で ，pとmか ら 発 芽 す る 記 号 に 注 目 す る ．pは 陽 ノ ー ド な の で ，複数 の 記号が発芽している．そこで，pで発芽し，mで発芽しない記号をβとすれば，
L(m)β ̸∈ D(x), σ(L(m)β) =L(p)β ∈ D(x) と な り，(2.1)と(2.3)を 満 た す．
こうして，ノードmから，求めたβを枝のラベルにしてMFWノードを伸ば し て 追 加 す る ．
例 10 図3.5に ，x = abbcaの タ イ プIIのMFWノ ー ド を 追 加 す る と き の 様 子 を 示 す．
ラ ベ ル 列 がbの 陽 ノ ー ド をp，ノ ー ドpのMF–link先 の う ち ，ラ ベ ル 列 がab の ノ ー ド をm と す る ．こ の と き ，タ イ プIIの 極 小 禁 止 語 はabβ (β ∈ X)と お
ノ ー ドpから 発 芽 し て い る 記 号 はbとc，ノー ドmか ら 発 芽 し て い る 記 号 は bで あ る ．よって ，βがcの と き は ，abcが 極 小 禁 止 語 の3条 件 を 満 た す の で ， ノ ー ドm か らMFWノ ー ド を 伸 ば し て い る ．
図 3.5: 接 尾 辞 木 へ の タ イ プIIの 反 辞 書 の 追 加 例
第 4 章 配列を用いた静的反辞書構築 の提案
4.1 接尾辞木を用いた反辞書構築手法の記憶量の内訳
接尾辞木を用いた反辞書構築手法は，計算量が線形とはいえ，アルファベッ トが多値の場合には係数が大きくなるという問題がある．この問題を解決す る た め に ，使 用 し て い る 記 憶 量 の 内 訳 を 調 べ る と ，記 憶 量 はMF–linkを 保 持 するためにほとんど占められていることがわかった．これは，MF–linkが使用 す る 記 憶 量 が ア ル ファベット サ イ ズ に も 比 例 す る の が 原 因 で あ る ．
こ の 問 題 を 解 決 す る た め に は ，MF–linkを 保 持 し な い で 反 辞 書 を 構 築 す る 新 た な 手 法 が 必 要 と な る ．
そ こで 本 研 究 では ，接尾 辞木 よ り も 少な い 記 憶 量で 接 尾 辞 を表 現 で き る接 尾辞配列に注目した．この章では，接尾辞配列を用いて，MF–linkを保持しな い 新 た な 反 辞 書 構 築 手 法 を 提 案 す る ．
4.2 反辞書の別表現
接 尾 辞 配 列 を 用 い て 極 小 禁 止 語 を 求 め る た め に ，極 小 禁 止 語 を 先 頭 記 号α と 系 列uの2つ に 分 割 す る こ と を 提 案 す る [1], [2]．
そのために，(2.10)で定義した全接頭記号集合XH(·)を用いて，XH(π(u))と XH(u)と の 差 集 合 をH(u)と 表 記 し ，
H(u) =
{ X \ XH(λ) (u=λ)
XH(π(u))\ XH(u) (u̸=λ) (4.1)
と 定 義 す る ．
そ し て ，H(u)を 用 い て 反 辞 書A(x)を 表 せ る こ と を ，次 の 定 理 1で 示 す．
定理 1 任 意 のx∈ X∗に 対 し て ， A(x) = {αu|α ∈ H(u),u∈ D(x)}.
証明 最 初 に ，αu∈ A(x) (α∈ X,u ∈ D(x))と お い た と き ，α∈ H(u)で あ る こ と を ，u=λとu̸=λの 場 合 に 分 け て 証 明 す る ．
ま ず，u = λの 場 合 ，α ∈ A(x)と な る の で ，αはx上 に 出 現 し て い な い 記 号 で あ る ．こ こ で ，XH(λ)はx上 に 出 現 す る 全 て の 記 号 の 集 合 な の で ，α ∈ X \ XH(λ) =H(u) で あ る ．
ま た ，u ̸= λの 場 合 ，αu ∈ A(x)か ら ，αu ̸∈ D(x), απ(u) ∈ D(x) と な る ． (2.10)から，α̸∈ XH(u), α ∈ XH(π(u))となる．よって，α∈ XH(π(u))\XH(u) = H(u) で あ る ．
次に，u∈ D(x), α∈ H(u)ならば，αu ∈ A(x)であることを，u=λとu̸=λ の 場 合 に 分 け て 証 明 す る ．
まず，u=λの場合，XH(λ)はx上に出現する全ての記号の集合である．よっ て ，(4.1)よ り，αは 未 出 現 記 号 で あ る ．こ の と き ，αuは ，(2.1), (2.2), (2.3)を 満 す．よって ，αu∈ A(x)で あ る ．
ま た ，u ̸=λの 場 合 ，(4.1)か ら ，α ∈ XH(π(u)), α ̸∈ XH(u) で あ る ．こ の と き(2.10)か ら ，απ(u) ∈ D(x), αu ̸∈ D(x) と な り，(2.1)と(2.2)を 満 す．ま た ， u∈ D(x)な の で ，(2.3)を 満 す．よって ，αu∈ A(x)で あ る ．
以 上 よ り，題 意 が 成 り 立 つ ．
2 と こ ろ で ，(2.12)で 定 義 し た 全 接 尾 記 号 集 合XT(·)を 用 い て ，
XT(u) = {β ∈ X |uβ ∈ D(x)}, (4.2)
T(u) =
{ X \ XT(λ) (u=λ)
XT(σ(u))\ XT(u) (u̸=λ) (4.3)
と 定 義 す る と ，定 理 1と 同 様 に 次 の 系 1が 成 り 立 つ ． 系 1 任 意 のx∈ X∗に 対 し て ，
A(x) = {uβ|β ∈ T(u),u∈ D(x)}.
な お ，系 1は ，こ の 章 で は 使 わ な い が ，第5章 で 用 い る ．
4.3 極小禁止語の先頭文字を削除した系列
任 意 の 部 分 系 列u∈ D(x)がH(u)̸=ϕの と き ，
GH={u|u∈ D(x),H(u)̸=ϕ} (4.4)
と 定 義 す る ．そ し て ，
σ(A(x)) ={σ(w)|w ∈ A(x)} と お く と ，定 理 1よ り，
GH=σ(A(x)) が 成 立 す る ．
こ のGHを 求 め る こ と が で き れ ば ，定 理 1か ら ，要 素u ∈ GHに 対 し てH(u) を求めることで反辞書を構築できる．しかし，GHを求めることは容易ではな い ．そ こ で ，容 易 に 求 め れ て ，GHを 含 む 集 合 を 考 え る こ と に す る ．
ま ず は ，(2.4)で 定 義 し た ラ ン クiの 接 尾 辞ri (0≤ i ≤ n)ご と に ，riの 全 て の 接 頭 辞 の 集 合P(ri)を2つ に 分 割 し た 集 合F(i),E(i)を 定 義 す る ．
F(i) = {u ∈ P(ri)||u| ̸= lcp (ri,rk) + 1,−1≤∀k≤n+ 1}, (4.5) E(i) = {u ∈ P(ri)||u|= lcp (ri,rk) + 1,−1≤∃k≤n+ 1}. (4.6) 明 ら か に ，P(rj) =F(j)∪ E(j),F(j)∩ E(j) = ϕ と な る ．
次 の 補 題 1で ，F(i)とGHの 関 係 を 示 す．
補題 1 任 意 のv ∈ X∗と あ るi (0≤i≤n)に 対 し て ，v ∈ F(i) な ら ば ， H(v) =ϕ.
証明 空 系 列λは ，λ ∈ E(i)で あ る ．よって ，v ̸= λ. そ こ で ，v = uβ (u = π(v), β ∈ X)と お く．
こ こ で ，背理 法 を 使って 証 明 す る ．い ま ，H(v)̸=ϕと 仮 定 す る ．こ の と き ， あ るα ∈ H(v)が 存 在 し ，α ∈ XH(u) \ XH(uβ)と お け る ．す な わ ち ，αu ∈ D(x), αuβ ̸∈ D(x)である．したがって，あるw ∈ X∗が存在し，αuw ∈ D(x), β ̸∈
P(w)とおける．このとき，lcp (uβ,uw) =|u|である．したがって，uβ ∈ P(ri) だ か ら ，lcp (ri,uw) = |u|と な る ．
一方，uw∈ D(x)である．よって，ある整数kが存在し，uw ∈ P(rk)とおけ る ．こ の と き ，lcp (ri,rk) =|u|と な る ．
し か し な が ら ，|v| =|u|+ 1な の で ，こ れ は|v| ̸= lcp (ri,rk) + 1と い う 仮 定 に 矛 盾 す る ．よって ，H(v) =ϕで あ る ．
2
補 題 1か らF(i)∩ GH = ϕで あ る ．す な わ ち ，GHの 要 素uはE(i)か ら 探 せ ばよい．ここで，uを効率よく探すため，E(i)に含まれる2つの系列に注目す る ．す な わ ち ，(2.5)で 定 義 し たL配 列 を 用 い て ，riご と に ，以 下 の 条 件 を 満 た すriの 接 頭 辞t¯i,¯bi ∈ P(ri)を 定 義 す る ．
|t¯i| = L[i−1] + 1, (4.7)
|b¯i| = L[i] + 1≤ |ri|. (4.8)
な お ，L[i] =|ri|の と き ，¯biは 存 在 し な い こ と を 注 記 す る ． 例 と し て ，x=ababbの と き のt¯i,b¯iを 表4.1に 示 す．
表 4.1: x=ababbの と き のt¯iと¯bi（¯biの—は ，存 在 し な い 事 を 示 す ）．
i ri L[i] t¯i ¯bi
-1 ⊥ -1
0 λ 0 λ —
1 ababb 2 a aba
2 abb 0 abb a
3 b 1 b —
4 babb 1 ba ba
5 bb -1 bb λ
6 ⊥
そ し て ，t¯iと¯biを 要 素 に 持 つ 集 合G(i)を 定 義 す る ． G(i) =
{ {t¯i,b¯i} (if ¯bi exists)
{t¯i} (otherwise) (4.9)
次 の 補 題 2で ，E(i)とG(i)の 関 係 を 示 す．
補題 2 任 意 のv ∈ X∗と あ るi (0 ≤ i ≤ n)に 対 し て ，v ∈ E(i) な ら ば ，あ るk が 存 在 し ，
v ∈ G(k).
証明 最初に，(2.7),(2.8)で定義した被覆集合の最小値と最大値を用いて，p=
C(v).min, q =C(v).maxと お く．
接尾辞配列が整列していることと，(4.6)から，|v|= lcp (ri,rp−1) + 1または
|v|= lcp (ri,rq+1)+1である．ここで，(2.6)から，lcp (rp−1,ri) = lcp (rp−1,rp),lcp (ri,rq+1) = lcp (rq,rq+1)で あ る ．
