10

「チャンク転置」を引用符で囲んだのは、専門用語がどうあるべきか、またはどのような用語であるべきかがわからないためです。プロセスの専門用語があるかどうかを知っているだけでも非常に役立ちます。

編集距離に関するウィキペディアの記事は、この概念に関する良い背景を示しています。

「チャンク転置」を考慮すると、

Turing, Alan.

一致する必要があります

Alan Turing

一致するよりも密接に

Turing Machine

つまり、距離計算は、テキストの部分文字列がテキスト内で単に移動されたときに検出する必要があります。これは、一般的なレーベンシュタイン距離の公式には当てはまりません。

文字列の長さはせいぜい数百文字です。さまざまな形式の著者名または著者名のリストです。私は DNA シーケンシングを行っていません (ただし、行っている人はこのテーマについて少し知っていると思います)。

4

6 に答える 6

3

あなたのアプリケーションの場合、バイオインフォマティクスからのいくつかのアルゴリズムを適応させることをおそらく考えるべきです。

たとえば、「Alan Turing」と「Turing Alan」を比較するように、すべてのセパレーターがスペースまたはその他の好きなものであることを確認することにより、最初に文字列を統一できます。次に、文字列の 1 つを分割し、一致する部分文字列の数をカウントして、他の文字列に対して断片を使用して正確な文字列一致アルゴリズム ( Horspool -Algorithm など) を実行します。

単に類似しているが等しくない一致を見つけたい場合は、類似性を説明するスコアを提供するため、ローカル アラインメントに沿ったものがより適している可能性がありますが、参照されている Smith-Waterman-Algorithm はおそらく少し過剰です。利用可能な最適なローカル アラインメント アルゴリズムでさえありません。

プログラミング環境によっては、実装が既に利用可能である可能性があります。私は最近、C++ 用のバイオインフォマティクス ライブラリであるSeqAnを個人的に使用しており、確実に必要な機能を提供しています。

まあ、それはかなり抽象的な答えでしたが、正しい方向に向けられていることを願っていますが、残念ながら、問題を解決するための簡単な公式は提供されていません.

于 2009-05-19T16:21:01.017 に答える
2

Jaccard 距離メトリック (JDM) を見てください。これは、姓が先、名が最後などのトークンレベルの不一致にかなり長けている、古き良きものです。2 つの文字列比較の場合、JDM の計算は、2 つの文字列が共通に持つ一意の文字の数を、それらの間の一意の文字の総数で割ったものです (つまり、和集合の積)。たとえば、「JEFFKTYZZER」と「TYZZERJEFF」という 2 つの引数がある場合、分子は 7、分母は 8 で、値は 0.875 になります。トークンとして私が選択した文字は、利用可能な唯一のものではありません。ところで、n-gram もよく使用されます。

于 2009-08-19T22:57:15.873 に答える
2

距離を編集するための最も簡単で効果的な最新の代替手段の 1 つは、Normalized Compression Distance (NCD) と呼ばれます。基本的な考え方は簡単に説明できます。zlibなど、言語に実装されている一般的なコンプレッサーを選択します。次に、文字列Aと文字列Bが与えられた場合、C(A)をAの圧縮サイズ、C(B)をBの圧縮サイズとします。ABは " AとBの連結" を意味するので、C(AB)は" " AとBの連結" の圧縮サイズを意味します。次に、分数を計算します。

( C(AB) - 最小( C(A) , C(B) )) / 最大( C(A) , C(B) )

この値は NCD( A , B) 編集距離と同様の類似性を測定しますが、選択したデータ コンプレッサに応じて、より多くの形式の類似性をサポートします。確かに、zlib は、あなたが説明している「チャンク」スタイルの類似性をサポートしています。2 つの文字列が類似している場合、連結の圧縮サイズはそれぞれの単独のサイズに近いため、分子は 0 に近く、結果は 0 に近くなります。2 つの文字列が非常に似ていない場合、圧縮後のサイズはおおよそ圧縮されたサイズが追加されるため、結果はほぼ 1 になります。zlib などのデータ圧縮プログラムに既にアクセスしている場合、この式は、編集距離や他のほとんどの明示的な文字列類似度測定よりも実装がはるかに簡単です。それは、ほとんどが「難しい」からです。ヒューリスティックや最適化などの作業はデータ圧縮部分で既に行われており、この式は、言語にとらわれない一般的な情報理論を使用して、見つかった類似のパターンの量を単純に抽出します。さらに、この手法は、記述した数百バイトのサイズ範囲では、ほとんどの明示的な類似度 (編集距離など) よりもはるかに高速です。これとサンプル実装の詳細については、Normalized Compression Distance (NCD) を検索するか、次の論文と github プロジェクトをご覧ください。

http://arxiv.org/abs/cs/0312044「圧縮によるクラスタリング」

https://github.com/rudi-cilibrasi/libcomplearn C 言語の実装

過去 10 年間に、この主題に関する他の多くの実装と論文があり、他の言語でも変更を加えて使用することができます。

于 2015-07-09T06:58:08.493 に答える
0

あなたが本当に望んでいるのは、文字列に対してのみ機能する編集距離であるか、または最も適切な意味または類似の意味を選択する意味論的距離であるかはわかりません。与えられた特定の用語または語句に最も適切に一致する語句を区別する方法については、情報検索のトピックを参照してください。ある意味では、文字列ではなく、非常に短いドキュメントを比較しています。

于 2009-05-18T15:11:28.143 に答える