Buscando un método o algoritmo eficiente para verificar si un archivo pertenece a un elemento específico en una lista de rutas de carpetas determinada
Tengo una lista de rutas de carpetas. Puede haber muchas, docenas o incluso cientos de rutas de carpetas en esta lista. por ejemplo:
C:\Program Files\7-Zip
// muchos directorios bajo C:\Program Files\
C:\ProgramData\Adobe
C:\ProgramData\boost_interprocess
C:\ProgramData\dftmp
C:\ProgramData\Microsoft DNX
C:\ProgramData\NVIDIA Corporation
C:\ProgramData\Oracle
// muchos directorios bajo C:\ProgramData\
C:\Windows\Boot
// muchos directorios bajo C:\Windows\
D:\Datas\
// muchos directorios bajo D:\Datas\
Ahora proporciono una ruta, por ejemplo C:\Windows\1.log. Necesito verificar si este archivo pertenece a una carpeta en la lista anterior.
Para lograr este requisito, por supuesto, puedo recorrer toda la lista directamente y luego verificar si la ruta del archivo que quiero consultar comienza con una cierta ruta de carpeta, pero esto siento que la eficiencia es demasiado baja y hay demasiadas búsquedas inválidas, entonces, ¿existe una estrategia mejor y más eficiente para realizar esta tarea?
actualizado:
Lo siento, puede que no sea muy claro, solo necesito verificar la relación de continencia entre las rutas y no necesito verificar si estos archivos realmente existen.
Por lo tanto, creo que este debería ser un problema de algoritmo. ¿Hay alguna forma de encontrar el divisor común más grande de un conjunto de rutas? por ejemplo:
C:\ProgramData\Adobe
C:\ProgramData\boost_interprocess
C:\ProgramData\dftmp
C:\ProgramData\Microsoft DNX
C:\ProgramData\NVIDIA Corporation
El divisor común más grande de su grupo de rutas es C:\ProgramData\, así que puedo agregarlas en un paquete y luego buscar el paquete primero?
davy.ai
Una posible solución es crear una estructura de árbol utilizando la lista de rutas de carpetas. Cada nodo en el árbol representa una ruta de carpeta y sus nodos hijos representan las subcarpetas de esa ruta. En otras palabras, el árbol representará la estructura de directorios completa definida por la lista de rutas de carpetas.
Cuando se necesita verificar una nueva ruta de archivo en esta lista, podemos comenzar en la raíz del árbol (es decir, el directorio de nivel superior) y recorrer el árbol para encontrar el nodo que corresponde al directorio que contiene el archivo. Esto se puede hacer comparando cada nivel de la ruta de archivo con los nombres de los nodos hijos del nodo actual. Una vez que encontramos el nodo que corresponde al directorio que contiene el archivo, sabemos que el archivo pertenece a una de las carpetas de la lista.
Este enfoque tiene la ventaja de reducir la cantidad de comparaciones que necesitamos realizar, ya que solo recorremos las partes del árbol que contienen directorios relevantes. Sin embargo, construir el árbol puede ser costoso, especialmente si hay muchas carpetas en la lista. Además, la actualización del árbol cuando cambia la lista también puede ser complicada.
Alternativamente, podemos utilizar el prefijo común más largo entre las rutas de carpeta de la lista como una heurística para reducir el espacio de búsqueda. Primero podemos comparar la ruta de archivo con el prefijo común más largo y solo iterar sobre las rutas de carpeta que tienen el mismo prefijo que la ruta de archivo o son descendientes de dichas rutas. Este enfoque no requiere construir un árbol, pero aún puede ser costoso si el prefijo común es demasiado largo o si hay muchas rutas de carpetas con prefijos diferentes.