I have a list of folder paths. There may be many, dozens or even hundreds of folder paths in this list. for example:

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\

Now I provide a path, such as C:\Windows\1.log. I need to check if this file belongs to a folder in the previous list. In order to achieve this requirement, I can of course traverse the entire list directly, and then check whether the path of the file I want to query starts with a certain folder path, but this feels that the efficiency is too low, and there are too many invalid searches, so , Is there a better and more efficient strategy to accomplish this task?

updated:

Sorry, I may not be very clear, I only need to check the containment relationship between the paths, and do not need to check whether these files really exist.

Therefore, I think this should be an algorithm problem. Is there any way to find the greatest common divisor of a set of paths? for example:

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

The greatest common divisor of their group of paths is C:\ProgramData\，so I can add them to one package. and then search the package first?

CodePudding user response：

Here's a Trie approach using nested dicts. Basically we can insert each folder into a dict of its parent folder. So a path like C:\dir1\dir2\ would be stored as

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

Here's a small class that inserts a given folderPath in our data structure and allows querying for commonPath for any new files/folders. The looping through nested dict might look a bit weird at first.

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"))

Above prints -

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


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

But if the data you are working on is huge(might have 100 MBs of data in memory), might be a good idea to use some Trie libraries written in C instead of this nested dict approach.

CodePudding user response：

thanks everybody. thanks for your sugesstions. I write a C version here. if someone need, you can test it.

#pragma once

#include <string>
#include <functional>
#include <unordered_map>

namespace Tests
{
    template <typename TCharType, bool IgnoreCase>
    struct PathTrieTraits
    {
        typedef typename std::basic_string<TCharType>::size_type SizeType;

        static void CalcHash(SizeType& value, SizeType fnvPrime, char ch) = delete;
    };

    template<>
    struct PathTrieTraits<char, true>
    {
        typedef std::basic_string<char>::size_type SizeType;

        static void CalcHash(SizeType& value, SizeType fnvPrime, char ch)
        {
            value ^= (SizeType)::tolower(ch);
            value *= fnvPrime;
        }
    };

    template<>
    struct PathTrieTraits<char, false>
    {
        typedef std::basic_string<char>::size_type SizeType;

        static void CalcHash(SizeType& value, SizeType fnvPrime, char ch)
        {
            value ^= (SizeType)ch;
            value *= fnvPrime;
        }
    };

    template <>
    struct PathTrieTraits<wchar_t, true>
    {
        typedef std::basic_string<wchar_t>::size_type SizeType;

        static void CalcHash(SizeType& value, SizeType fnvPrime, wchar_t ch)
        {
            ch = (wchar_t)::towlower(ch);
            value ^= (SizeType)ch;
            value *= fnvPrime;
        }
    };

    template <>
    struct PathTrieTraits<wchar_t, false>
    {
        typedef std::basic_string<wchar_t>::size_type SizeType;

        static void CalcHash(SizeType& value, SizeType fnvPrime, wchar_t ch)
        {
            value ^= (SizeType)ch;
            value *= fnvPrime;
        }
    };

    template <typename TCharType,
        typename THasher = std::hash<std::basic_string<TCharType>>,
        typename TPredicate = std::equal_to<std::basic_string<TCharType>>
    >
        class TPathNode
    {
    public:
        typedef TPathNode<TCharType>                                                SelfType;
        typedef std::basic_string<TCharType>                                        StringType;
        typedef typename StringType::size_type                                      SizeType;
        typedef std::unordered_map<SizeType, SelfType>                              ChildrenType;

        enum PathNodeAttribute
        {
            PathNodeAttribute_None = 0,
            PathNodeAttribute_Leaf = 1 << 0,
            PathNodeAttribute_Trunk = 1 << 1
        };
    public:
        TPathNode(const StringType& name) :
            Attribute(PathNodeAttribute_None),
            FileName(name)
        {
        }

        TPathNode(StringType&& name) :
            Attribute(PathNodeAttribute_None),
            FileName(name)
        {
        }

        TPathNode() :
            Attribute(PathNodeAttribute_None)
        {
        }

        SizeType GetCount() const
        {
            return Children.size();
        }

        bool IsEmpty() const
        {
            return Children.empty();
        }

        const SelfType* FindChild(SizeType hash) const
        {
            auto pos = Children.find(hash);

            return pos != Children.end() ? &pos->second : nullptr;
        }

        SelfType* FindChild(SizeType hash)
        {
            auto pos = Children.find(hash);

            return pos != Children.end() ? &pos->second : nullptr;
        }

        SelfType* EmplaceChild(SizeType hash, SelfType&& node)
        {
            auto ret = Children.emplace(std::make_pair(hash, node));
            return ret.second ? &ret.first->second : nullptr;
        }

        bool IsTrunk() const
        {
            return (Attribute & PathNodeAttribute_Trunk) != 0;
        }

        bool IsLeaf() const
        {
            return (Attribute & PathNodeAttribute_Leaf) != 0;
        }

        void AddAttribute(PathNodeAttribute attr)
        {
            Attribute = static_cast<PathNodeAttribute>((int)Attribute | (int)attr);
        }

        void RemoveAttribute(PathNodeAttribute attr)
        {
            Attribute = static_cast<PathNodeAttribute>((~(int)attr) & (int)Attribute);
        }

        void Clear()
        {
            Attribute = PathNodeAttribute_None;
            FileName.clear();            
            Children.clear();
        }

    private:
        PathNodeAttribute           Attribute;
        StringType                  FileName;
        ChildrenType                Children;
    };

    template <typename TCharType,
        typename TTrieTraits = PathTrieTraits<TCharType, true>,
        typename THasher = std::hash<std::basic_string<TCharType>>,
        typename TPredicate = std::equal_to<std::basic_string<TCharType>>
    >
        class TPathTrieTree
    {
    public:
        typedef TPathNode<TCharType, THasher, TPredicate>                           PathNodeType;
        typedef typename PathNodeType::StringType                                   StringType;
        typedef typename PathNodeType::SizeType                                     SizeType;

        struct SearchResult
        {
            SizeType Pos;
            SizeType Hash;
#if _DEBUG
            StringType Text;
#endif

            SearchResult() :
                Pos(StringType::npos),
                Hash(0)
            {
            }

            SearchResult(
                SizeType pos,
                SizeType hash
#if _DEBUG
                , StringType text
#endif

            ) :
                Pos(pos),
                Hash(hash)
#if _DEBUG
                , Text(text)
#endif
            {
            }
        };

    public:
        void Add(const StringType& path)
        {
            if (path.empty())
            {
                return;
            }

            Add(path.c_str(), path.size());
        }

        void Add(const TCharType* pathStr)
        {
            if (pathStr == nullptr)
            {
                return;
            }

            return Add(pathStr, std::char_traits<TCharType>::length(pathStr));
        }

        void Add(const TCharType* pathStr, SizeType length)
        {
            PathNodeType* curNode = &Root;
            SizeType startPos = 0;

            do
            {
                SearchResult Result = SearchAndHash(pathStr, startPos, length);

                if (Result.Pos == startPos)
                {
                    // 连续的分隔符？
                    // 
                      startPos;
                    continue;
                }
                else if (Result.Pos != StringType::npos)
                {
                    PathNodeType* targetNode = curNode->FindChild(Result.Hash);

                    if (targetNode == nullptr)
                    {
                        curNode->AddAttribute(PathNodeType::PathNodeAttribute_Trunk);

                        targetNode = curNode->EmplaceChild(Result.Hash, PathNodeType(StringType(pathStr   startPos, pathStr   Result.Pos)));
                    }

                    curNode = targetNode;
                    startPos = Result.Pos   1;
                    continue;
                }
                else if (startPos < length)
                {
                    // 没有分隔符了？那这是最后一个节点元素
                    curNode->AddAttribute(PathNodeType::PathNodeAttribute_Trunk);

                    curNode = curNode->EmplaceChild(Result.Hash, PathNodeType(StringType(pathStr   startPos, pathStr   length)));

                    curNode->AddAttribute(PathNodeType::PathNodeAttribute_Leaf);
                    return;
                }
                break;
            } while (true);

            if (curNode != nullptr)
            {
                curNode->AddAttribute(PathNodeType::PathNodeAttribute_Leaf);
            }
        }

        bool IsChild(const StringType& path) const
        {
            if (path.empty())
            {
                return false;
            }

            return IsChild(path.c_str(), path.size());
        }

        bool IsChild(const TCharType* pathStr) const
        {
            return IsChild(pathStr, std::char_traits<TCharType>::length(pathStr));
        }

        bool IsChild(const TCharType* pathStr, SizeType length) const
        {
            const PathNodeType* curNode = &Root;
            SizeType startPos = 0;

            do
            {
                SearchResult Result = SearchAndHash(pathStr, startPos, length);

                if (Result.Pos == startPos)
                {
                    // 连续的分隔符？
                    // 
                      startPos;
                    continue;
                }
                else if (Result.Pos != StringType::npos)
                {
                    // 说明这个segment可能是也可能不是最后一个元素
                    const PathNodeType* targetNode = curNode->FindChild(Result.Hash);

                    // 当前节点下没有这个名字的子节点？
                    if (targetNode == nullptr)
                    {
                        return curNode->IsLeaf();
                    }

                    curNode = targetNode;
                    startPos = Result.Pos   1;
                    continue;
                }
                else if (startPos < length)
                {
                    // 没有分隔符了？那这是最后一个节点元素
                    if (curNode->IsLeaf())
                    {
                        return true;
                    }

                    const PathNodeType* targetNode = curNode->FindChild(Result.Hash);
                    if (targetNode == nullptr)
                    {
                        return curNode->IsLeaf();
                    }

                    return targetNode->IsLeaf();
                }
                else
                {
                    break;
                }
            } while (true);

            return false;
        }

        bool IsEmpty() const
        {
            return Root.IsEmpty();
        }

        void Clear()
        {
            Root.Clear();
        }

    private:
        static SearchResult SearchAndHash(const TCharType* str, SizeType startPos, SizeType maxLength) 
        {
            static const SizeType WalkIter = sizeof(TCharType) / sizeof(char);

#if _WIN64
            static_assert(sizeof(SizeType) == 8, "This code is for 64-bit SizeType.");

            const SizeType FNVOffsetBasis = 14695981039346656037ULL;
            const SizeType FNVPrime = 1099511628211ULL;

#else
            static_assert(sizeof(SizeType) == 4, "This code is for 32-bit SizeType.");

            const SizeType FNVOffsetBasis = 2166136261U;
            const SizeType FNVPrime = 16777619U;
#endif

            SizeType Value = FNVOffsetBasis;

            for (SizeType i = startPos; i < maxLength;   i)
            {
                TCharType ch = str[i];

                if (str[i] == '\\' || str[i] == '/')
                {
#if _WIN64
                    Value ^= Value >> 32;
#endif
                    return SearchResult(
                        i,
                        Value
#if _DEBUG
                        , StringType(str   startPos, str   i)
#endif
                    );
                }

                TTrieTraits::CalcHash(Value, FNVPrime, ch);
            }

#if _WIN64
            Value ^= Value >> 32;
#endif

            return SearchResult(
                StringType::npos,
                Value
#if _DEBUG
                , StringType(str   startPos, str   maxLength)
#endif
            );
        }
    private:
        PathNodeType                Root;
    };
}

tests example:

   Tree.Add("C:\\Program Files\\XXX");
    Tree.Add("C:\\Program Files\\Ymal");
    Tree.Add("D:\\Tests\\XXX/");
    Tree.Add(R"(Art_Resources\Characters\Hero\105\Textures)");
    Tree.Add(R"(Art_Resources\Characters\Hero\107\Textures)");

    assert(Tree.IsChild("C:\\Program Files\\XXX"));
    assert(Tree.IsChild("C:\\Program Files\\XXX/1.log"));
    assert(Tree.IsChild("C:\\Program Files\\XXX/XXX2"));
    assert(Tree.IsChild("C:\\Program Files\\XXX/XXX2/7.exe"));
    assert(!Tree.IsChild("C:\\Program Files\\XXXX/1.log"));
    assert(!Tree.IsChild("C:\\Program Data\\XXXX/1.log"));
    assert(!Tree.IsChild("D:\\Program Data\\XXXX/1.log"));
    assert(!Tree.IsChild("D:\\Tests\\XXXX/1.log"));
    assert(Tree.IsChild("D:\\Tests\\XXX/1.log"));
    assert(Tree.IsChild("D:\\Tests\\XXX/X2"));

    assert(!Tree.IsChild(R"(Art_Resources\Characters\Hero\101\Ani)"));
    assert(!Tree.IsChild(R"(Art_Resources\Characters\Hero\107\10700.FBX)"));
    assert(Tree.IsChild(R"(Art_Resources\Characters\Hero\107\Textures\10700.FBX)"));