有一個字符串映射如何將其與給定字符串進行比較

Question

我們有像名字一樣的字符串對的映射：位置（像絕對位置一樣的unix a la myfolder/）。我們給了一些地點la myfolder/mysubfolder/myfile。如何找到最適合給定網址的地圖位置？

例子，我們有一個地圖，如：

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

我們給定值myfolder/mysubfolder/myfile/blablabla/（串）。 我們想知道它與我們地圖中哪個項目最相關。 搜索結果爲service4爲最相關內容的地圖項。

那麼如何通過給定的字符串值來查找它最相關的地圖元素呢？

請提供一些代碼，因爲我是C++ nube，不知道如何實現這樣的事情？

所以我簡化了一個問題 - now all relation I need is in how deep given path is在字符串的情況下，可以通過遍歷所有地圖路徑來查看長度，尋找給定路徑的出現並記住在給定路徑中找到的最長地圖項目路徑。

Answer 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"; 

Answer 2

有兩種選擇：

1. 如果您需要運行很多查詢：
   1. 構建反向映射或使用雙向映射。
   2. 使用UPPER_BOUND查找第一大要素和
      • 如果您需要最長的公共前綴元素，看看這個和以前（最後小）元素，並選擇一個較長的公共前綴。
      • 如果您需要作爲前綴的元素，請回溯掃描，直至找到作爲前綴的元素。
2. 如果你只需要一個查詢，簡單的線性搜索會更快（構建逆映射需要O（N日誌（N）），而一個迭代只需爲O（n） ），再加上它更容易實現。只需遍歷地圖，爲每個值計算前綴長度，並記住目前爲止的最佳匹配（我想建議使用std::max_element，但它通過比較運算符實現最大值，而通過度量需要最大值）。

Answer 3

如果我正確理解您的問題，您希望通過值（字符串）搜索鍵，其中匹配值是提供的搜索詞的子字符串。我認爲這不是一個簡單的解決方案，因爲這是一個普遍問題（即任意字符串及其所有子字符串）。

但是，在您的示例中用作值的字符串具有特定的結構（即文件系統路徑）。你可以利用這個結構來提出一個乾淨的解決方案。首先，製作bi-directional map。然後，執行以下查找過程：

1. 如果路徑爲空，則失敗。
2. 根據請求路徑在地圖上進行反向查找
3. 如果找到，返回相關值。
4. 從路徑中彈出最後一個組件。
5. Loop。

如果列表很短，您可能只想遍歷（鍵，值）對列表並選擇值最相似的鍵（即最長的子字符串）。