algorithm - 英语文本的ukkonen后缀树算法?

  显示原文与译文双语对照的内容

我觉得这一点有点厚。 我花了几天的时间来完全围绕后缀树构造,但是因为我没有数学背景,很多解释都是因为它们开始过度使用数学符号。 最近我发现的最接近的解释是 快速字符串搜索后缀树,但他覆盖了不同的点和算法的某些方面仍然不清楚。

在堆栈溢出上逐步解释这个算法对我来说是无价的,我相信。

为了参考,这里是关于算法的Ukkonen文档: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

我的基本理解是:

  • 我需要迭代给定字符串的每个前缀P
  • 我需要遍历前缀P 中的每个后缀,并将它的添加到树
  • 为了向树添加后缀,我需要迭代在S 中的每个字符,迭代包含在后缀中遍历现有分支的迭代,或者在后缀中没有匹配的边,或者没有匹配的边缘。 当没有找到匹配的边缘来为C 向下行走时,为C 创建一个新的叶边缘。

基本算法似乎是O ( n 2 ),就像大多数解释中指出的,因为我们需要逐步遍历所有前缀,然后我们需要逐步遍历每个前缀的后缀。 Ukkonen的算法显然是想就是我的唯一,因为他使用的后缀指针的技术,不过我认为时不正常的理解。

我也无法理解:

  • "活动点"的分配,使用和更改的确切时间和方式
  • 算法的canonization方面发生了什么
  • 为什么我看到的实现需要使用它们所使用的边界变量

磅编辑 ( 四月 13,2012 )

下面是我编写的完整源代码,根据下面的jogojapan回答。 代码在生成树的过程中输出一个详细的描述和text-based图表。 它是第一个版本,可以进行优化等等,但它可以工作,这是最主要的事情。

[Redacted URL, see updated link below ]

磅编辑 ( 四月 15,2012 )

源代码已经完全重写了,现在不仅工作正常,而且它支持自动 canonization,并呈现一个更好的输出文本图。 源代码和示例输出位于:

https://gist.github.com/2373868

时间:

嗨,我试图在 ruby 中实现上面解释的实现,请检查一下。 看起来可以正常工作。

实现的唯一区别是,我试图使用边缘对象而不仅仅是使用符号。

它也存在于 https://gist.github.com/suchitpuri/9304856


 require 'pry'


class Edge
 attr_accessor :data, :edges, :suffix_link
 def initialize data
 @data = data
 @edges = []
 @suffix_link = nil
 end

 def find_edge element
 self.edges.each do |edge|
 return edge if edge.data.start_with? element
 end
 return nil
 end
end

class SuffixTrees
 attr_accessor :root, :active_point, :remainder, :pending_prefixes, :last_split_edge, :remainder

 def initialize
 @root = Edge.new nil
 @active_point = { active_node: @root, active_edge: nil, active_length: 0}
 @remainder = 0
 @pending_prefixes = []
 @last_split_edge = nil
 @remainder = 1
 end

 def build string
 string.split("").each_with_index do |element, index|


 add_to_edges @root, element 

 update_pending_prefix element 
 add_pending_elements_to_tree element
 active_length = @active_point[:active_length]

 # if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] == @active_point[:active_edge].data[active_length..@active_point[:active_edge].data.length-1])
 # @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1]
 # @active_point[:active_edge].edges <<Edge.new(@active_point[:active_edge].data)
 # end

 if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length] )
 @active_point[:active_node] = @active_point[:active_edge]
 @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0])
 @active_point[:active_length] = 0
 end
 end
 end

 def add_pending_elements_to_tree element

 to_be_deleted = []
 update_active_length = false
 # binding.pry
 if( @active_point[:active_node].find_edge(element[0])!= nil)
 @active_point[:active_length] = @active_point[:active_length] + 1 
 @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil
 @remainder = @remainder + 1
 return
 end



 @pending_prefixes.each_with_index do |pending_prefix, index|

 # binding.pry 

 if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil

 @active_point[:active_node].edges <<Edge.new(element)

 else

 @active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge] == nil

 data = @active_point[:active_edge].data
 data = data.split("") 

 location = @active_point[:active_length]


 # binding.pry
 if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element)!= nil ) 


 else #tree split 
 split_edge data, index, element
 end

 end
 end 
 end



 def update_pending_prefix element
 if @active_point[:active_edge] == nil
 @pending_prefixes = [element]
 return

 end

 @pending_prefixes = []

 length = @active_point[:active_edge].data.length
 data = @active_point[:active_edge].data
 @remainder.times do |ctr|
 @pending_prefixes <<data[-(ctr+1)..data.length-1]
 end

 @pending_prefixes.reverse!

 end

 def split_edge data, index, element
 location = @active_point[:active_length]
 old_edges = []
 internal_node = (@active_point[:active_edge].edges!= nil)

 if (internal_node)
 old_edges = @active_point[:active_edge].edges 
 @active_point[:active_edge].edges = []
 end

 @active_point[:active_edge].data = data[0..location-1].join 
 @active_point[:active_edge].edges <<Edge.new(data[location..data.size].join)


 if internal_node
 @active_point[:active_edge].edges <<Edge.new(element)
 else
 @active_point[:active_edge].edges <<Edge.new(data.last) 
 end

 if internal_node
 @active_point[:active_edge].edges[0].edges = old_edges
 end


 #setup the suffix link
 if @last_split_edge!= nil and @last_split_edge.data.end_with?@active_point[:active_edge].data 

 @last_split_edge.suffix_link = @active_point[:active_edge] 
 end

 @last_split_edge = @active_point[:active_edge]

 update_active_point index

 end


 def update_active_point index
 if(@active_point[:active_node] == @root)
 @active_point[:active_length] = @active_point[:active_length] - 1
 @remainder = @remainder - 1
 @active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1])
 else
 if @active_point[:active_node].suffix_link!= nil
 @active_point[:active_node] = @active_point[:active_node].suffix_link 
 else
 @active_point[:active_node] = @root
 end 
 @active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0])
 @remainder = @remainder - 1 
 end
 end

 def add_to_edges root, element 
 return if root == nil
 root.data = root.data + element if(root.data and root.edges.size == 0)
 root.edges.each do |edge|
 add_to_edges edge, element
 end
 end
end

suffix_tree = SuffixTrees.new
suffix_tree.build("abcabxabcd")
binding.pry

...