問題タブ [interval-tree]

特定の範囲 (開始日と終了日) に該当するデータセットの数を視覚化しようとしています。thisの例に従って、私はそれを行うことができました。私のコードはこちらです。下部の視覚化により、ユーザーは年の範囲をフィルター処理できます。フィルターの結果は、上部のビジュアライゼーションに表示されます。ただし、コンソールを確認すると、次のようなエラーが発生しています

2 つのビジュアライゼーションのレンダリングが適切でないためです。Lysenko Interval Tree を使用しています。よろしくお願いします。問題をより明確にするための画像の例

間隔のセットが 2 つあります。1 つは、たとえば 0 から 100 の間の「正の」間隔を含みます。もう 1 つは -100 と 0 の間の「負の」間隔を含みます。各セットの間隔は必ずしも一意ではなく (この場合、「セット」よりも「コレクション」の方が適している可能性があります)、重複する可能性があります。たとえば、正の集合は

{ [0, 10], [5,15], [5,15], [10,15], [10,20], [25, 40] }

そして負の集合は

{ [-15, 0], [-15,-5], [-20,-15], [-30,-25] }

各セット内の隣接する重複しない間隔 (つまり、一方の右端点が他方の左端点と等しい間隔) を組み合わせて、[0,10] + [10] などのより長い間隔を形成できます。 ,20] = [0,20] および [-15,0] + [-20,-15] = [-20,0] ですが、[0,10] と [5,15]を組み合わせて [0 ] にすることはできません、15]。

正の間隔と負の間隔は、絶対数でまったく同じ範囲にまたがる場合、互いに相殺される場合があります。たとえば、[5,15] + [-15,-5] = 0 および [0,10] + [10,20] + [-15,0] + [-20,-15] = [0,20] + [-20,0] = 0.

残りの間隔の合計の長さを最小限に抑える方法で間隔を結合およびキャンセルするための効率的なアルゴリズムを探しています。例では、残りの全長 = len([5,15]) + len([10,15]) + len([25,40]) + len([-30,-25]) = 10 + 5 + 15 + 5 = 35。

この種の問題は、文献やここのどこかですでに対処されているかもしれません（何も見つかりませんでしたが、正式な方法でそれを定式化する方法がわからないためかもしれません）ので、参考にしていただければ幸いです。およびリンク; または、ここに投稿されたソリューションでももちろん十分です。

以下は、取ることができる（非常に）大まかな手順についての私の最初の素朴な考えです。アイデアは、左端点が負の間隔の左端点と一致する正の間隔は、その右端点が負の間隔の右端点と一致する場合、またはいずれかの場合に「潜在的にキャンセル可能」であるということです。その隣接する間隔は「潜在的にキャンセル可能」です。

l区間の左端 ( ) と右端 ( )を示すために両方のセットに正の数を使用し、正/負のセットに対して/および/とr呼びます。設定します。l+l-r+r-S = 0

1. のようなすべての左端点l+ = l- = lと のようなすべての右端点を見つけますr+ = r- = r。そのようなlおよびそれぞれについて、およびrを見つけます。n_l = min{number of positive intervals with l+ = l; number of negative intervals with l- = l}n_r = min{number of positive intervals with r+ = r; number of negative intervals with r- = r}

2. l_minからの一致した左端点のセットから最小のものを見つけ、{l}からの一致した右端点のセットから最大Step 1のものを見つけます。次のステップでさらに処理するために、完全にその間にあるすべての間隔を保持します。を計算します）。r_max{r}Step 1l_minr_maxS = S + (the total length of the intervals which do not fall entirely between the two bounds l_min and r_max

3. 昇順で左側のエンドポイントによって各セットの間隔を並べ替えます。

4. 左の各終点で、間隔を長さの降順に並べます。

5. 一番左の point から始まるすべての正の区間をループしますl_min。

6. 区間の右側の終点をrからの一致した右側の終点のセットと比較しStep 2ます。

7. 一致するStep 6ものが見つからない場合は、左端点が現在の間隔の右端点と等しい次の間隔を探します。

8. の間隔Step 7が見つかった場合は、それを使用して に戻りStep 6ます。

9. 間隔Step 7が見つからない場合は、現在の間隔の長さを length の合計に追加しSます。n_l現在の区間の左側の終点に対応する値を 1 減らします: n_l := n_l - 1。の新しい値が得られた場合はn_l = 0、 に進みStep 2ます。n_l > 0次にStep 5、現在の間隔と同じ左側のエンドポイントで次の間隔に移動します。以降のステップから現在の間隔を削除します。

10. 一致するStep 6場合は、負の間隔を使用して に移動しStep 5ます。

進行中の作業...

[...]

2. 各セット (正の S+ と負の S-) について、一意でない間隔を同一として扱い、可能な限り長い間隔の組み合わせを作成します。k+ = 1..N_C+ および k- = 1..N_C- で結合した後、それぞれ N_k+ および N_k- 間隔を含む N_C+ および N_C- の異なる組み合わせが可能であるとします。

3. これらの組み合わせを 2 つのセット間で比較し (間隔が最も長い組み合わせから始めて)、一致するセクションを除外/キャンセルします。

4. 残りの全長を計算します。

明らかに、上記のために記入しなければならない詳細がたくさんありますが、現時点では、このアプローチが最小の解決策を見つけることを保証するかどうかさえわかりません.

たとえば、次のようなデータがあります。

一致する行を返すには、コンテンツと範囲フィールドに提供された入力とコンテンツを一致させる必要があります。ご覧のとおり、Content フィールドは文字列のコレクションで、Range フィールドは 2 つの数値の間の範囲です。ハッシュ化された入力との照合に使用するために、データのハッシュ化を検討しています。個々の文字列ハッシュコードのコレクションを繰り返し処理し、コンテンツ フィールドに格納することを考えていました。Range フィールドについては、インターバル ツリーを使用して調べていました。しかし、課題は、コンテンツ入力と範囲入力をハッシュするときに、コンテンツ フィールドの文字列のコレクションに対して生成されたハッシュコードにそのハッシュコードが存在するかどうかをどのように確認するかです。範囲フィールドについても同様です。

これを達成できる他の代替方法があれば教えてください。ありがとう。