имея карту строк, как сравнить ее с заданной строкой - PullRequest
Новая
       50

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

2 голосов
/ 12 мая 2011

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

Например, у нас есть карта типа: 

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

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

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

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

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

Ответы [ 3 ]

2 голосов
/ 12 мая 2011

Существует два варианта:

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

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

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

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

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

1 голос
/ 12 мая 2011

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

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