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

问题描述

我们有这样的名字字符串对地图：位置（类似Unix的绝对位置一拉 MyFolder中/ ）。我们给出了一些位置的拉 MyFolder中/ mysubfolder / MYFILE 。如何找到它的地图位置合适的给定的URL最？

例子中，我们有地图，如：

 服务1：MyFolder中/
服务2：MyFolder中/ mysubfolder /
服务3：MyFolder中/ myothersubfolder /
服务4：MyFolder中/ mysubfolder / MYFILE
 

我们正在给定值 MyFolder中/ mysubfolder / MYFILE / blablabla / （字符串）。
我们要找出这在我们的地图项涉及最多。
搜索结果应为服务4 与最相关的内容的地图项。

因此​​，如何通过给定的字符串值找到哪个地图元素，它涉及的是什么？

请提供一些code，因为我是C ++ NUBE并没有得到如何inplement这样的事？

所以我简单的一个问题有点 - <一个href=\"http://stackoverflow.com/questions/5997723/having-a-map-with-paths-how-to-compare-tham-to-given-path\">now所有的关系我需要的是深定的路径是怎样这串情况下，可以由aceived只是iteratin在所有地图的路径看thare langth，搜索在给定的路径appearence和记忆中给出的发现最长寿的地图项路径路径。

解决方案

有两种选择：

1. 如果您需要运行多个查询：
   
   
   
   1. 构建逆映射或使用双向映射。
   
   
   2. 使用UPPER_BOUND查找第一大元素，
      
      
      
      • 如果您需要最长的共同preFIX元素，检查并previous（最后一个小）元素，然后选择一个较长的共同preFIX。
      
      
      • 如果您需要的元素是preFIX，扫描回来，直到你发现这是一个preFIX的元素。
      
      
   
   


2. 如果你只需要一个查询，简单的线性搜索会更快（构建逆映射需要的 O（N日志（N））的，而一个迭代只需 O（N） 的），再加上它的更容易实现。只需在地图上迭代，每个值计算preFIX长度和记忆的最佳匹配为止（我想使用的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屋！