确保不存在重复的目录路径

Question

我正在编写一个脚本，其中用户选择目录，然后将这些目录存储在数组属性中，以便可以递归抓取它们。{  "archives": [    "C:\\AMD\\Packages",    "C:\\Users",    "C:\\Windows",    "D:\\",    "E:\\Pictures\\Birthday"  ]}我显然不想存储重复的路径或其他路径包含的路径。例如，如果用户要选择一个新文件夹添加到数组中，E:\\Pictures，E:\\Pictures\\Birthday则将被丢弃并替换为它，因为E:\\Pictures包含E:\\Pictures\\Birthday。{  "archives": [    "C:\\AMD\\Packages",    "C:\\Users",    "C:\\Windows",    "D:\\",    "E:\\Pictures"  ]}我知道这可以通过解析所有正在考虑的值（即['C:', 'AMD', 'Packages'], [...], ...等）然后将它们相互比较来完成。然而，这似乎非常密集，尤其是当路径数组变得更大并且目录路径更长时。您也可以通过将字符串与includes. 例如，如果A包含B或B包含A，则将它们拆分，并丢弃长度较长的。for (const dir of dirs){  if (newPath.includes(dir) || dir.includes(newPath)){    if (newPath.split('\\') < dir.split('\\')){      // remove dir from json object and replace it with newPath    }  } else {    pathArray.push(dir)  }}阅读以下答案之一后，我才意识到该includes方法遇到了比较相似但独特的路径即C:\Users和 的问题C:\User。虽然必须有更好的方法来做到这一点？

Answer 1

这个功能会给你你想要的结果。它首先查看路径的父级是否存在于档案中，如果存在，则不执行任何操作。如果没有，则删除路径的所有子项，然后插入新路径。

更新

我delim为该函数添加了一个输入，使其也可用于 unix/MacOS 样式的文件名。

let data = {

  "archives": [

    "C:\\AMD\\Packages",

    "C:\\Users",

    "C:\\Windows",

    "D:\\",

    "E:\\Pictures"

  ]

};

const add_to_archives = (path, data, delim) => {

  // does the parent of this path already exist? if so, nothing to do

  if (data.archives.reduce((c, v) =>

      c || path.indexOf(v.slice(-1) == delim ? v : (v + delim)) === 0, false)) return data;

  // not found. remove any children of this path

  data.archives = data.archives.filter(v => v.indexOf(path.slice(-1) == delim ? path : (path + delim)) !== 0);

  // and add the new path

  data.archives.push(path);

  return data;

}

add_to_archives("E:\\Pictures\\Too", data, "\\");

console.log(data);

add_to_archives("E:\\PicturesToo", data, "\\");

console.log(data);

add_to_archives("D:\\Documents", data, "\\");

console.log(data);

add_to_archives("C:\\AMD", data, "\\");

console.log(data);

data = {

  "archives": [

    "/var/www/html/site",

    "/etc",

    "/usr/tim",

    "/bin"

  ]

};

add_to_archives("/var/www/html/site2", data, "/");

console.log(data);

add_to_archives("/etc/conf.d", data, "/");

console.log(data);

add_to_archives("/usr", data, "/");

console.log(data);

add_to_archives("/var/www/html", data, "/");

console.log(data);

.as-console-wrapper {

  max-height: 100% !important;

}

Answer 2

我们可以通过使用前缀树来解决这个问题

目的是限制我们检查包含或“包含”的路径数量。

如果您有很多兄弟姐妹（树遍历 + 查找作为每个文件夹的键），这种方法可能很有用。如果您经常在archives

算法

tree = {}

foreach path

    split the path in folders (one may iterate with substring but it is worth it?)

    try to match folders of that path while traversing the tree

    if you encounter a stop node, skip to next path

    if not, 

        if your path end on an existing node

            mark that node as a stop node

            drop the children of that node (you can let them be, though)

        else

            include the remaining folders of the path as node in tree

            mark the last node as a stop node

实施

请注意，如果路径包含名为“stop”的文件夹，则下面的实现将失败。按主观偏好顺序

• 使用Map和Symbol('stop')

• 或一棵真正的树（至少不要在 boolean 旁边存储文件夹stop）

• 如果您设法到达路径的尽头，请不要假设任何停止节点并始终丢弃子节点

• 希望没有人试图比你更聪明并重命名stop为一些晦涩的 - 文件夹将不存在 -lolol_xxzz9_stop

function nodupes(archives){

    tree = {};

    archives.forEach(arch=>{

        const folders = arch.split('\\');

        folders.splice(1,1);

        //case of empty string such as D:\\\

        if(folders[folders.length-1].length==0){folders.pop();}

        let cur = tree;

        let dropped = false;

        let lastFolderIndex = 0;

        let ok = folders.every((folder,i)=>{

            if(cur[folder]){

                if(cur[folder].stop){

                    dropped = true;

                    return false;

                }

                cur = cur[folder];

                return true;

            }

            cur[folder] = {}

            cur = cur[folder];

            lastFolderIndex = i;

            return true;

        });

        if(ok){

            cur.stop = true;

            //delete (facultatively) the subfolders

            if(lastFolderIndex < folders.length-1){

                console.log('cleanup', folders, 'on node', cur)

                Object.keys(cur).forEach(k=>{

                    if(k != 'stop'){

                        delete cur[k];

                    }

                })

            }

            

        }

    });

    //console.log('tree', JSON.stringify(tree,null,1));

    //dfs on the tree to get all the paths to... the leaves

    let dfs = function(tree,paths,p){

        if(tree.stop){

            return paths.push(p.join('\\\\'));

        }

        Object.keys(tree).forEach(k=>{

            dfs(tree[k], paths, p.concat(k));

        });

    }

    let paths = [];

    dfs(tree, paths,[]);

    return paths;

}

let archives = [

    'C:\\\\ab',

    'D:\\\\', //just some root

    'D:\\\\ab',//be dropped

    'D:\\\\abc',//dropped as well

    'F:\\\\abc\\\\e',//two folder creation

    'C:\\\\ab\\c',

    'B:\\\\ab\\c',

    'B:\\\\ab',//expect B\\\\ab\\c to be dropped

]

console.log(nodupes(archives))