問題タブ [fuzzy]

2 つの単語リストの関数に興味があります。これは、それらの間の順序にとらわれない編集距離を返します。

つまり、引数は (たとえばスペースで区切られた) 単語の 2 つのリストになり、戻り値はリスト内の単語の編集 (またはレーベンシュタイン) 距離の最小合計になります。

"cat rat bat"との間の"rat bat cat"距離は 0 になります。 と の間の距離は"cat rat bat"と"fat had bad"の間の距離と"rat bat cat"同じ"had fat bad"になります。

私の直感 (コンピューター サイエンスの授業で育まれていない) では、ブルート フォースを使用する以外に解決策は見つかりません。

最初の行から始めて、列を選択し、既にアクセスした列に再度アクセスすることなく、次の行に移動します。すべての組み合わせを試すまで、これを何度も繰り返します。

私には、これは巡回セールスマンの問題に少し似ているように思えます。そうですか、どうすれば私の特定の問題を解決できますか?

Lucene ファジー マッチングは、基本的な editDistance アルゴリズムを使用してファジー マッチングを実装します。他の類似性メトリックを使用する Lucene のあいまい一致の他の実装はありますか? 同音異義語も特定する必要があります。また、lucene のさまざまなファジー マッチング アプローチを比較してください。

私は現在、観測ごとに 4 つの値を含む一連の観測に対して一連のファジー ルールを自動的に生成しようとしています。各観測は状態に対応します (良い例はフィッシャーのアイリス データです)。

Matlab では、単一のセル (a、b、c、d) に対応する状態が含まれる 4 次元ルール テーブルを作成しています。表を縮小するために、行と列の類似性チェックのHong と Leeの方法に従っていますが、3 番目と 4 番目の次元の行と列に対処する方法を理解するのが困難です。この方法から、各次元が個別に扱われ、ルールが真の場合、テーブルが単純化されていることが理解できます。マージのルールは次のとおりです。

1. 隣接する列または行のすべてのセルが同じ場合。
2. 2 つのセルが同じ場合、または隣接する
   列または行でいずれかが空で、両方のセルの少なくとも 1 つが空でない場合。
3. 列または行のすべてのセルが空で、
   隣接する 2 つの列または行のセルが同じ場合、3 つを結合します。
4. 列または行のすべてのセルが空で、
   隣接する 2 つの列または行のセルが同じであるか、いずれかが空の場合、3 つを結合します。
5. 列または行のすべてのセルが空で、
   その左側の列または行のすべての空でないセルが同じ領域を持ち、その右側の列または行のすべての空でないセルが同じ領域を持つ場合、ただし前述のリージョンとは 1 つ異なりますが、これら 3 つの列を 2 つの部分にマージします。

紛らわしいビットのために今。行/列全体が隣接するものと同じかどうかを確認するだけ (ルール 1) は、十分に単純に思えます。

これは正しいです？

しかし、行/列の要素が一致するかどうか、またはどちらかがゼロであるかどうか (ルール 2 および 4) を確認するには、少し迷っています。それはこれらの線に沿ったものでしょうか:

3 番目と 4 番目の次元については、次のようになります。

私は3つ以上の考えにとても混乱しているので、4次元配列の助けさえあれば役に立ちます! 私の意味を理解するために論文を読むことをお勧めします.彼ら自身は虹彩データを使用していますが、2Dテーブルの例しか示していません.

一連のオブジェクトがあるとしますS。fセットがその上にS特定のデータ構造を構築する場合、次のアルゴリズムがあります。が大きい場合、および/または非常に異なるオブジェクトが含まれている場合は、大きくなり、使用できなくなります (つまり、割り当てられたメモリに収まりません)。これを克服するために、いくつかの交差しないサブセットに分割し、サブセットごとにビルドします。構造体を使用すると、構造体を使用するよりも効率が低下しますが、少なくともこの方法では、メモリの制約に適合できます。のサイズはそれ自体よりも速く成長するため、 の合計サイズは のサイズよりもはるかに小さくなります。Df(S) = DSDSS = S1 + S2 + ... + SnDinf(S)SDiD

nただし、 を減らすこと、つまりサブセットの数を減らすことは依然として望ましいことです。または の合計サイズを小さくしDiます。このため、それぞれに「類似した」オブジェクトが含まSれるように分割する必要があります。入力オブジェクトが互いに「十分に類似している」場合、より小さな出力構造が生成されるためです。Sif

問題は、 のオブジェクトの「類似性」Sと のサイズがf(S)相関する一方で、 を評価する以外に後者を計算する方法がなく、あまり高速f(S)ではないことです。f

私が現在持っているアルゴリズムは、次の各オブジェクトを からSのいずれかに繰り返し追加するSiことです。これにより、（この段階で）結合Diサイズの増加が最小限に抑えられます。

これにより実用的な結果が得られますが、確かに最適とはかなりかけ離れています (つまり、可能な最小の結合サイズ)。また、これは遅いです。いくらか高速化するために、 がすでに にあるオブジェクトと「十分に類似している」size(f(Si + {x})) - size(f(Si))ものだけを計算します。ixSi

そのような種類の問題に対する標準的なアプローチはありますか?

分枝境界アルゴリズム ファミリについては知っていますが、非常に遅くなるため、ここでは適用できません。私の推測では、合理的な時間内に の最適な分布を計算することは不可能SですSi。しかし、反復的に改善する一般的なアルゴリズムはありますか?

編集：

コメントが指摘したように、私は「類似性」を定義したことはありません。実際、私が望むのはSi、組み合わせたサイズDi = f(Si)が最小または少なくとも十分に小さいサブセットに分割することだけです。「類似度」はこれだけで定義されており、残念ながら簡単に計算することはできません。簡単な概算がありますが、それはあくまでも概算です。

したがって、後者を計算する簡単な方法がないsum f(Si)ことを考慮して最小化する (おそらくヒューリスティックな) アルゴリズムが必要です。良い結果が得られる可能性が非常に低いケースを破棄するために使用する近似値のみです。

グラフ内の構造を検索するためのレーベンシュタイン距離の一般化はありますか?

誰かがASCII文字に似ているUnicodeの文字を見つける簡単な方法を知っていますか。例として、「キリル文字の小さな文字DZE（ѕ）」があります。似たような文字を検索して置き換えたいのですが。同様に、私は人間が読める形式を意味します。見ても違いはわかりません。

私は最近、完全な管理フロントエンド/ CMSを備えた会社のWebサイトを開発しています。残念ながらセキュリティ上の理由からお見せできない管理者フロントエンドには、範囲リスト、コレクション リスト、デザイン リストがあります。これらのリンクを JQuery で機能させたいので、[Ranges] をクリックすると、Ranges リストが前面に表示され、現在アクティブなリストがフェードアウトし、同時にあいまいになります。Range リストがデフォルトで他のリストの前にあるように、約 50% の不透明度 (推測) で作成したいと思います。ただし、不透明度が 50% の場合でも、その背後にあるテキストを (他のリストで) 見ることができます。バックグラウンド (「後ろ」のリスト) のテキストをグレーでぼやけさせたいのですが、たとえば、Windows Live メールの前面に Windows フォト ビューアー ウィンドウがある場合に気付きました - Windows Live メールの右下にあるステータス テキストがぼやけていて、背後のウィンドウにはっきりと表示されます)。また、前景のテキストを黒くして焦点を合わせたいと思います。テキストの色を変更するのは簡単です (ピージー レモン スクイーズ!)。「JQuery fuzzy」および同様の用語について簡単なGoogleを実行しましたが、何も見つかりませんでした。

これを行う方法があるかどうか誰か教えてもらえますか (できれば $(selector).fuzz(50%); と同じくらい簡単です)?

前もって感謝します。

よろしく、

リチャード

Daitch-Mokotoff soundexing と Damerau-Levenshtein の両方を使用して、アプリケーションのユーザー エントリと値が「同じ」かどうかを調べています。

レーベンシュタイン距離は絶対値として使用することになっていますか? 20 文字の単語がある場合、4 の距離はそれほど悪くありません。単語が4文字の場合...

私が今行っているのは、距離/長さを取得して、単語の何パーセントが変更されたかをよりよく反映する距離を取得することです。

それは有効で実証済みのアプローチですか？それともただのバカですか？

オランダ語を話す人々にとって、2つの文字「ij」は「y」と簡単に交換できる1文字と見なされます。

私が取り組んでいるプロジェクトでは、ダメラウ・レーベンシュタイン距離の変形を使用して、「ij」と「y」の間の距離を現在の値2ではなく1として計算したいと思います。

私はこれを自分で試しましたが失敗しました。私の問題は、両方のテキストの長さが異なるという事実をどのように処理するかについての手がかりがないことです。誰かがこれを解決する方法についての提案/コードフラグメントを持っていますか？

ありがとう。

私はvimでFuzzyFinderをMiniBufExplorerと一緒に使用しています（.vimrcでこの設定を使用：g：miniBufExplorerMoreThanOne = 1）。

FuzzyFinder をカバレッジ ファイル モードで使用しています (ここでは、私が理解しているように、command-t とほとんど同じように機能します)。

問題は、FuzzyFinder を使用して新しいファイルを開くたびに、開いている現在のウィンドウで開くのではなく、垂直に分割された新しい小さなウィンドウを作成することです。

この動作を変更する方法はありますか?

編集: これは、新しく変更されたバージョンのミニバッファー (vim スクリプト ページからリンク) でのみ発生します。私がそれについて何ができるかわからない。