多维数据查找

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 
}