Vous pouvez vous abonner à nos annonces de séminaires http://gallium.inria.fr/seminaires/ S E M I N A I R E __ / _` _ / / o / ) __) / / / / / /\/| (___/ (_/ (_ (_ / (__/ / | I N R I A - Paris 2 rue Simone Iff (ou: 41 rue du Charolais) Salle Lions 1, bâtiment C MERCREDI 12 juin, 10h30 -------------- Victor Miraldo -------------- Universiteit Utrecht ==================================== Lessons from Structural Differencing ==================================== Structural differencing aims at detecting changes at a smaller granularity than lines of code, as opposed to the UNIX diff, for example. This improved granularity helps in developing better merge functions, that require less human interaction, consequently it is usually more expensive to compute than a regular line-based patch. This talk will go over the implementation of an efficient structural differencing algorithm, focusing on how it differs from the state-of-the art and the general lessons we can extract from it. Our algorithm works over a novel representation for structured patches, which enables us to represent arbitrary tree permutations and duplications. Surprisingly, this added expessive power lowers the algorithm's complexity. The final algorithm runs in linear time, making it a competitive approach, in practice.