導語：
模糊比對可以算是現代編輯器(在選擇要打開的檔案時)的一個必備特性了，它所做的就是根據使用者輸入的部分内容，猜測使用者想要的檔案名，并提供一個推薦清單供使用者選擇。
樣例如下：
Vim (Ctrl-P)
‘模糊比對’這是一個極為有用的特性，同時也非常易于實作。
問題分析：
我們有一堆字元串(檔案名)集合，我們根據使用者的輸入不斷進行過濾，使用者的輸入可能是字元串的一部分。我們就以下面的集合為例：
>>> collection = ['django_migrations.py',
'django_admin_log.py',
'main_generator.py',
'migrations.py',
'api_user.doc',
'user_group.doc',
'accounts.txt',
]
當使用者輸入’djm‘字元串時，我們假定是比對到’django_migrations.py’和’django_admin_log.py’，而最簡單的實作方法就是使用正規表達式。
解決方案：
1.正常的正則比對
将’djm’轉換成’d.*j.*m’然後用這個正則嘗試比對集合中的每一個字元串，如果比對到了就被列為候選。
>>> import re
>>> def fuzzyfinder(user_input, collection):
suggestions = []
pattern = '.*'.join(user_input) # Converts 'djm' to 'd.*j.*m'
regex = re.compile(pattern) # Compiles a regex.
for item in collection:
match = regex.search(item) # Checks if the current item matches the regex.
if match:
suggestions.append(item)
return suggestions
>>> print fuzzyfinder('djm', collection)
['django_migrations.py', 'django_admin_log.py']
>>> print fuzzyfinder('mig', collection)
['django_migrations.py', 'django_admin_log.py', 'main_generator.py', 'migrations.py']
這裡根據使用者的輸入我們得到了一個推薦清單，但是推薦清單中的字元串是沒有進行重要性區分的。有可能出現最合适的比對項被放到了最後的情況。
實際上，還是這個例子，當使用者輸入’mig‘時，最佳選項’migrations.py’就被放到了最後。
2.帶有rank排序的比對清單
這裡我們對比對到的結果按照比對内容第一次出現的起始位置來進行排序。
'main_generator.py' - 0
'migrations.py' - 0
'django_migrations.py' - 7
'django_admin_log.py' - 9
下面是相關代碼：
suggestions.append((match.start(), item))
return [x for _, x in sorted(suggestions)]
['main_generator.py', 'migrations.py', 'django_migrations.py', 'django_admin_log.py']
這次我們生成了一個由二進制tuple組成的清單，即清單中的每一個元素為一個二進制tuple，而該二進制tuple的第一個值為比對到的起始位置、第二個值為對應的檔案名，然後使用清單推導式按照比對到的位置進行排序并傳回檔案名清單。
現在我們已經很接近最終的結果了，但還稱不上完美——使用者想要的是’migration.py’，但我們卻把’main_generator.py’作為第一推薦。
3.根據比對的緊湊程度進行排序
當使用者開始輸入一個字元串時，他們傾向于輸入連續的字元以進行精确比對。比如當使用者輸入’mig‘他們更傾向于找的是’migrations.py’或’django_migrations.py’，而不是’main_generator.py’，是以這裡我們所做的改變就是查找比對到的最緊湊的項目。
剛才提到的問題對于Python來說不算什麼事，因為當我們使用正規表達式進行字元串比對時，比對到的字元串就已經被存放在了match.group()中了。下面假設輸入為’mig’，對最初定義的’collection’的比對結果如下：
regex = '(m.*i.*g)'
'main_generator.py' -> 'main_g'
'migrations.py' -> 'mig'
'django_migrations.py' -> 'mig'
'django_admin_log.py' -> 'min_log'
這裡我們将推薦清單做成了三元tuple的清單的形式，即推薦清單中的每一個元素為一個三元tuple，而該三元tuple的第一個值為比對到的内容的長度、第二個值為比對到的起始位置、第三個值為對應的檔案名，然後按照比對長度和起始位置進行排序并傳回。
suggestions.append((len(match.group()), match.start(), item))
return [x for _, _, x in sorted(suggestions)]
['migrations.py', 'django_migrations.py', 'main_generator.py', 'django_admin_log.py']
針對我們的輸入，這時候的比對結果已經趨向于完美了，不過還沒完。
4.非貪婪比對
由 Daniel Rocco 發現了這一微妙的問題：當集合中有[‘api_user’, ‘user_group’]這兩個元素存在，使用者輸入’user‘時，預期的比對結果(相對順序)應該為[‘user_group’, ‘api_user‘]，但實際上的結果為：
>>> print fuzzyfinder('user', collection)
['api_user.doc', 'user_group.doc']
上面的測試結果中：’api_user’要排在’user_group’前面。深入一點，我們發現這是因為在搜尋’user’時，正則被擴充成了’u.*s.*e.*r’，考慮到’user_group’有2個’r’，是以該模式比對到了’user_gr‘而不是我們預期的’user‘。更長的比對導緻在最後的比對rank排序時名次下降這一違反直覺的結果，不過這問題也容易解決，将正則修改為’非貪婪比對’即可。
pattern = '.*?'.join(user_input) # Converts 'djm' to 'd.*?j.*?m'
regex = re.compile(pattern) # Compiles a regex.
match = regex.search(item) # Checks if the current item matches the regex.
>>> fuzzyfinder('user', collection)
['user_group.doc', 'api_user.doc']
現在，fuzzyfinder已經可以(在上面的情況中)正常工作了，而我們不過隻寫了10行代碼就實作了一個 fuzzy finder。
結論：
以上就是我在我的 pgcli 項目(一個有自動補全功能的Postgresql指令行實作)中設計實作’fuzzy matching’的過程記錄。
我已經将 fuzzyfinder 提取成一個獨立的Python包，你可以使用指令’pip install fuzzyfinder’在你的項目中進行安裝和使用。
感謝 Micah Zoltu 和 Daniel Rocco 對算法的檢查和問題修複。
如果你對這個感興趣的話，你可以來 twitter （https://twitter.com/amjithr）上找我。
結語：
當我第一次考慮用Python實作“fuzzy matching”的時候，我就知道一個叫做 fuzzywuzzy 的優秀庫，但是 fuzzywuzzy 的做法和這裡的不太一樣，它使用的是 “levenshtein distance” 來從集合中找到最比對的字元串。”levenshtein distance“是一個非常适合用來做自動更正拼寫錯誤的技術，但在從部分子串比對長檔案名時表現的不太好(是以這裡沒有使用)。