Bonjour,
 
J'essaie de développer un algorithme permettant de conserver dans une structure l'ensemble des versions d'une même structure (par exemple un historique wiki, un pseudo-fichier CVS, ...). J'appelle ça du versioning mais, devant le peu d'informations que j'ai réussi à trouver sur le sujet sur le net (et devant le fait que ce que j'ai développé jusque là ne me satisfait pas pleinement sur le plan des capacités), je me demande s'il n'y a pas un terme plus spécifique.
Auriez-vous un début de piste (un article, un mot, un chercheur, un article wiki,...) qui pourrait m'aider ?
Merci d'avance

Les systèmes de versioning conservent tout simplement le diff (delta encoding) entre deux "versions" successives et stockent ces diffs (avec potentiellement des snapshots intégraux, à l'instar d'un DivX, pour accélérer la récupération d'une version donnée) plutôt que de stocker toutes les versions.

En cherchant plus en détail diff sur wikipedia (je l'avais déjà fait mais sans explorer plus en détail, m'attendant à une simple exlication technique, j'aurais dû), j'ai trouvé un lien vers la distance de Levenshtein. A priori, c'est exactement ce que je recherche. Avec tout ça, je suis paré.
Merci

Heuuu non c'est pas du tout la distance de levenshtein que tu cherches, elle ne te donne qu'un nombre (la distance entre deux chaînes) mais ne te permet pas de retrouver une chaîne A à partir d'une chaîne B et de la distance entre A et B.
 
Pour des algos de diff, tu peux voir An algorithm for differential file comparison de J. W. Hunt et M. D. McIlroy

C'est la page wiki de levenshtein qui m'a plu parce qu'il y avait un algorithme dessus
Tu as raison, c'est exactement de diff que j'ai besoin
Ceci dit, en adaptant un peu l'algorithme de Levenshtein, on doit bien pouvoir retrouver une sorte de "plus court chemin entre deux chaînes", non ?

Je vais creuser un peu le code de java-diff, en tout cas, je pense pas trop faire fausse route, là

Et merci pour le lien, je m'en vais potasser ça ²

Un algo pas très fûté mais simple serait de conserver les versions entières (à supposer que les fichiers ne sont pas énormes), et de temps en temps, d'en zipper par paquets de 5 ou 10. Par ex., avec un fichier en 33 versions, on zippe les v1 à v10, puis v11 à v20, puis v21 à v30. Naturellement, l'algo de compression va supprimer les redondances. On peut décider de ne pas comprimer 3 les dernières versions, qui sont les plus utilisées, ou de zipper les v1 et v2, puis d'ajouter les versions suivantes au fur et à mesure.
Là où un tel algo n'est pas top performant, est lorsque l'on veut récupérer 2 versions se trouvant dans des paquets différents (la v8 et la v13 par ex.). Il faut alors dézipper les 2 paquets. Pour des fichiers de qq dizaines de ko, ça fait des zip assez faibles, et l'opération est rapide avec les PC actuels. L'autre pb, c'est que la compression est loin d'être optimale.

Merci de ton intervention
Je me disais justement qu'après l'étude de diff, il me faudrait trouver le meilleur système de stockage.
Au départ j'étais parti pour stocker toutes les versions indépendamment, chacune dans un objet d'une table spécifique de ma base... Du naïf de chez naïf, quoi. Il fallait arranger ça
J'aime assez ton idée. Dans mon cas (les fichiers que je veux stocker sont des fichiers de type wiki écrits à la main donc pas très gros en théorie et assez proches entre deux versions), ça pourrait être intéressant à adopter (en mélangeant avec le diff, histoire de compresser encore les n versions d'un packet).
Comme la dernière version est la plus utilisée et que j'aurai (relativement rarement) à accéder aux versions lointaines, je pense utiliser la méthode suivante (avec n le nombre total de versions) :
- je fais des paquets de x versions.
- je stocke indépendamment les unes des autres les (n mod x) dernières versions.

Fréquement moins qu'un bon algo de diff, d'ailleurs il a été prouvé que la compression de données est un cas particulier du calcul de différence

Tu es un fin spécialiste du domaine ou c'est juste une sacrée bonne culture générale en informatique, Masklinn ?

Juste de la culture générale