2

I am searching for a good algorithm for managing configuration variables in form of tree with wildcards (x.y.z, x..z, x..* etc.).

Is there something with search time better than O(N)? (insert / delete time are not so important).

Currently I have a flat list (pairs key=>value), and I search all matching values, then sort them by importance (basically, more wildcards => less important) and choose one with best score.

peSHIr
  • 6,279
  • 1
  • 34
  • 46
ts.
  • 10,510
  • 7
  • 47
  • 73
  • Can you clarify what it is that you're trying to do? What queries do you want to support? – templatetypedef Mar 24 '11 at 08:58
  • ie. having list of keys x.*.*, x.*.z, x.y.* and search string x.y.z i have to return value for key x.*.z. Searching for x.y.v returns x.y.*, searching for v.y.z returns nothing. – ts. Mar 24 '11 at 09:22
  • Is there a special significance to the dot? I presume * does not match .? – Josh Mar 24 '11 at 12:27
  • yes, dot is a separator and * does not match it – ts. Mar 24 '11 at 13:10

2 Answers2

4

As epitaph points out, a trie or radix-tree will do the trick. A radix-tree will generally be more space efficent.

I guess there are a dozens of implementations out there. Take a look at my implementation here.

lookup() will allow you to search for a given key.

startwith() will return all those keys and their corresponding values that start with the passed string. It is effectively a wild-card search.

foolano
  • 76
  • 1
  • 5
  • Note that once you have reached a leaf in a radix-tree you still have to compare the remaining part of the string. That makes both trees O(K). But I guess in the real world a radix-tree will be slightly faster. – foolano Mar 24 '11 at 16:26
  • yes, sure, but I've a kart-trie and in kart-trie you don't need to compare the remaining part of the string so it is O(log(n)) or O(log(k)*log(n)). – Micromega Mar 24 '11 at 16:45
  • I don't know about real world, didn't tried it, and it seems that the author and inventor didn't know it either: http://code.dogmap.org/kart/. But the time complexity of a binary tree is O(log(n)), isn't it? – Micromega Mar 24 '11 at 17:01
1

What you want is a trie-datastructure or a radix-tree. When you want to search for a wildcard just use the inverse trie with the trie together. You can find a simple solution here: code.dogmap.org/kart.

Micromega
  • 12,486
  • 7
  • 35
  • 72