Многомерный поиск данных

Question

У меня есть коллекция кортежей из N значений. Значением может быть подстановочный знак (соответствует любому значению) или конкретное значение. Каков наилучший способ поиска всех кортежей в коллекции, соответствующих определенному кортежу, без сканирования всей коллекции и тестирования элементов один за другим?

например. 1.2.3 соответствует 1.*.3 и *.*.3, но не 1.2.4 или *.2.4.

Какую структуру данных я здесь ищу?

Answer 1

Я бы использовал три для реализации этого.Вот как я должен построить дерево:

Структура данных будет выглядеть следующим образом:

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
}