java - 给定一个位数组，如何在位特里找到最近的签名？

Question

给定一个位的 Trie，以及作为位数组/向量的输入，如何在 Trie 中找到输入向量的最近邻？

我正在尝试执行的算法如下：给定一个位向量 V 和一个置换函数 F，执行以下操作：

1- F(V) = V_; 其中 V_ 是 V 的签名。

2- 在 trie 中插入 V_；

一段时间后......给定一个位向量U，执行以下操作：

1- F(U) = U_;

2-在树中找到最近的签名。

最近的签名由汉明距离定义。

Answer 1

您可以使用Branch 和 bound来逐步缩小搜索空间。在树上进行深度优先搜索，并跟踪到目前为止有多少位未匹配。当您找到更接近目标的叶子时，您会更新当前上限。当你进入一个比当前上限更远的子树时，你会修剪它。如果有匹配的子树，则始终先进入匹配的子树。