|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yuri Burger 2:5020/400 28 May 2003 15:25:04
To : Sergiy Kanilo
Subject : Re: Hечеткое сравнение строк
--------------------------------------------------------------------------------
Hello, Sergiy!
You wrote to Yuri Burger on Tue, 27 May 2003 18:19:51 +0000 (UTC):
SK> безымянное namespace в данном случае практически
SK> бесполезно
В нем лежит вспомогательная тулза, видимостью готорой я не хочу вводить в
заблуждение юзера. Так что оправдано.
SK> ведущие подчеркивания в идентификаторах не
SK> рекомендуются
Открой STL, boost ;-)
SK> параметры d и maxD вполне ИМХО можно заменить одним,
Ы? maxD - это сквозной барьер, константа, задаваемая в корневом вызове
(принимать const int - изврат). d - это текущий счетчик величины разрыва
строки.
SK> хотя проверка _d в цикле и присвоение ему 0 в конце
SK> выглядит несколько подозрительно
Проверка - это барьер для рекурсии. Проверка в цикле - это конечно излишне,
достаточно былоб сделать проверку в самом начале функции, но писать
if(d==maxD){return best;} вместо дополнительной проверки в цикле - эт тож смое
что ты написал про временные s1 и s2 ;-)
А сброс в 0... Логика такая - при сравнении строк делается попытка
"раздвинуть" одну из них так, чтоб у них совпало максимум символов. Тоесть,
сделать вместо сравнения "1234" с "124" сравнение "1234" с "12_4". Размер
максимальной "дыры" - это maxD. Если же при входе в очередную рекурсию мы
сделали сравнение двух текущих символов и сдвинулись на следующие, то размер
текужей дыры сбрасывается в 0, т.к. таковая завершилась в момент сравнения
текущих символов, но при этом онаже (дыра) продолжает рости в той ветке, где
происходит повторый вход в рекурсию.
SK> в первом темплейте в типе T указатель можно угадать
SK> после третьего прочтения, (возможно подразумевались
SK> итераторы,
Они и есть. Тоесть, подходит всё, что может быть использовано в качестве
итератора (в том числе и указатель).
SK> но +1 для стандартных итераторов недопустимо)
Ды ну ;-) Допустимо для итераторов произвольного доступа - таких как у
вектора и стринга. Hо вообще, ты прав в том смысле, что сравнивать могут и
листы. Так что лучше поправить на инкремент.
SK> minmax нестандартен (стандартным есть <algorithm> )
SK> и иклудится по-видимому только для одного min и одного max,
Справедливо. Лучше заюзать std::min/max да и s1 и s2 отпадут за
ненадобностью.
SK> while(true) с последующим if()brake; и ++ для параметров в конце,
SK> вы меня извините, но в этом for() видится за версту
Hу не скажи. Часто например запрещают (на фирмах) использование for без
инициализации, типа for(;a<b;a++) изза извращенного прочтения: для /пусто/
делать a++ пока a<b
В таких случаях требуют использование while, дабы оно читалось.
SK> трижды встречающийся кусок lf=...; if(best<lf){best=lf;} так и
SK> просится в инлайновую функцию
Ты прав. Только не в инлайновыю функцию, а просто заменить на присваивание
результатом std::max. Оптимизатор должен обойти лишнее приравнивание, а код
гораздо меньше и понятней становится.
SK> введение s1 и s2 основано на предвосылке, что экономия
SK> одного такта при компиялции без оптимизации важнее, чем
Можно выкинуть и не потерять в производительности, просто нужно пользовать
min/max не из макросов.
SK> static_cast<doube> - ИМХО это не то место, где стоит
SK> его использовать
Что ты предлагаешь, сишное преобразование? Одна из причин введения кастов -
это возможность быстрого нахождения их в сырце.
SK> пустые строки не сравниваются,
Справедливо. Фиксим :)
SK> а что стоило немного расширить область параметров чтобы немного оградить
SK> пользователя
Ы? Что ты имеешь в виду?
Вот что получилось:
#ifndef __FUZZYCOMPARE_H__
#define __FUZZYCOMPARE_H__
#include <algorithm>
namespace fuzzy
{
namespace
{
template<typename T> int compare(T fb,T fe,T sb,T se,int d,int maxD,int
f,int best)
{
int of;
while(true)
{
if(d==maxD||fb==fe||sb==se||(f+std::min(fe-fb,se-sb))<=best){break;}
of=f;
if(*fb==*sb){best=std::max(best,++f);}
T t=sb;
best=std::max(best,compare(fb,fe,++t,se,d+1,maxD,of,best));
t=fb;
best=std::max(best,compare(++t,fe,sb,se,d+1,maxD,of,best));
++fb;
++sb;
d=0;
}
return best;
}
}
template<typename T> double compare(const T& first,const T& second,int
maxD=3)
{
size_t size=std::max(first.size(),second.size());
return size>0 ?
static_cast<double>(compare(first.begin(),first.end(),second.begin(),second.end
(),0,maxD,0,0))/size : 0;
}
}
#endif
With best regards, Yuri Burger aka J.O. Kruger. E-mail: jo_kruger@mail.ru
--- ifmail v.2.15dev5
* Origin: Unknown (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Hечеткое сравнение строк 