Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Difference Algorithm

Difference Algorithm

- Myers Algorithm
- SES / LCS
- Edit Graph

- Paul Heckel Algorithm

YuyaHorita

August 31, 2018
Tweet

More Decks by YuyaHorita

Other Decks in Programming

Transcript

  1. "HFOEB  *OUSPEVDUJPO w ࠩ෼ͱ͸ʁ w ฤूͱ͍͏ߟ͑ํ  .ZFST"MHPSJUIN w

    'FBUVSFT w 4&4-$41SPCMFN w &EJU(SBQI w ݪཧ w .ZFST0WFSWJFX  1BVM)FDLFM"MHPSJUIN w 'FBUVSFT w ݪཧ w )FDLFM0WFSWJFX  4VNNBSZ
  2. source = [1, 2, 3, 4, 5] ࠩ෼ͱ͸ʁ target =

    [1, 3, 5, 7] EJ⒎ TPVSDF UBSHFU 
  3. source = [1, 2, 3, 4, 5] ࠩ෼ͱ͸ʁ target =

    [1, 3, 5, 7] EJ⒎ TPVSDF UBSHFU  %FMFUF %FMFUF *OTFSU
  4. source = [1, 2, 3, 4, 5] ࠩ෼ͱ͸ʁ target =

    [1, 3, 5, 7] EJ⒎ TPVSDF UBSHFU  %FMFUF %FMFUF *OTFSU &EJU4DSJQU
  5.  ฤूͱ͍͏ߟ͑ํ        

     TPVSDF UBSHFU EJ⒎ TPVSDF UBSHFU  %FMFUF %FMFUF *OTFSU
  6. 'FBUVSFT w 4JNQMF w 0 /% $PNQMFYJUZ w %FMFUF*OTFSU4DSJQU w

    4IPSUFTU w "EPQUFEJO%J⒎6UJM IUUQTEFWFMPQFSBOESPJEDPNSFGFSFODFBOESPJETVQQPSUWVUJM%J⒎6UJM
  7. &EJU(SBQI source = [A, B, C, A, B, B, A]

    target = [C, B, A, B, A, C] ίϯϐϡʔλͰղ͚ͦ͏ͳײ͡ʹදݱ
  8. source = [A, B, C, A, B, B, A] target

    = [C, B, A, B, A, C] (0, 0) A B C A B B A C B A B A C 0 1 2 3 4 5 0 1 2 3 4 5 6 source target 4UBSU (7, 6) &OE
  9. source = [A, B, C, A, B, B, A] target

    = [C, B, A, B, A, C] (0, 0) A B C A B B A C B A B A C 0 1 2 3 4 5 0 1 2 3 4 5 6 source target NBUDIQPJOU QPJOUBTTBNFTZNCPM (7, 6) 4UBSU &OE
  10. source = [A, B, C, A, B, B, A] target

    = [C, B, A, B, A, C] (0, 0) A B C A B B A C B A B A C 0 1 2 3 4 5 0 1 2 3 4 5 6 source target NBUDIQPJOU QPJOUBTTBNFTZNCPM (7, 6) &EHFʹԊͬͯɺ4UBSU͔Β&OE·ͰҠಈ͢Δ ӈɾԼɾࣼΊํ޲ͷҠಈ㲈EFMFUF JOTFSU EPOPUIJOH 4UBSU &OE 4UBSU &OE
  11. source = [A, B, C, A, B, B, A] target

    = [C, B, A, B, A, C] (0, 0) A B C A B B A C B A B A C 0 1 2 3 4 5 0 1 2 3 4 5 6 source target NBUDIQPJOU QPJOUBTTBNFTZNCPM (7, 6) 4&4 4UBSU &OE 4UBSU࠲ඪ&OE࠲ඪͷ࠷୹ܦ࿏  4UBSU &OE
  12. (0, 0) 0 1 2 3 4 5 (7, 6)

    0 1 2 3 4 5 6 Delete A Delete B 3JHIU.PWFNFOU #PUUPN.PWFNFOU %JBHPOBM.PWFNFOU EFMFUF JOTFSU EPOPUIJOH TBNFTZNCPM NBUDIQPJOU QPJOUBTTBNFTZNCPM Insert B Insert C source = [A, B, C, A, B, B, A] target = [C, B, A, B, A, C] A B C A B B A C B A B A C target Delete B 4UBSU &OE source 4UBSU &OE
  13. ҠಈίετJT%JBHPOBM  source = [A, B, C, A, B, B,

    A] target = [C, B, A, B, A, C] (0, 0) 0 1 2 3 4 5 (7, 6) 0 1 2 3 4 5 6 Delete A Delete B NBUDIQPJOU QPJOUBTTBNFTZNCPM Insert B Insert C A B C A B B A C B A B A C target Delete B 4UBSU &OE ࠷୹ܦ࿏ͷ૯Ҡಈίετ % 4&4ͷεΫϦϓτ਺ source 4UBSU &OE
  14. (0, 0) 0 1 2 3 4 5 (7, 6)

    0 1 2 3 4 5 6 Delete A Delete B NBUDIQPJOU QPJOUBTTBNFTZNCPM Insert B Insert C source = [A, B, C, A, B, B, A] target = [C, B, A, B, A, C] A B C A B B A source C B A B A C target Delete B 4UBSU &OE 3 1 x - y = k 0 -1 2 Y Z 4UBSU &OE
  15. (0, 0) 0 1 2 3 4 5 (7, 6)

    0 1 2 3 4 5 6 Delete A Delete B NBUDIQPJOU QPJOUBTTBNFTZNCPM Insert B Insert C source = [A, B, C, A, B, B, A] target = [C, B, A, B, A, C] A B C A B B A source C B A B A C target Delete B 4UBSU &OE 3 1 x - y = k 0 -1 2 Y Z k + 1 k - 1 k 4UBSU &OE
  16. (0, 0) 0 1 2 3 4 5 (7, 6)

    0 1 2 3 4 5 6 Delete A Delete B NBUDIQPJOU QPJOUBTTBNFTZNCPM Insert B Insert C source = [A, B, C, A, B, B, A] target = [C, B, A, B, A, C] A B C A B B A source C B A B A C target Delete B 4UBSU &OE 3 1 0 -1 2 Y Z k + 1 k - 1 k ඇର֯ͳҠಈΛ%ճߦͬͨ࠷௕ͷܦ࿏ %͕ح਺ͳΒLح਺ͷର֯ઢ %͕ۮ਺ͳΒLۮ਺ͷର֯ઢ্Ͱࢭ·Δ 4UBSU &OE
  17. For D ← 0 to M + N Do For

    k ← -D to D in steps of 2 Do Until D Path gets to furthest point Do Move on edges If (N, M) is the reached point Then Found the SES. Array[with: k] M = source.count N = target.count %͕ح਺ͳΒLح਺ͷର֯ઢ %͕ۮ਺ͳΒLۮ਺ͷର֯ઢ্Ͱࢭ·Δ &EJU(SBQI্Ͱ࠷ԕͷύε͸֎प Complexity: O((M+N)D) ίετ%Ͱߦ͚ͨ࠷ԕͷ࠲ඪΛLઢຖʹه࿥ %શͯԼҠಈ %શͯӈҠಈ &OE࠲ඪ
  18. w 4JNQMF0QUJNJ[BCMF w 0 / $PNQMFYJUZ w %FMFUF *OTFSU .PWF4DSJQU

    w /PU"MXBZT4IPSUFTU w #BTFPG 'FBUVSFT 3Y%BUB4PVSDFT
  19. TPVSDF UBSHFU 4ZNCPM5BCMF       

         &MFNFOU DPVOUJOTPVSDF DPVOUJOUBSHFU JOEFYJOTPVSDF                OVMM        OVMM source = [1, 2, 3, 4, 5, 4] target = [1, 3, 5, 2, 2, 7] w TPVSDF UBSHFUͷ֤ཁૉ &MFNFOU Λ,FZͱͯ͠ɺ%JDUJPOBSZͷ4ZNCPM5BCMFʹొ࿥ w 7BMVFʹ͸ͦͷཁૉͷ TPVSDF಺Ͱͷ਺ɺUBSHFU಺Ͱͷ਺ɺTPVSDF಺ͰͷJOEFY ˞ݸ͚ͩͷ৔߹ ݸPS̎ݸҎ্ͷ৔߹͸OVMM
  20. TPVSDF UBSHFU 4ZNCPM5BCMF       

         &MFNFOU DPVOUJOTPVSDF DPVOUJOUBSHFU JOEFYJOTPVSDF                OVMM        OVMM source = [1, 2, 3, 4, 5, 4] target = [1, 3, 5, 2, 2, 7] w TPVSDF UBSHFUͷ֤ཁૉ &MFNFOU Λ,FZͱͯ͠ɺ%JDUJPOBSZͷ4ZNCPM5BCMFʹొ࿥ w 7BMVFʹ͸ͦͷཁૉͷ TPVSDF಺Ͱͷ਺ɺUBSHFU಺Ͱͷ਺ɺTPVSDF಺ͰͷJOEFY ɾશཁૉΛ؅ཧ͢Δ4ZNCPM5BCMFΛҰͭ༻ҙ ɾTPVSDF UBSHFUͦΕͧΕͷཁૉͷొ࿥࡞ۀΛߦ͏ ˞ݸ͚ͩͷ৔߹ ݸPS̎ݸҎ্ͷ৔߹͸OVMM
  21. UBSHFU TPVSDF 4ZNCPM5BCMF       &MFNFOU

    DPVOUJOTPVSDF DPVOUJOUBSHFU JOEFYJOTPVSDF                OVMM        OVMM w TPVSDF UBSHFUͷͦΕͧΕͷཁૉͱରରԠͨ͠\TPVSDF UBSHFU^3FGFSFODFTΛ༻ҙ͢Δɻ w ରରԠ͍ͯ͠Δཁૉ΁ͷࢀরΛอ࣋͠ɺࢀরݩ͸4ZNCPM5BCMFPS΋͏ยํͷ഑ྻ ˞ͲͪΒʹ΋ͦͷཁૉ͕͋Δ৔߹͸΋͏ยํͷ഑ྻ͕༏ઌ       TZNCPM5BCMF TZNCPM5BCMF TZNCPM5BCMF TZNCPM5BCMF TZNCPM5BCMF TZNCPM5BCMF UBSHFU3FGFSFODFT
  22. UBSHFU TPVSDF 4ZNCPM5BCMF       &MFNFOU

    DPVOUJOTPVSDF DPVOUJOUBSHFU JOEFYJOTPVSDF                OVMM        OVMM w TPVSDF UBSHFUͷͦΕͧΕͷཁૉͱରରԠͨ͠\TPVSDF UBSHFU^3FGFSFODFTΛ༻ҙ͢Δɻ w ରରԠ͍ͯ͠Δཁૉ΁ͷࢀরΛอ࣋͠ɺࢀরݩ͸4ZNCPM5BCMFPS΋͏ยํͷ഑ྻ ˞ͲͪΒʹ΋ͦͷཁૉ͕͋Δ৔߹͸΋͏ยํͷ഑ྻ͕༏ઌ       UIF0UIFS UIF0UIFS UIF0UIFS UIF0UIFS TZNCPM5BCMF TZNCPM5BCMF UBSHFU3FGFSFODFT
  23. UIF0UIFS UIF0UIFS UIF0UIFS UIF0UIFS TZNCPM5BCMF TZNCPM5BCMF    

      UIF0UIFS UIF0UIFS UIF0UIFS TZNCPM5BCMF UIF0UIFS TZNCPM5BCMF       TPVSDF TPVSDF3FGFSFODFT UBSHFU UBSHFU3FGFSFODFT
  24. w UIF0UIFSࢀরͷ৔߹.PWF w TZNCPM5BCMFࢀরͷ৔߹TPVSDFˠ%FMFUF UBSHFUˠ*OTFSU UIF0UIFS UIF0UIFS UIF0UIFS UIF0UIFS TZNCPM5BCMF

    TZNCPM5BCMF       UIF0UIFS UIF0UIFS UIF0UIFS TZNCPM5BCMF UIF0UIFS TZNCPM5BCMF       TPVSDF TPVSDF3FGFSFODFT UBSHFU UBSHFU3FGFSFODFT
  25. ૬खଆͷ഑ྻʹཁૉ͕͋ΔͳΒɺJOEFYΛม͑Δ.PWFͰ0, 4ZNCPM5BCMF͔͠ࢀরग़དྷͳ͍ͳΒɺ TPVSDFͳΒ%FMFUFɺUBSHFUͳΒ*OTFSU͢Δ͔͠ແ͍ UIF0UIFS UIF0UIFS UIF0UIFS UIF0UIFS TZNCPM5BCMF TZNCPM5BCMF 

         UIF0UIFS UIF0UIFS UIF0UIFS TZNCPM5BCMF UIF0UIFS TZNCPM5BCMF       ˞ແବͳ.PWF͕ൃੜ͢ΔՄೳੑ༗Γ TPVSDF TPVSDF3FGFSFODFT UBSHFU UBSHFU3FGFSFODFT w UIF0UIFSࢀরͷ৔߹.PWF w TZNCPM5BCMFࢀরͷ৔߹TPVSDFˠ%FMFUF UBSHFUˠ*OTFSU
  26. ɾHeckel, Paul (1978), "A Technique for Isolating Differences Between Files”,

    Communications of the ACM, 21: 264–268, doi:10.1145/359460.359467, retrieved 2011-12-04 ɾE. W. Myers, ‘‘An O(ND) difference algorithm and its variations,’’ Algorithmica, 1 (1986), pp. 251−266. 3FGFSFODFT