問題タブ [word-diff]

2 つの文字列があり、それらの違いを表示したいと考えています。たとえば、「I am from Mars」と「I am from Venus」という文字列がある場合、出力は「I am from Venus」になります。(通常、監査ログなどで何が変更されたかを示すために使用されます)

これには簡単なアルゴリズムがありますか？私は C# を使用していますが、一般的なアルゴリズムはどのプログラミング言語からでも適応できると思います。

または、この種のことを行うフレームワーク クラス/サードパーティ ライブラリはありますか?

PHP で 2 つの文字列の違いを強調する最も簡単な方法は何ですか?

Stack Overflow の編集履歴ページの行に沿って考えています。新しいテキストは緑で、削除されたテキストは赤です。事前に作成された関数またはクラスが利用可能であれば、それが理想的です。

プロファイリングは、これが私が書いた小さな単語ゲームのコードの最も遅いセグメントであることを示しています:

ノート：

• distance()は 500 万回以上呼び出されており、その大部分は getchildren からのもので、単語リスト内のword1 文字だけ異なるすべての単語を取得することになっています。
• wordlist は、同じ数の文字を含む単語のみを持つように事前にフィルター処理されているため、同じ数の文字を持つwordことが保証されます。word1word2
• 私は Python を初めて使用するので (3 日前に学習を開始しました)、命名規則やその他のスタイルに関するコメントも歓迎します。
• wordlistの場合、「2+2lemma.txt」ファイルを使用して12dict の単語リストを取得します

結果：

みんなありがとう、さまざまな提案を組み合わせて、プログラムを2倍の速度で実行できるようになりました（質問する前に自分で行った最適化に加えて、最初の実装から約4倍の速度が向上しました）

AとBと呼ぶ2セットの入力でテストしました

Optimization1: word1,2 ...のインデックスを反復処理します。

を使用して文字のペアを反復するzip(word1, word2)

入力 A の実行時間は 11.92 から 9.18、入力 B の実行時間は 79.30 から 74.59 になりました

Optimization2: distance-method に加えて、different-by-one の別のメソッドを追加しました (これは、A* ヒューリスティックのために他の場所でまだ必要でした)。

入力 A の実行時間は 9.18 から 8.83、入力 B の実行時間は 74.59 から 70.14 になりました

最適化 3: ここでの大きな勝者は、izip代わりに使用することでしたzip

入力 A の実行時間は 8.83 から 5.02 になり、入力 B の実行時間は 70.14 から 41.69 になりました

低レベル言語で書いたほうがいいかもしれませんが、今のところこれで満足しています。みんな、ありがとう！

もう一度編集: より多くの結果最初の文字が一致しないケースをチェックするマークの方法を使用して、5.02 -> 3.59 および 41.69 -> 29.82 からダウンしました。

それに基づいての代わりに組み込むiziprangeと、次のようになりました。

これにより、タイムが 3.59 -> 3.38 および 29.82 -> 27.88 に短縮されました。

さらに成果が！

「単語」から1文字離れたすべての文字列のリストを生成し、 is_neighbor 関数の代わりに wordlist にあるものを確認するというSumuduの提案を試してみると、次のようになりました。

最終的には遅くなりましたが (3.38 -> 3.74 および 27.88 -> 34.40)、有望に思えました。最初は、最適化する必要がある部分は「one_letter_off_strings」だと思っていましたが、プロファイリングではそうではなく、遅い部分は実際には

「oneoff」と「wordlist」を切り替えて、逆に比較すると、2 つのリストの共通点を探していることに気が付いたときに、何か違いがあるのではないかと考えました。それを文字の set-intersectionに置き換えます:

バム！3.74 -> 0.23 および 34.40 -> 2.25

これは本当に驚くべきことであり、元の素朴な実装との合計速度の差: 23.79 -> 0.23 および 180.07 -> 2.25 であり、元の実装よりも約 80 倍から 100 倍高速です。

誰かが興味を持っている場合は、プログラムを説明し、ここで言及されていないものを含めて行われた最適化について説明するブログ投稿を作成しました (コードの別のセクションにあるため)。

大論争：

わかりました、私と Unknown は大きな議論をしています。彼の回答のコメントで読むことができます。彼は、C に移植した場合、元の方法 (セットを使用する代わりに is_neighbor を使用) を使用した方が高速になると主張しています。thisとthisの例に従ってください。Windows ではプロセスが少し異なるように見えますか? わかりませんが、私はそれをあきらめました。とにかく、ここにプログラムの完全なコードがあり、テキストファイルは12dict 単語リストから来ています「2+2lemma.txt」ファイルを使用します。コードが少し乱雑で申し訳ありませんが、これは私が一緒にハッキングしたものです。また、単語リストからコンマを削除するのを忘れていたので、実際には同じ比較のためにそのままにしておくか、cleanentries の文字のリストにコンマを追加して修正できるバグです。

is_neighbors メソッドは使用されていませんが、残しました。これは、C への移植が提案されているメソッドです。これを使用するには、getchildren を次のように置き換えます。

Cモジュールとして動作させることに関しては、私はそこまで行きませんでしたが、これは私が思いついたものです:

私はこれを使用してプロファイリングしました：

python -m cProfile "Wordgame.py"

記録された時間は、AStar メソッド呼び出しの合計時間です。高速入力セットは「詩の詩人」であり、長い入力セットは「詩人の詩」でした。タイミングは明らかに異なるマシン間で異なるため、誰かがこれを試した場合は、プログラムそのままの結果と C モジュールの結果を比較してください。

特定の種類のドキュメントに対して diff をより適切に機能させようとしているだけです。たとえば、LaTeX の場合、厳密には 1 行だけの長い段落があるかもしれませんが、1 つの文だけが変更された場合にその段落全体を表示したくはありません。特に、ある種のバージョン管理を実行していて、共著者が私と同じ段落 (ただし同じ文ではない) を編集している場合。私はそれが競合として現れたくありません。

それは二次的な質問です。主な問題は、diff を使用して文ごとに調べることができるかどうかです。ありがとう。

編集

wdiffほぼ完璧です。diffしかし、のように同等のマージはありdiff3ますか?

この StackOverflow の回答には、行内の違いを強調する KDiff3 の画像があります。コマンドラインで同じことを（たとえば、色で）表示できるツールを知っている人はいますか？

これを考えるもう 1 つの方法は、パッチ ファイル内の各相違点を比較することです。

最新バージョンで何が変更されたかを判断するために、SQL プロシージャーを頻繁に比較する必要があります。問題は、誰もが独自の書式設定スタイルを持っており、SQL は (通常) 改行を配置する場所を気にしないことです (たとえば、where 句をすべて 1 行に配置するか、各 AND の前に改行を配置するかなど)。

これにより、(特に長い手順の場合) 実際の違いを確認することが非常に困難になります。改行を無視できるようにする (つまり、空白として扱う) 無料の diff/merge ユーティリティが見つからないようです。これまでのところ、WinMerge と Beyond Compare を試してみましたが、うまくいきませんでした。これら2つの例を同一と見なす差分ツール(理想的には無料)を知っている人はいますか?

元。1:

元。2:

前もって感謝します。

2 つの文字列を単語単位で比較する必要があります。diff のようなものですが、行ではなく単語です。

ウィキペディアで行われているように http://en.wikipedia.org/w/index.php?title=Horapollo&action=historysubmit&diff=21895647&oldid=21893459

結果として、2 つの文字列が異なる単語のインデックスの 2 つの配列を返したいと思います。

これを実行できる .NET 用のライブラリ/フレームワーク/standalone_methods はありますか?

PS数キロバイトのテキストを比較したい

2 つのテキスト ブロックの違いを示したいと思います。テキスト行または個々の文字を比較するのではなく、指定された文字 ('\n'、' '、'\t' など) で区切られた単語のみを比較したいと思います。これについての私の主な理由は、比較するテキストのブロックには通常、改行が多くなく、文字の比較がわかりにくいということです。

行と文字を比較するために C# で次の O(ND) ロジックに出くわしましたが、単語を比較するためにそれを変更する方法がわかりません。

さらに、単語間のセパレーターを追跡し、それらが差分に含まれていることを確認したいと思います。したがって、スペースがハードリターンに置き換えられた場合、それを差分として表示したいと思います。

Asp.Net (c#) を使用して、削除された元のテキストと追加された新しいテキストを含むテキスト ブロック全体を表示しています (削除/追加されたことを示すために、両方が強調表示されます)。これらのテクノロジーで動作するソリューションをいただければ幸いです。

これを達成する方法についてのアドバイスをいただければ幸いです。

2 つのテキスト ファイル間の変更を表示できるが、改行を含む空白の変更を無視できる diff のようなツールを知っている人はいますか?

次に例を示します。

私がしたことは、1 つの単語を削除してリフローすることだけでしたが、"diff -b" はすべての行で変更を検出しました (そうあるべきです。これが diff のバグだと言っているわけではありません)。しかし、大きな LaTeX ファイルの場合、これは大きな問題です。長い段落の 1 つの単語を変更すると、返される差分は基本的に役に立たなくなります。

ところで、これには通常の行がアトミックな diff よりもはるかに多くの計算能力が必要であることは承知しています。私は人間が生成した小さなファイルに対してのみこれを行っており、必要に応じて長い間待つことができます.

私は2つのテキストを持っています。それらの間で単語ベースの差分を作成したいと思いますが（unixユーティリティのようwdiffに）、出力に詳細情報（つまり、追加/削除された単語が始まる文字の位置）があります。

私は Java でこれを行う必要があるため、違いの単純な出力 (のようなwdiff) は私には適していません: 違いを表すオブジェクトを操作したいと思います。