forked from Alepha/Alepha
131 lines
3.4 KiB
C++
131 lines
3.4 KiB
C++
static_assert( __cplusplus > 2020'99 );
|
|
|
|
#include "string_distance.h"
|
|
|
|
#include <cstdlib>
|
|
#include <cassert>
|
|
|
|
#include <vector>
|
|
#include <algorithm>
|
|
#include <exception>
|
|
#include <stdexcept>
|
|
|
|
namespace Alepha::Hydrogen::Algorithm ::detail:: string_distance_m
|
|
{
|
|
namespace
|
|
{
|
|
template< typename T >
|
|
class Matrix
|
|
{
|
|
private:
|
|
const std::size_t stride;
|
|
const std::size_t height;
|
|
std::vector< T > storage;
|
|
|
|
public:
|
|
explicit
|
|
Matrix( const std::size_t stride, const std::size_t height )
|
|
: stride( stride ), height( height ), storage( stride * height ) {}
|
|
|
|
struct Coordinate { std::size_t x; std::size_t y; };
|
|
|
|
private:
|
|
template< typename Self >
|
|
T &
|
|
index_impl( Self &self, const Coordinate coordinate )
|
|
{
|
|
return self.storage[ coordinate.x + coordinate.y * self.stride ];
|
|
}
|
|
|
|
template< typename Self >
|
|
T &
|
|
at_impl( Self &self, const Coordinate coordinate )
|
|
{
|
|
if( coordinate.x >= stride ) throw std::out_of_range{ "Overindexed x" };
|
|
if( coordinate.y >= height ) throw std::out_of_range{ "Overindexed y" };
|
|
return self.storage.at( coordinate.x + coordinate.y * self.stride );
|
|
}
|
|
|
|
public:
|
|
T &at( Coordinate coordinate ) { return at_impl( *this, coordinate ); }
|
|
const T &at( Coordinate coordinate ) const { return at_impl( *this, coordinate ); }
|
|
|
|
T &operator[]( Coordinate coordinate ) { return index_impl( *this, coordinate ); }
|
|
const T &operator[]( Coordinate coordinate ) const { return index_impl( *this, coordinate ); }
|
|
};
|
|
|
|
template< typename T0, typename T1 >
|
|
auto
|
|
min( T0 a, T1 b )
|
|
{
|
|
return std::min( a, b );
|
|
}
|
|
|
|
template< typename T0, typename ... T >
|
|
auto
|
|
min( T0 a, T ... t )
|
|
{
|
|
return min( a, min( t... ) );
|
|
}
|
|
}
|
|
|
|
std::size_t
|
|
exports::rewriteStringDistance( const std::string_view a, const std::string_view b )
|
|
{
|
|
Matrix< std::size_t > table( a.size() + 1, b.size() + 1 );
|
|
|
|
for( std::size_t i= 0; i < a.size(); ++i ) table.at( { i, 0 } );
|
|
for( std::size_t i= 0; i < b.size(); ++i ) table.at( { 0, i } );
|
|
|
|
for( std::size_t i= 1; i <= a.size(); ++i )
|
|
{
|
|
for( std::size_t j= 1; j <= b.size(); ++j )
|
|
{
|
|
auto &next= table.at( { i, j } );
|
|
const auto &up= table.at( { i - 1, j - 1 } );
|
|
const auto &left= table.at( { i - 1, j } );
|
|
const auto &right= table.at( { i, j - 1 } );
|
|
if( a.at( i - 1 ) == b.at( j - 1 ) ) next= up;
|
|
else next= 1 + min( up, left, right );
|
|
}
|
|
}
|
|
|
|
return table.at( { a.size(), b.size() } );
|
|
}
|
|
|
|
std::size_t
|
|
exports::optimalStringDistance( const std::string_view a, const std::string_view b )
|
|
{
|
|
Matrix< std::size_t > table( a.size() + 1, b.size() + 1 );
|
|
|
|
for( std::size_t i= 0; i < a.size(); ++i ) table.at( { i, 0 } );
|
|
for( std::size_t i= 0; i < b.size(); ++i ) table.at( { 0, i } );
|
|
|
|
for( std::size_t i= 1; i <= a.size(); ++i )
|
|
{
|
|
for( std::size_t j= 1; j <= b.size(); ++j )
|
|
{
|
|
const std::size_t cost= a.at( i - 1 ) != b.at( j - 1 );
|
|
assert( cost == 0 or cost == 1 );
|
|
|
|
auto &next= table.at( { i, j } );
|
|
const auto del= table.at( { i - 1, j } ) + 1;
|
|
const auto ins= table.at( { i, j - 1 } ) + 1;
|
|
const auto sub= table.at( { i - 1, j - 1 } ) + cost;
|
|
|
|
next= min( del, ins, sub );
|
|
|
|
if( i > 1 and j > 1
|
|
and a.at( i - 1 ) == b.at( j - 2 )
|
|
and a.at( i - 2 ) == b.at( j - 1 ) )
|
|
{
|
|
next= min( table.at( { i, j } ),
|
|
table.at( { i - 2, j - 2 } ) + cost );// transposition
|
|
}
|
|
}
|
|
}
|
|
|
|
return table.at( { a.size(), b.size() } );
|
|
}
|
|
}
|