Help us understand the problem. What is going on with this article?

PythonのSequenceMatcherをRustに移植する

More than 3 years have passed since last update.

TL;DR

https://github.com/toruot/difflib.rs
※ エラーハンドリングとか動作検証とかザルです。

SequenceMatcherとは

diffを算出するプログラム。Python本体組み込みのdifflibモジュールに収録されている。アルゴリズムは、ゲシュタルトアプローチというものを採用している。

http://docs.python.jp/3.4/library/difflib.html

6.3. difflib — 差分の計算を助ける

HTML や context diff, unified diff などいろいろなフォーマットで出力するために、このモジュールを利用することができます。

基本的なアルゴリズムは、1980年代の後半に発表された Ratcliff と Obershelp による”ゲシュタルトパターンマッチング”と大げさに名づけられたアルゴリズム以前から知られている、やや凝ったアルゴリズムです。このアイデアは、マッチ列から左または右に伸びる断片に対して再帰的にあてはめられます。この方法では編集を最小にする列は取り出されませんが、人間の目からみて「正しい感じ」にマッチする傾向があります。
実行時間: 基本的な Ratcliff-Obershelp アルゴリズムは、最悪の場合3乗、期待値で2乗となります。 SequenceMatcher オブジェクトでは、最悪のケースで2乗、期待値は比較されるシーケンス中に共通に現れる要素数に非常にややこしく依存しています。最良の場合は線形時間になります。

difflibソースコード: https://hg.python.org/cpython/file/3.5/Lib/difflib.py

http://gihyo.jp/dev/column/01/prog/2011/diff_sd200906

diffの動作原理を知る~どのようにして差分を導き出すのか

本稿ではWuのアルゴリズムについて解説しましたが,ここでは他のアルゴリズムについて軽く紹介します。

  • 動的計画法(Dynamic Programming)

  • Myersのアルゴリズム
    GNU diffutilsや分散型バージョン管理システムの1つであるGitのdiffエンジンとして採用されているXLibdiffの実装はこのアルゴリズムを基にしています。

  • Gestalt Approach
    2つの要素列中の連続する共通部分を探し出し,その共通部分を中心に2つの要素列をそれぞれ分割します。そして,その分割した2つの要素列の左部分と右部分のそれぞれから再び共通部分を探し出すといったことを繰り返し,最後にその共通部分を全部つなげてLCSなどを算出するというアルゴリズムです。

https://unoh.github.io/2008/11/13/diff_with_c.html

Gestalt Approach

Pythonに標準で搭載されているdifflibパッケージで使われているアルゴリズムです。このアルゴリズムはまず最初に2つのシーケンス間の最長一致項を検出した後、その一致項を起点に、文字列を左側と右側に分割し、両側に対してまた最初に戻るということを繰り返すことによってLCSを求めます。
こちらに解説とアセンブリコードが載っています。

http://bokko.hatenablog.com/entry/20081001/1222793274

Mercurialのdiff

Mercurialで使われているGestalt Approachについては、まだ、あんまり真面目に資料読んでないので、実際の計算量とかはよくわかってないけど、上記の実験結果を見る限りではGitとほぼ同じ。Mercurialのdiffは実はPythonに標準搭載されているdifflibをそのまま使っているんだが、このdifflib、最初からUnified Formatをサポートしたりしていて、実はかなり便利だったりする。しかも速いし。

difflib.rs

https://github.com/toruot/difflib.rs

SequenceMatcherをメインに、difflibのいくつかの機能をRustで実装しました。

READMEのサンプル実行例:
tmp.png

逐語的に移植したため、アルゴリズムの詳細を理解したわけではありませんが、それっぽく動作しています。すごいですね(アルゴリズムを考案した人とPythonで実装した人が)。

crates.ioで検索するとdiff関連のcrateがいくつか見つかりますが、どれもアルゴリズムはWuのようです。

以前からdifflibのDifferクラスを改造してこんなものを作ったりしていたのですが、SequenceMatcherには触れたことが無かったので、今回、移植してみました。

結論は特にないのですが、PythonとRustの勉強が両方できてお得でした。namedtupleとか知らなかった。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away