|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yuri Burger 2:5020/400 30 May 2003 14:40:15
To : Yuri Burger
Subject : Re: Hечеткое сравнение строк
--------------------------------------------------------------------------------
Hello, Yuri!
You wrote to Alex Astafiev on Fri, 30 May 2003 10:28:30 +0000 (UTC):
YB> while(d!=maxD&&fb!=fe&&sb!=se&&(f+std::min(fe-fb,se-sb))>best)
Да, забыл пояснить. Сравнение d!=maxD - это ограничение на величину
фиктивного разрыва, или на количество удаляемых подряд символов. По дэфолту
задается maxD=3, тоесть считается, что если одна из строк (или её часть)
сдвинута относительно другой более чам на maxD позиций, то это совершенно
другая строка и дальнейшее сравнение не имеет смысла.
Далее, условия fb!=fe и sb!=se (first begin, first end и second begin,
second end) являются ограничителями по длине строк.
Условие (f+std::min(fe-fb,se-sb))>best - это эвристика, ограничивающая
перебор. Она останавливает перебор если текущее число совпавших символов в
сумме с оставшимися позициями (допускается самый оптимистический прогноз, мол
совпадут все последующие позиции) не дает более лучшего решения, нежели
найденное ранее.
With best regards, Yuri Burger aka J.O. Kruger. E-mail: jo_kruger@mail.ru
--- ifmail v.2.15dev5
* Origin: Unknown (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
