|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yuri Burger 2:5020/400 30 May 2003 14:28:30
To : Alex Astafiev
Subject : Re: Hечеткое сравнение строк
--------------------------------------------------------------------------------
Hello, Alex!
You wrote to Yuri Burger on Wed, 28 May 2003 17:42:21 +0400:
AA> но было неплохо сделать
AA> 1) Пояснение алгоритма (ибо эха не C.SOURCES, а RU.ALGORITHMS)
AA> 2) Комментарии
AA> 3) Хотя бы описание вх/вых параметров или осмысленые имена оных.
Поясняю алгоритм.
Цель: дать оценку "похожести" двух строк [0,1]. Предполагается что одна из
строк является "вариантом" другой, где пропущены/добавлены/исправлены некоторые
символы. Hапрмер, алгоритм должен дать возможность выявить сходство между
такими строками:
123456789 и 4567
123456789 и 123789
123456789 и 123*45**789
...
Решение: пусть I{}, J{} есть множества операций удаления символа в
произвольной позиции первой (для I) и второй (для J) строки соответственно.
Тогда, найдем такие множества I, J что посимвольное сравнение строк, полученных
после применения всех операций из I, J, даст максимальное совпадение. В случае
приведенных выше примеров, результатами применения операций из найденных
множеств должны стать строки:
123456789 и 4567 -> 456789 и 4567 (удалили 1,2,3)
123456789 и 123789 -> 123789 и 123789 (удалили 4,5,6)
123456789 и 123*45**789 -> 12345789 и 12345789 (удалили 5,6, и все
*)
В двух словах - происходит поиск максимального перекрытия двух строк путем
сжатия онных (если кому понятней, то можно использовать метафору растяжения,
тоесть добавления фиктивных элементов).
Параллельное изменение обоих строк дает симметричность алгоритма, тоесть
сравнение первой строки со второй и второй с первой даст одинаковый результат.
Далее, остается лишь подсчитать число совпадающих позиций и разделить его
на длину максимальной строки из исходных двух.
Очевидно, что алгоритм должен быть рекурсивным.
Процедура при этом распадается на 3 ветви: последовательное сравнение,
сравнение с предварительным удалением в первой строке, сравнение с
предварительным удалением во второй строке. Реализуется это так:
процедура
удаляем текущую позицию в копии первой
строки и входим в рекурсию с новой
первой и старой второй строками
удаляем текущую позицию в копии второй
строки и входим в рекурсию со старой
первой и новой второй строкой
сравниваем текущие позиции в старых строках
и перемещаемся на новую позицию (цикл)
В C++ моими и Sergiy Kanilo стараниями :) это выглядит так (последний
вариант):
#ifndef __FUZZYCOMPARE_H__
#define __FUZZYCOMPARE_H__
#include <algorithm>
namespace fuzzy
{
template<typename T> int compare(T fb,T fe,T sb,T se,int d,int maxD,int
f,int best)
{
while(d!=maxD&&fb!=fe&&sb!=se&&(f+std::min(fe-fb,se-sb))>best)
{
int of=f;
if(*fb==*sb){best=std::max(best,++f);}
T t=sb;
best=compare(fb,fe,++t,se,d+1,maxD,of,best);
t=fb;
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 ?
compare(first.begin(),first.end(),second.begin(),second.end(),0,maxD,0,0)*1.0/s
ize : 0;
}
}
#endif
А используется так:
std::string s1;
std::string s2;
s1="";
s2="";
std::cout<<s1<<" = "<<s2<<" : "<<fuzzy::compare(s1,s2)<<std::endl;
s1="йцукен";
s2="йцукен";
std::cout<<s1<<" = "<<s2<<" : "<<fuzzy::compare(s1,s2)<<std::endl;
std::cout<<s2<<" = "<<s1<<" : "<<fuzzy::compare(s2,s1)<<std::endl;
s1="цукен";
s2="йцукен";
std::cout<<s1<<" = "<<s2<<" : "<<fuzzy::compare(s1,s2)<<std::endl;
std::cout<<s2<<" = "<<s1<<" : "<<fuzzy::compare(s2,s1)<<std::endl;
With best regards, Yuri Burger aka J.O. Kruger. E-mail: jo_kruger@mail.ru
--- ifmail v.2.15dev5
* Origin: Unknown (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
