修士学位論文
パラメタ化照合を用いた
オンライン文字列事典の作成に関する研究
東北大学大学院 情報科学研究科
システム情報科学専攻 篠原研究室
博士課程前期二年の課程
大井 雄介
2014 年 2 月 17 日
i
目次
第 1 章 序論
1
1.1
背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
本論文の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
第 2 章 準備
4
2.1
文字列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
オンライン整数列大事典 . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.3
文字列の生成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3.1
漸化式による方法 . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3.2
準同型写像による方法 . . . . . . . . . . . . . . . . . . . . . . . .
6
索引構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.4.1
接尾辞木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.4.2
一般化接尾辞木 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.4.3
ポジションヒープ . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.4
第 3 章 文字列事典
10
3.1
オンライン文字列事典 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.2
文字列処理の基本アルゴリズム . . . . . . . . . . . . . . . . . . . . . . .
11
連長圧縮 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.2.1
3.3
データ構造
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
パラメタ化ポジションヒープ . . . . . . . . . . . . . . . . . . . .
13
種々の定義から生成される文字列 . . . . . . . . . . . . . . . . . . . . . .
14
3.4.1
フィボナッチ文字列 . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.4.2
トリボナッチ文字列 . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.3.1
3.4
ii
3.5
3.4.3
スターミアン文字列 . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.4.4
シュー・モールス文字列 . . . . . . . . . . . . . . . . . . . . . . .
17
3.4.5
Padovan 文字列 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
3.4.6
Paperfolding 文字列 . . . . . . . . . . . . . . . . . . . . . . . . . .
18
3.4.7
Rudin-Shapiro 文字列 . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.4.8
Baum-Sweet 文字列 . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.4.9
Period-doubling 文字列 . . . . . . . . . . . . . . . . . . . . . . . .
23
3.4.10 ハノイ文字列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
種々の定義から生成される文字列の性質 . . . . . . . . . . . . . . . . . .
24
第 4 章 文字列の検索
26
4.1
文字列の検索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
4.2
パラメタ化照合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
4.2.1
素朴な手法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
4.2.2
パラメタ化照合 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
4.2.3
索引構造を用いたパラメタ化照合 . . . . . . . . . . . . . . . . . .
28
4.3
パラメタ化ポジションヒープの一般化
. . . . . . . . . . . . . . . . . . .
28
4.3.1
一般化パラメタ化ポジションヒープの構築 . . . . . . . . . . . . .
29
4.3.2
一般化パラメタ化ポジションヒープによるパターン照合
. . . . .
31
4.4
無限文字列に含まれる部分文字列 . . . . . . . . . . . . . . . . . . . . . .
32
4.5
文字列事典における文字列の検索 . . . . . . . . . . . . . . . . . . . . . .
40
第 5 章 まとめと今後の課題
41
5.1
まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
5.2
今後の課題
41
参考文献
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
1
第1章
序論
1.1
背景
文字列は，文章を表現するために用いられるだけでなく，画像，音声ファイルといっ
たデータを表現する基本的な構造であり，計算機に情報を格納するための基礎的な役割
を担っている．近年，情報爆発により計算機で膨大なデータを取り扱う必要が生じてい
るため，検索などの情報を効率的に取り扱うための文字列処理に関する研究の重要性が
ますます高まっている．
一方で，文字列と同じく基本的な構造の 1 つである整数列に対して，オンライン整数列
大辞典 (OEIS:The On-Line Encyclopedia of Integer Sequences)1 [19] と呼ばれる整数列
のオンライン事典が存在している．整数列大事典では整数列をクエリとして検索するこ
とで，入力した整数列がどの既存の整数列にあたるのかを容易に調べることができる．検
索結果にはどの数列かだけではなく，数列の一般項や出典，基本的性質等が表示される．
整数列大事典を用いることで，研究の際に出てきた既知の数列の性質や出典について
容易に調べることができる．また，フィボナッチ数列といった有名な整数列について調
( )
べるだけでなく，例えば，1，4，28，220，1820 という条件から 4n
という二項係数を検索
n
することができる．このように，検索結果として二項係数や数列の一般項といった数式
を得ることができるため，式変形を行う際の手段としても有用である．
整数列大事典の他にも，Mathematica や Maple などの数式処理システムといった数式
を用いた研究を支援するシステムが存在しており，研究者は等式変形や行列計算などの
作業を計算機に任せることができる．
1
http://oeis.org
2
このような整数列や数式に対する支援システムはいくつか存在しているが，文字列学
においては文字列処理を行うプログラム以外では対話的に研究者を支援するシステムが
存在していない．整数列大事典による既知の整数列の検索や，数式処理システムを用い
た処理の恩恵を考慮すると文字列学においても既存の文字列に関する知識のデータベー
ス化や文字列処理のツールの作成などが文字列学の研究に大きな役割を果たすと考えら
れる．そこで本研究では，文字列学の研究を支援する仕組みとしてオンライン文字列事
典を提案する．
オンライン文字列事典では，文字列やアルゴリズムについての辞典，特徴のある文字
列の検索の 2 つを主な内容とする．
主な内容の 1 つとして，文字列の基本的な性質やアルゴリズムについてまとめる．文
字列学では，文字列照合や圧縮といった文字列を処理するアルゴリズムが重要な役割を
果たす．文字列照合では照合の様子，データ構造では構築した構造がどのようになって
いるかを視覚化することで理解の助けとなると考えられる．そこで，文字列事典では可
視化や実際に入力を与え動かしながら見ることのできるコンテンツなど理解しやすい工
夫を加えたまとめを行う．
2 つ目の内容として，オンライン整数列大辞典で数列の検索ができることが重要な役割
を果たすのと同様に，ある文字列がどんな特徴をもつか，どのような文字列に属するか
などについて検索できる機能をつくる．文字列事典の特徴のある文字列の検索では，主
に無限文字列を対象として考える．無限文字列とは，その名の通り無限に続く文字列で
ある．特に，無限文字列の中でもフィボナッチ文字列のような規則に従って生成される
無限文字列が知られており，それらの文字列の解析が重要である．文字列事典では，フィ
ボナッチ文字列の様な特徴をもつ無限文字列に対する検索機能の作成を行う．
オンライン数列大辞典で検索対象としている整数列は，円周率であれば 3.1415 · · · と
一意に定まるものであるが，本研究で対象とする文字列では aba と bab のように文字列
を構成するアルファベットが異なっているが，その構造が同じになる文字列が多数存在
し得る．そこで本研究では，文字列の構造に着目した照合方法であるパラメタ化照合 [5]
を用いることで，文字列中の記号に依存しない検索機能を実現する．検索機能を作成す
るにあたって，パラメタ化照合のための索引構造として提案されているパラメタ化ポジ
3
ションヒープ [22] を複数文字列に対応させた一般化パラメタ化ポジションヒープを提案
する．また，無限文字列からの照合を十分に行うために，無限文字列の部分文字列の解
析をする．
1.2
本論文の構成
本論文の構成は次の通りである．第 1 章では本研究の背景について述べた．第 2 章で
は，本論文で用いる文字列処理の基本的な定義について述べる．第 3 章では，本研究で
作成するオンライン文字列事典の概要，および各コンテンツの内容について詳細に述べ
る．第 4 章では，第 3 章でも述べる文字列事典の検索について，用いる手法の説明や本
研究で作成したシステムの説明，そして，作成の際に用いた文字列の性質に関する実験
の結果について述べる．第 5 章では，本研究のまとめ，今後の課題について述べる．
4
第2章
準備
2.1
文字列
文字の有限集合を Σ とし，アルファベットと呼ぶ．Σ∗ の要素を文字列と呼び，文字列
w の長さを |w| と表す．長さ |w| = 0 の文字列を ε で表し，空文字列と呼ぶ．空文字の長
さは |ε| = 0 である．文字列 w = xyz に対して，x，y ，z をそれぞれ文字列 w の接頭辞，
部分文字列，接尾辞と呼ぶ．1 ≤ i ≤ |w| を満たす任意の i において，文字列 w の i 番目
の文字列を w[i] とする．つまり，長さ n の文字列 w は w = w[1]w[2]w...w[n] となる．
また，1 ≤ i ≤ j ≤ |w| を満たす任意の i，j において文字列 w の位置 i から位置 j までの
部分文字列を w[i : j] と表し，w[i : j] = w[i]w[i+1]...w[j] となる．文字列 w を反転させた文
字列を wR とする．w = w[1]w[2] . . . w[n − 1]w[n] に対して wR = w[n]w[n − 1] . . . w[2]w[1]
である．また，w = wR となる文字列を回文と呼ぶ．
文字列 w について，すべての i ≤ 1 ≤ |w| − p に対して w[i] = w[i + p] が成立するとき
正整数 p は w の周期 (period) であり，文字列 w の周期の中で最も小さい p を最小周期と
呼び period(w) と表す．
Π ∩ Σ = ∅ となる Π を，パラメタアルファベット Π と呼び，文字列 T ∈ (Σ ∪ Π)∗ を
(Σ, Π) 上のパラメタ化文字列と呼ぶ．
2.2
オンライン整数列大事典
オンライン整数列大辞典 [2] とは，アメリカの数学者 N. J. A. Sloane によって 1996 年
に作られたオンラインデータベースである．オンライン整数列大辞典には 2014 年 1 月 8
5
日現在で 235011 個もの数列が登録されている．利用者は検索クエリとして，数値列，数
値列に関係する用語，辞典内で割り当てられている数値列の ID のいずれかを入力する
ことで，辞典に登録されている数列を検索することができる．検索結果として，数列の
ID，数列名 (NAME)，オフセット (OFFSET)，参考文献 (REFERENCES)，LINKS，公式
(FORMULA)，例 (EXAMPLE)，サンプルコード (MAPLE，MATHEMATICA，PROG)，
相互参照 (CROSSREFS)，キーワード (KEYWORD)，数列の登録者 (AUTHOR)，ステー
タス (STATUS) が得られる．利用者は，検索結果から入力した数値列がどの数列にあた
るかや参考文献を容易に調べることができる．その他に，公式や一般項も調べることが
可能なため，数式計算の補助的役割も果たしており，数式を用いた研究の支援システム
としても有用な役割を果たしている．加えて，現在新たな数式の登録を利用者からも受
け付けており，数学者共通のデータべースとなっている．
2.3
文字列の生成
オンライン整数列大辞典の文字列版の作成を目指す本研究では，無限文字列を文字列
辞典の対象として考える．無限文字列とは無限に続く文字列であり，ここでは次に述べ
る漸化式による方法，および準同型写像による方法の 2 つの規則によって生成される無
限文字列を考える．生成規則を適用し 0 番目，1 番目，2 番目，. . . ，n 番目，. . . に生成され
る文字列を w0 ，w1 ，w2 ，. . . ，wn ，. . . と表す．
例 1. フィボナッチ文字列は無限文字列であり，w∞ = abaababaabaababaababaabaababaab . . .
となる．w∞ は，w0 = ε，w1 = b，w2 = a，w3 = ab，. . . と文字列を無限に生成することで得
られる文字列である．
2.3.1
漸化式による方法
n 番目の文字列 wn を 1，2，. . . ，n − 1 番目の文字列 w1 ，w2 ，. . . ，wn−1 を用いて定義する．
wn の式で用いる w1 ，w2 ，. . . ，wn−1 について初期値を与えることで，wn ，wn+1 ，wn+2 ，. . .
を再帰的に求めることができる．
例 2. 文字列 wn を次の漸化式で定義する．
6
wn = wn−1 + wn−2 (n ≥ 2)
漸化式の初期値を w1 = b，w2 = a とする．この時，n = 4 まで文字列を生成すると，次
の文字列が生成される．
w1 = b
w2 = a
w3 = w2 + w1 = ab
w4 = w3 + w2 = aba
2.3.2
準同型写像による方法
Σ において，準同型写像 σ : Σ∗ → Σ∗ を考える．準同型写像 σ の定義は次の通りである．
定義 1 (準同型写像). 写像 σ が x, y ∈ Σ∗ に対して，σ(xy) = σ(x)σ(y) が成り立つとき，
写像 σ は準同型写像である．
準同型写像 σ を n 回適用して生成される文字列を wn と表す．
例 3. Σ = {a, b} とし，準同型写像 σ : Σ∗ → Σ∗ を次のように定義する．
σ(a) = ab
σ(b) = a
この準同型写像を用いて生成される n = 4 までの文字列 wn は次の通りである．
w1 = b
w2 = σ(b) = a
w3 = σ(a) = ab w4 = σ(ab) = σ(a)σ(b) = aba
これらの方法によって生成される文字列事典の対象となる文字列の定義について，節 3.4
において詳しく述べる．
7
図 2.1: aababa に対する接尾辞木
2.4
索引構造
文字列の照合を効率良く行うために接尾辞木 [20]，一般化接尾辞木 [8]，ポジションヒー
プ [12] といった索引構造について研究されている．文字列事典では，文字列やアルゴリ
ズムについての辞典としてこれらの索引構造について述べるとともに，文字列の検索部
分でも索引構造として用いる．
2.4.1
接尾辞木
文字列 w$ の接尾辞木とは，1 から |w| + 1 で順番付けされた |w| + 1 個の葉をもつ順序
木である．$ ∈
/ Σ は文字列の終端を表す辞書順最小の文字である．接尾辞木の任意の辺
は w$ の部分文字列をラベルとしてもつ．
例 4. 文字列 aababa$ に対する接尾辞木は図 2.1 となる．
接尾辞木を用いたパターン照合では，根からパターンの文字列を辿っていく．接尾辞木
には，テキストの各位置から始まる接尾辞がすべて含まれているため，パターンを葉まで
辿った場合，その葉の番号がパターンがテキストに出現する位置となる．例えば，図 2.1
の接尾辞木で ba$ というパターンの照合を行うと 5 番目の葉まで辿ることができ，テキ
8
図 2.2: aababa，abab，aabb に対する一般化接尾辞木
ストの 5 番目から出現することがわかる．
2.4.2
一般化接尾辞木
接尾辞木が単一の文字列に対する索引構造であるのに対して，複数文字列に対応させた
のが一般化接尾辞木である．N 個の文字列を含む一般化接尾辞木を構築する際には，各文字
列の後ろに終端記号 $0 ，
$1 ，. . . ，
$N −1 を付与し，連接した文字列 w0 $0 ，w1 $1 ，. . . ，wN −1 $N −1
に対して接尾辞木を構築する．
例 5. 文字列 aababa，abab，aabb の一般化接尾辞木は図 2.2 となる．それぞれ aababa$0 ，
abab$1 ，aabb$2 と終端記号を加え接尾辞木を構築する．
2.4.3
ポジションヒープ
文字列 w のすべての接尾辞を長さの昇順もしくは降順に並べた順序集合に対するシー
ケンスハッシュ木 [10] を文字列 w に対するポジションヒープ [12] と呼ぶ．
例 6. 文字列 aababa に対するポジションヒープは図 2.3 となる．文字列 aababa に終端
記号 $ を加え，降順に並べた順序集合は (aababa$，ababa$，baba$，aba$，ba$，a$) である．
ポジションヒープを構築する際には，順序集合の先頭から順に，木に存在しない最短の
接頭辞を追加していくため，図 2.3 の例では右に示す文字列が，ポジションヒープに追
加される．
9
図 2.3: aababa に対するポジションヒープ
ポジションヒープを用いたパターン照合では，根からパターンの文字列を辿っていく．
この時，パターンをすぺて読み込んだ位置にある頂点番号にあたる文字列はパターンが
すべて出現するといえる．また，パターンで辿る際に通過した頂点は一致する箇所の候
補となる．
例 7. 図 2.3 のポジションヒープを例に考える．パターンを aba として，ポジションヒー
プを辿った際に通過する頂点は 1，2，4 である．ここで，パターンをすべて読み込んだ位
置にあたる 4 番目の順序集合の文字列は aba$ であり，テキストの 4 番目からパターンが
出現することがわかる．一方で，候補となっている 1 番目から始まる文字列は aababa$
であるため出現せず，4 番目から始まる ababa$ には出現することがわかる．
10
第3章
文字列事典
3.1
オンライン文字列事典
文字列に関して，文字列処理を行うアルゴリズムや様々な性質をもった文字列が存在
している．これらの文字列の性質やアルゴリズムについてまとめ，研究支援システムと
してオンライン文字列事典を提案する．
文字列事典のドキュメントの作成には Sphinx [1] を用いる．Sphinx は html や pdf など
に柔軟に出力が可能なドキュメント作成ツールであり，HTML5 や Javascript と組み合わ
せることで対話的な操作や図の描画も可能となる．また，Sphinx は python で作成されて
いるため python との相性が良く，python で記述したソースコードをドキュメントに簡
単に引用できる．そこで文字列事典では主に python でソースコードを記述する．図 3.1
に Sphinx を用いて作成した文字列事典を示す．
本研究で作成する文字列事典では，文字列やアルゴリズムについての辞典，特徴のあ
る文字列の検索の 2 つを主な内容としている．文字列の検索については第 4.1 章で詳細
を述べる．文字列やアルゴリズムについての辞典は以下の 3 つの内容から成る．
1. 文字列処理の基本アルゴリズム
2. データ構造
3. 種々の定義から生成される文字列
本章では，これら 3 つの内容の詳細について述べる．
11
図 3.1: オンライン文字列事典
3.2
文字列処理の基本アルゴリズム
文字列処理の基本アルゴリズムの説明として以下の内容を載せている．
• パターン照合アルゴリズム：素朴な方法，Knuth-Morris-Pratt 法 [11]，Boyer-Moore
法 [9]，Karp-Rabin 法 [14]，· · ·
• 基本的な性質に関するアルゴリズム：周期，境界，回文，連，接頭辞，接尾辞，· · ·
• ソートアルゴリズム：マルチキークイックソート，クイックソート，バブルソート，
マージソート，· · ·
• 圧縮アルゴリズム：連長圧縮，LZ77，· · ·
12
図 3.2: 連長圧縮の表示例
3.2.1
連長圧縮
文字列処理の基本アルゴリズムの説明の例として，圧縮アルゴリズムである連長圧縮
を用いて説明する．連長圧縮とは，元データの連続した記号をその記号と長さを用いて
符号化する手法である．例えば，aabbaaaba という文字列を連長圧縮すると a2b2a3b1a1
となる．逆に圧縮された文字列 a2b2a3b1a1 から，記号および長さを用いると aabbaaaba
という元の文字列を得ることができるため，連長圧縮は可逆圧縮である．
このアルゴリズムについて文字列事典にまとめたものが図 3.2 である．Sphinx を用いる
ことで，python で記述したスクリプトを関数単位で引用することができ実際のコードと
併記してアルゴリズムの説明が記述できる．また，Javascript を用いてユーザの入力に応
じた出力を即座に表示できる仕組みをもつ．作成した連長圧縮のページでは，実際に使用
者が入力した文字列を圧縮する様子を容易に確かめることができる．例えば aaaabbbbccc
という入力を与えると，入力テキストを圧縮した結果である a4b4c3 や圧縮率といった情
報を見ることができる．
圧縮アルゴリズム以外のソートアルゴリズムやパターン照合についても同様に，アル
ゴリズムとコードを併記した説明や，実際に動かすことができるコンテンツを載せてい
る．基本的な性質である周期や境界については，定義だけではなく，入力を与えることに
13
よってその場で値を求められるフォーム，ソートアルゴリズムならば内部で用いるテー
ブルの値やマッチングの様子を描画するなど，実際にアルゴリズムの動く様子を確かめ
ることができる．
3.3
データ構造
データ構造では，接尾辞木，接尾辞配列などの文字列処理に有用なデータ構造や索引
構造の説明として以下の内容を載せている．
• 接尾辞トライ
• 接尾辞木
• 接尾辞配列
• 有向無閉路文字列グラフ (Directed Acyclic Word Graph:DAWG)
• ポジションヒープ
• ウェーブレット木 ..
.
3.3.1
パラメタ化ポジションヒープ
索引構造の説明として図 3.3 に実際の例としてパラメタ化ポジションヒープ [22] の表
示を示す．ここでは入力されたテキストに対するパラメタ化ポジションヒープの描画を
行っている．入力に対する木構造を描画するだけではなく，構造を用いたマッチングの
様子も出力する．図 3.3 では入力をテキスト ababaab，パターン ab として照合を行った
場合に，マッチングする位置を表す {1, 2, 3, 4, 6} の頂点を塗りつぶして区別するように
している．索引構造では特に，木構造などの可視化が理解に役立つと考えられる．構造
を描画することにより，構造の理解が深まることや，自身で図を作る手間の削減などの
効果が見込める．データ構造の説明では，可視化だけではなくデータ構造の定義や構築
アルゴリズムを実際のソースコードと併せて記載している．
14
図 3.3: パラメタ化ポジションヒープの表示例
3.4
種々の定義から生成される文字列
種々の定義から生成される文字列について，以下に挙げるフィボナッチ文字列などの
文字列学の対象となる種々の文字列の定義や性質の説明を載せている．
• フィボナッチ文字列
• トリボナッチ文字列
• シュー・モールス文字列
• Padovan 文字列
• スターミアン文字列
• Paperfolding 文字列
• Rudin-Shapiro 文字列 ..
.
フィボナッチ文字列の説明の様子を図 3.4，図 3.5 に示す．Sphinx では数式の表現に対応
しているため，図 3.4 に示したフィボナッチ文字列の定義の様に数式を用いた定義を容易
に表現することができる．併せて図 3.5 に示す文字列を実際に生成することのできるコ
ンテンツも載せている．図 3.5 では，任意の n を指定することで n 番目のフィボナッチ文
字列を生成することができる．n の値を変えながら観察を行うことにより，文字列の変化
15
図 3.5: フィボナッチ文字列を出力
図 3.4: フィボナッチ文字列の定義
する挙動を確かめることができる．また，それぞれの文字列で初期値として扱っている
部分を指定して生成できるようにすることで，F ib1 = b, F ib2 = a を F ib1 = d, F ib2 = f
とした fdffd といった同じ構造をもつ文字列の観察も可能としている．
文字列事典にまとめている文字列の定義の一部を以下に示す．
3.4.1
フィボナッチ文字列
フィボナッチ文字列 F ibn とは以下の漸化式によって生成される無限文字列である．
F ib0 = ε，F ib1 = b，F ib2 = a
F ibn = F ibn−1 + F ibn−2 (n ≥ 2)
生成される文字列は F ib1 = b，F ib2 = a，F ib3 = ab，F ib4 = aba，F ib5 = abaab，. . . とな
り，文字列の長さの数列 1, 1, 2, 3, 5, ... はフィボナッチ数列となる．フィボナッチ文字列
は漸化式だけではなく以下の準同型写像を用いても生成可能である．
σ(a) = ab
σ(b) = a
初期入力を F ib1 = b とすることで，F ib2 = a，F ib3 = ab とフィボナッチ文字列が生成
される．
16
3.4.2
トリボナッチ文字列
フィボナッチ文字列と似た構造をもつ文字列として隣接 3 項を用いるトリボナッチ文
字列が存在する．トリボナッチ文字列 T ribn は以下の漸化式によって生成される．
T rib0 = ε，T rib1 = a，T rib2 = ab，T rib2 = abac
T ribn = T ribn−1 + T ribn−2 + T ribn−3 (n ≥ 4)
トリボナッチ文字列もフィボナッチ文字列と同様に，準同型写像を用いた生成方法が存
在する [21]．T rib1 = a を初期値として，以下の準同型写像によりトリボナッチ文字列が
生成される．
σ(a) = ab
σ(b) = ac
σ(c) = c
トリボナッチ文字列の各項の長さの数列は 1, 2, 4, 7, 13, 24, ... となり，トリボナッチ数列
として知られている．
3.4.3
スターミアン文字列
スターミアン文字列 Swn とは任意の n 個の整数から成る指示配列 SW = (SW1 , SW2 , ..., SWn )
を用いて Swn−1 を繰り返す回数を指定することにより得られる無限文字列である [16]．
Sw−1 = b，Sw0 = a
Swn = (Swn−1 )SW [n] + Swn−2
ここで，(Swn−1 )SW [n] は Swn−1 を SW [n] 個連接した文字列を表す．SW = (SW1 , SW2 , ..., SWn )
を SW = (1, 1, ..., 1) と指示配列のすべての要素を 1 とすることで Swn = Swn−1 + Swn−2
となり，フィボナッチ文字列を生成することができる [7]．
17
例 8. SW = (1, 3, 2, 1) として生成されるスターミアン文字列は次の通りである．
Sw−1 = b
Sw0 = a
Sw1 = (a)1 + b = ab
Sw2 = (ab)3 + a = abababa
Sw3 = (abababa)2 + ab = abababaabababaab
Sw4 = (abababaabababaab)1 + abababa = abababaabababaababababa
3.4.4
シュー・モールス文字列
シュー・モールス整数列 T mn は T m0 = 0 に対して以下の準同型写像を適用すること
で得られる [13]．
σ(0) = 01
σ(1) = 10
この生成方法を用いる際に，0 → a，1 → b とすることで整数列ではなくシュー・モール
ス文字列を生成できる．また，整数列の場合には T mn は n − 1 番目の文字列と n − 1 番
目の文字列をビット反転させたものを連接することで得ることもできる．
T m0 = 0
T mn = T mn−1 + T mn−1
18
例 9. T m0 = 0 から定義の通りに生成していくと次のような文字列が得られる．
T m0 = 0
T m1 = T m0 + T m0 = 0 + 1 = 01
T m2 = T m1 + T m1 = 01 + 10 = 0110
T m3 = T m2 + T m2 = 0110 + 1001 = 01101001
T m4 = T m3 + T m3 = 01101001 + 10010110 = 0110100110010110
3.4.5
Padovan 文字列
Padovan 文字列とは以下の漸化式から生成される無限文字列である [18]．
P ad0 = a，P ad1 = b，P ad2 = c
P adn = P adn−3 + P adn−2
n ≥ 3 の文字列は P ad3 = ab，P ad4 = ac，P ad5 = cab，P ad6 = abbc，P ad7 = bccab，. . .
となり，Padovan 文字列の長さの数列は 1，1，1，2，2，3，4，5，7，9，. . . である．この数列は
Padovan 数列と呼ばれる．
3.4.6
Paperfolding 文字列
Paperfolding 文字列 P fn とは初期値 P f0 = a に対して以下の準同型写像 σ を適用する
ことで得られる無限文字列である [3]．
σ(a) = ab
σ(b) = cb
σ(c) = ad
σ(d) = cd
19
得られた文字列に対して以下の準同型写像 δ を適用すると，Paperfolding 数列を得るこ
とができる．
δ(a) = 0
δ(b) = 0
δ(c) = 1
δ(d) = 1
例 10. P f0 = a に σ を適用して得られる文字列のうち，P f3 までの文字列は次の通りで
ある．
P f0 = a
P f1 = ab
P f2 = abcb
P f3 = abcbadcb
この得られた文字列に対して．準同型写像 δ を適用することで得られる Paperfolding 数
列は次の通りである．
P f0 = 0
P f1 = 00
P f2 = 0010
P f3 = 00100110
また，Paperfolding 数列 P f = 001001100 · · · の先頭から第 n 番目の項 P f [n] の値は以
20
下の式から導かれる値となる．
0
n = 4m
P f [n] = 1
n = 4m + 2
P f [m] n = 2m + 1
3.4.7
Rudin-Shapiro 文字列
Rudin-Shapiro 文字列 RSn とは RS0 = a に対して以下の準同型写像 σ を適用すること
で得られる無限文字列である [15]．
σ(a) = ab
σ(b) = ac
σ(c) = db
σ(d) = dc
得られた文字列に対して以下の準同型写像 δ を適用することで，Rudin-Shapiro 数列を得
ることができる．
δ(a) = 1
δ(b) = 1
δ(c) = −1
δ(d) = −1
例 11. RS0 = a に σ を適用して得られる文字列のうち，RS3 までの文字列は次の通りで
21
ある．
RS0 = a
RS1 = ab
RS2 = abac
RS3 = abacabdb
この得られた文字列に対して，準同型写像 δ を適用することで得られる Rudin-Shapiro 数
列は次の通りである．
RS0 = 1
RS1 = 11
RS2 = 111 − 1
RS3 = 111 − 111 − 11
Rudin-Shapiro 数列 RS = 111 − 111 − 111 · · · の先頭から第 n 番目の項 RS[n] は，n を
∑
2 進数に変換した値 n = (ϵk , ϵk−1 , . . . , ϵ1 , ϵ0 ) から a(n) = k−1
i=0 ϵi · ϵi−1 を計算した結果を
用いて以下の式で表現できる．
RS[n] = (−1)a(n)
3.4.8
Baum-Sweet 文字列
Baum-Sweet 文字列 BSn は BS0 = A に次の準同型写像 h を適用することで生成され
る [4, 6]．
22
h(A) = AB
h(B) = CB
h(C) = BD
h(D) = DD
例 12. 初期値 BS0 = A から順に h を適用していくことで以下の文字列が得られる．
BS0 = A
BS1 = AB
BS2 = ABCB
BS3 = ABCBBDCB
BS4 = ABCBBDCBCBDDBDCB
BS0 = A に h を適用していくと，BSn = ABCBBDCBCBDDBDC . . . という文字列が
得られる．この文字列に対して，準同型写像 τ を適用することで 0，1 から成る Baum-Sweet
数列が生成される．
τ (A) = 1
τ (B) = 1
τ (C) = 0
τ (D) = 0
23
3.4.9
Period-doubling 文字列
Period-doubling 文字列の定義は次の通りである [4]．初期値 P d0 = 0 に対して以下の
準同型写像を適用することで得られる．
σ(0) = 01
σ(1) = 00
例 13. 生成される P dn は以下の通りである．
P d0 = 0
P d1 = 01
P d2 = 0100
P d3 = 01000101
この定義から生成される Period-doubling 文字列は P dn = 010001010100010 . . . となる．
Period-doubling 文字列の最小周期 period(P dn ) はその名の通り，P d0 ，P d1 ，P d2 ，. . . の順
に 1，2，4，8，16，. . . と 2 倍に増えていく．
3.4.10
ハノイ文字列
ハノイの塔と呼ばれるパズルゲームの解を文字列で表現することができる [4]．ハノイ
の塔は図 3.6 の様に３か所の棒と移動させる円盤があり，左端の棒から右端の棒へと円
盤を動かすことを目的とするゲームである．移動の際には，円盤を 1 つずつ動かす，小
さい円盤の上に大きい円盤は置けないという制約の元で移動を行う．この移動円盤の移
動を文字列によって表現する．棒の位置を左から A，B ，C とすると，A → B ，A → C ，
B → C ，B → A，C → A，C → B の 6 通りの移動が考えられる．それぞれの移動を a，
24
図 3.6: ハノイの塔
b，c，a，b，c とする．円盤の枚数を 2N 枚としたときの解法は次の式で表される．
H0 = ε
H2N +1 = H2N aσ −1 (H2N ) (N ≥ 0)
H2N = H2N −1 cσ(H2N −1 ) (N ≥ 1)
ここで，σ ，σ −1 は以下の通りである．
σ(a) = b，σ(b) = c，σ(c) = a，σ(a) = b，σ(b) = c，σ(c) = a
σ −1 (a) = c，σ −1 (b) = a，σ −1 (c) = b，σ −1 (a) = c，σ −1 (b) = a，σ −1 (c) = b
例 14. N = 1 の時に生成される文字列は次の通りである.
H2 = acb
H3 = acbabac
H2 は円盤を 2 枚用いる時の解であり，その動きは図 3.7 の様になる．
3.5
種々の定義から生成される文字列の性質
上に挙げた無限文字列は規則に従って生成されるだけではなく，それぞれ特徴的な性
質をもつ．文字列事典では文字列の定義のみではなく，各文字列がもつ性質についても
25
図 3.7: ハノイの塔 H2 の挙動
まとめている．ここでは，文字列がもつ性質として文字列事典に載せている内容の一部
について述べる.
文字列の性質の 1 つである回文 (最初から読んでも最後から読んでも同じ文字列とな
る文字列) に関する性質をもつ文字列が複数存在する．フィボナッチ文字列では F ibn の
最後の 2 文字を取り除く，もしくは最後の 2 文字の順番を逆にしたものを文字列の最初
に付け加えると回文となる性質をもつ．また，Paperfolding 文字列，Rudin-Shapiro 文字
列を数列にしたものに含まれる回文の長さはそれぞれ {0, 1, 2, 3, 4, 5, 6, 7, 9, 11, 13}(n ≥
5),{0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14}(n ≥ 6) のみとなることが証明されている [3]．
また，シュー・モールス文字列について次の性質が成り立つ．シュー・モールス文字
列 T mn に含まれる回文の最大の長さは，n が偶数の時 |T mn |，n が奇数の時 |T mn−1 | と
なる．これは，シュー・モールス文字列が 1 文字の文字列，つまり回文から始まり，そ
れ以降は反転させた文字列と連接していくことにより生成していくため，T mn 自体が回
文，回文ではない文字列が交互に生成されることから明らかである．
その他の性質についても，例えばスターミアン文字列に対して，スターミアン文字列
中の 2 回繰り返しである square の最大数についての研究 [16] や 3 回繰り返しである cube
の数の研究 [17] などの文字列の繰り返し構造についての性質が示されている．
26
第4章
文字列の検索
4.1
文字列の検索
本研究ではオンライン整数列大辞典を参考にし，節 3.4 で挙げた無限文字列から検索
できるシステムの構築を目指す．例えば baa という文字列を検索すると，この文字列は
n ≥ 5 のフィボナッチ文字列やシュー・モールス文字列中に出現するといった情報の検
索を考える．しかし，定義上で F ib1 = b，F ib2 = a としているが，これらの初期値を別
の文字に置き換えた場合でも F ibn = F ibn−1 + F ibn−2 の生成規則に従って文字列を生成
することでフィボナッチ文字列と同じ性質をもつ文字列が得られる．例えば，F ib1 = y，
F ib2 = x とすると F ib6 = xyxxyxyx，F ib1 = c，F ib2 = g とすると F ib6 = gcggcgcg と
いう文字列が生成される．これらの文字列は用いられている文字が異なるものの，共に
フィボナッチ文字列の漸化式から生成されているため，F ib6 = abaababa と同じ構造を
もつ文字列である．このため，本研究で作成する文字列の検索システムでは，一意に定
まる整数列に対するデータベースである整数列大事典の検索システムとは異なり，文字
列が異なるものの同じ構造をもつ文字列も検索対象として考える必要がある．
また，文字の組み合わせの問題とは別の問題として．文字列事典で取り扱う文字列が
無限文字列であるということが挙げられる．無限の文字列をデータベースとして作成す
ることはできないため，無限文字列をある n まで生成した有限の文字列を用いる必要が
ある．この生成した文字列中に，本来その無限文字列に出現しているはずの文字列が過
不足なく出現しているかどうかが問題点となる．
本章では，これら 2 つの問題点の解決策および実際に文字列事典で作成する検索シス
27
テムの紹介をする．
4.2
パラメタ化照合
ここでは，まず 1 つ目の問題である文字が異なるが構造が同じ文字列の検索に対する
問題に対する解決策について述べる．
4.2.1
素朴な手法
異なる文字から成る文字列と同じ構造をもつ文字列を探す素朴な手法としては，含ま
れる文字列を置き換えて照合を行う手法が考えられる．パターン中の文字を各無限文字
列に含まれる文字列へ置換しパターン照合を行うことで，異なる文字からなる文字列と
同じ構造をもつ文字列を見つけることが可能となる．例としてパターン cdc を考える．
c → a，d → b とすると aba，c → b，d → a とすると bab をパターンとした検索を行う．
ここで，テキストを F ib6 = abaababa とした場合，aba は 0，3，5 番目，bab は 4 番目に
出現するため，cdc はフィボナッチ文字列であると判断される．しかし，この素朴な手法
による照合ではパターン中に含まれるアルファベットの種類数を |Σ| とすると，すべての
パターンで検索するためには |Σ|! 通りの置き換えを考える必要が生じる．
4.2.2
パラメタ化照合
文字列の構造に着目した照合を行う手法としてパラメタ化照合 [5] が Baker によって提
案された．パラメタ化照合は，ソフトウェアのメンテナンス，プログラムの剽窃の発見，
RNA の構造照合などに使われる．
固定するアルファベットを Σ，置き換えを考えるアルファベットを Π とし，Σ ∪ Π 上
の文字列をパラメタ化文字列とする．
定義 2 (パラメタ化一致). 2 つのパラメタ化文字列に対して，Π から Π への全単射が存
在するとき 2 つのパラメタ化文字列はパラメタ化一致するという．
パラメタ化照合を効率良く行うために prev 符号 [5] を考える．prev 符号とは以下の定
義にしたがってパラメタ化文字列を符号化したものである．
28
定義 3 (prev 符号化).
T [i] T [i] ∈ Σ
T ⟩[i] = 0
⟨T
T [i] ∈ Π and T [i] ̸= T [j] f or any 1 ≤ j < i
i − k T [i] ∈ Π and k = max{j : T [j] = T [i] and a ≤ j < i}
2 つのパラメタ化文字列を prev 符号化した文字列が一致する場合にもパラメタ化一致
すると言える．
例 15. Σ = {a, b}，
Π = {x, y}，パラメタ化文字列 t 1 = axbyxax，t 2 = aybxyay とす
る．この時，t 1 ，
t 2 を prev 符号化した ⟨tt1 ⟩，⟨tt2 ⟩ は ⟨tt1 ⟩ = a0b03a2，⟨tt2 ⟩ = a0b03a2 となり，
⟨tt1 ⟩ = ⟨tt2 ⟩ であるため，t 1 ，
t 2 はパラメタ化一致する．
文字列事典では検索する対象として種々の定義から生成される文字列中のすべての文
字に対して置き換えを考える．つまり，文字列中のすべての記号を Π と考えたパラメタ
化文字列の照合を考える．
4.2.3
索引構造を用いたパラメタ化照合
文字列の検索をするにあたって，索引構造を作成することで高速な検索が可能となる．
本研究では索引構造としてパラメタ化ポジションヒープ [22] を用いる．この索引構造はポ
ジションヒープ [12] をパラメタ化文字列に拡張した索引構造であり，パラメタ化文字列を
prev 符号化した文字列に対してポジションヒープの構築を行う．例として図 4.1，図 4.2，
図 4.3 に F ib5 = abaab，T M3 = abbabaab，T rib3 = abac の各文字列に対するパラメタ
化ポジションヒープを示す． 頂点には何文字目からの接頭辞であるかの値，辺には遷移
する記号が付されている．prev 符号化したパターンをパラメタ化ポジションヒープを辿
ることによって，そのパターンが出現しているかどうか調べることができる.
4.3
パラメタ化ポジションヒープの一般化
文字列事典の検索では，検索対象として 1 つの文字列ではなくフィボナッチ文字列，ス
ターミアン文字列，· · · と文字列事典に含まれているすべての文字列を検索対象とする
29
図 4.1: F ib5 に対するパラ 図 4.2: T M3 に対するパラ 図 4.3: T rib3 に対するパ
メタ化ポジションヒープ メタ化ポジションヒープ ラメタ化ポジションヒープ
ため，索引構造を 1 つの文字列ごとにもつのではなく，複数文字列で考える必要がある．
そこで，接尾辞木を複数の文字列に対応させた一般化接尾辞木 [8] の様にパラメタ化ポジ
ションヒープを一般化した一般化パラメタ化ポジションヒープを提案する．文字列事典
の検索では，文字列事典に載せている文字列をすべて含む一般化パラメタ化ポジション
ヒープを索引構造として検索を行う．
4.3.1
一般化パラメタ化ポジションヒープの構築
ポジションヒープを構築する際には，存在する辺に含まれない最短の接頭辞を追加し
ていくため，1 つの文字列に対して構築したものと複数の文字列をまとめたものとでは同
じ文字列の位置を示す頂点の辺のラベルが異なる辺も存在する．また，同じラベルをも
ち頂点が重複しているために区切り文字 $ ∈
/ Σ で辺を構築していた部分について，複数
の文字列に拡張したことによって 3 つ以上の頂点をもつことがある．この場合には $ で
遷移させていた部分を，文字列を追加した順に $0 , $1 , ..., $T −1 と異なる区切り文字を用い
て区別する．
複数文字列から成るパラメタ化ポジションヒープの構築アルゴリズムを Algorithm 1
に示す．パラメタ化ポジションヒープの構築アルゴリズム [22] を複数文字列に拡張する
ため，入力として T 個のパラメタ化文字列から成るリスト [S0 , S1 , ..., ST −1 ] を考える．ま
ず，1 つの文字列 Sn に対して重複した頂点をもたない状態のパラメタ化ポジションヒー
プを構築する．Sn での構築を行った後に，そこで構築されたポジションヒープに対して
次の文字列 Sn+1 を読み込み，更新していく．追加しようとする文字列がすべて存在する
場合には，区切り文字 $0 , $1 , . . . を追加する文字列の後ろに連接し，重複頂点の無いよう
30
Algorithm 1: 一般化パラメタ化ポジションヒープ構築アルゴリズム
Input: 要素数 |T | のパラメタ化文字列のリスト T = [S0 , S1 , ..., S|T |−1 ]
Output: パラメタ化ポジションヒープ PPH (tt)
1 create root and ⊥ nodes;
2 psp(root) =⊥;
3 for each character c，create edge (⊥, c, root);
4 for i = 0 to |T | − 1 do
5
currentN ode = root;
6
t = T [i];
7
s = textlen + 1;
8
for j = 1 to |t| do
9
if t [j] ∈ Π then
10
next[j] = 0;
11
if lastOccur[tt[j]] = undefined then
12
prev [j] = 0;
15
else
prev [j] = j − lastOccur[tt[j]];
next[j − prev [j]] = prev [j];
16
lastOccur[tt[j]] = j ;
13
14
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
else
prev [j] = t [j], next[j] = t [j];
lastCreateN ode = undefined;
while not exist edge (currentN ode, prev [j], nextN ode) do
create node psprefs ;
create edge (currentN ode, prev [j], psprefs );
if lastCreateN ode ̸= undefined then
psp(lastCreateN ode) = psprefs ;
lastCreateN ode = psprefs ;
currentN ode = psp(currentN ode);
if t [s] ∈ Π then
if next[s] > 0 then
prev [s + next[s]] = 0;
else
lastOccur[tt[s]] = undefined;
s = s + 1;
35
currentN ode = nextN ode;
if lastCreateN ode ̸= undefined then
psp(lastCreateN ode) = currentN ode;
36
textlen = textlen + |t|;
33
34
31
図 4.4: 文字列のリスト [abaab，abac，abbabaab] に対する一般化パラメタ化ポジション
ヒープ
に構築をしていく．また，文字列の位置を表す頂点の値はリスト [S0 , S1 , ..., ST −1 ] に含ま
れる文字列をすべて連接した文字列 S0 S1 ...ST −1 の先頭からの位置で数えることとする．
図 4.1，図 4.2，図 4.3 の索引構造を 1 つにまとめた索引構造が図 4.4 となる．
4.3.2
一般化パラメタ化ポジションヒープによるパターン照合
一般化パラメタ化ポジションヒープで文字列の照合を行う際には，ポジションヒープ
と同様に，根の位置からパターンを辿っていく．通過した頂点を照合位置の候補に，パ
ターンを読み込んだ位置にある頂点を一致箇所とすることで，ポジションヒープと同様
の照合を行える．一般化パラメタ化ポジションヒープでは，区切り文字が $0 , $1 , ..., $T −1
と複数存在する点がポジションヒープとは異なるが，パターンを読み込む際に通過した
頂点と繋がっている区切り文字で遷移する頂点を照合の候補とすることですべての照合
が可能である．
32
4.4
無限文字列に含まれる部分文字列
オンライン文字列事典では，フィボナッチ文字列をはじめとする無限文字列を検索対
象とするため，索引構造を作る際にどこまでの文字列を考慮するかが問題となる．そこ
で，無限文字列 wn ，wn+1 を生成し，wn と wn+1 に含まれる部分文字列の差を調べる．wn
に出現しないが，wn+1 に出現する部分文字列を調べることで，索引構造を作成した際に
検索されない文字列を求めることができる．
例 16. フィボナッチ文字列に含まれる部分文字列を例に考える．
n = 5 とすると，F ib5 = abaab，F ib6 = abaababa であり，それぞれの部分文字列は次の
通りである．
substring(F ib5 ) = {a, b, ab, ba, aa, aba, baa, aab, abaa, baab, abaab}
substring(F ib6 ) = {a, b, ab, ba, aa, aba, baa, aab, aba, bab,
abaa, baab, aaba, abab, baba, abaab, baaba,
aabab, ababa, abaaba, baabab, aababa,
abaabab, baababa, abaababa}
substring(F ib5 )，substring(F aib6 ) を比較すると bab など太字の部分文字列が substring(F ib5 )
に出現しないことがわかる．同時に，長さ 3 未満の部分文字列は substring(F ib5 ) でも出
現していることがわかる．
フィボナッチ文字列について，F ibn に含まれる部分文字列の長さごとに出現する種類
数を求めた結果が表 4.1，図 4.5，図 4.6 である．F ibn と比較して，F ibn+1 では F ibn に
出現する部分文字列に加えて新たに別の部分文字列が出現している．また，長さの短い
部分文字列について wn+1 ，wn+2 ，. . . と増やしていった際に，wn で出現している種類数を
超えない結果となった．
また，フィボナッチ文字列以外の文字列について，各 n の値における部分文字列の長
さごとの種類数の解析結果を図 4.7，図 4.8，図 4.9，図 4.10，図 4.11，図 4.12，図 4.13，
図 4.14，図 4.15，図 4.16，図 4.17 に示す．フィボナッチ文字列以外の文字列でも出現
33
400
部分文字列の種類数
350
300
250
200
150
100
50
0
200
400
600
800
1000
n=0
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n=10
n=11
n=12
n=13
n=14
n=15
n=16
部分文字列の長さ
図 4.5: フィボナッチ文字列 F ibn の部分文字列の長さごとの種類数
200
180
部分文字列の種類数
160
140
120
100
80
60
40
20
0
50
100
150
200
n=0
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n=10
n=11
n=12
n=13
n=14
n=15
n=16
部分文字列の長さ
図 4.6: フィボナッチ文字列 F ibn の部分文字列の長さごとの種類数 (抜粋)
34
表 4.1: F ibn に含まれる部分文字列の長さごとの種類数
HH
HH n 1 2 3 5 6 7
8
9
長さ HHH
1
2
3
4
5
6
7
8
9
10
11
1
-
1
-
2
1
-
2
2
1
-
する部分文字列の種類数に同じ特徴が見られた．
2
3
3
2
1
-
2
3
4
5
6
7
7
6
5
4
3
2
3
4
5
6
7
8
9
10
10
10
2
3
4
5
6
7
8
9
10
11
12
35
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n=10
n=11
n=12
n=13
n = 14
n = 15
3000
種類数
2500
2000
1500
1000
500
0
0
1000
2000
3000
4000
5000
6000
Tm
6000
5000
4000
種類数
Trib
3500
3000
2000
1000
0
0
2000
部分文字列の長さ
4000
6000
8000
n=0
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n = 10
n = 11
n = 12
n = 13
部分文字列の長さ
図 4.7: トリボナッチ文字列 T ribn の部分文 図 4.8: シュー・モールス文字列 T mn の部
分文字列の長さごとの種類数
字列の長さごとの種類数
種類数
Pad
n=0
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n = 10
n = 11
n = 12
n = 13
n = 14
2000
1800
1600
1400
1200
1000
800
600
400
200
0
0
500
1000
1500
2000
2500
部分文字列の長さ
図 4.9: Padovan 文字列 P adn の部分文字列の長さごとの種類数
Hanoi
Pd
8000
7000
種類数
6000
5000
4000
3000
2000
1000
0
5000
10000
部分文字列の長さ
15000
n=0
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n = 10
n = 11
n = 12
n = 13
n = 14
3500
種類数
9000
0
3000
n=0
2500
n=1
n=2
2000
n=3
1500
n=4
1000
n=5
500
n=6
n=7
0
0
1000
2000
3000
4000
部分文字列の長さ
図 4.10: Period-doubling 文字列 P dn の部分 図 4.11: ハノイ文字列 Hanoin の部分文字
文字列の長さごとの種類数
列の長さごとの種類数
36
12000
種類数
10000
8000
6000
4000
2000
0
0
5000
10000
15000
部分文字列の長さ
n=0
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n = 10
n = 11
n = 12
n = 13
n = 14
Pf(01)
n=0
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n = 10
n = 11
n = 12
n = 13
n = 14
14000
12000
10000
種類数
Pf
14000
8000
6000
4000
2000
0
0
5000
10000
15000
20000
部分文字列の長さ
図 4.12: Paperfolding 文字列 P fn の部分文 図 4.13: Paperfolding 文字列 P f (01)n の部
分文字列の長さごとの種類数
字列の長さごとの種類数
12000
種類数
10000
8000
6000
4000
2000
0
0
5000
10000
15000
n=0
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n = 10
n = 11
n = 12
n = 13
n = 14
RS(01)
14000
12000
10000
種類数
RS
14000
8000
6000
4000
2000
0
0
5000
部分文字列の長さ
10000
15000
n=0
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n = 10
n = 11
n = 12
n = 13
n = 14
部分文字列の長さ
図 4.14: Rudin-Shapiro 文字列 RSn の部分 図 4.15: Rudin-Shapiro 文字列 RS(01)n の
文字列の長さごとの種類数
部分文字列の長さごとの種類数
BS(01)
BS
9000
12000
8000
n=0
10000
n=1
6000
8000
n=2
n=3
6000
n=4
n=2
種類数
種類数
n=0
7000
n=1
5000
n=3
4000
n=4
3000
4000
n=5
2000
n=6
1000
0
n=7
0
0
5000
10000
部分文字列の長さ
15000
n=8
n=5
2000
n=6
n=7
0
5000
10000
15000
n=8
部分文字列の長さ
図 4.16: Baum-Sweet 文字列 BSn の部分文 図 4.17: Baum-Sweet 文字列 BS(01)n の部
字列の長さごとの種類数
分文字列の長さごとの種類数
37
Algorithm 2: 出現しない部分文字列の最小の長さを求めるアルゴリズム
Input: n
Output: wn+1 に出現するが，wn には出現しない部分文字列の最小の長さ min
1 generate wn and wn+1 , min = −1;
2 while i = 1 to |wn | and min = -1 do
3
substrn = [];
4
for j = 1 to |wn | − i do
5
if wn [i : j + i] ̸∈ substrn then
6
Add wn [i : j + i] to substrn ;
7
8
9
10
for j = 1 to |wn+1 | − i do
if wn+1 [i : j + i] ̸∈ substrn then
min = |wn+1 [i : j + i]|;
return min;
このように，ある n において，どの長さまでの部分文字列をすべて含んでいるかを求
め，その文字列を用いることで，検索するパターンに対して十分に長い文字列をもった
索引構造を構築することができる．含まれる部分文字列の差を求める際には，部分列の
長さごとに処理を行う．Algorithm 2 に含まれる部分文字列の差の最小の長さを求めるア
ルゴリズムを示す．
まず，wn の部分文字列 wn [i : j] を長さの短いものから wn の先頭から順に重複を除い
て列挙する．列挙した wn の部分文字列 wn [i : j] に対して wn+1 中の同じ長さをもつ部分
文字列 wn+1 [i : j] を先頭から比較していき，wn 中にはない部分文字列が出現した場合，
その長さを出現しない部分文字列の最小の長さとする．
種々の定義から生成される文字列それぞれについて求めた結果が表 4.2，図 4.18，図 4.19
である．P f (01)，RS(01)，BS(01) はそれぞれ，Paperfolding 数列，Rudin-Shapiro 数列，
Baum-Sweet 数列を表す．表 4.2，図 4.18 より，大半の文字列が n = 12 前後で 200 文字程
度の部分文字列を含むことがわかる．同じ n の値でも生成される文字列の長さが異なるた
め，図 4.19 では x 軸に wn の長さ |wn | を取っている．長さで考えた場合には |wn | = 5000
程度が十分な長さであった．表 4.2 中の太字になっている数値を取る n の値を，文字列
事典の索引構造として用いた．また，表 4.2 には示していないが，Padovan 文字列では
最小値 202 となる n = 28 を用いた．
38
表 4.2: wn+1 に含まれるが wn に含まれない部分文字列の長さの最小値
HH
H文字列
HH
n
HH
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Fib
1
1
2
2
3
5
7
10
15
23
36
57
91
146
235
379
612
989
1599
2586
4183
6767
Trib
Tm
Pf Pf(01)
1
1
1
2
1
1
2
1
2
4
2
3
6
3
5
10
5
9
18
9
16
34
17
29
66
33
53 130
65
97 258 129
178 514 257
327 1026 513
601 2050 1025
1105 4098 2049
2032
3737
6873
-
RS RS(01) Pad
1
1
1
2
1
3
2
3
3
5
4
9
6
17
10
33
18
65
34
129
66
257 130
513 258
1025 514
2049 1026
-
1
2
2
4
4
6
10
18
34
66
130
258
514
1026
-
BS BS(01)
1
1
1
1
1
1
1
2
1
3
2
4
2
6
2
10
2
18
2
34
2
66
3 130
4 256
5 514
6 1026
7 2050
9
11
14
18
23
30
39
-
Pd
H
1
1
2
1
2
3
3
3
4
9
3
6
33
6
10 129
9
18 513
16
34 2049
25
66
40 130
73 258
136 514
265 1026
520 2050
1033 4098
-
39
出現しない部分文字列の長さの最小値
7,000
Fib
6,000
Trib
Tm
5,000
Pf
4,000
Pf(01)
RS
3,000
RS(01)
Pad
2,000
BS
BS(01)
1,000
Pd
H
0
10
20
30
40
n
図 4.18: wn+1 に含まれるが wn に含まれない部分文字列の長さの最小値
出現しない部分文字列の長さの最小値
7,000
Fib
6,000
Trib
Tm
5,000
Pf
4,000
Pf(01)
RS
3,000
RS(01)
2,000
Pad
BS
1,000
BS(01)
Pd
0
5000
10000
15000
20000
25000
30000
35000
40000
H
n番目に生成される文字列wnの長さ|wn|
図 4.19: wn+1 に含まれるが wn に含まれない部分文字列の長さの最小値
40
図 4.20: パラメタ化ポジションヒープを用いた文字列の検索
4.5
文字列事典における文字列の検索
文字列事典に追加されている文字列すべてを含んだパラメタ化ポジションヒープを索引
構造として，検索機能を作成する．また，索引構造に用いる文字列は図 4.18，図 4.19 の
結果を元に，パターンの長さが 200 程度の文字列に対応できる n で生成した文字列 wn を
用いる．索引構造を用いて入力されたパターンの検索を行うと一致する頂点の値を求める
ことができる．この求めた値は，入力とした文字列のリスト [S0 , S1 , ..., ST −1 ] に含まれる
文字列をすべて連接した S0 S1 ...ST −1 の文字列の先頭からの位置となる．[S0 , S1 , ..., ST −1 ]
の各文字列の長さを用いて，どの文字列のどの位置に出現するか求めることができる．
図 4.20 に，文字列事典上に作成したパラメタ化照合による検索機能を示す．Sphinx 自
体に元々実装されている全文検索と同時に入力した文字列を含む文字列が存在するか検
索する．検索結果として，どの文字列か，出現している文字列の生成した長さの中での
すべての出現位置，そして，それぞれの文字列の説明ページへのリンクを表示している．
41
第5章
まとめと今後の課題
5.1
まとめ
本研究では，現在提供されているオンライン整数列大辞典を元に，文字列学の支援シ
ステムとして，文字列に関するアルゴリズムやデータ構造についてまとめたオンライン
文字列事典1 を提案した．オンライン文字列事典の作成のために，フィボナッチ文字列を
はじめとした種々の定義から生成される文字列の定義や性質および文字列処理に関係す
るアルゴリズムの調査を行った．加えて，無限文字列の検索を行うために，文字列に含
まれる部分文字列を調べ，wn による種類数の違いを求め，索引構造の作成を行った．無
限文字列などの特徴ある文字列のデータベースの作成を行い，検索機能作成のためにパ
ラメタ化ポジションヒープを用いた複数の文字列に対する索引構造として一般化パラメ
タ化ポジションヒープを提案した．
5.2
今後の課題
今後の課題として，フィボナッチ文字列の様な特徴のある文字列や文字列処理に関す
るアルゴリズムなどの追加によるコンテンツの充実が挙げられる．無限文字列について，
アルファベットサイズを大きくした場合について漸化式や準同型写像を用いて生成し，そ
の性質について調査していくことにより，新たな文字列の発見にもつながると考えられ
る．さらに，各々のコンテンツについて現在行われている研究のサーベイを行い詳細な
性質を追加していくこと，アルゴリズムやデータ構造が実際にどのような場面で役立て
1
http://www.shino.ecei.tohoku.ac.jp/stringology/にて公開中
42
られているかなどの情報を追加していくことなども重要である．
43
参考文献
[1] Overview - sphinx 1.1.3 documentation, 2013. http://sphinx-doc.org/ (2014/1/7).
[2] オンライン整数列大辞典, 2013. http://oeis.org/?language=japanese (2014/1/7).
[3] J.-P. Allouche. Schrodinger operators with rudin-shapiro potentials are not palindromic. American Institute of Physics, 1997.
[4] Jean-Paul Allouche and Jeffrey Shallit. Automatic sequences: theory, applications,
generalizations. Cambridge university press, 2003.
[5] Brenda S Baker. A theory of parameterized pattern matching: algorithms and
applications. In Proceedings of the twenty-fifth annual ACM symposium on Theory
of computing, pp. 71–80. ACM, 1993.
[6] Leonard E Baum and Melvin M Sweet. Continued fractions of algebraic power series
in characteristic 2. The Annals of Mathematics, Vol. 103, No. 3, pp. 593–610, 1976.
[7] Jean Berstel. Sturmian and episturmian words. In Algebraic Informatics, pp. 23–47.
2007.
[8] Paul Bieganski, John Riedl, JV Cartis, and Ernest F Retzel. Generalized suffix trees
for biological sequence data: Applications and implementation. In Proceedings of
the Twenty-Seventh Hawaii International Conference on System Sciences, Vol. 5,
pp. 35–44. IEEE, 1994.
[9] Robert S Boyer and J Strother Moore. A fast string searching algorithm. Communications of the ACM, Vol. 20, No. 10, pp. 762–772, 1977.
44
[10] Edward G Coffman Jr and J Eve. File structures using hashing functions. Communications of the ACM, Vol. 13, No. 7, pp. 427–432, 1970.
[11] Maxime Crochemore and Wojciech Rytter. Jewels of stringology. World Scientific,
2003.
[12] Andrzej Ehrenfeucht, Ross M McConnell, Nissa Osheim, and Sung-Whan Woo.
Position heaps: A simple and dynamic text indexing data structure. Journal of
Discrete Algorithms, Vol. 9, No. 1, pp. 100–121, 2011.
[13] Ralph
E
Griswold.
The
morse-thue
sequence,
2002.
http://www.cs.arizona.edu/patterns/weaving/webdocs/gre mt.pdf (2014/1/7).
[14] Richard M Karp and Michael O Rabin. Efficient randomized pattern-matching
algorithms. IBM Journal of Research and Development, Vol. 31, No. 2, pp. 249–260,
1987.
[15] M. Lothaire. Applied Combinatorics on Words (Encyclopedia of Mathematics and
Its Applications). Cambridge University Press, 2005.
[16] Marcin Pi and Wojciech Rytter. Asymptotic behaviour of the maximal number of
squares in standard sturmian words. In Prague Stringology Conference 2009, pp.
237–248, 2009.
[17] Marcin Pi and Wojciech Rytter. The number of cubes in sturmian words. In Prague
Stringology Conference 2012, pp. 89–102, 2012.
[18] Jamie Simpson. Modified padovan words and the maximum number of runs in a
word. The Australasian Journal of Combinatorics, Vol. 46, pp. 129–145, 2010.
[19] Neil JA Sloane, et al. The on-line encyclopedia of integer sequences. Notices of the
American Mathematical Society, Vol. 50, No. 8, pp. 912–915, 2003.
[20] Peter Weiner. Linear pattern matching algorithms. In Annual Symposium on Switching and Automata Theory, pp. 1–11. IEEE, 1973.
45
[21] 佐々木崇人, 大崎嗣豊, 石野明, 篠原歩. 無限 n-ボナッチ文字列の繰り返し構造につい
て. 電子情報通信学会技術研究報告. COMP, コンピュテーション, Vol. 107, No. 24,
pp. 55–61, 2007.
[22] 大友雄平, 成澤和志, 篠原歩. 種々のパターン照合問題に対するポジションヒープの
構築. 電子情報通信学会技術研究報告. COMP, コンピュテーション, Vol. 112, No.
340, pp. 7–14, 2012.
46
謝辞
学士，博士前期課程の 3 年間という長期にわたり，このような研究の場を与えて頂くと
ともに，本論文をまとめるにあたり，指導教員として多くのご教示，ご鞭撻を賜りまし
た東北大学 大学院情報科学研究科 篠原 歩 教授，ならびに成澤 和志 助教に厚く御礼申
し上げます．
また，本論文審査の副審査員を務めて頂きました，東北大学 大学院情報科学研究科 乾
健太郎 教授，ならびに東北大学 大学院情報科学研究科 木下 賢吾 教授には，御専門の立
場から的確なご助言や貴重なご意見を賜りましたことを，心から御礼申し上げます．
そして，日頃の研究室での活動全般にわたりご支援頂いた，東北大学 大学院情報科学
研究科 篠原研究室の皆様に心から感謝申し上げます．最後に，博士前期課程に進学する
機会を与えて下さり，長い間，最後まで信じて見守ってくださった家族，私生活におい
ていつも温かく支えてくれた友人一同に，深く感謝いたします．
© Copyright 2024 ExpyDoc
