算法整數

類似的名單我有一個包含兩個表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

回答

相關問題