有向無閉路文字列グラフ (Directed Acyclic Word Graph：DAWG)

text =
接尾辞リンクを表示する
pattern =
・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