2 个版本
| 0.1.1 | 2020年2月18日 |
|---|---|
| 0.1.0 | 2020年2月18日 |
#2024 在 数据结构
23KB
308 行
NClist
嵌套包含列表（NClist）是一种可以查询重叠区间元素的数据结构。它由 Alexander V 和 Alekseyenko Christopher J. Lee 在 2007 年的《生物信息学》杂志上发表（doi: 10.1093/bioinformatics/btl647）。
工作原理
NClist 的内部机制依赖于以下观察：当一组区间（基于它们的区间界限，所有区间都不包含在任何其他区间中）按照它们的起始坐标排序时，也按照它们的结束坐标排序。如果满足这个要求，可以通过在查询起始处进行二分搜索并返回直到查询结束坐标经过的项来找到与区间重叠的项，其复杂度为 O(log(N) + M)，其中 N 是集合的大小，M 是重叠的数量。
唯一剩下的问题是包含在其他区间中的区间。这是通过将它们取出并存储在单独的集合中，并将此集合链接到原始区间来解决的。现在，在查找重叠时，不仅要检查包含的区间，还要搜索这些嵌套集合。这可以通过递归（如论文所示）或使用队列（用于此包）来实现。这意味着如果所有区间都包含在其父级中，最坏情况下的复杂度变为 O(N)。
该链接文章还提供了关于可以高效搜索的磁盘版本的信息，但此包实现是在内存中，并将项存储在（单个）Vec 中。
如何使用
如果您为 T 实现了 Interval 特性，则可以从 Vec<T> 创建可搜索的 NClist<T>。该 Interval 特性还要求 T 是 Ord。创建 NClist 会验证结束坐标是否大于起始坐标。这意味着负宽度和零宽度区间不能用于 NClist<T>。
示例
use nclist::NClist;
// Given a set of `T` where `T` implements the `Interval` trait
let v = vec![(10..15), (10..20), (1..8)];
// Create the NClist, this consumes v
let nc = NClist::from_vec(v);
// count overlaps, the query is provided as a reference to a `std::ops::Range`
assert_eq!(nc.count_overlaps(&(10..12)), 2);
// remember, intervals are half open
assert_eq!(nc.count_overlaps(&(20..30)), 0);
//or query them using an iterator
let mut q = nc.overlaps(&(7..10));
assert_eq!(q.next(), Some(&(1..8)));
assert_eq!(q.next(), None);
使用建议
NClist<T> 是不可变的。对项目进行任何可变访问都可能使区间界限无效（例如使用 RefCell 进行内部可变访问可以解决这个问题）。此外，不支持插入和删除。我可以推测，区间树也更适合这种访问类型。在生物信息学中使用，其中区间数据通常以（排序的）列表形式提供（gff、gtf、bed），NClist<T> 是一个完美的选择，并且具有非常好的易用性。显然，当嵌套深度有限时，实现效果更好，但在简单测试中的性能似乎始终优于 rust-bio 的 IntervalTree。
依赖项
~440KB