问题标签 [interval-tree]

我有两个文件 文件 1

chr1:4847593-4847993 TGCCGGAGGGGGTTTCGATGGAACTCGTAGCA

文件 2

PBSN|X|75083240|75098962| TTTACTACTTAGTAACACAGTAAGCTAAACAACCAGTGCCATGGTAGGCTTGAGTCAGCT CTTTCAGGTTCATGTCCATCAAAGATCTACATCTCTCCCCTGGTAGCTTAAGAGAAGCCA TGGTGGTTGGTATTTCCTACTGCCAGACAGCTGGTTGTTAAGTGAATATTTTGAAGTCC

文件 1 有大约 8000 多行，下面有不同的标题和序列。我首先想匹配从文件 1 到文件 2 的开始和结束坐标，或者看看它是否彼此接近，如果是，则用 +- 100 说，然后匹配文件 2 中的序列，然后打印出文件 2 的标题信​​息和匹配的序列。我的方法使用区间树（在 python 中我仍在尝试掌握它），存储坐标？
我尝试使用 re.match 但它没有给我准确的结果。任何提示将不胜感激。谢谢。

我的第一次尝试，现在我遇到了另一个路障，所以对于我的第二个第二个文件，如果我的开始和结束分别是 5000 和 8000，我想通过减去 2000 来改变它，所以我的新开始和停止是 3000 和 5000 这是我的代码

我正在尝试可视化属于特定范围（开始日期和结束日期）的数据集的数量。按照这个例子，我能够做到这一点。我的代码在这里。底部的可视化允许用户过滤年份范围。过滤器的结果显示在顶部的可视化中。但是，如果您检查控制台，则会出现错误

由于这两个可视化的渲染不正确。我正在使用李森科区间树。我会感谢你的帮助。用于更好地说明问题的示例图像

我有两组区间：一组包含介于 0 和 100 之间的“正”区间；另一个包含 -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. 从最左边的点 开始循环遍历所有正区间l_min。

6. 将区间的右端点r与来自的匹配右端点集进行比较Step 2。

7. 如果没有Step 6找到匹配项，则寻找下一个区间，其左端点等于当前区间的右端点。

8. 如果找到区间 in Step 7，则使用它返回Step 6。

9. 如果没有Step 7找到区间 in ，则将当前区间的长度添加到长度的总和中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_C+ 和 N_C- 不同的组合，每个组合都包含 N_k+ 和 N_k- 区间。

3. 比较两组之间的这些组合（从包含最长间隔的那些组合开始）消除/取消重合部分。

4. 计算总剩余长度。

显然，上面有很多细节需要填写，但在这一点上，我什至不确定这种方法是否能保证找到最小解决方案。

我想创造这样的东西，就像这里解释的那样。

然而，而不是映射到字符串。我想映射到一个数组。所以我尝试了这样的事情。

但这会返回：

有没有办法实现这一目标？

更新 5：

此功能已作为 pandas 20.1 的一部分发布（在我生日那天 :]）

更新 4：

PR 已合并！

更新 3：

PR 已移至此处

更新 2：

似乎这个问题可能有助于在 pandas 中重新打开 IntervalIndex 的 PR。

更新：

我不再有这个问题，因为我现在实际上是在查询 和 的重叠范围，A而B不是B在 范围内的点A，这是一个完整的区间树问题。不过我不会删除这个问题，因为我认为它仍然是一个有效的问题，而且我没有一个好的答案。

问题陈述

我有两个数据框。

在 dataframeA中，两个整数列一起表示一个区间。

在 dataframeB中，一个整数列代表一个位置。

我想做一种连接，以便将点分配给它们所在的每个间隔。

间隔很少但偶尔重叠。如果一个点落在该重叠范围内，则应将其分配给两个区间。大约一半的点不会落在一个区间内，但几乎每个区间都会在其范围内至少有一个点。

我一直在想什么

我最初打算将我的数据从 pandas 中转储出来，并使用intervaltree或banyan或者bx-python但后来我遇到了这个gist。事实证明，shoyer 的想法从来没有进入过 pandas，但这让我开始思考——可能在 pandas 中做到这一点，因为我希望这段代码尽可能快地运行 python，所以我'宁愿直到最后才将我的数据从熊猫中转储出来。我也觉得这可以通过bins和 pandascut功能实现，但我是 pandas 的新手，所以我可以使用一些指导！谢谢！

笔记

潜在相关？Pandas DataFrame groupby 可变长度的重叠间隔

我遇到了一个问题，高维区间树可能会有所帮助。我可以理解一维区间树是如何工作的。但我看不出应该如何在更高的维度上实现。

区间树和范围树

Wikipedia上的解释说对每个维度使用范围树和区间树。但我看不到它是如何工作的！我不清楚那里的解释......请检查“更高维度”部分：

首先，构建一个 N 维的范围树，它允许有效地检索具有查询区域 R 内起点和终点的所有区间。一旦找到相应的范围，剩下的就是那些将区域包围在某个范围内的范围。方面。

如果范围树更有效，为什么我们需要区间树？

对于Range Trees，我们可以看到它是为区间内的查询点制作的（树不存储区间）。因此，我假设维基百科的意思是：

首先，构建一个 N 维的范围树，它允许有效地检索查询区域 R 内具有开始或结束点的所有区间。

然后..什么？如果我从此时开始为每个维度创建一个区间树，即使原始对象不与我的查询相交，这些区间中的任何一个都将位于我的搜索框上。请检查以下图片以尝试可视化我在说什么。

也许，我不清楚的是：如何交叉两个区间树的区间结果以确保它位于一个实体上？

有人可以解释在这种情况下如何使用范围树吗？

R树

顺便提一下，我知道 R Tree 的存在。但我想先了解高维的区间树。此外，就像注释一样，在维基百科他们说：

区间树——一维（通常是时间）的退化 R 树。

我强烈不同意。否则，我们为什么要谈论高维区间树？如果我很好地理解这两种方法：

R Tree 使用 MBR 对实体进行分组，而 Interval Tree 使用点。

R Tree 可以存储任何类型的空间实体，而 Interval Tree 只存储区间。

R Tree 需要时不时地拆分节点，看起来很昂贵。区间树从不拆分节点。

我有一个数据，例如根据以下内容：

我需要将内容与为内容和范围字段提供的输入相匹配，以返回匹配的行。如您所见，内容字段是字符串的集合，而范围字段是两个数字之间的范围。我正在研究散列数据，用于与散列输入匹配。正在考虑遍历单个字符串哈希码的集合并将其存储在 Content 字段中。对于 Range 字段，我正在查看使用区间树。但是接下来的挑战是，当我对内容输入和范围输入进行哈希处理时，我将如何找到哈希码是否存在于为内容字段中的字符串集合生成的哈希码中，并且对于范围字段也是如此。

请让我知道是否有任何其他替代方法可以实现这一目标。谢谢。

假设我有一个这样的范围列表

[[1,3], [2,5], [4,6], [8,10], [12,15], [13,17]]

现在我想找到一个范围说[3,11]落入。我的算法应该给我这个范围落入的所有范围。例如，这个输出应该是

Output - [1,3], [2,5], [4,6], [8,10]

我该如何解决这个问题？

PS：我知道分段树可能会有所帮助。我可以在哪里构建树来存储区间并查询位于区间内的点，但是如何在给定区间的情况下获取所有区间。

这是一个关于一个有点复杂的问题的算法问题。基础是这样的：

基于可用时隙和保留时隙的调度系统。插槽有一定的标准，我们称之为标签。如果可用时隙的标签集是保留时隙的超集，则保留通过这些标签与可用时隙匹配。

作为一个具体的例子，以这个场景为例：

在 11:00 到 12:30 之间可以进行标签预订A，B从 12:00 到 13:30可以使用，C并且D从大约 12:00 到 12:30 有重叠。

这里A已经进行了预订，因此在 11:15-ish 和 12:00-ish-ish 之间没有其他预订A或B不能进行其他预订。

简而言之就是这个想法。可用插槽没有特定限制：

• 一个可用的插槽可以包含任意数量的标签
• 任意数量的插槽可以随时重叠
• 插槽是任意长度的
• 预订可以包含任意数量的标签

系统中唯一需要遵守的规则是：

• 添加预留时，至少有一个剩余的可用插槽必须与预留中的所有标签匹配

澄清一下：当同时有两个可用的插槽时，例如 tag A，那么当时可以进行两次预订A，但不能再进行了。

我可以使用间隔树的修改实现；作为快速概述：

• 所有可用的插槽都添加到间隔树中（保留重复/重叠）
• 所有保留的插槽都被迭代并且：
  • 从树中查询与预订时间匹配的所有可用时隙
  • 与预订标签匹配的第一个被切片，并从树中删除切片

当该过程完成后，剩下的就是剩余的可用槽片，我可以查询是否可以为特定时间进行新的预订并添加它。

数据结构看起来像这样：

标签本身就是键值对象，它们的列表就是一个“标签集”。如果有帮助，可以将它们序列化；到目前为止，我使用的是一种 Pythonset类型，这使得比较很容易。时隙开始/结束时间是树中的 UNIX 时间戳。我并不是特别喜欢这些特定的数据结构，如果有用的话可以重构它们。

我面临的问题是这不是没有错误的。每隔一段时间，预订就会潜入与其他预订发生冲突的系统中，我还不知道这到底是怎么发生的。当标签以复杂的方式重叠时，它也不是很聪明，需要计算最佳分布，以便所有预留可以尽可能地适合可用的插槽；事实上，目前在重叠场景中如何将预订与可用时隙进行匹配是不确定的。

我想知道的是：区间树主要用于此目的，但我当前的系统将标签集匹配作为附加维度添加到此系统是笨重且固定的；有没有一种数据结构或算法可以优雅地处理这个问题？

必须支持的操作：

1. 向系统查询与特定标签集匹配的可用时隙（考虑可能降低可用性但它们本身不是所述标签集的一部分的预留；例如，在上面的示例中查询 的可用性B）。
2. 确保不能将没有匹配的可用插槽的预订添加到系统中。

我有一组 ip 范围，我需要查找用户给定的 ip 是否存在于给定的 ip 范围列表之间。

这是这个问题的延续

如何使用节点js检查给定的ip是否在给定的ip范围之间

Jonas 帮助我获取了 ip 是否存在。但我不想进行详尽的迭代搜索，我想进行快速的性能密集型搜索，因为我的 ip 范围（或数字范围）列表会很大。

我研究了 jonas 指出的布隆过滤器，但我不相信布隆过滤器可能会有所帮助。我也在看区间树，但我不认为它可以搜索区间，它将区间作为输入。

我的 ip 列表范围https://github.com/client9/ipcat/blob/master/datacenters.csv#L4

如何快速搜索它。我正在使用节点 js