python - 寻找一种有效的方法或算法来检查文件是否属于某个文件夹路径列表中的某个项目

Question

我有一个文件夹路径列表。这个列表中可能有很多、几十个甚至上百个文件夹路径。例如:

C:\Program Files\7-Zip
// many directories under C:\Program Files\

C:\ProgramData\Adobe
C:\ProgramData\boost_interprocess
C:\ProgramData\dftmp
C:\ProgramData\Microsoft DNX
C:\ProgramData\NVIDIA Corporation
C:\ProgramData\Oracle
// many directories under C:\ProgramData\

C:\Windows\Boot
// many directories under C:\Windows\

D:\Datas\
// many directories under D:\Datas\

现在我提供一个路径，比如C:\Windows\1.log。我需要检查这个文件是否属于上一个列表中的文件夹。为了实现这个需求，我当然可以直接遍历整个列表，然后查看我要查询的文件路径是否以某个文件夹路径开头，但是这样感觉效率太低了，还有无效搜索太多，那么，有没有更好更高效的策略来完成这个任务？

---

更新:

sorry，我可能不是很清楚，我只需要检查路径之间的包含关系，不需要检查这些文件是否真的存在。

因此，我认为这应该是一道算法题。有没有办法找到一组路径的最大公约数？例如:

C:\ProgramData\Adobe
C:\ProgramData\boost_interprocess
C:\ProgramData\dftmp
C:\ProgramData\Microsoft DNX
C:\ProgramData\NVIDIA Corporation

他们这组路径的最大公约数是C:\ProgramData\，所以我可以把他们加到一个包里。然后先搜索包？

Answer 1

这是一种使用嵌套字典的 Trie 方法。基本上我们可以将每个文件夹插入到其父文件夹的字典中。所以像 C:\dir1\dir2\ 这样的路径将被存储为

{
  "C:": {
    "dir1": {
      "dir2": {}
    }
}

这是一个小类，它在我们的数据结构中插入给定的 folderPath 并允许查询 commonPath 以获取任何新文件/文件夹。循环遍历嵌套的字典一开始可能看起来有点奇怪。

import json

class PathTrie():
    def __init__(self, *args, **kwargs):
        self.data = {}

    def insertPath(self, folderPath):
        temp = self.data
        for dirName in folderPath.split('\\'):  # ASSUME: dirs are valid and don't contain '\'
            if temp.get(dirName) is None:
                temp[dirName] = {}
            temp = temp[dirName]

    def getCommonPath(self, path):
        commonPath = ""
        temp = self.data
        for dirName in path.split('\\'):
            if temp.get(dirName) is None:
                return commonPath
            commonPath += dirName + '\\'
            temp = temp[dirName]
        return commonPath  # you can strip last '\'' if needed

    def print(self):
        print(json.dumps(self.data, indent=2))


if __name__ == '__main__':
    trie = PathTrie()
    trie.insertPath("C:\\ProgramData\\dir1")
    trie.insertPath("C:\\ProgramData\\dir2")
    trie.insertPath("C:\\User\\dir3")
    trie.print()
    print(trie.getCommonPath("C:\\ProgramData\\dir2\\file1"))
    print(trie.getCommonPath("C:\\ProgramData\\file1"))

以上打印-

{
  "C:": {
    "ProgramData": {
      "dir1": {},
      "dir2": {}
    },
    "User": {
      "dir3": {}
    }
  }
}


C:\ProgramData\dir2\
C:\ProgramData\

但是如果你正在处理的数据很大(内存中可能有 100+ MB 的数据)，使用一些用 C 编写的 Trie 库而不是这个嵌套的字典可能是个好主意方法。