Suffix Tree的实现代码
原理见前面的博文。下面是粗略实现的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()
Online Algorithm
译自维基百科：在计算机科学中，在线算法是指一种可以顺序的方式逐块处理输入的算法。比如说，算法只要“喂”一口数据即可开始，而不需要得到全部的数据。反之，离线算法是指手边的问题必须要一开始就获得全部的数据才能解决。（举例来说，选择排序要求得到整个列表才能开始排序，而插入排序则不需要。）
Online Algorithm
译自维基百科：在计算机科学中，在线算法是指一种可以顺序的方式逐块处理输入的算法。比如说，算法只要“喂”一口数据即可开始，而不需要得到全部的数据。反之，离线算法是指手边的问题必须要一开始就获得全部的数据才能解决。（举例来说，选择排序要求得到整个列表才能开始排序，而插入排序则不需要。）
Levenshtein Distance
Levenshtein Disctance是常用的一种计算两个字符串之间的编辑距离的算法。他将问题用动态规划的方法分解为：计算对于A字符串的每一个字符，计算将它编辑为B字符串每一字符所需要的最少步骤。通常采用top-down的顺序，从A串的第一个字母开始算起，将每次的结果累加，直到A,B的最后一个字母。
（图片来自wikipedia）
#!/usr/bin/env python
def levenshtein(s, t):
"""Implementation for levenshtein algorithm"""
m = len(s) + 1
n = len(t) + 1
d = [ 0 for i in range(m*n)]
for i in range (0, m):
d[i*n] = i
for i in range (0, n):
d[i] = i
for i in range(1, m):
for j in range(1, n):
if s[i-1] == t[j-1]:
cost = 0
else:
cost = 1
d[i*n+j] = min( d[(i-1)*n + j] +1,
d[i*n + j - 1] +1,
d[(i-1)*n + j - 1] + cost)
pretty_print(s, t, d)
return d[m*n - 1]
def pretty_print(s, t, d):
"""Pretty print for distance matrix"""
m = len(s) + 1
n = len(t) + 1
for i in range(0, m):
for j in range(0, n):
print d[i*n + j ],
print
if __name__ == '__main__':
print levenshtein('sitting', 'kitten')
半容半耻的八达岭长城经历
按：要说此行有什么收获，那么只能说是下雪带来的挑战，以及拉近了部门同事之间的距离。这些经验完全可以在长城以外的地方获得。也许这种环境对我们来说是个挑战，但是想想当时修长城的劳工们要在没有台阶的情况下背石头上山，就一点成就感都没有了。看着垒起城墙的那些石块，联想到今天我们还需要纳 税建电子城墙，也不知道作为文明讲到底进步了多少？下山的时候，我期待能在哪里找到一座死在山上的劳工们的纪念碑，映入眼睛却只是巨大的“同一个世界，同 一个梦想”的招牌。滑车的幕后的潜规则，更让我个人对八达岭的印象差到了极点。有生之年不会再去第二次。
——————————————————————————————
同事都是第一次来长城（头应该小时候来过），来之前也没什么准备。包括没有在网上google下长城的位置，走向，有无潜规则等等。所以在车上就被导游忽悠了一下。一下车就买了门票+滑车票。然后跟着另一个拿旗的导游去排滑车队。
由于派对的队伍过长，所以在问过下山的游客后，说服了同事放弃排队，徒步上山（事后同事一致认为这个决定导致了我们在长城的独特经验）。
由于早上开始就下起了大雪，所以长城上面有很多积雪。很多斜坡都非常的滑。上台阶时候要非常的小心，没有台阶的地方就只能靠手扶城墙边的扶手一点点的向上挪。期间发生了很多事情，基本是以打滑为主题的。此外还在休息时拍了很多照片。
前面提到我们没有做太充分的准备，导致对我们爬坡的进度并不熟悉。当我们到了一个人相对多起来的烽火台时才了解到我们是从后门登的长城，已经到了所谓风景最好北八楼。之后从南侧下山除了有些地段打滑之外，没有什么挑战。
下城时发现实际上从正门到北八其实没有多远，滑车根本属于多余。于是出城后跑到滑车售票口退了票。
要说此行有什么收获，那么只能说是下雪带来的挑战，以及拉近了部门同事之间的距离。这些经验完全可以在长城以外的地方获得。也许这种环境对 我们来说是个挑战，但是想想当时修长城的劳工们要在没有台阶的情况下背石头上山，就一点成就感都没有了。看着垒起城墙的那些石块，联想到今天我们还需要纳 税建电子城墙，也不知道作为文明讲到底进步了多少？下山的时候，我期待能在哪里找到一座死在山上的劳工们的纪念碑，映入眼睛却只是巨大的“同一个世界，同 一个梦想”的招牌。
八达岭长城其实根本没有多长，如果不下雪的话南北都很好爬。如果说不到长城非好汉的话，八达岭长城也排不上好。崭新的石块，简陋的滑车和城里小商贩，与其说是文化古迹，倒不如说是没有任何建筑美感的揽财工事。 加上滑车的幕后的潜规则，更让我个人对八达岭的印象差到了极点。有生之年不会再去第二次。
App Store才是盗版的终结
讨论来自：http://internet.solidot.org/article.pl?sid=09/02/17/0324219
我们很难分清给一个国际化的东东定罪要遵照哪国法律，也不能去各国法律在该方面限制的最小集。比如关于新闻内容，你一定不同意对BBC的审查遵守中国或者 朝鲜的法律。关于妇女化妆的规定你一定不会愿意遵守伊朗和阿富汗的法律。海盗湾本身和其访问者是否违法，取决于当地法庭做出的裁决。
即使当地法庭认为它违法，关于软件和电影的分发，本来就有争议。计算机和Internet已经让这些产品的边际成本和库存成本为零，软件又不能像传统商品 那样通过市场竞争将利润趋紧于零。因此传统的销售策略已经不适用于Internet时代。因此软件和DRM影片的产权保护的是垄断厂商的暴利，不是整个社 会利益。没有法律的威胁下，没有用户真正的愿意为一个零边际成本的产品付费。
这些厂商如果聪明的话，应该赶紧通过要花库存成本（hosting）的App Store低价发售软件和DRM影片。对于软件和DVD盗版，睁一只眼闭一只眼就行了，后者或者随着在App Store那样的商店的普及而消亡，或者逐渐的合法化。不论将来怎么样，厂商现在打压他们都不是一种讨好的举动。
C++中的高阶函数
函数式语言都支持高阶函数。SICP里面称为高阶过程。
在数学和计算机科学中，高阶函数是至少满足下列一个条件的函数:* 接受一个或多个函数作为输入
* 输出一个函数在数学中它们也叫做算子(运算符)或泛函。微积分中的导数就是常见的例子，因为它映射一个函数到另一个函数。
那么,C++中能不能实现高阶函数呢？考虑下面的代码：
struct Func {
int operator () (int a, int b);
};
Func obj;
int func( Func, int, int);
func(obj, a, b);
这样的形式符合高阶函数定义的第一种情况，理论上是可行的。Google后发现，Boost的bind就是基于这种思想实现的。其实，C++中的接受和返回函数指针和函数对象作为参数的函数，都可以看成是一种高阶函数。
奥巴马竞选胜利演说
前两天同事发给我两个嘉宾谈奥巴马当选。今天我抽空看了一下。原来是两个弃权的loser，大谈自己觉得选谁都“不稳”。大有一副换汤不换样，我谁也不信的架势。没想到这种根深蒂固的江湖思想现在还在台湾，甚至是移民美国的台湾人脑中盛行。我想这也是不仅仅是大陆，甚至是台湾民主进程举步为艰的原因。视频我拖着看的，不想浪费时间。记住的观点提炼如下：
1、上面提到的，谁都不值得信任，因此我们弃权了。
这种观点是典型的奴性思维。你手中的选票不是给你选老爸，选上帝的。是让你投票给政策对你有利的候选人。如果你认两个候选人的政策都对你不利，那你移民美国干吗去了？下地狱炼佛去了么？
2、我们俩左右不了美国政治，因此我们索性不投了。
这是5000年专政留下来的后遗症。江山不是我的，我管不着。可惜这些人拿到了美国的选举权后依然保留着这种后遗症。这些人从出生开始就放弃了对自己身政治权利的使用，不管移民到哪，他的公民权利都是浪费。
3、丫还年轻，啥都不懂，能治理好美国么？
你当人家选王储呢？美国是奥巴马一个人治理的么？那么多顾问干什么吃的？副总统和国务卿干什么吃的？五角大楼和华尔街的精英干什么吃的？人家哦从嗯希拉里到迈凯恩一路赢过来，不还是靠实力赢的么？难道靠的是黑人先天的生理优势？ 这两个人的手中的选票，应该留着投给埃及挖出来的木乃伊一票。
附奥巴马竞选胜利演说。
[youku XNTE1NzEwNDg]
