用替换分组数百万个字符串

Question

我有一大堆(XXM-XXXM)字符串看起来像(一个小样本):

我不知道所有可能的错误字符串,也不知道其排列.我想将所有类似的错误组合在一起,并生成一些统计信息,显示每个错误字符串组的错误计数.

所以,基本上,我想将最相似的字符串组合在一起,字符串可以属于多个组.

谢谢!

Answer 1

免责声明：我以前从未解决过这样的问题。

我可以想出几种方法来思考你的问题：

• 您正在尝试将每一行聚类为一组簇
  • 检查数据挖掘算法
• 簇中每条线之间的差异会很小，两个不同簇中的线之间的差异会相当大
• 您可以通过比较两条线的集合交集来快速收集相似的线：set(line1.split) & set(line2.split)- 结果集中的元素计数指示这两条线的接近程度。

一段 Python 代码可能如下所示：

import fileinput

CLUSTER_COUNT = 5
MAX_DISTANCE = 5

def main():
    clusters = [Cluster() for i in range(CLUSTER_COUNT)]
    MAXDISTANCE = 3
    for line in  fileinput.input():
        words = set(line.split())
        cluster = sorted(clusters, key=lambda c: c.distanceTo(words))[0]
        cluster.addLine(words, line)

    # print out results (FIXME: write clusters to separate files)
    for cluster in clusters:
        print "CLUSTER:", cluster.intersection
        for line in cluster.lines:
            print line
        print "-" * 80
        print

class Cluster(object):
    def __init__(self):
        self.intersection = set()
        self.lines = []
    def distanceTo(self, words):
        if len(self.intersection) == 0:
            return MAX_DISTANCE 
        return len(words) - len(self.intersection & words)
    def addLine(self, words, line):
        self.lines.append(line) 
        if len(self.intersection) == 0:
            self.intersection = words
        else:
            self.intersection = self.intersection & words

if __name__ == '__main__':
    main()

如果您在主要数据上运行它，您最终应该得到几个集群。注意：更改代码以将簇写入单独的文件。我认为您会希望再次递归地通过代码运行集群，直到找到您感兴趣的子集。