3

BK Trees に関するこの投稿を読んで、次のスニペットが少しわかりにくいことがわかりました。

「しばらくの間、クエリ、検索で使用している文字列、および文字列がクエリから離れて返される最大距離の 2 つのパラメータがあるとします。任意の文字列を取得し、それをテストしてクエリと比較するとします。 . 結果の距離を d と呼びます。三角形の不等式が成り立つことがわかっているため、すべての結果は最大で d+n の距離、少なくともテストからの距離は dn でなければなりません。

検索している単語から何かがd離れていて、エラーを許容できる場合、違いを「元に戻す」には、現在の単語からn少なくとも距離が必要になることが直感的にわかります。d-n同様にd+n、違いを「逆転」させた後、さらにn個の違いを導入できるため、最大でも持つことができます。

これを得るために三角形の不等式がどのように使用されたか混乱しています。d(test, query) = d および d(query, found) <= n とすると、次の不等式によります。

d(test, query) + d(test, nextWordToSearch) >= d(query, found)
d + d(test, nextWordToSearch) >= n

どうすれば見つけることができますか

d - n <= d(test, nextWordToSearch) <= d + n
4

3 に答える 3

3

@templatetypedef の回答を使用して、三角形の不等式を使用して上限と下限の両方を見つけることができました。

d(query, desiredNode) = n
d(query, test) = d1

d(query, test) + d(test, desiredNode) >= d(query, desiredNode)
d1 + d(test, desiredNode) >= n
d(test, desiredNode) >= |n - d1|

d(test, query) + d(query, desiredNode) >= d(test, desiredNode)
|d1 + n| >= d(test, desiredNode)

したがって：

|d1 + n| >= d(test, desiredNode) >= |d1 - n|

非負の尺度の性質のために使用される絶対値。

于 2016-01-22T19:22:40.493 に答える
1

以下では、クエリ ワードからテスト ワード (現在のノードの単語) までの距離を d とし、検索する最大距離を n とします。あなたはそれを証明することに興味があります

n - d ≤ d(test, anyResultingWord) ≤ n + d.

三角形の不等式を含む質問で使用した数学は、下限を確立するのに十分です。上限に問題があるのは、ここで三角形の不等式を実際に使用したくないためだと思います。

実際には使用する必要はありません - 実際、おそらく使用すべきではありません! - 三角形の不等式を使用して上限を取得します。

d(x, y) は x と y の間のレーベンシュタイン距離として定義されることに注意してください。これは、x を y に変換するために必要な挿入、削除、または置換の最小数です。n + d で d(test, anyResultingWord) の上限を設定します。そのためには、次のことに注意してください。テスト単語から始めて、次のように結果の単語に変換できます。

  • まず、それをクエリ ワードに戻すことから始めます。これには d 回の編集が必要です。
  • クエリ単語を結果の単語に変換します。これには n 回の編集が必要です。

全体として、これにより、テスト単語を結果単語に変換するために必要な一連の n + d 合計編集が得られます。これが最善の方法かもしれませんが、そうではないかもしれません。私たちが言えることは、d(test, anyResultingWord) は最大で n + d でなければならないということです。これは、最大で n + d 回の編集でテストを結果の単語に変換できることがわかっているためです。これが上限の由来です。これは、三角形の不等式の結果ではなく、距離計量の定義方法の結果です。

于 2016-01-17T21:26:43.517 に答える
1

まず、 がd三角形の不等式に従うことを理解する必要があります。これを矛盾によって証明しましょう：

任意の 3 つの文字列aが であるbとc仮定すると、 が得られますが、その場合はステップでd(a,c)>d(a,b)+d(b,c)見つけることができるため、矛盾が生じます。これが、三角形の不等式および に従う理由です。d(a,c)d(a,b)+d(b,c)dd(a,c)<=d(a,b)+d(b,c)

そのツリーを検索する方法を想像してみましょう。クエリと最大距離fを入力として受け取る検索機能があります。QN

質問:なぜその関数は、セグメント内にあるエッジを調べる必要があるの[d-n,d+n]ですか?

他の弦をいくつか紹介しましょう。を文字x列にしてd(Q,x)<=n、t調べている現在のノードにします。明らかに、上記の表記でdはd(Q,t).

したがって、上記の質問を再定式化するために、次のように尋ねることができます。

なぜd(Q,t)-n<=d(t,x)<=d(Q,t)+nですか？

d(Q,t)簡単にするために、 as a、d(t,x)as b、およびd(Q,x)asと表記しましょうc。

三角不等式から明らかなのが

  1. a+b>=c => b>=c-a
  2. a+c>=b
  3. b+c>=a => b>=a-c

1. と 3. からわかりますb>=|a-c|。したがって、すべてをまとめると、 になり|a-c|<=b<=a+cます。

さて、これで証明は終わりではありません0<=c<=N。

これは次のように簡単に実行 a-N<=a-c<=|a-c|<=b<=a+c<=a+N => a-N<=b<=a+Nできb>=0ますmax(a-N,0)<=b<=a+N。

于 2018-09-17T18:45:14.773 に答える