問題タブ [similarity]

基本ケースと付属ケースの違いを特定しようとしています。パーセンテージなどで類似性を教えてくれるライブラリを探しています。

例えば：

私は10個の異なるHTMLページを持っています。※いずれも404応答でランダムコード2行のみ（時刻や今日の名言など）。

ここで、新しい 404 ページを提供すると、「%80」と同様の結果が返されますが、別のページを提供すると、まったく異なる、または同じ Web サイトであるが、コンテンツがまったく異なる場合、「%20 類似」のようなものを取得する必要があります。

基本的に私がやりたいことは、新しい応答を受け取ったときに、新しい応答が以前に提供したこれらの 10 ページに似ているかどうかを識別したいということです。

私はこれを .NET で解決しようとしています。ライブラリまたはアルゴリズムの推奨事項は素晴らしいでしょう。

データベースに多くの記事 (タイトル、テキスト付き) があります。質問をしたときに Stack Overflow の「関連する質問」のような、X 個の最も類似した記事を見つけるアルゴリズムを探しています。

これについてグーグルで検索してみましたが、すべての記事を他のすべての記事と比較し、類似点をどこかに保存するなど、他の「類似テキスト」の問題に関するページしか見つかりませんでした。SO は、入力したばかりのテキストに対して「リアルタイム」でこれを行います。

どのように？

作業中のプロジェクトに対してCSVインポートツールを実行しています。クライアントは、Excelでデータを入力し、CSVとしてエクスポートして、データベースにアップロードできる必要があります。たとえば、次のCSVレコードがあります。

もちろん、会社は別のテーブルに保持され、外部キーとリンクされているため、挿入する前に正しい会社IDを見つける必要があります。データベース内の会社名とCSV内の会社名を比較してこれを行う予定です。文字列が完全に同じである場合、比較は0を返し、文字列が大きくなるにつれて大きくなる値を返す必要がありますが、strcmpはここでそれをカットしません。理由は次のとおりです。

「AcmeCompany」と「AcmeComapny」の差指数は非常に小さいはずですが、「AcmeCompany」と「CmeaMpnyaco」の差指数は非常に大きいか、「AcmeCompany」と「AcmeComp」です。文字数が異なっていても、差指数も小さいはずです。また、「AcmeCompany」と「CompanyAcme」は0を返す必要があります。

したがって、クライアントがデータの入力中にタイプを作成した場合、おそらく挿入したい名前を選択するようにクライアントに促すことができます。

これを行うための既知のアルゴリズムはありますか、または多分私たちはそれを発明することができます:)？

タイトルのとおり、いくつかの文字列間の類似性の最長部分をプログラムで判断する方法を見つけようとしています。

例：

• file:///home/gms8994/Music/t.A.T.u./
• file:///home/gms8994/Music/nina%20sky/
• file:///home/gms8994/Music/A%20Perfect%20Circle/

file:///home/gms8994/Music/3 つの弦すべてに共通する最も長い部分であるため、理想的には に戻ります。

具体的には、Perl ソリューションを探していますが、任意の言語 (または擬似言語) でのソリューションで十分です。

コメントから: はい、最初だけです。ただし、この質問では無視されるリストに他のエントリが含まれている可能性があります。

テキストの不規則性を見つけるライブラリやソフトウェアを知っている人はいますか? たとえば、私が持っているとしましょう...

このソフトウェアまたはライブラリは、最初に類似するテキストの部分を切り取ります (圧縮ソフトウェアがテキストの類似した部分を繰り返しエンコードして圧縮するのとよく似ています) が、エラー トレランスのための変数を使用して、テキストの類似した部分を見つけることができます。 、テキスト比較アプリケーションまたは差分/マージツールと非常によく似ており、実際に異なると見なされるものを強調表示できます. このツールを作ることを考えていますが、車輪の再発明はしたくありません。これをリモートで実行できるものがあれば、このプロジェクトに役立つ可能性があるか、少なくとも作成しないことを知りたいです。言うまでもなく、この回答は他の人が同じものを探すのに役立つ可能性があります。需要は供給に対して十分に高いと思います。

ファイルの類似性を判断することに関連するいくつかの質問をここで見ましたが、それらはすべて特定のドメイン (画像、音声、テキストなど) にリンクされています。ソリューションとして提供される手法では、比較対象のファイルの基になるファイル形式に関する知識が必要です。私が探しているのは、この要件のない方法です。この方法では、含まれるデータの種類を理解する必要なく、任意のバイナリ ファイルを比較できます。つまり、2 つのファイルのバイナリ データの類似性パーセンテージを判断しようとしています。

これは多くのことに適用できる可能性がありますが、私が取り組んでいる特定の問題があります。現在、実用的なソリューションもありますが、理想的ではないと思います。比較方法と結果の保存に関しては、おそらく多くの最適化があります。うまくいけば、ここにいる何人かの人々が私にいくつかの新しいアイデアを与えることができます. 数日後に現在の方法に関する情報を編集する予定ですが、私がすでに行っている方法を説明することで、問題に関する人々の考えを偏らせたくはありません.

私が取り組んでいる問題は、ビデオ ゲームの ROM イメージのクローン検出です。エミュレーションの経験がない方のために説明すると、ROM はゲーム カートリッジのデータのダンプです。ROM「クローン」は通常、同じゲームの修正版であり、最も一般的なタイプは翻訳版です。たとえば、ファミコン用のオリジナルのファイナルファンタジーの日本語版と英語版はクローンです。ゲームはほぼすべてのアセット (スプライト、音楽など) を共有していますが、テキストは翻訳されています。

現在、さまざまなシステムのクローンのリストを維持する作業を行っているグループがいくつかありますが、私が知る限り、これはすべて手動で行われています。私が試みているのは、「これらは同じゲームのように見える」のではなく、データの類似性に基づいて、類似した ROM イメージを自動的かつ客観的に検出する方法を見つけることです。クローンを検出する理由はいくつかありますが、主な動機の 1 つは、Solid 圧縮を使用することです。これにより、すべてのゲーム クローンを同じアーカイブにまとめて圧縮できます。多くの場合、圧縮されたクローン セット全体は、個々の ROM の 1 つよりもわずかに多くのスペースしか占有しません。

潜在的なアプローチを考え出す際に考慮すべきいくつかの懸念事項:

• ROM のサイズは、システムによって大きく異なります。小さいものもありますが、最新のシステムには 256MB 以上の大きなものがある場合があります。一部の (すべての?) システムでは、可能なサイズとして 2 の累乗しかありません。これらのシステムの 1 つで 130MB のゲームを実行すると、256MB の ROM が使用され、ほとんど空になります。このため、ゲームのバージョンがしきい値を超え、2 倍のサイズのカートリッジを使用する必要がある場合、一部のクローンのサイズが大幅に異なる可能性があることに注意してください。
• 現在、多くのシステムには数千の既知の ROM があり、ほとんどのシステムでは新しい ROM が常にリリースされています。古いシステムでも、変更された ROM を頻繁に作成する主要な ROM ハッキング コミュニティがあります。
• ROM のすべての可能なペアの類似性データを格納すると、より一般的なシステムのいずれかで数百万行のデータが生成されます。5000 の ROM を備えたシステムでは、2500 万行の類似性データが必要になり、1 つの新しいゲームでさらに 5000 行が追加されます。
• 中断された場合に中断したところから再開できるように、処理の状態は回復可能でなければなりません。どの方法でも、多くの処理が必要になるため、すべてが 1 つのバッチで実行されると仮定するのは安全ではありません。
• 新しい ROM はいつでも追加される可能性があるため、この方法では、「完全な」セットが既にあると想定しないでください。つまり、既存のすべての ROM の類似性をすでに把握した後でも、新しい ROM が追加された場合 (これは前の処理が完全に終了する前に発生する可能性もあります)、それを以前のすべての ROM と比較して判断する方法が必要です。 （もしあれば）それはのクローンです。
• 精度よりも処理速度を優先する必要があります（ある程度）。2 つの ROM が 94% または 96% 類似しているかどうかを知ることは特に重要ではありませんが、新しい ROM を以前のすべての ROM と比較するのに 1 日かかる場合、プログラムはおそらく完全には完了しません。

取り組むのは興味深い問題でした。他の人が何を考え出すことができるかを楽しみにしています。詳細が必要な場合は、コメントでお知らせください。提供できるように努めます。

通常提案されているもの (レーベンシュタイン距離、soundex など) よりも、可変長文字列でより良い結果をもたらす文字列類似性アルゴリズムを探しています。

例えば、

与えられた文字列 A: "Robert",

ストリング B: "Amy Robertson"

よりも良い一致だろう

文字列C：「リチャード」

また、できれば、このアルゴリズムは言語にとらわれないようにする必要があります (英語以外の言語でも機能します)。

問題は次のとおりです。

通常は 20 ～ 50 語の要約が 1 つありますが、これを他の比較的類似した要約と比較したいと思います。概要が参照する一般的なカテゴリと地理的な場所は、既にわかっています。

たとえば、同じ地域の人々が家を建てることについて書いている場合、ガレージや裏庭のプールを建てるのではなく、実際に家を建てることについて言及しているというある程度の確信を持って、それらの要約をリストできるようにしたいと思います.

現在、データ セットは約 50,000 ドキュメントで、1 日あたり約 200 ドキュメントの増加率です。

優先される言語は、Python、PHP、C/C++、Haskell、または Erlang のいずれかで、仕事を遂行できるものであればどれでもかまいません。また、差し支えなければ、特定の言語を選んだ理由を教えていただきたいです。

tow pdfファイルの類似性を知りたいのですが、詳細な内容比較はしたくありません。その外部構造からだけの解決策はありますか?それは可能ですか?ありがとう!

Googleニュースに似ていますが、基本的なトピックが何であるかを判断し、次にどのトピックが関連しているかを判断できるという意味で異なる2つのニュースアイテムのコンテンツの類似性を判断したいと思います。

したがって、記事がサダム・​​フセインに関するものである場合、アルゴリズムは、ドナルド・ラムズフェルドのイラクでの商取引に関する何かを推奨する可能性があります。

k最近傍法のようなキーワードとそれらが機能する理由についての少しの説明を投げかけることができれば（可能であれば）、残りの調査を行い、アルゴリズムを微調整します。誰かが以前に似たようなことを試みたに違いないことを私は知っているので、始める場所を探しているだけです。