如何使用近似查询存储数据？

Question

我正在尝试找到一种可以快速访问（优于 O(n)）的方法来存储我的数据。

我的数据库由表示有关某些项目的一些信息的数据（4096 字节字符串）组成。
问题是，查询永远不会准确。我得到一个 Item，然后需要使用函数找到最接近的匹配项F(a,b)。

只是一个例子：

1234
3456
6466
F(a,b) = return % of similar digits  

GetClosest(1233,F) = 1234

问题是 F(a,b) 是一个复杂的算法，（不是一个合适的度量）。

我现在所拥有的只是遍历整个数据库以搜索最佳匹配。
是否有一种树或其他集群数据库类型可以让我更快地找到复杂性？

更多信息：

F 以百分比形式返回相似度值。其中 100% 是完美匹配。

Answer 1

您可能想尝试检索 (re trie val) 树，即 TRIE。有些人将其称为基数树。

这个想法是创建树节点结构，其中包含数据字段可能包含的每个字符的分支。

让我们使用一个简单的例子，一个数字字段。显然，字符范围是0-9。每个树节点将包含十（10）个分支。让我们以 4 字节无符号整数 2^32 - 1 的最坏情况为例，即 4294967295。它的长度是多少？只需通过取 4294967295 以 10 为底的对数整数并加 1 即可计算长度。

mysql> select floor(log10(power(2,32)) + 1);
+-------------------------------+
| floor(log10(power(2,32)) + 1) |
+-------------------------------+
|                            10 |
+-------------------------------+
1 row in set (0.00 sec)

因此，您将拥有一个最大高度为 10 的 TRIE。从 TRIE 的根部开始，如果您的数字为 4294967295，则您将遍历分支 4,2,9,4,9,6,7,2,9， 5. 在每个分支，您将执行数组样式的二分搜索。

如果位于该 TRIE 节点的分支完全匹配，您可以为该级别分配一个百分比，然后递归地沿着该分支检查下一个数字，并从更深的 TRIE 节点返回百分比，以添加到该级别的百分比。当前搜索的TRIE节点。

如果位于该 TRIE 节点的分支不完全匹配，则您将在那里停止递归搜索并返回 0 或您可能想要指定的其他百分比。

给定所有搜索到的 TRIE 节点的返回值总和，您可能需要对百分比进行求和，然后将该答案除以字符串的长度。换句话说，

每个节点的百分比 = (1 / (需要搜索的 TRIE 节点数)) 或零 (0)。

Sum(Pct) = (完全匹配的TRIE节点数)/(需要搜索的TRIE节点数[被搜索字符串的长度])。

给定您存储的数字字段的长度，由于字段长度，您的时间复杂度为 O(log n)。对于每个 TRIE 节点，您需要 O(log n) 来搜索正确的分支。总的来说，您的搜索应该有 O(log (log n)) 搜索时间。

如果该字段是字母数字字段，则此性能会更加突出。假设仅使用 ASCII，每个 TRIE 节点将有 256 个分支。TRIE 的高度取决于字符字段的长度。将这个 TRIE 表示为可变长度字符串将产生非常稀疏的 TRIE 节点，但仍然可以快速搜索。

无论您使用什么数据库，请仔细规划将用于表示 TRIE 节点的数据类型。您可能还想对表进行分区，以便长度为 n 的字符串在分区 n 中终止。因此，每个分区的搜索时间为 O(log n)。

http://en.wikipedia.org/wiki/Trie

http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node24.html

http://www.webreference.com/js/tips/000318.html

http://en.wikipedia.org/wiki/Radix_tree