有向無閉路文字列グラフ (Directed Acyclic Word Graph:DAWG)¶
・length(text) = dummy
定義¶
DAWGのオンライン構築アルゴリズム¶
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 | ###
Blumer et al. 1984 による DAWG のオンライン構築アルゴリズム
###
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 ).join(", ")
slinkTarget = if (not (@slink?)) then "X" else "#{@slink.id}"
(if @isFinal then "*" else " ") + "Node(#{@id}): {#{children}}, sl->#{slinkTarget}" + ", len=#{@len}"
class BottomNode extends Node
constructor: (@rootNode) ->
super "Bottom"
@len = -1
@rootNode.slink = this
# ボトム頂点はすべての文字に対して遷移先(根頂点)がある.
hasTransition: (c) -> true
# ボトム頂点はすべての文字に対する遷移先が根頂点である.
nextState: (c) -> @rootNode
toString: -> "BottomNode"
class DAWG
constructor:(@text) ->
@nextId = 0
@nodeList = []
@terminalNode = @rootNode = @createNode(length=0)
@bottomNode = new BottomNode(@rootNode)
@construction()
@markFinal()
# このDAWGの頂点数を返す.(ボトム頂点は含まない)
size: ->
@nodeList.length
# 指定された len を持つ頂点を生成する.
createNode: (length) ->
newNode = new Node(@nextId++)
newNode.len = length
@nodeList.push( newNode )
return newNode
# 頂点 v をコピーした頂点を生成して返す.ただし len は指定されたもの.
copyNode: (v, length) ->
newNode = @createNode(length)
newNode.isFinal = v.isFinal
for c of v.edgeList
newNode.edgeList[c] = v.edgeList[c]
newNode.slink = v.slink
return newNode
# オンライン構築アルゴリズムの根幹部分.
construction: ->
for c, i in @text
v = @terminalNode
@terminalNode = @createNode(length=i+1)
until v.hasTransition(c)
v.edgeList[c] = @terminalNode
v = v.slink
u = v.nextState(c)
if v.len + 1 == u.len # solid edge
@terminalNode.slink = u
else # v.len + 1 < u.len # non-solid edge
v.edgeList[c] = newNode = @copyNode(u, length=v.len+1)
u.slink = @terminalNode.slink = newNode
v = v.slink
while v.len + 1 < v.nextState(c).len
v.edgeList[c] = newNode
v = v.slink
return
|