difflib與兩個以上的文件名

Question

我有幾個文件名，我試圖比較。下面是一些例子：

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嗎？

謝謝。

Answer 1

這並不是說它「混淆了十和數字的位置」，而是因爲在第一場比賽中，十人位置並沒有不同，所以它被認爲是匹配前綴的一部分。

對於您的用例，似乎有一個相當簡單的解決方案來解決這種模糊問題：只匹配所有相鄰的對，並取最小值。就像這樣：

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可能會返回tuple而不是namedtuple。這不會影響代碼，但如果您添加一些調試print它會中斷。

現在，pairs是由zipping合在一起創建的所有相鄰名稱對的列表names和names[1:]。 （如果不明確，print(zip(names, names[1:])。如果您使用的是Python 3.x，則需要使用print(list(zip(names, names[1:]))，因爲zip返回的是惰性迭代器而不是可打印列表。）

現在我們只想請在每個配對上撥打prefix，然後取回我們返回的最小值。這就是min的用途。 （我通過它generator expression，這可能是一個棘手的概念 - 但如果你只是想它是一個list comprehension，不建立列表，這很簡單。）

你可以明顯壓縮這個進入二，三線同時還留下可讀性：

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', 'FilePrefix10.j , etc. down to' 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。如果他們都是一樣的，那麼這個集合將只有一個元素，即{'F'}，然後是{'i'}等。如果它們不是，它將具有多個元素{'1', '2'}-這就是我們知道我們已經超過了前綴。

Answer 2

要確定的唯一方法是檢查所有文件名。因此，只需遍歷它們，檢查保留的最大匹配字符串。

您可以嘗試這樣的事：

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」，但我想的算法是顯而易見的任何級別的程序員。