python字符串相似度处理性能问题求助

jkh7

文件中包含如下的内容：
aaaaaaaaaaa
bbbbbbbbbbbbb
aaaaaaaaaaaaaaa
bbbbbbbbbbbb
bbbbbbbbbbbbbbb

文件中行数大概有几十万行。

用python脚本对文件进行处理，统计相似度比较高的行及出现的次数。
如上的内容统计结果为：
aaaaaaaaaa 2
bbbbbbbbbbbbb 3

脚本如下：
def ansy_file(fileName):
    file = open(fileName)
    bFlag=0
    errorInfo={}
    dealTime=time.time()
    while 1:
        bFlag=0

        line = file.readline()
        if not line:
            break

       for k in errorInfo:
           s=difflib.SequenceMatcher(None, k, line)
           if(s.ratio()>0.6):
               count=errorInfo[k]
               errorInfo[k]=count+1
               bFlag=1
               break
       if(bFlag==0):
           errorInfo[lineErrorLog]=1

     print errorInfo.keys()

文件内容很大时，这个脚本处理时间非常长，需要处理一天的时间，请问有什么方法进行优化？

jkh7

在线等回复，谢谢

jeppeter

回复 1# jkh7


    还是没有明确你的想法，你没有说明你的真正的想法。因为你的相似是什么？假如你的比较方法，那就要得到你的相似。

jkh7

其实就是计算字符串的相似度，这个是有算法的：
1．编辑距离（Levenshtein Distance）
2．最长公共子串 (LCS)
3. 余弦定理 (向量空间算法)

我是在python里找了difflib的库实现计算，但是效率比较低，想请教跟高效率的算法。

wenhq

split文件并行处理？所谓的文件merge算法？

jkh7

谢谢，我改用c语言实现了，性能提高很多。

noword2k

参考一下这篇文章吧
http://blog.youxu.info/spell-correct.html

jkh7

谢谢，学习了