algorithm - Secuencia de operaciones más corta que transforma un árbol de archivos a otro.

edit-distance filetree (5)

Enumere todos los archivos en B y sus tamaños y sumas de comprobación asociados; ordenar por tamaño / suma de comprobación.
Enumere todos los archivos en A y sus tamaños y sumas de comprobación asociados; ordenar por tamaño / suma de comprobación.
Ahora, haciendo una comparación de lista ordenada, haga lo siguiente:
a. para cada archivo en A pero no en B, elimínelo.
segundo. para cada archivo en B pero no A, créelo.
do. para cada archivo en A y B, cambie el nombre de todos los que encuentre de A a B, luego haga copias del resto en B. Si va a sobrescribir un archivo existente, guárdelo en un lado en una lista separada. Si encuentra A en esa lista, úselo como archivo fuente.

Haga lo mismo con los directorios, eliminando los que están en A pero no en B y agregándolos en B pero no en A

Realice la iteración por suma de comprobación / tamaño para asegurarse de que nunca tendrá que visitar los archivos dos veces o preocuparse por eliminar un archivo que más tarde deberá volver a sincronizar. ¿Supongo que está intentando mantener dos directorios sincronizados sin copiar innecesariamente?

La complejidad general es O (N log N) más el tiempo que demore en leer todos esos archivos y sus metadatos.

Este no es el problema de la distancia de edición de árbol; es más un problema de sincronización de lista que sucede para generar un árbol.

Dados dos árboles de archivos A y B, ¿es posible determinar la secuencia más corta de operaciones o una secuencia corta de operaciones que es necesaria para transformar A en B?

Una operación puede ser:

Crear una carpeta nueva, vacía
Crea un nuevo archivo con cualquier contenido.
Borrar un archivo
Eliminar una carpeta vacía
Renombrar un archivo
Renombrar una carpeta
Mueve un archivo dentro de otra carpeta existente
Mueve una carpeta dentro de otra carpeta existente

A y B son idénticos cuando tendrán los mismos archivos con el mismo contenido (o el mismo tamaño de CRC) y el mismo nombre, en la misma estructura de carpetas.

Esta pregunta me ha estado confundiendo por algún tiempo. Por el momento tengo la siguiente idea básica:

Calcular una base de datos:
- Almacenar nombres de archivos y sus CRC
- Luego, busque todas las carpetas sin subcarpetas y calcule un CRC a partir de los CRC de los archivos que contienen y un tamaño del tamaño total de los archivos que contienen.
- Asciende el árbol para hacer un CRC para cada carpeta padre
Utilice el siguiente bucle con la base de datos A y la base de datos B:
- Calcule A ∩ B y elimine esta intersección de ambas bases de datos.
- Use una combinación interna para encontrar CRC coincidentes en A y B, primero las carpetas, ordenadas por tamaño desc
- mientras haya un resultado, use el primer resultado para hacer que una carpeta o archivo se mueva (posiblemente creando nuevas carpetas si es necesario), elimine de ambas bases de datos las filas de origen del resultado. Si hubo un movimiento, actualice los CRC de las carpetas principales de la nueva ubicación en la base de datos A.
- Luego elimine todos los archivos y carpetas a los que se hace referencia en la base de datos A y cree aquellos a los que se hace referencia en la base de datos B.

Sin embargo, creo que esta es realmente una forma subóptima de hacerlo. ¿Qué podrías darme como consejo?

¡Gracias!

El primer paso a seguir es determinar qué archivos deben crearse / renombrarse / borrarse.

A) Crea un mapa hash de los archivos del Árbol A
B) Ir a través de los archivos del árbol B
B.1) Si hay un archivo idéntico (nombre y contenido) en el mapa hash, entonces déjelo solo
B.2) Si el contenido es idéntico pero el nombre es diferente, cambie el nombre del archivo por el del mapa hash
B.3) Si el contenido del archivo no existe en el mapa hash, elimínelo
B.4) (si uno de 1,2,3 era verdadero) Eliminar el archivo del mapa hash

Los archivos que quedan en el mapa hash son los que deben crearse. Este debería ser el último paso, después de que se haya resuelto la estructura del directorio.

Una vez que las diferencias de archivos se han resuelto, es bastante complicado. No me sorprendería si no hubiera una solución óptima eficiente para este problema (NP-completo / difícil).

La dificultad radica en que el problema no se subdivide naturalmente. Cada paso que realice debe considerar el árbol de archivos completo. Lo pensaré un poco más.

EDITAR: Parece que los algoritmos de distancia de edición de árbol más estudiados consideran solo la creación / eliminación de nodos y la reclasificación de nodos. Esto no es directamente aplicable a este problema porque este problema permite mover subárboles enteros, lo que lo hace mucho más difícil. El tiempo de ejecución más rápido actual para el problema de la distancia de edición "más fácil" es O(N^3) . Me imagino que el tiempo de ejecución para esto será significativamente más lento.

Enlaces útiles / Referencias

Un algoritmo de descomposición óptimo para la distancia de edición de árbol - Demaine, Mozes, Weimann

Es posible que desee revisar los algoritmos de distancia de edición de árbol. No sé si esto se asignará claramente a su sistema de archivos, pero podría darle algunas ideas.

https://github.com/irskep/sleepytree (código y papel)

Este problema es un caso especial del problema de la distancia de edición del árbol , para el cual (desafortunadamente) se sabe que encontrar una solución óptima es NP-difícil. Esto significa que probablemente no haya algoritmos buenos, rápidos y precisos para el caso general.

Dicho esto, el artículo que vinculé contiene varias discusiones interesantes sobre algoritmos de aproximación y algoritmos que funcionan en casos restringidos del problema. Puede encontrar la discusión interesante, ya que ilumina muchos de los problemas que realmente surgen al resolver este problema.

¡Espero que esto ayude! ¡Y gracias por publicar una pregunta increíble!

Sólo un problema no trivial es mover carpetas y archivos. Cambiar el nombre, eliminar y crear es trivial y se puede hacer en el primer paso (o mejor en el último cuando termine).

Luego puede transformar este problema en un problema con el árbol transformador con las mismas hojas pero con una topología diferente.

Usted decide qué archivos se moverán de alguna carpeta / cubo y qué archivos se dejarán en la carpeta. La decisión se basa en el número de archivos iguales en origen y destino.
Se aplica la misma estrategia para mover carpetas en la nueva topología.

Creo que debería estar cerca de ser óptimo u óptimo si se olvida de los nombres de las carpetas y piensa solo en los archivos y la topología.