3

我有一个包含两个表的 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 都包含键a和c而b和d只包含在其中一个中。因此，如果我们只看键，相似度将是 0.5。A 和 D 只有c相同，a , b , d和e只包含在一个列表中。所以它们不会很相似。

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

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

我非常感谢有关此主题的任何帮助、链接或资源。

4

1 回答 1

1

如果我理解正确，您想将所有记录与来自用户输入的一组固定记录进行比较（假设它是一个结构与 相同的表Values）=> O(n*m 1 *m 2 ) （其中 n=对象数，n*m 1 =值中的记录数，m 2 =用户输入中的键） -如果 m 1, 2是常数因子，则基本上是 O(n) ：

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-29T12:49:50.067 回答