n***k
发帖数: 2780 | 1 what's the best data structure for storing and looking up a huge amount of
url's (presented in a prefix format) like these:
com.google.www -> value1
com.yahoo.finance -> value2
com.yahoo.finance/stocks -> value3
com.yahoo/finance -> value2
1.2.3.4/node/123 -> value4
....
the requirements are:
1. it has to be compact (compression if necessary).
2. lookup time should be fast (constant would be ideal, but a few level of
tree lookup is fine too). |
g*******s
发帖数: 490 | |
n***k
发帖数: 2780 | 3 thanks for your response.
Yes, I guess Trie might be the right solution. however, how can we use Trie
to solve wildcards for lookups?
for example, "com.yahoo.*" should match all nodes like these:
"com.yahoo"
"com.yahoo.finance"
"com.yahoo.sports"
...
【在 g*******s 的大作中提到】
: trie?
: 这里有讨论trie的compression
: http://en.wikipedia.org/wiki/Trie#Compressing_tries
|
g*******s
发帖数: 490 | 4 这个example比较简单，com.yahoo.的所有孩子就是了。。。比较复杂的wildcard search也是可以实现的 |
f*******4
发帖数: 1401 | 5 如果是 "*.yahoo.*.aaa" 之类怎么实现最好？
search也是
可以实现的
【在 g*******s 的大作中提到】
: 这个example比较简单，com.yahoo.的所有孩子就是了。。。比较复杂的wildcard search也是可以实现的
|
