この記事は、2015年のGo Advent Calendarの25日目の記事です。 Go Advent Calendarのその2とその3ができる前、最終日だけ空いてて滑り込みで登録したのはいいけど、なんかネタないかなーと思いつつ、自分のgithubリポジトリを漁っていたらdiffのアルゴリズムをGoで実装したやつが出てきたので紹介してみます。 gonpはGoによるdiffのアルゴリズム実装です。元々は昔々C++で書いたdtlというdiffライブラリの簡易移植で、diffを取るのに必要な以下の要素を求めることができます。 編集距離(Edit Distance) LCS(Longest Common Subsequence) SES(Shortest Edit Script) diffのアルゴリズムにはさまざまな種類があり、中でもdiffに限らず様々な用途に応用可能な動的計画法が有名です。ただ
![gonp〜Goによるdiffのアルゴリズム実装〜 - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/c81b9666dec30788b16f7c8cef09e6c12e37cc03/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Fadvent-calendar-ogp-background-7940cd1c8db80a7ec40711d90f43539e.jpg%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk3MiZoPTM3OCZ0eHQ9Z29ucCVFMyU4MCU5Q0dvJUUzJTgxJUFCJUUzJTgyJTg4JUUzJTgyJThCZGlmZiVFMyU4MSVBRSVFMyU4MiVBMiVFMyU4MyVBQiVFMyU4MiVCNCVFMyU4MyVBQSVFMyU4MiVCQSVFMyU4MyVBMCVFNSVBRSU5RiVFOCVBMyU4NSVFMyU4MCU5QyZ0eHQtYWxpZ249bGVmdCUyQ3RvcCZ0eHQtY29sb3I9JTIzM0EzQzNDJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTU2JnM9OGYzZjM0NDhmMmE1OTk4ZWQwYjY1NWQzOGU4NjQzYzY%26mark-x%3D120%26mark-y%3D96%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZoPTc2Jnc9OTcyJnR4dD0lNDBjdWJpY2RhaXlhJnR4dC1jb2xvcj0lMjMzQTNDM0MmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9MzYmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz0wZGMyYWE5YjNiOWY5YzY4NTk2MTRmYjIzYTU5OTUxYQ%26blend-x%3D120%26blend-y%3D445%26blend-mode%3Dnormal%26txt64%3DaW4gTWVyY2FyaQ%26txt-width%3D972%26txt-clip%3Dend%252Cellipsis%26txt-color%3D%25233A3C3C%26txt-font%3DHiragino%2520Sans%2520W6%26txt-size%3D36%26txt-x%3D134%26txt-y%3D546%26s%3D7b1708337b725bb9b5f65228ce955b30)