1

我目前有两个 CSV 文件，它们在每个 csv 的第 1 列中包含数千个值。这些值是字母数字大写字符。

我当前的 python 脚本为每个 CSV 填充一个集合以单独获取唯一值，然后比较这两个集合，然后仅识别两个 CSV 中存在的条目：-

import csv 
Cell1 = [x[0] for x in csv.reader(open('C:\Documents and Settings\Me\Desktop\CSV1.csv','r'))] 
Cell2 = [y[0] for y in csv.reader(open('C:\Documents and Settings\Me\Desktop\CSV2.csv','r'))] 

uniqueSet = set(Cell1) & set(Cell2) 

print uniqueSet

以上工作完全没有问题，并撤回了我期望的所有条目。不过，我想进一步开发一套脚本，基本上在两个 CSV 之间进行比较，并确定除了一个字符之外相同的条目。例如，如果 CSV1 包含“ABCDE123”而 CSV2 包含“ABCDE124”，我希望这也能返回一个匹配项。

不幸的是，字符串的长度会有所不同，因为我正在考虑运行某种代码来比较 7 个字符中的 6 个字符是否相等。

关于从哪里开始的任何建议？

4

1 回答 1

0

我不确定你在这里能比 Theta(n^2) 做得更好。最终，您正在寻找：

result = [s from s in cell1 if matches_something_in_cell2(s)]

您被一个字符关闭的情况似乎不适用于任何一种散列算法，您也不会从全局排序中受益，这就是您在巨型集合上设置交集的方式。

您可以通过按字符串长度对其进行分区来进行预处理cell2，因此当您查看给定值是否cell1匹配时，您至少需要检查cell2具有预期长度的值。这只是修剪搜索空间；你的算法仍然是二次的。

排序可能会有所帮助，但我会把它留给你做调查（或另一个知道它将如何帮助的回答者，或者更好地，一些巧妙的数据结构来更有效地解决问题）。

同时，您可以尝试像这样（伪代码）进行一些修剪的暴力破解：

def matches_something_in_cell2(s):
    n = len(s)
    for candidate in preprocessed_list_from_cell2_of_strings_of_length(n):
        diffs = 0
        for i in range(n):
            if s[i] != candidate[i]:
                diffs += 1
                if diffs > 1
                    break
        if diffs <= 1
            return True
    return False

我希望我知道更好的方法。如果出现更好的情况，我将删除此答案。

于 2013-06-09T20:14:31.773 回答