当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

字符串相似性算法【最长公共字符串算法】 【LCS】

发表于: 2012-06-30   作者:dqifa   来源:转载   浏览次数:
摘要: #!/user/bin/env python # -*- coding: utf-8 -*- class arithmetic(): def __init__(self): pass ''' 【编辑距离算法】 【levenshtein distance】 【字符串相似度算法】 ''' def
#!/user/bin/env python  
# -*- coding: utf-8 -*-  
  
class arithmetic():  
      
    def __init__(self):  
        pass  
    ''' 【编辑距离算法】 【levenshtein distance】 【字符串相似度算法】 '''
    
    def levenshtein(self,first,second):  
        if len(first) > len(second):  
            first,second = second,first  
        if len(first) == 0:  
            return len(second)  
        if len(second) == 0:  
            return len(first)  
        first_length = len(first) + 1  
        second_length = len(second) + 1  
        distance_matrix = [range(second_length) for x in range(first_length)]   
        #print distance_matrix  
        for i in range(1,first_length):  
            for j in range(1,second_length):  
                deletion = distance_matrix[i-1][j] + 1  
                insertion = distance_matrix[i][j-1] + 1  
                substitution = distance_matrix[i-1][j-1]  
                if first[i-1] != second[j-1]:  
                    substitution += 1  
                distance_matrix[i][j] = min(insertion,deletion,substitution)  
        #print distance_matrix  
        return distance_matrix[first_length-1][second_length-1]
    
    def lcs(self,first,second):  
        first_length = len(first)  
        second_length = len(second)  
        size = 0  
        x = 0  
        y = 0  
        matrix = [range(second_length) for x in range(first_length)]  
        #print matrix  
        for i in range(first_length):  
            for j in range(second_length):  
                #print i,j  
                if first[i] == second[j]:  
                    if i - 1 >= 0 and j - 1 >=0:  
                        matrix[i][j] = matrix[i-1][j-1] + 1  
                    else:  
                        matrix[i][j] = 1  
                    if matrix[i][j] > size:  
                        size = matrix[i][j]  
                        x = j  
                        y = i  
                else:  
                    matrix[i][j] = 0  
        #print matrix  
        #print size,x,y   
  
        return second[x-size+1:x+1]  
      
if __name__ == "__main__":  
    arith = arithmetic()  
    print arith.levenshtein('GUMBOsdafsadfdsafsafsadfasfadsfasdfasdfs','GAMBOL00000000000dfasfasfdafsafasfasdfdsa')  
    print arith.lcs('GUMBOsdafsadfdsafsafsadfasfadsfasdfasdfs','GAMBOL00000000000dfasfasfdafsafasfasdfdsa')

 

from:http://www.lamprisi.com/forum.php?mod=viewthread&tid=3935&highlight=LCS

字符串相似性算法【最长公共字符串算法】 【LCS】

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
最长公共子序列(LCS) 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 题目: 给定两个字符
动态规划算法解LCS问题 作者 July 二零一零年十二月三十一日 本文参考:微软面试100题系列V0.1版第1
偶然看见了人家的博客发现这么一个问题,研究了一下午, 才发现其中的奥妙。Stupid。 题目描述: 回
关于题目理解,请注意和最长公共子序列的区别,最长公共子字符串的解法是动态规划,但是比较难想到
LCS:给出两个序列S1和S2,求出的这两个序列的最大公共部分S3就是就是S1和S2的最长公共子序列了。公
一、什么是最长公共子序列 什么是最长公共子序列呢?举个简单的例子吧,一个数列S,若分别是两个或
【算法剖析】求字符串中无重复字符的最长字串 1、问题描述   这个问题来自leetcode中的Longest Su
1、问题描述   这个问题来自leetcode中的Longest Substring Without Repeating Characters,诚如
详见: http://blog.yemou.net/article/query/info/tytfjhfascvhzxcytp96 经常会遇到复杂问题不能简
处理字符串的过程中,难免会遇到字符匹配的问题。常用的字符匹配方法 1. 朴素模式匹配算法(Brute-Fo
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号