算法整数

类似的名单我有一个包含两个表SQLite数据库：算法整数

Objects: 
    object_id int, 
    name varchar(50) 

Values: 
    key char(12), 
    value int, 
    object_id int

正如你可以看到每个对象包含键 - 值对的列表。该列表通常包含10到60个条目。（key，object_id）的组合在值表中是唯一的。

然后我得到用户的键值对列表，并希望搜索数据库中最相似的对象。用户提供的对象在大多数情况下不会直接匹配我数据库中的任何对象。

相似性意味着两个对象的键的列表几乎相同，并且这些键的值相似（在大多数情况下，值也不会相等）。该列表可以是可变长度的。

考虑以下列表：

A = { a: 10, b: 20, c: 30 } 
B = { a: 11, c: 80, d: 90 } 
C = { c: 70, d: 89, e: 40, f: 100 } 
D = { c: 65, d: 80, e: 41 }

A和B都包含密钥一个和Ç而b和d只包含在它们中的一个。所以如果我们只看关键字，相似度就是0.5。 A和d只有Ç共同点，一个，b，d和Ë仅包含在一个列表中。所以他们不会很相似。

在下一步中，我必须查找匹配键的值。因此，在A和B的示例中，必须比较密钥a和c的值。 a非常相似，而c不是很好的匹配。

是否可以直接用SQLite进行这样的搜索？如果不是，那么搜索最好的方法/算法是什么？搜索应该尽可能快，但不应该消耗太多的计算能力/内存，因为我在移动设备上执行此操作。

我非常感谢任何关于此主题的帮助，链接或资源。如果我没有得到它，你想要的所有记录与一组固定的从用户输入记录比较

来源

2012-11-27 2dpc

如何定义'相似的键'或'几乎相等的对象'？ –

这些键本身是否相等。这些列表可以包含可变数量的键值对，以便一些键位于两个列表中，一些键不在。如果大多数键都包含在两个列表中，并且只有少数键仅在其中一个中，则对象几乎相等。这些键的值应该尽可能相似（总是整数）。 – 2dpc

所以'相似性'意味着至少有K个键是相等的？ –

（让我们说这是相同的结构Values表）=>O（n * m个。在值的记录，米的物体，n * m个 =无*米）（其中n =没有在用户输入=键） - 基本上为O（n）如果米_1,2是常数因子：

select 
    v1.object_id, 
    count(distinct v1.key) cnt_obj_keys, 
    count(distinct v2.key) cnt_usr_keys, --replace with a constant from outside code 
    count(case 
      when v1.key = v2.key 
      then 1 
     end) cnt_similar_keys, 
    count(case 
      when v1.key = v2.key and v1.value = v2.value 
      then 1 
     end) cnt_similar_values 
from values v1 
cross join values_from_user v2 
group by v1.object_id 
;

然后，您只需要使用每个对象的公式即O（n）来计算用于对对象进行排序并获取它们的第一个x的未指定索引 - 例如，：

order by 
    cnt_similar_keys/(cnt_obj_keys + cnt_usr_keys - cnt_similar_keys), 
    cnt_similar_values/cnt_similar_keys

来源

2012-11-29 12:49:50 Aprillion

回答

相关问题