python从多个文件中删除相似的字符串

Question

我已经从不同的网站抓取了 txt 文件，现在我需要将它们粘贴到一个文件中。各个网站上有许多彼此相似的线路。我想删除重复的内容。这是我尝试过的:

import difflib

sourcename = 'xiaoshanwujzw'
destname = 'bindresult'
sourcefile = open('%s.txt' % sourcename)
sourcelines = sourcefile.readlines()
sourcefile.close()
for sourceline in sourcelines:

    destfile = open('%s.txt' % destname, 'a+')
    destlines = destfile.readlines()

    similar = False
    for destline in destlines:
        ratio = difflib.SequenceMatcher(None, destline, sourceline).ratio()
        if ratio > 0.8:
            print destline
            print sourceline
            similar = True

    if not similar:
        destfile.write(sourceline)

    destfile.close()

我将为每个源运行它，并逐行写入同一个文件。结果是，即使我多次对同一个文件运行它，该行始终会附加到目标文件中。

编辑:我已经尝试过答案的代码。还是很慢。即使我最小化 IO，我仍然需要比较 O(n^2)，特别是当你有 1000 多行时。我每个文件平均有 10,000 行。

还有其他方法可以删除重复项吗？

Answer 1

这是一个简短的版本，它执行最少的 IO 并自行清理。

import difflib

sourcename = 'xiaoshanwujzw'
destname = 'bindresult'

with open('%s.txt' % destname, 'w+') as destfile:

  # we read in the file so that on subsequent runs of this script, we 
  # won't duplicate the lines.
  known_lines = set(destfile.readlines())

  with open('%s.txt' % sourcename) as sourcefile:
    for line in sourcefile:
      similar = False
      for known in known_lines:
        ratio = difflib.SequenceMatcher(None, line, known).ratio()
        if ratio > 0.8:
          print ratio
          print line
          print known
          similar = True
          break
      if not similar:
        destfile.write(line)
        known_lines.add(line)

我们不是每次从文件中读取已知行，而是将它们保存到一个集合中，用于进行比较。该集本质上是“destfile”内容的镜像。

关于复杂性的说明

从本质上来说，这个问题的复杂度为 O(n²)。因为您正在寻找与已知字符串的相似性，而不是相同的字符串，所以您必须查看每个以前见过的字符串。如果您希望删除精确的重复项，而不是模糊匹配，则可以在集合中使用简单的查找，复杂度为 O(1)，从而使整个解决方案的复杂度为 O(n)。

可能有一种方法可以通过对字符串使用有损压缩来降低基本复杂性，以便两个相似的字符串压缩为相同的结果。然而，这既超出了堆栈溢出答案的范围，也超出了我的专业知识。是an active research area所以你可能会幸运地挖掘文献。

您还可以使用精度较低的替代方法 quick_ratio() 和 real_quick_ratio() 来减少 ratio() 所花费的时间。