2

我们有像 name:location 这样的字符串对的映射（unix 像绝对位置 a la myfolder/）。我们得到了一些位置 a la myfolder/mysubfolder/myfile。如何找到最适合给定网址的地图位置？

示例我们有一个类似的地图：

service1:myfolder/
service2:myfolder/mysubfolder/
service3:myfolder/myothersubfolder/
service4:myfolder/mysubfolder/myfile

我们被赋予了价值myfolder/mysubfolder/myfile/blablabla/（字符串）。我们想找出它与地图中的哪个项目最相关。搜索结果应service4为相关内容最多的地图项。

那么如何通过给定的字符串值找到与它最相关的地图元素呢？

请提供一些代码，因为我是 C++ nube 并且不知道如何实现这样的事情？

所以我稍微简化了一个问题 -现在我需要的所有关系都是给定路径的深度，在字符串的情况下，可以通过迭代所有地图路径来查看 thare langth，搜索给定路径中的外观并记住最长的地图在给定路径中找到的项目路径。

4

3 回答 3

2

有两种选择：

  1. 如果您需要运行许多查询：
    1. 构建逆映射或使用双向映射。
    2. 使用 upper_bound 和
      • 如果您需要具有最长公共前缀的元素，请检查此元素和上一个（最后一个较小的）元素并选择具有较长公共前缀的元素。
      • 如果您需要作为前缀的元素，请向后扫描，直到找到作为前缀的元素。
  2. 如果您只需要一个查询，简单的线性搜索会更快（构建逆映射需要O(n log(n))，而一次迭代只需要O(n)），而且更容易实现。只需遍历地图，为每个值计算前缀长度并记住迄今为止的最佳匹配（我想建议使用std::max_element，但它通过比较运算符实现最大值，而您需要按指标最大值）。
于 2011-05-12T14:47:51.473 回答
1

如果您的地图是这样定义的：

typedef std::map<std::string,std::string> MyMap;
MyMap my_map;

...搜索词的定义如下：

std::string my_key_to_find = "service4";

...然后您可以获得与此键关联的值，如下所示：

std::string found_val;
MyMap::const_iterator it = my_map.find(my_key_to_find);
if( it != my_map.end() )
  found_val = it->second;
else
  std::cout << "Key not found!\n";
于 2011-05-12T14:26:10.113 回答
1

如果我正确理解您的问题，您想按值（字符串）搜索键，其中匹配值是所提供搜索词的子字符串。我不认为作为一般问题（即任意字符串及其所有子字符串）有一个简单的解决方案。

但是，在您的示例中用作值的字符串具有特定的结构（即文件系统路径）。您可以利用此结构提出一个干净的解决方案。首先，制作一个双向地图。然后，实现以下查找过程：

  1. 如果路径为空，则失败。
  2. 根据请求路径在map中反向查找
  3. 如果找到，则返回相关值。
  4. 从路径中弹出最后一个组件。
  5. 环形。

如果列表很短，您可能只想遍历 (key,value) 对的列表并选择值最相似的键（即最长的公共子字符串）。

于 2011-05-12T14:48:36.810 回答