問題タブ [approximate]

類似性を示すために出力を取得したい

と

どうすればこれを行うことができますか？「hom」を「home」に変更するために、近似マッチングを使用したいと思います。

さて、私はsurfaceViewで簡単なアプリを作成しています。ここでは、画面の上部から下部に移動するボールのビットマップがあります。下部に到達すると、再び上部に表示され、再び落下し始めます。

次に、ボールが落ちているときにクリックすると画面の上部に戻るように作成しようとしました。ただし、クリックできないため（1ピクセルしかないため）、問題が発生しています。onTouchListenerをクリックの座標getX()とgetY()座標に設定しました。クリックのx座標とy座標が、ボールの現在の位置のx座標とyに等しい場合、ボールは画面の上部に戻ります。

ただし、これは機能しません。ボールをクリックできるようにするには、その時点でボールがあった正確な中央のピクセルをクリックする必要があるためです。だから私の質問は私がどのように言うかです：クリックがボールの現在の位置に近いか、ほぼ等しい場合は、トップに戻ります。私はこれに慣れていないので、私がお詫びする愚かな質問をしているなら、私は学ぶために最善を尽くしています。そして、助けてくれてありがとう。それは有り難いです。

アイテムが 3 次元空間で別のアイテムに十分に近いかどうかを調べる STL マップを作成したいと考えています。これまでのところ、私の "less-than-functor" は非常にうまく機能しており、次のリンクに貼り付けられています。

現在、この問題は「最近傍」問題ではありません。むしろ「少し離れたところに隣人がいるか」という問題です。

私の例は、単一の次元を示しています。わかりやすくするために、Y/Z 寸法をスキップしました。

これまでの私の試み：

まれに、つまり、非常にまれですが、位置が重複している場合に、マップが一致するエントリを見つけられないことがあります。

まだSTLコンテナを使用していますが、これを実装するためにもっとうまくできることはありますか?

私は適応型の「ほぼ等しい」メソッド（C＃で書かれていますが、質問は一般的です）を作成しようとしています.2つのdoubleを受け入れ、「ほぼ等しい」かどうかブール値を返します。アダプティブとは、次のことを意味します。

1.234 および 1.235 ==> TRUE

しかし

1.234567 および 1.234599 ==> FALSE

つまり、「ほぼ等しい」の精度は、数値の精度に適応します。

2 つの変数がほぼ等しいかどうかを調べるにはどうすればよいですか?で丸めの概念を見つけました。しかし、イプシロンに何を使用するかという未解決の問題がまだあります。

この種の問題のベストプラクティスを知っている人はいますか? 前もって感謝します！

編集: 私の最初の質問には、取得しようとしていたものに関する十分な情報が含まれていませんでした。申し訳ありません。より高い精度の数値をより高い基準で扱い、より低い精度の数値に対してより寛大になるプログラムが必要です。ペアのその他の例は次のとおりです (「(0)」は暗黙のゼロです)。

1.077 および 1.07(0) は false を返します (77 は 70 と大きく異なるため)

1.000077 および 1.00007(0) は false を返します (77 は 70 とは大きく異なるため)

1.071 および 1.07(0) は true を返します (71 は 70 に近いため)

1.000071 および 1.00007(0) は true を返します (71 は 70 に近いため)

実装コードに関係なく、「非常に異なる」ものと「近い」ものを判断するための何らかの「許容範囲」変数があると思います。

画像処理には OpenCV を使用しています。分離したい人体を探しています（セグメント）。

現在、体の輪郭を見つけて、ポリゴンで輪郭を近似することができます。次に、その輪郭を cvWatershed で使用して、体を実際に分離します。

中心に向かってオフセットして輪郭を描く方法を知っている人はいますか? 説明のために、下の画像を参照してください。

青: 輪郭のポリゴン近似

赤: 欲しいポリゴンですが、見つかりません。（上の画像はPhotoshopを使っていますが…）

現在の輪郭を見つけて描画する方法は次のとおりです。

編集：以下の回答に基づいて、2つの解決策を見つけました：

RSpec では、次のようなことができます。

これを再帰的に近似する組み込みの方法はありますか? 例えば：

組み込みの方法がない場合は、これを自分で作成できる (そして作成する) ことに気付きます。

みんな、ハイブで、私たちは使用します

トップNクエリの場合。
速度が速くないことがわかっているので、countsketchアルゴリズムや別のアルゴリズムなど、top-kクエリの近似アルゴリズムについて学びます。
top-kクエリを高速化するために、ハイブに近似アルゴリズムを追加できますか？

テキスト文字列のおおよその一致を合計したり、最初に一致した文字列から情報を引き出したりするのに問題があります。

次のようなデータがあります。

最新のテキスト文字列には、以前のテキスト文字列にすべて大文字の「THEN」と「AT」が追加されていることに注意してください。

次のようなテーブルが必要です。

これも：

最も古い日付のテキストに対応するID番号 (他のテキストが派生した「元の」テキスト)。 それぞれの近似一致の合計。最も古い日付に対応するテキスト。そして、最も古い日付に対応するテキストの日付。

何千万ものケースがあるため、プロセスの自動化に問題があります。

私は Windows 7 を実行しており、高速コンピューティング サーバーにアクセスできます。

アイデア

ここから、「agrep」を使用できますが、どのコンテキストで使用できるかわかりません。どんな助けでも大歓迎です！

注：以下の3つの回答は、最初に尋ねた方法で私の質問に答えますが、「AT」と「THEN」という言葉がなくてもテキストケースが異なることについては言及していません. 実際、それらのほとんどは正確には一致しません。これを元の質問に入れる必要がありました。しかし、私はまだ答えが欲しいです。

ありがとう！

列 A の文字列の数が列 B の文字列とほぼ一致するかどうかを確認しようとしています。

例：

列 B に文字列「angry_birds_iph_app」があり、列 A のどこかに「angry_birds_iph_app」と「angry_birds_adrd_app」が表示されている場合、関数が 2 を返すようにしたいと思います。

私は最近、データベース内の顧客レコードの重複をチェックするアルゴリズムの開発を任されています。DB レイアウトは非常に単純です。FullName、Street、City、ZIP、Phone などのフィールドを含む数万行...

最初に少し背景を説明します。

私はアルゴリズムについて大規模な調査を行い、すべての分野がすべての状況で同じようにうまく機能するとは限らないため、さまざまなアルゴリズムを使用して特定の量ですべてのフィールドを重み付けする必要があると判断しました。たとえば、LastName の加重係数は 0.50 です。評価するときは、使用するアルゴリズムと、それらが最終決定にどの程度影響するかを選択します。
係数 0.25: JaroWinkler
係数 0.60: コサイン 2 グラム類似度
係数 0.15: DamerauLevenshtein

すべてがうまく機能し、少し調整するだけで、ほとんどエラーなく陽性を検出できます。ここまでは順調ですね。ただし、ご想像のとおり、O(n^2) の実行時間 (実際には E フォーム i=0 から i=n) は、何万ものレコードを処理する場合にはあまり効果的ではありません。言うまでもなく、積極的な最適化、コンパイラーの最適化によるスピード、マルチスレッド化などは単なる応急処置にすぎません。本当の問題は複雑さだからです。

本質的に、私は潜在的な一致を事前にフィルタリングする方法を探しており、現在これについて3日間の調査を行っています. R ツリー、R* ツリー、KD ツリー、ユークリッド ベクトル、ミンハッシングなどに関する貴重な情報を見つけました。ただし、これらすべてに関するほとんどの情報は、かなり学術的なものです。私が見つけた最も価値のあるリソースは、「大規模なデータ セットのマイニング」の第 3 章でした。

今、私の本当の質問に：

この情報をすべて読みましたが、すべてをまとめる方法がわかりません。

文字列を入れて、「一致する確率が> 0.20のすべてを見つけてください」と言うことができる、ツリーまたはグラフのデータ構造でのある種のインデックス付けについて考えていました。このアルゴリズムは非常に高速です。次に、潜在的な (>0.20) 一致のリストを取得したら、いくつかのアイテムを「高価な」が選択的なアルゴリズムと比較することができます。これにより、実行時間が非常に妥当な値になるはずです。

上記のことを行うための何らかの参照コードを見つけようとしていますが、学術論文以外には何も思いつかないようです。実際にコンパイルされた「simstring」を見つけましたが、7つのテストレコードとうまく一致していないようでした..誰かが私を正しい方向に向けることができますか? 確かに、誰かが以前にこれに遭遇し、解決策を見つけたに違いありません...

事前にどうもありがとうございました！

PS 私はこれを C++ で行っていますが、C#/C/Java/PHP のサンプルは問題ありません。