有一个字符串的地图如何比较给定的字符串 [英] having a map of strings how to compare it to given string

问题描述

我们有字符串对的地图，如名称：location（unix like absolute location a la myfolder / ）。我们被赋予了一些位置，其中一个是 myfolder / mysubfolder / myfile 。如何找到适合给定URL的地图位置？

我们有一个地图，例如：

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

我们被赋予价值 myfolder / mysubfolder / myfile / blablabla / （string ）。
我们想要找出我们地图中与哪个项目最相关的项目。
搜索结果应为 service4 作为具有最相关内容的地图项。

那么如何找到给定字符串值最关联哪个地图元素？

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

所以我简化了一个问题 - 现在我需要的所有关系都在于给定路径的深度是多少？在字符串的情况下，可以通过在所有地图上进行迭代来查看这个空格，搜索appearence给定路径并记住在给定路径中找到的最长长的地图项路径。

解决方案

有两个选项：

1. 如果需要运行许多查询：
   
   
   
   1. 构建反向映射或使用双向映射。 >
      
   2. 使用upper_bound和
      
      
      
      • 查找第一个更大的元素如果您需要具有最长公共前缀的元素，请检查此和上一个（最后一个较小的）元素，然后选择具有较长公用前缀的元素。
      
      
      • 如果您需要作为前缀的元素，请扫描回你会发现一个前缀元素。
      
      
   
   



2. 如果你只需要一个查询，简单的线性搜索将会更快（构建逆映射需要 O（n log（n）），而一次迭代只需要 O（n）），加上它更容易实施。简单地迭代地图，每个值计算前缀长度，并记住迄今为止最好的匹配（我想建议使用 std :: max_element ，但它通过比较实现最大运营商，而您需要最大化的指标）。

We have map of string pairs like name:location (unix like absolute location a la myfolder/). We are given with some location a la myfolder/mysubfolder/myfile. How to find which of maps location fit to given url most?

Example we have a map like:

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

We are given value myfolder/mysubfolder/myfile/blablabla/ (string). We want to find out to which item in our map it relates the most. Search result shall be service4 as map item with most related content.

So how to find by given string value to which map element it relates the most?

Please provide some code because I am C++ nube and do not get how to inplement such thing?

So I simplified a problem a bit - now all relation I need is in how deep given path is which in string case can be aceived by just iteratin over all maps paths looking at thare langth , searching for appearence in given path and remembering most long map item path found in given path.

解决方案

There are two options:

1. If you need to run many queries:
   1. Build the inverse map or use bidirectional map.
   2. Find first larger element using upper_bound and
      • If you need element with longest common prefix, check this and previous (last smaller) element and choose the one with longer common prefix.
      • If you need element that is a prefix, scan back until you find an element that is a prefix.

2. If you need just one query, simple linear search will be quicker (building the inverse map takes O(n log(n)), while one iteration takes just O(n)), plus it's easier to implement. Simply iterate over the map, for each value calculate the prefix length and remember the best match so far (I wanted to suggest using std::max_element, but it implements maximum by comparison operator while you need maximum by metrics).

这篇关于有一个字符串的地图如何比较给定的字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！