VP树最近邻搜索

VP树搜索算法的一个相对简单且易于阅读的Rust实现。

VP树算法不需要知道项目的坐标，只需要知道它们之间的距离。它可以有效地搜索多维空间，只要你可以定义它们之间的相似性（例如，点、颜色，甚至图像）。

请参阅API参考或示例以获取详细信息。

此算法不支持平方距离。在实现欧几里得距离时，您必须使用sqrt()。Vantage Point树需要度量空间。

#[derive(Copy, Clone)]
struct Point {
    x: f32, y: f32,
}

/// `MetricSpace` makes items comparable. It's a bit like Rust's `PartialOrd`.
impl vpsearch::MetricSpace for Point {
    type UserData = ();
    type Distance = f32;

    fn distance(&self, other: &Self, _: &Self::UserData) -> Self::Distance {
        let dx = self.x - other.x;
        let dy = self.y - other.y;

        // You MUST use sqrt here! The algorithm will give wrong results for squared distances.
        (dx*dx + dy*dy).sqrt()
    }
}

fn main() {
    let points = vec![Point{x:2.0,y:3.0}, Point{x:0.0,y:1.0}, Point{x:4.0,y:5.0}];

    let vp = vpsearch::Tree::new(&points);
    let (index, _) = vp.find_nearest(&Point{x:1.0,y:2.0});

    println!("The nearest point is at ({}, {})", points[index].x, points[index].y);
}

Rust内置类型实现MetricSpace

此库包含一个孤儿规则的解决方案。您需要在实现MetricSpace时添加您的crate类型

struct MyImpl; // it can be any type, as long as it's yours
impl vpsearch::MetricSpace<MyImpl> for Vec<u8> {
    // continue as usual
}

内存效率提示

Tree克隆所有项目并将它们放入树中。如果项目太大无法克隆，并且您宁愿在其他地方保留项目，您也可以！

而不是存储项目，让树存储对您的项目存储的索引，并将实际项目作为user_data传递给您的MetricSpace::distance()函数。

let items = /* your actual items are here */;
let indices: Vec<_> = (0...items.len() as u32).collect();
let tree = Tree::new_with_user_data_ref(&items, &indices);
let res = tree.find_nearest(&needle, &items);