2

我有几个要比较的文件名。这里有些例子：

files = ['FilePrefix10.jpg', 'FilePrefix11.jpg', 'FilePrefix21.jpg', 'FilePrefixOoufhgonstdobgfohj#lwghkoph[]**^.jpg']

我需要做的是从每个文件名中提取“FilePrefix”，这取决于目录。我有几个包含许多 jpg 的文件夹。在每个文件夹中，每个 jpg 都有一个与该目录中的每个其他 jpg 相同的 FilePrefix。我需要 jpg 文件名的可变部分。我无法提前预测 FilePrefix 将是什么。

我的想法是使用 difflib（在 Python 中）比较两个文件名并以这种方式提取 FilePrefix（以及随后的变量部分）。我遇到了以下问题：

>>>> comp1 = SequenceMatcher(None, files[0], files[1])
>>>> comp1.get_matching_blocks()
[Match(a=0, b=0, size=11), Match(a=12, b=12, size=4), Match(a=16, b=16, size=0)]

>>>> comp1 = SequenceMatcher(None, files[1], files[2])
>>>> comp1.get_matching_blocks()
[Match(a=0, b=0, size=10), Match(a=11, b=11, size=5), Match(a=16, b=16, size=0)]

如您所见，第一个size不匹配。它混淆了十位和数字的位置，使我很难匹配两个以上文件之间的差异。是否有正确的方法size在目录中的所有文件中找到最小值？或者，是否有更好的方法来提取 FilePrefix？

谢谢你。

4

2 回答 2

2

不是“混淆十位和数字位”，而是在第一次比赛中，十位没有什么不同，所以它被认为是匹配前缀的一部分。

对于您的用例，似乎有一个非常简单的解决方案来解决这种歧义：只需匹配所有相邻的对，然后取最小值。像这样：

def prefix(x, y):
    comp = SequenceMatcher(None, x, y)
    matches = comp.get_matching_blocks()
    prefix_match = matches[0]
    prefix_size = prefix_match[2]
    return prefix_size

pairs = zip(files, files[1:])
matches = (prefix(x, y) for x, y in pairs)
prefixlen = min(matches)
prefix = files[0][:prefixlen]

该prefix函数非常简单，除了一件事：我让它采用两个值的单个元组而不是两个参数，只是为了更容易调用map. 我使用了[2]而不是.size因为在 2.7 中有一个烦人的错误，difflib第二次调用get_matching_blocks可能会返回 atuple而不是 a namedtuple。这不会影响代码原样，但如果你添加一些调试print它会中断。

现在，pairs是所有相邻名称对的列表，通过zipping在一起创建names和names[1:]。（如果不清楚，print(zip(names, names[1:])。如果您使用的是 Python 3.x，则需要print(list(zip(names, names[1:]))改为，因为zip返回惰性迭代器而不是可打印列表。）

现在我们只想调用prefix每一对，并取我们得到的最小值。这min就是为了。（我向它传递了一个生成器表达式，起初这可能是一个棘手的概念——但如果你只是将它视为不构建列表的列表推导式，那非常简单。）

您显然可以将其压缩为两三行，同时仍保持可读性：

prefixlen = min(SequenceMatcher(None, x, y).get_matching_blocks()[0][2] 
                for x, y in zip(files, files[1:]))
prefix = files[0][:prefixlen]

但是，值得考虑的SequenceMatcher是，这可能是矫枉过正。它在任何地方寻找最长的匹配，而不仅仅是最长的前缀匹配，这意味着它在字符串的长度上本质上是 O(N^3)，而它只需要 O(NM)，其中 M 是结果的长度. 另外，可能会有比最长前缀长的后缀，所以它会返回错误的结果，这并非不可想象。

那么，为什么不手动进行呢？

def prefixes(name):
    while name:
        yield name
        name = name[:-1]

def maxprefix(names):
    first, names = names[0], names[1:]
    for prefix in prefixes(first):
        if all(name.startswith(prefix) for name in names):
            return prefix

prefixes(first)只是给你'FilePrefix10.jpg'，'FilePrefix10.jp',' , etc. down toFilePrefix10.j'F'`。所以我们只是遍历这些，检查每个是否也是所有其他名称的前缀，然后返回第一个。

而且您可以通过逐个字符而不是逐个前缀来思考来更快地做到这一点：

def maxprefix(names):
    for i, letters in enumerate(zip(*names)):
        if len(set(letters)) > 1:
            return names[0][:i]

在这里，我们只是检查所有名称中的第一个字符是否相同，然后检查所有名称中的第二个字符是否相同，依此类推。一旦我们找到一个失败的地方，前缀就是所有字符（来自任何名称）。

将zip名称列表重新组织成一个元组列表，其中第一个是每个名称的第一个字符，第二个是每个名称的第二个字符，依此类推。即，[('F', 'F', 'F', 'F'), ('i', 'i', 'i', 'i'), …]。

只是为我们提供enumerate了索引和值。所以，而不是让('F', 'F', 'F', 'F')你得到0, ('F, 'F', F', 'F'). 最后一步我们需要该索引。

现在，要检查它们('F', 'F', 'F', 'F')是否相同，我只是将它们放在一个set. 如果它们都相同，则该集合将只有一个元素——<code>{'F'}、then{'i'}等。如果它们不同，它将有多个元素——<code>{'1', '2'}——这就是我们知道我们已经超越了前缀的方式。

于 2013-12-19T23:49:55.483 回答
1

唯一可以确定的方法是检查所有文件名。因此，只需遍历它们，随时检查保留的最大匹配字符串。

你可以尝试这样的事情：

files = ['FilePrefix10.jpg',
         'FilePrefix11.jpg',
         'FilePrefix21.jpg',
         'FilePrefixOoufhgonstdobgfohj#lwghkoph[]**^.jpg',
         'FileProtector354.jpg
         ]
prefix=files[0]
max = 0
for f in files:
    for c in range(0, len(prefix)):
        if prefix[:c] != f[:c]:
            prefix = f[:c-1]
            max = c - 1
print prefix, max

请原谅解决方案的“非 Pythonicness”，但我希望该算法对任何级别的程序员都是显而易见的。

于 2013-12-19T23:55:56.547 回答