差分検出アルゴリズム三種盛り - Object.create(null)
こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください. はじめに さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました. しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です. というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説
Big Sky :: レーベンシュタイン距離を使ったあいまい grep コマンド「lsdgrep」作ってみた
元ネタはずいぶんと昔の記事なのだけど。 編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー ■ 編集距離 (Levenshtein Distance) 昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベン... http://d.hatena.ne.jp/naoya/20090329/1238307757 思い付きはまったく関係ない所から。 mp3 が数千ファイル入ってるフォルダで何かの手違いで同じ曲が入ってしまう事が結構あって重複取り去る作業してた。ID3が違ってるとMD5も違うのでレーベンシュタインの文字列距離を使ってファイル名が似てるの調べたら422ファイル消せる事が分かった。 — Vim芸人 (@mattn_jp) February 25, 2017 これを
そーだいなるらくがき帳: 2大OSSデータベースのMySQLとPostgreSQLの違いについて話してきた
第32回 PostgreSQL 勉強会(2015年10月10日)で登壇してきました。 内容は前に書いたエントリーの MySQL使いが知るべきPostgreSQLとの違いと変わらない一つのこと MySQL使いの人がPostgreSQLを始めるときの罠をまとめてみた を元に発表してきました。 と言っても今回は参加者がPostgresSQLに詳しい前提だったのでMySQLを中心に話をしました。 実際の資料は下記のとおりです。 当日はビデオ撮影があったのでそのうち動画が上がると思います。 第32回 PostgreSQL 勉強会まとめ ~ togetter ~ 流石に２時間は疲れました。 内容としては眠くならないように面白おかしく伝えようと思ったのですがなかなか難しかったです。 前半はMySQLとPostgreSQLの方向性の違いをメインにしました。 後半はMySQLは僕が実際にハマった事などをメイ
MySQL使いが知るべきPostgreSQLとの違いと変わらない一つのこと
— そーだい＠初代ALF (@soudai1025) 2015, 8月 24 とブーメラン投げて見事に刺さってるので今から記事書く。 両サイドにはかなり厳しい話もするが俺の本音を聴いておけ（関白宣言） まぁ歴史の長いRDBなのでお互いの比較記事は沢山ある。 なのでマルチスレッド(MySQL)とマルチプロセス(PostgreSQL)だとかVACUUMだって話はしない。 むしろ実際に使ってみた際の違いをにフォーカスする。 1. SQLの違い 基本的にMySQLでやっていたことはPostgreSQL出来る。 しかし関数の挙動の違いは幾つかある。 例えば時間から曜日に該当する数字に変換した場合に MySQL → date_format(time,"%w") 0から始まり、日曜日に該当する PostgreSQL → to_char(time,'D') 1から始まり、日曜日に該当する など挙動に互換性
segmentio/dekuのコード読んで自分でも仮想DOMのdiffアルゴリズムを書いてみた - Qiita
VirtualDOM Advent Calendar 2014 - Qiitaの6日目です。 前回、チラッと紹介したdeku、どんなもんかそこまで詳しく知らなかったのでコード読んでみた。 segmentio/deku Dekuの特徴 APIはほぼReactと一緒 render/renderToString/setState/shouldUpdate 小さい 手元でビルドしたのが23kb(Reactが90kb) 公式が9kb謳ってるのは、昔の名残かな…？gzipかもしれないけど diff即生DOM操作なんでヘッドレスで動くような構造ではない duo.jsに依存して書かれてる まあsegment.io製だし デクだけにシンプル。小さいのが特徴。 アルゴリズムとしての本質はここみればわかる deku/diff.js at master · segmentio/deku dekuを参考に自分で仮想
グラフの差分描画に対応しました・ほか - Mackerel ブログ #mackerelio
本日、Mackerelのアップデートを行いました。主な変更は以下のとおりです: グラフの差分描画に対応いたしました。Mackerelに投稿されたカスタムメトリックおよびサービスメトリックの時系列データをウェブ上のグラフに描画する際、これまでは実際に投稿された値しか描画できませんでしたが、その1分ごとの差分値を描画できるようになりました。 描画方法の変更は、カスタムメトリックグラフ右上の設定ボタンより行えます。 今後、APIの対応とmackerel-agentのプラグインからの差分描画指定、また、差分値の監視を行えるよう対応を進めてまいります。 ホスト数・ロール数が多い時にグラフの描画が遅い問題に一部対処いたしました。グラフの改善は今後も継続して行います。 その他、細かなUI改善を行いました。
YappoLogs: xlsx ファイルを git diff しやすくする為の天才的な wrapper script を書いた
皆さんはプロジェクトのリソースとしてエクセルの xlsx ファイルを使う事があると思います。 何てったって事務職の人ですら楽々使えるスーパー優れた UI なので、 web の管理画面とかを作り込むよりもエクセルでシート作ってもらってしまった方が早いケースも多いんです。現実の世界では。 で、普通の人は TSV にするだの CSV にしてもらうだのすると思うんですが、一方的にデータ貰うだけなら良いんだけど、相手とやり取りする時にはどうしても xlsx ファイル経由とかにしないと相手がこまる！やっぱりエンジニアのエは優しさのエだから相手に優しくしないとだめです。 で、 xslx ファイルでエンジニア以外の人とデータやり取りするとやっぱり、バージョン管理したくなるのが人情です。 でも xslx ファイルはバイナリファイルなので git diff とかが残念です。。。 って事で作っちゃいました。 h
JSON Diff
Paste some JSON in each of the text fields. Click "Compare" to see the diff. Changed portions are displayed in yellow. Additions are displayed in green. Deletions are displayed in red. It also works as a JSON viewer. Click the disclosure triangles to display/hide portions of the JSON. Invalid JSON is indicated by the text fields turning red. Swap the contents of the text areas by clicking "Swap".
git difftool --dir-diff が便利すぎて泣きそうです
Git の 1.7.11 から git difftool コマンドに --dir-diff というオプションが追加されたのですが、これがライフ チェンジングだと思ったので紹介します。 --dir-diff 登場以前の git difftool は「ファイルごとに順番に差分を表示していく」ことしかできず、使い勝手はいまいちでした。それが、--dir-diff オプションの登場で状況が一変したわけです。 こんな感じの使い心地だよ ある Git レポジトリーで dir1/a.txt と dir2/c.txt を編集したとしましょう。 この状態で git difftool --dir-diff または git difftool -d を実行してみると・・・。 はい、差分のあるファイルが一覧で表示されました。 (difftool に WinMerge を設定して、メニューから [ツリー表示] を有効
C++: 編集距離を求めるアルゴリズム
編集距離(edit distance)とは二つの文字列がどの程度異なっているかを示す数値であり、レーベンシュタイン距離(Levenshtein distance)を指すことが多い。文字の挿入、削除、置換それぞれを一つの操作として必要な操作の最小数を求めるものだ。例えば、kittenとsittingの編集距離を求める場合、下記のように3回の操作でkittenをsittingに変更できるので編集距離は3となる。 1. sitten (k を s に置換） 2. sittin (e を i に置換） 3. sitting (g を挿入) そこで今回は編集距離を求める複数のアルゴリズムについてC++で実装してみた。 動的計画法 編集距離を求めるもっとも一般的なアルゴリズムは、動的計画法(dynamic programming)だろう。計算時間はO(mn)であり、手軽だ。C++で書いたコードを下に示
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - mixu/fastlint: Lint faster by only running linters and other tools on files that have recently changed or files that are different from `master` in git.
githubのGemfile.lockやpackage.jsonのdiffからそれぞれのライブラリのdiffへ飛べるChrome拡張を作った - walf443's blog
GitHub - YahooArchive/kobold: Visual regression testing framework, comparing screenshots from multiple builds