Имея карту с путями, как сравнить их с данным путем?

Question

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

Например, у нас есть карта, к которой мы можем прибегнуть, если нам нужно:

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

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

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

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

Answer 1

У меня нет готового ответа на C ++, но недавно мне пришлось сделать что-то подобное в C #, и я придумал следующее:

Переберите весь вектор, проверяя интересный путь, чтобы увидеть, начинается ли он с элемента. самый длинный такой матч является победителем. Это будет операция O (n), в зависимости от количества путей в наборе сравнения.

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

Итак, я отсортировал вектор по убыванию длины пути, чтобы первое совпадение, с которым я столкнулся, также было наилучшим (я думаю, что я получил среднюю O (n / 2) операцию), и сохранил результаты в виде словарь, поэтому мне не нужно было бы перебирать поиск снова.

Надеюсь, это поможет!

Answer 2

Вы можете использовать Расстояние Левенштейна

EDIT

Так как мне наконец-то понадобилось нечто подобное, и этот вопрос остается открытым. Вот код, с которым я поиграл. Как расстояние до прямой строки, так и применение алгоритма Левенштейна к токенам пути.

C ++ Код

/*
----- String based Levenshtein ----
Matching : this/is/a/strange/path

0 : this/is/a/strange/path
2 : this/is/a/strong/path
2 : that/is/a/strange/path
4 : is/this/a/strange/path
5 : this/is/a/strange
13 : this/is/a
15 : this/is
16 : that/was
18 : this
24 : completely/different/folder

----- Path based Levenshtein ----
Matching : this/is/a/strange/path

0 : this/is/a/strange/path
1 : this/is/a/strange
2 : this/is/a/strong/path
2 : that/is/a/strange/path
2 : this/is/a
2 : is/this/a/strange/path
3 : this/is
4 : this
7 : that/was
8 : completely/different/folder
*/

#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>

/// returns the smaller of two parameters
template< typename T >
    T levmin( T v1, T v2 )
    {   return ( v1 < v2 ) ? v1 : v2; }

/// Returns the Levenshtein distance between the specified strings
template < typename T, typename T_STR > 
    typename T_STR::size_type levstr(const T_STR &s1, const T_STR &s2)
{
    typename T_STR::size_type l1 = s1.length(), l2 = s2.length();
    std::vector< typename T_STR::size_type > d( ( l1 + 1 ) * ( l2 + 1 ) );

    typename T_STR::size_type i, j;
    for ( i = 0; i <= l1; i++ )
        d[ i * l2 ] = i;

    for ( i = 0; i <= l2; i++ )
        d[ i ] = i;

    for ( i = 1; i <= l1; i++ )
        for ( j = 1; j <= l2; j++ )
            d[ i * l2 + j ] = levmin( levmin( d[ ( i - 1 ) * l2 + j ] + 1, d[ i * l2 + ( j - 1 ) ] + 1 ),
                                      d[ ( i - 1 ) * l2 + ( j - 1 ) ] + ( s1[ i - 1 ] == s2[ j - 1 ] ? 0 : 1 ) 
                                    );

    return d[ ( l1 * l2 ) + l2 ];       
}

/// Returns the Levenshtein distance between the specified split paths
template < typename T, typename T_STR, typename T_LST > 
    typename T_STR::size_type levpath(const T_LST &lst1, const T_LST &lst2)
{
    typename T_STR::size_type l1 = lst1.size(), l2 = lst2.size();
    std::vector< typename T_STR::size_type > d( ( l1 + 1 ) * ( l2 + 1 ) );

    typename T_STR::size_type i, j;
    for ( i = 0; i <= l1; i++ )
        d[ i * l2 ] = i;

    for ( i = 0; i <= l2; i++ )
        d[ i ] = i;

    for ( i = 1; i <= l1; i++ )
        for ( j = 1; j <= l2; j++ )
            d[ i * l2 + j ] = levmin( levmin( d[ ( i - 1 ) * l2 + j ] + 1, d[ i * l2 + ( j - 1 ) ] + 1 ),
                                      d[ ( i - 1 ) * l2 + ( j - 1 ) ] + levstr< T, T_STR>( lst1[ i - 1 ], lst2[ j - 1 ] )
                                    );

    return d[ ( l1 * l2 ) + l2 ];       
}

/// Generic split path function
/*
    Returns a vector of path tokens
*/
template < typename T, typename T_STR, typename T_LST >
    T_LST splitpath( const T_STR &s, const T sep )
    {   T_LST lst;
        typename T_STR::size_type i = 0, l = 0;
        while( T_STR::npos != ( i = s.find_first_of( sep, i ) ) )
        {   if ( l < i )
                lst.push_back( T_STR( s, l, i - l ) );
            l = ++i;
        } // end while
        if ( l < s.length() )
            lst.push_back( T_STR( s, l, s.length() - l ) );
        return lst;
    }

/// Generic join path function
/*
    Returns a string of joined vector tokens
*/
template < typename T, typename T_STR, typename T_LST >
    T_STR joinpath( const T_LST &p, const T sep )
    {   T_STR s;
        for ( typename T_LST::const_iterator it = p.begin(); it != p.end(); it++ )
        {   if ( s.length() ) s += sep; s += *it; }
        return s;
    }


// String types
typedef char t_levchar;
typedef std::basic_string< t_levchar > t_levstr;
typedef std::vector< t_levstr > t_levpath;
typedef std::vector< t_levpath > t_levpathlist;

// Sort compare for split paths
template< typename T, typename T_STR, typename T_LST > struct levcmp 
{   levcmp( const T_LST &p ) { m_p = p; }
    bool operator() ( const T_LST &i, const T_LST &j ) 
    { return levpath< T, T_STR, T_LST >( i, m_p ) < levpath< T, T_STR, T_LST >( j, m_p ); }
    T_LST m_p;
};

// Sort compare for strings
template< typename T, typename T_STR > struct levcmp_str 
{   levcmp_str( const T_STR &s ) { m_s = s; }
    bool operator() ( const T_STR &i, const T_STR &j ) 
    { return levstr< T, T_STR >( i, m_s ) < levstr< T, T_STR >( j, m_s ); }
    T_STR m_s;
};

int main( int argc, char* argv[] )
{
    // Path to compare with
    const t_levchar* compare_path = "this/is/a/strange/path";

    // Paths to sort
    const t_levchar* path_list[] = 
    { 
        "this/is/a/strong/path",
        "that/is/a/strange/path",
        "this/is/a/strange",
        "this/is",
        "this/is/a",
        "this",
        "this/is/a/strange/path", 
        "is/this/a/strange/path", 
        "that/was",
        "completely/different/folder",
        0
    };

    printf( "\n----- String based Levenshtein ----\n"
            "Matching : %s\n\n", compare_path );

    // Create vector from paths         
    std::vector< t_levstr > paths;
    for( int i = 0; path_list[ i ]; i++ ) 
        paths.push_back( path_list[ i ] );

    // Sort the paths
    std::sort( paths.begin(), paths.end(), levcmp_str< t_levchar, t_levstr >( compare_path ) );

    // Show the result
    for ( std::vector< t_levstr >::iterator it = paths.begin(); it != paths.end(); it++ )
        printf( "%d : %s\n", 
                (int)levstr< t_levchar, t_levstr >( *it, compare_path ),
                (const char*)it->c_str() );

    printf( "\n----- Path based Levenshtein ----\n"
            "Matching : %s\n\n", compare_path );

    // Create vector from split paths
    t_levpath splitcompare = splitpath< t_levchar, t_levstr, t_levpath >( compare_path, '/' );
    t_levpathlist splitpaths;
    for ( int i = 0; path_list[ i ]; i++ ) 
        splitpaths.push_back( splitpath< t_levchar, t_levstr, t_levpath >( path_list[ i ], '/' ) );

    // Sort the paths
    std::sort( splitpaths.begin(), splitpaths.end(),
                levcmp< t_levchar, t_levstr, t_levpath >( splitcompare ) );

    // Show the results
    for ( t_levpathlist::iterator it = splitpaths.begin(); it != splitpaths.end(); it++ )
        printf( "%d : %s\n", 
                (int)levpath< t_levchar, t_levstr, t_levpath >( *it, splitcompare ),
                (const char*)joinpath< t_levchar, t_levstr, t_levpath >( *it, '/' ).c_str() );

    return 0;
}

Answer 3

//I don't know what path is, I'll pretend it's a std::string
//algorithm is the same, just functions change
const std::vector<boost::path>& services;
const std::string& findme = ???

std::vector<boost::path>::iterator result = services.end();
for(auto i = services.begin(); i != services.end(); ++i) {
     //if this path is shorter than the best so far, skip it
     if (result == services.end() || i->second.size()>result->second.size()) {
         const size_t colonpos = i->second.find(':', 8); //find colon
         //if this path is longer than findme, skip it
         if (findme.size() >= i->second.size()-colonpos) {
             //make sure they match, in _reverse_ order (faster in this case)
             int o=i->second.size()-1;
             for( ; o>=colonpos; --o) {
                 if (i->second[o] != findme[o-colonpos])
                     break;
             }
             //if it was a match, this is the new best result
             if (o < colonpos)
                 result = i;
         }
     }
}

//either result is services.end() meaning none matched
//or result is the _longest_ path that matched

Очевидно, boost::path не является std::string, но, вероятно, имеет член, чтобы получить std::string или подобный объект, так что вам просто нужно добавить этот член в i->second и result->second