多維數據查找

Question

我有一個N值元組的集合。值可以是通配符（匹配任何值）或具體值。查找匹配特定元組的集合中的所有元組而不掃描整個集合和測試項目的最佳方法是什麼？

E.g. 1.2.3匹配1.*.3和*.*.3，但不是1.2.4或*.2.4。

我在這裏尋找什麼數據結構？

Answer 1

我會用trie來實現這個。這是我怎麼構建線索：

的數據結構類似於：

Trie{ 
    Integer value 
    Map<Integer, Trie> tries 
} 

要插入：

insert(tuple, trie){ 
    curTrie = trie 
    foreach(number in tuple){ 
    nextTrie = curTrie.getTrie(number) 
    //add the number to the trie if it isn't in there 
    if(nextTrie == null){ 
     newTrie = new Trie(number) 
     curTrie.setTrie(number, newTrie)   
    } 
    curTrie = curTrie.getTrie(number) 
    } 
} 

要獲取所有元組：

getTuples(tuple, trie){ 
    if(head(tuple) == "*"){ 
    allTuples = {} 
    forEach(subTrie in trie){ 
     allTuples.union(getTuples(restOf(tuple), subTrie)) 
     forEach(partialTuple in allTuples){ 
     partialTuple = head(tuple)+partialTuple 
     } 
    } 
    return allTuples 
    } 
    if(tuple == null) 
    return {trie.value} 

    if(trie.getTrie(head(tuple)) == null) 
    raise error because tuple does not exist 
    allTuples = {} 
    allTuples.union(getTuples(restOf(tuple), trie.getTrie(head(tuple)) 
    forEach(partialTuple in allTuples){ 
    partialTuple = head(tuple)+partialTuple 
    } 
    return allTuples 
}