我正在寻找一种好的算法,用于以带有通配符(x.y.z、x..z、x..* 等)的树形式管理配置变量。
是否有搜索时间比 O(N) 更好的东西? (插入/删除时间并不那么重要)。
目前,我有一个平面列表(键=>值对),我搜索所有匹配的值,然后按重要性对它们进行排序(基本上,更多通配符=>不太重要)并选择得分最高的一个。
最佳答案
正如墓志铭所指出的,特里树或基数树就可以解决问题。基数树通常会更节省空间。
我猜那里有几十种实现。看看我的实现 here .
lookup()将允许您搜索给定的键。
startwith() 将返回所有以传递的字符串开头的键及其相应的值。它实际上是一种通配符搜索。
关于algorithm - 使用通配符管理配置树的好算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5416778/