Un Blog De George Ang

原理见前面的博文。下面是粗略实现的python代码,GPL版权。

#!/usr/bin/env python

def getSuffixes(sequence):
    """Extract suffixes for a sequence"""
    return [ sequence[i:] for i in range(0, len(sequence)) ]

def getPrefixes(sequence):
    """Extract preffixes for a sequence"""
    return [ sequence[:i] for i in range(1, len(sequence) + 1) ]

def commonDiff(seq1, seq2):
    """ Get the common prefix the two sequences and two different suffixes """
    index = 0
    for i in range(0, min(len(seq1), len(seq2))):
	if seq1[i] == seq2[i]:
	    index += 1
	else:
	    break
    return (seq1[0:index], seq1[index:], seq2[index:])

class SuffixNode(object):
    """Node class of a Suffix Tree"""
    def __init__(self, parent, path):
	self.parent = parent
        self.path = path
	self.nodes = []
	self.suffix = None

    def isRoot(self):
        """test if current node is root node."""
	return self.path is None

    def addSuffix(self, suffix):
        """add a suffix to the current subtree."""

	(common, suf1, suf2) = commonDiff(self.path, suffix)

	if len(common) == 0:
	    # do not belong to this branch
	    return False
	elif len(suf2) == 0:
	    # shorter than current branch
	    return True
	elif len(suf1) == 0:
	    # longer than current branch
	    if len(self.nodes) == 0:
		# leaf just append to it
		self.path = suffix
		return True
	    else:
		# internal node, try subbranches
		for node in self.nodes:
		    if node.addSuffix(suf2):
			return True

	elif len(self.nodes) == 0:
	    # leaf split it
	    self.path = common
	    self.nodes.append(SuffixNode(self, suf1))
	    self.nodes.append(SuffixNode(self, suf2))
	    return True
	else:
	    # split the internal node
	    newnode1 = SuffixNode(self, suf1)
	    newnode2 = SuffixNode(self, suf2)
	    self.path = common
	    for node in self.nodes:
		node.parent = newnode1
		newnode1.nodes.append(node)
	    self.nodes = []
	    self.nodes.append(newnode1)
	    self.nodes.append(newnode2)
	    return True

    def __repr__(self):
        """representation of node object"""
	return self.path

    def structure(self):
        """tree structure was return as a nested dictionary."""
	return { self.path : [ node.structure() for node in self.nodes ] }

class SuffixTree(SuffixNode):
    """A SuffixTree Implementation."""
    def __init__(self, sequence):
	super(SuffixTree, self).__init__( None, '')
	self.feed(sequence)

    def feed(self, sequence):
        """feed the tree a sequence"""

	prefixes = getPrefixes(sequence)
	for prefix in prefixes:

	    suffixes = getSuffixes(prefix)
	    for suffix in suffixes:
		succ = False
		for node in self.nodes:
		    if node.addSuffix(suffix):
			succ = True
			break
		if not succ:
		    self.nodes.append(SuffixNode(self, suffix))

def printTree(tree, level = 0):
    """docstring for printTree"""
    if tree == None: return
    print '    '*level + tree.path
    for node in tree.nodes:
	printTree(node, level+1)

def main():
    """docstring for main"""
    tree = SuffixTree( ('mississippi') )
    printTree(tree)

def test():
    """docstring for test"""
    print getPreffixes('mississippi')

if __name__ == '__main__':
    main()

译自维基百科：在计算机科学中，在线算法是指一种可以顺序的方式逐块处理输入的算法。比如说，算法只要“喂”一口数据即可开始，而不需要得到全部的数据。反之，离线算法是指手边的问题必须要一开始就获得全部的数据才能解决。（举例来说，选择排序要求得到整个列表才能开始排序，而插入排序则不需要。）

译自维基百科：在计算机科学中，在线算法是指一种可以顺序的方式逐块处理输入的算法。比如说，算法只要“喂”一口数据即可开始，而不需要得到全部的数据。反之，离线算法是指手边的问题必须要一开始就获得全部的数据才能解决。（举例来说，选择排序要求得到整个列表才能开始排序，而插入排序则不需要。）