Permutación óptima para almacenamiento diferencial

Question

Este es un problema práctico que me encontré hace poco. Estoy convencido de que ya se ha resuelto, pero no sé por dónde empezar, ya que desconozco toda la terminología. Espero que alguien pueda orientarme :)

Suponga que tiene n archivos de varios tamaños. Puede utilizar un programa informático para obtener un archivo diff, que contiene la diferencia entre dos archivos. En función de la similitud del fichero oA y oB Esta diferencia dAB podría ser muy pequeño. El tamaño de un diff no se ve afectado por el orden de los archivos; dAB tiene el mismo tamaño que dBA . Sin embargo, los diferenciales son monodireccionales: Para reconstruir oA necesitarías oB y dBA como dAB no serviría de nada.

Quieres encontrar la permutación óptima de los diffs, de forma que partiendo sólo de uno de los archivos originales, puedas recrear todos los demás archivos. El tamaño de todos los archivos diff posibles ya se conoce. Por ejemplo, dados los ficheros oA , oB , oC , oD y oE la permutación óptima podría ser dAB , dAC , dBD , dCE .

Answer 1

Se puede plantear como un problema de árbol de expansión mínimo. Crea un grafo completo con los vértices correspondientes a tus ficheros. Etiqueta cada arista con el tamaño del archivo de diferencias entre los dos archivos; como señalas, estas diferencias son las mismas independientemente de la dirección. A continuación, puede utilizar Algoritmo de Kruskal para encontrar un árbol de expansión de peso mínimo.

Para elegir qué archivos quieres conservar, empieza con el archivo más pequeño que tengas, digamos A. Para cada una de las aristas de A en el árbol de mínimo peso, elige el archivo de diferencias que hace la transición de A al archivo correspondiente al siguiente vértice. A continuación, de cada uno de estos vértices, tomar cada archivo diff moviendo hacia fuera.

Así que para tu ejemplo, tu árbol de expansión tendría el siguiente aspecto:

A -- B -- D
|
C -- E