1つの長文から多数の言葉を探す方法。
自動リンクで使うアルゴリズム。
グラフ生成 † 
単語1件追加と単語1件削除の繰り返し。
グラフに単語1件追加 †
- ノード生成
与えられた単語→Unigram列。そのままの順序でノード化。
辞書語の2文字目へのノード辞書も用意。
リンク先のほうからリンク元を探すときに使う。
削除 †
ノード消す。ただし他の単語末尾を含まないこと。単語末尾から先頭方向は他の単語と共有していたノードなので消せない。
消したノードに刺さっていたリンクも消す。
リンクの探し方…はじめから双方向にしておくか、探索。
刺さっていたgotoリンクなら消すノードを探した時に見つかっているはず。
刺さっていたfailureリンクはfailure先→元探索で探す。
ノードの型 †
- string
状態遷移条件の文字を集めてそれを代わりにできるが、文字同一視するためには必要。
単語末尾（単語発見と見なすタイミング）でないなら空文字列。 - goto
次のノード辞書。遷移条件文字→ノードリファレンスかノードID - failure
goto不可能な場合の遷移先。1つだけなので辞書は不要。遷移条件も不要。リンク先リファレンスだけ。
リンク元/先のノードが表す文字は同じになる。
探索 †
探索開始ノード、道順を示すUniglam列を受けて、ゴールになるノードを返す。
ゴールできなかったら返さない。
道中で単語発見があれば、その語を記録。ゴール後に参照できるように。
単語の記録が要らない場合もあるので、単語発見と記録のコードはパラメーターとして他からもらう。
failure元→先 †
元が示す語の2文字目から元ノードが示す文字までの部分文字列を探索。たどり着いたノードがfailure先。元/先は同じ文字。これを繰り返せるだけ繰り返し。
1文字語のfailure先はルート。2文字以上の語では見つからないこともある。
failure先→元 †
2文字目ノード辞書を使う。
そこから同じ語を探索。
たどり着いたノードがfailure元。
グラフ生成 †
単語1件追加と単語1件削除の繰り返し。
グラフに単語1件追加 †
- ノード生成
与えられた単語→Unigram列。そのままの順序でノード化。
辞書語の2文字目へのノード辞書も用意。
リンク先のほうからリンク元を探すときに使う。
削除 †
ノード消す。ただし他の単語末尾を含まないこと。単語末尾から先頭方向は他の単語と共有していたノードなので消せない。
消したノードに刺さっていたリンクも消す。
リンクの探し方…はじめから双方向にしておくか、探索。
刺さっていたgotoリンクなら消すノードを探した時に見つかっているはず。
刺さっていたfailureリンクはfailure先→元探索で探す。
ノードの型 †
- string
状態遷移条件の文字を集めてそれを代わりにできるが、文字同一視するためには必要。
単語末尾（単語発見と見なすタイミング）でないなら空文字列。 - goto
次のノード辞書。遷移条件文字→ノードリファレンスかノードID - failure
goto不可能な場合の遷移先。1つだけなので辞書は不要。遷移条件も不要。リンク先リファレンスだけ。
リンク元/先のノードが表す文字は同じになる。
探索 †
探索開始ノード、道順を示すUniglam列を受けて、ゴールになるノードを返す。
ゴールできなかったら返さない。
道中で単語発見があれば、その語を記録。ゴール後に参照できるように。
単語の記録が要らない場合もあるので、単語発見と記録のコードはパラメーターとして他からもらう。
failure元→先 †
元が示す語の2文字目から元ノードが示す文字までの部分文字列を探索。たどり着いたノードがfailure先。元/先は同じ文字。これを繰り返せるだけ繰り返し。
1文字語のfailure先はルート。2文字以上の語では見つからないこともある。
failure先→元 †
2文字目ノード辞書を使う。
そこから同じ語を探索。
たどり着いたノードがfailure元。