Имея карту строк, как сравнить ее с заданной строкой

Question

У нас есть карта пар строк, таких как name:location (unix как абсолютное местоположение а-ля myfolder/). Нам дают с некоторым местоположением а-ля myfolder/mysubfolder/myfile, Как определить, какая из карт больше всего подходит для данного URL?

Пример у нас есть карта вроде:

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

Нам дано значение myfolder/mysubfolder/myfile/blablabla/ (Строка). Мы хотим выяснить, к какому пункту на нашей карте это относится больше всего. Результат поиска должен быть service4 как элемент карты с наиболее связанным содержанием.

Так как же найти по заданному строковому значению, к какому элементу карты он относится больше всего?

Пожалуйста, предоставьте некоторый код, потому что я C++ Nube и не понимаю, как дополнить такую ​​вещь?

Поэтому я немного упростил задачу - теперь все, что мне нужно, это то, насколько глубоким является заданный путь, который в строковом случае может быть воспринят путем итерации по всем путям карт, смотря на длину, ища внешний вид в данном пути и запоминая самую длинную карту. путь к предмету найден в заданном пути.

Answer 1

Есть два варианта:

1. Если вам нужно выполнить много запросов:
   1. Постройте обратную карту или используйте двунаправленную карту.
   2. Найти первый больший элемент, используя upper_bound и
      • Если вам нужен элемент с самым длинным общим префиксом, отметьте этот и предыдущий (последний меньший) элемент и выберите элемент с более длинным общим префиксом.
      • Если вам нужен элемент, который является префиксом, сканируйте назад, пока не найдете элемент, который является префиксом.
2. Если вам нужен только один запрос, простой линейный поиск будет быстрее (построение обратной карты занимает O (n log (n)), в то время как одна итерация занимает всего O (n)), плюс его легче реализовать. Просто итерируйте по карте, для каждого значения вычислите длину префикса и запомните наилучшее совпадение (я хотел бы предложить использовать std::max_element, но он реализует максимум по оператору сравнения, в то время как вам нужен максимум по метрике).

Answer 2

Если я правильно понимаю ваш вопрос, вы хотите искать ключи по значению (строке), где совпадающие значения являются подстрокой предоставленного поискового запроса. Я не думаю, что есть простое решение для этой общей проблемы (т.е. произвольные строки и все их подстроки).

Однако строки, используемые в качестве значений в вашем примере, имеют особую структуру (то есть пути файловой системы). Вы можете использовать эту структуру, чтобы придумать чистое решение. Сначала сделайте двунаправленную карту. Затем реализуйте следующий процесс поиска:

1. Если путь пуст, сбой.
2. Обратный поиск в карте на основе пути запроса
3. Если найдено, вернуть соответствующее значение.
4. Удалите последний компонент с пути.
5. Loop.

Если список короткий, вы можете просто просмотреть список пар (ключ, значение) и выбрать ключ, в котором значение является наиболее похожим (т.е. самая длинная общая подстрока).

Answer 3

Если ваша карта определена так:

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