接尾辞トライ (Suffix Trie)¶
文字列を入力してください.(色分けはアルファベットサイズ10までですが,接尾辞トライそのものは大きなアルファベットに対しても正しく構築しています) ・length(w) = dummy
定義¶
接尾辞トライのオンライン構築アルゴリズム¶
/Scripts/CoffeeScript/SuffixTrie.coffee
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | ###
SuffixTrie のオンライン構築アルゴリズム
###
class Node
constructor: (@id) ->
@edgeList = {}
@isFinal = false
@slink = null
@len = 0
# 文字 c による遷移があるかどうかを判定する.
hasTransition: (c) -> c of @edgeList
# 文字 c による遷移先の頂点を返す.
nextState: (c) -> @edgeList[c]
toString: ->
sortedKeys = sortedKeyList( @edgeList )
children = ( "[#{c}, #{@edgeList[c].id}]" for c in sortedKeys )
slinkTarget = if (not (@slink?)) then "X" else "#{@slink.id}"
(if @isFinal then "*" else " ") + "Node(#{@id}): [#{children}] : sl->#{slinkTarget}"
class BottomNode extends Node
constructor: (@rootNode) ->
super "Bottom"
@len = -1
@rootNode.slink = this
# ボトム頂点はすべての文字に対して遷移先(根頂点)がある.
hasTransition: (c) -> true
# ボトム頂点はすべての文字に対する遷移先が根頂点である.
nextState: (c) -> @rootNode
toString: -> "BottomNode"
class SuffixTrie
constructor:(@text) ->
@nextId = 0
@nodeList = []
@terminalNode = @rootNode = @createNode()
@bottomNode = new BottomNode(@rootNode)
@construction()
@markFinal()
# このSuffixTrieの頂点数を返す.(ボトム頂点は含まない)
size: ->
@nodeList.length
# 新しい頂点を生成する.
createNode: () ->
newNode = new Node(@nextId++)
@nodeList.push( newNode )
return newNode
# オンライン構築アルゴリズムの根幹部分.
construction: ->
for c, i in @text
v = @terminalNode
v.edgeList[c] = prevNode = @terminalNode = @createNode()
v = v.slink
until v.hasTransition(c)
v.edgeList[c] = prevNode.slink = @createNode()
prevNode = prevNode.slink
v = v.slink
prevNode.slink = v.nextState(c)
return
toString: ->
return (v.toString() for v in @nodeList).join("\n")
# 受理状態を設定していく.
markFinal: ->
v = @terminalNode
until v is @bottomNode
v.isFinal = true
v = v.slink
return
## 連想配列(オブジェクト)のキーを整列した配列を返す
sortedKeyList = (assoc_array) ->
(k for k of assoc_array ).sort()
|