接尾辞トライ (Suffix Trie)

文字列を入力してください．（色分けはアルファベットサイズ10までですが，接尾辞トライそのものは大きなアルファベットに対しても正しく構築しています）
w =
・length(w) = dummy
dummyAA

定義

接尾辞トライのオンライン構築アルゴリズム

/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()