我的情况
假设我有数千个对象，在本例中可能是电影。
我以许多不同的方式解析这些电影，收集有关每个电影的参数，关键字和统计信息。让我们称它们为钥匙。我还为每个键分配一个权重，范围从 0 到 1，具体取决于频率、相关性、强度、分数等。
例如，以下是电影世界末日的一些键和重量：
"Armageddon"
------------------
disaster 0.8
bruce willis 1.0
metascore 0.2
imdb score 0.4
asteroid 1.0
action 0.8
adventure 0.9
... ...
可能有几千个这样的键和重量，为了清楚起见，这是另一部电影：
"The Fast and the Furious"
------------------
disaster 0.1
bruce willis 0.0
metascore 0.5
imdb score 0.6
asteroid 0.0
action 0.9
adventure 0.6
... ...
我称之为电影的指纹，我想使用它们在我的数据库中查找类似的电影。
我还想象可以插入电影以外的内容，例如文章或Facebook个人资料，并根据需要为其分配指纹。但这不应该影响我的问题。
我的问题
所以我已经走到了这一步，但现在是我觉得棘手的部分。我想取上面的指纹，把它变成一个容易比较和快速的东西。我尝试创建一个数组，其中索引0=disaster，1=bruce willis，2=metascore它们的值是权重。
对于我上面的两部电影，结果是这样的：
[ 0.8 , 1.0 , 0.2 , ... ]
[ 0.1 , 0.0 , 0.5 , ... ]
我尝试以不同的方式进行比较，只需乘以：
public double CompareFingerprints(double[] f1, double[] f2)
{
double result = 0;
if (f1.Length == f2.Length)
{
for (int i = 0; i < f1.Length; i++)
{
result += f1[i] * f2[i];
}
}
return result;
}
或比较：
public double CompareFingerprints(double[] f1, double[] f2)
{
double result = 0;
if (f1.Length == f2.Length)
{
for (int i = 0; i < f1.Length; i++)
{
result += (1 - Math.Abs(f1[i] - f2[i])) / f1.Length;
}
}
return result;
}
等等。
这些都返回了非常令人满意的结果，但它们都有一个共同的问题：它们非常适合比较两部电影，但实际上，当我想将单个电影指纹与存储在MSSQL数据库中的数千个指纹进行比较时，这非常耗时并且感觉非常糟糕。特别是如果它应该与自动完成之类的东西一起使用，我想在几分之一秒内返回结果。
我的问题
我在这里有正确的方法，还是我以一种非常低效的方式重新发明轮子？我希望我的问题不是针对堆栈溢出的广泛问题，但我在下面通过一些想法缩小了范围。
几个想法
- 我的指纹真的应该是一个重量数组吗？
- 我应该考虑对指纹进行哈希处理吗？它可能有助于指纹存储，但使比较复杂化。通过使用对位置敏感的哈希，我发现了一些提示，这可能是一种有效的方法，但数学有点超出我的能力范围。
- 我应该从SQL中获取所有数千部电影并使用结果，还是有没有办法将我的比较实现到SQL查询中并仅返回前100次点击？
- 稀疏数据表示是要研究的吗？(感谢速度8ump)
- 我可以应用比较实际指纹或 OCR 时使用的方法吗？
- 我听说有一种软件可以通过在数千篇已发表的论文和以前的测试中发现相似之处来检测考试作弊。他们使用什么方法？
干杯！
替代方法：特征向量
你所描述的是一个经典的特征向量。特征向量中的每一列描述一个类别。您的特征向量是一种特殊类型：它具有模糊数据，描述了属于某个类别的程度。
处理此类向量时，应应用模糊逻辑进行计算。对于模糊逻辑，您必须稍微玩一下 areound，直到找到最适合您的模糊运算的数字运算符。例如，模糊 AND 和 OR 可以用 "min" 和 "max" 或 "*" 和 "+" 甚至更复杂的指数运算来计算。您必须在良好的结果和快速计算之间找到适当的平衡。
不幸的是，模糊逻辑不太适合SQL数据库。如果你走模糊的方式，你应该考虑将所有数据保存在内存中，并使用某种数值处理加速(处理器SIMD指令，CUDA/OpenCL，FPGA等)。
备选方案：星形/雪花模式
另一种方法是构建经典的数据仓库方案。这非常适合现代 SQL 数据库。它们具有很好的加速功能，可以从中型数据仓库(多达数十亿条记录)检索数据：
- 实例化视图(用于数据缩减) (
- 压缩)位图索引(用于快速组合多个功能)
- 压缩存储(用于快速传输大量日期)
- 传输(根据数据的特征对数据进行物理分离)
要使用这些优化，您必须先准备日期。
分层维度
您应该根据雪花方案对要素进行分层排序。当数据以这种方式排序时(并且您有相应的索引)，数据库可以使用一组新的优化，例如位图过滤。
以这种方式组织的数据应主要是只读的。数据库将需要数据结构，这些数据结构对于特殊类型的查询非常快，但更新成本也非常高。
例如，位图索引。位图索引是一个二进制矩阵。矩阵的行是数据库中一个表的行。这些列是此表中一行的可能值。矩阵中的条目为1，当表中相应行中的列作为根据矩阵列的值时。否则为 0。
位图索引将以压缩的二进制格式存储。对于数据库，通过使用快速二进制处理(通过使用处理器 SIMD 指令甚至 OpenCL/CUDA 等对二进制值进行 AND 或 ORing 或 ORing)来组合多个位图索引非常容易。
有一些特殊的位图索引可以跨越多个表，因此称为位图联接索引。它们是专门为在雪花架构中组织的数据而构建的。
尺寸减小
还应使用降维来减少必须存储的要素数量。为此，您可以使用主成分分析等技术。有了这个，您可以将多个高度耦合的特征组合成一个人工特征，并完全删除根本不改变其值的特征。
离散维度成员
对于模糊逻辑，使用浮点数很好。但是，在数据仓库中存储数据时，最好减少到可能的值。位图索引和分区仅适用于有限数量的值。您可以使用分类算法来实现这一点，例如自组织特征图或粒子群优化。
备选方案3：混合方法
您可以轻松地将上述两种方法结合起来。使用精简说明(更少的维度，更少的成员)将日期存储在数据仓库中。每个数据集都包含原始特征。当您从数据仓库中检索数据集时，您可以使用备选方案 1 中的技术来处理完整的描述，例如，根据当前上下文确定竞争的最佳候选者。
这个想法很酷，这样我可以找到布鲁斯的所有好电影(imdb> 5.5)，他在其中扮演主要角色(布鲁斯威利斯> 0.9)，这是动作(动作> 0.5)而不是恐怖(恐怖<0.1)。我讨厌恐怖。
您的想法：
- 权重数组是不好的，因为如果你得到越来越多的键，如果电影没有这个Actor，那么它仍然必须有一个值(0)，这是浪费空间(想象一下每部电影附加了数百万个键)。
- 哈希没有意义，因为您不会按确切值访问任何内容，您将始终将键与用户输入的值进行比较，其中许多将是可选的(这意味着您不在乎它们是 0 还是 10)。
- 视情况而定，见下文。
我认为您在这里需要的是一种Tag系统(例如SO one)，您可以在其中轻松添加新标签(例如，对于新演员或何时会有比蓝光或高清更好的标签等)。所以一个带有标签 [id]-[name] 的表。
然后，您的电影必须有一个字段来存储零到百万标签的字典[id]-[score]。这应该是一个 blob(或者有什么方法可以在 SQL 数据库中保存字典或数组？)或数组(如果你的标记 ID 从 0 开始并递增 1，则不需要键，而是索引)。
当您搜索匹配指纹条件的电影时，您必须从数据库中读取每部电影的指纹。这应该比SQL查询慢，但仍然可以(每部电影可能有100-1000个标签，这使得读取只有几KB)，除非你必须通过网络传输这些数据，然后考虑使用服务器应用程序。也许存储过程会有所帮助。
指纹格式
关于您的第一个问题，是否应该使用权重数组，这归结为您想要的详细程度。一系列权重将提供最高的指纹"分辨率"，因为缺乏更好的术语;它允许对任何两部给定电影的相似程度进行更精细的测量。Sinatr 建议使用标签代替权重具有很大的优化潜力，但它基本上将权重限制为 0 或 1，因此难以表示 0.3-0.7 范围内的现有权重。您必须自己决定使用细节较少的表示的性能增益是否超过这些表示的降低的比较准确性。
哈希斯
关于你的第二个问题，恐怕我不能提供太多指导。我不熟悉在这种上下文中使用哈希，但我不明白您如何轻松比较它们;在大多数用途中，哈希的全部意义在于它们不容易被逆转来了解原始输入。
SQL 优化
对于第三个问题，用于获取比较候选项的 SQL 查询可能是性能优化潜力的丰富来源，特别是如果您知道指纹的某些特征。特别是如果高权重或低权重相对罕见，那么您可以使用它们来淘汰许多糟糕的候选人。例如，如果您使用的是电影，则预计很多权重为 0(大多数电影不包含布鲁斯·威利斯)。您可以查看候选影片中高于 .8 左右的任何权重(您需要进行一些微调以确定适用于您的数据集的确切值)，然后让您的 SQL 查询排除至少在这些键的某些部分中为 0 的结果(再次， 分数需要微调)。这允许您快速丢弃在 SQL 查询阶段不太可能是良好匹配的结果，而不是对它们进行完整(昂贵)比较。
其他选项
根据对象指纹更改的频率，另一种可能有效的方法是预先计算指纹比较值，具体取决于对象的指纹更改频率。然后，从索引表中获取最佳候选项是：SELECT id1, id2, comparison FROM precomputed WHERE (id1 = foo OR id2 = foo) AND comparison > cutoff ORDER BY comparison DESC。预先计算新对象的比较将是添加它的过程的一部分，因此如果能够快速添加对象是优先事项，那么这种方法可能效果不佳。或者，您可以在计算值后简单地缓存值，而不是预先计算它们。这对初始搜索没有任何作用，但后来的搜索会获得好处，并且添加对象保持便宜。
我认为哈希是你正在寻找的，哈希表给你O(1)插入、删除和搜索。
我也有类似的情况，我必须对八个不同整数的数组进行哈希处理。我使用了 C++ boost 库中的以下代码。
size_t getHashValue ()const{
size_t seed = 0;
for (auto v : board)
seed ^= v + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
我的数组被称为board，这是C++中foreach循环的语法，size_t只是一个无符号整数，其余的与C#相同。
请注意，由于我有不同的值，我可以轻松地将值本身用作哈希函数，这样我就可以保证数组中的每个元素都有一个不同的哈希值。
由于情况并非如此，因此您需要更改代码以包含数组中每个条目的哈希，以构建整个数组的哈希，如下所示：
foreach (float entry in array)
// hashOf is something you would need to do
seed ^= hashOf(entry) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
如果您的条目在小数点后只有一个数字，则可以乘以 10 并将问题移动到整数域。 希望这有帮助。
编辑：
有关哈希十进制值，请参阅此问题：C# Decimal.GetHashCode() 和 Double.GetHashCode() 相等。
这种方法的性能中继在哈希函数上，函数的概率分布越均匀，获得的性能就越好。 但恕我直言，哈希表是你能看到的最好的