|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Zahar Kiselev 2:5030/382.1 13 Apr 2003 18:39:54
To : Oleg Khrulev
Subject : Разбор почтового адреса.
--------------------------------------------------------------------------------
Apr 01 12:45 03, Oleg Khrulev wrote to All:
OK> Задача состоит в поиске максимального количества дублей (не
OK> обязательно всех).
OK> Вопросы:
OK> 1. Есть ли у кого-нибудь информация для решения этой задачи?
OK> 2. По каким критериям можно строить оценочную функцию для определения
OK> вероятности: являются ли две строки дублями?
Есть два способа определения похожести строк: первый носит название Алгоритм
Левенштейна и легко находится Гуглом, а название второго неизвестно и он
приведен ниже. Буду благодарен тому, кто сможет сказать как ЭТО называется в
теории. Или хотябы где такой же алгоритм можно найти в интернете.
Лично мне он достался в начале девяностых в наследство от одного спеца по
написанию русских бухгалтерских программ, давно уехавшего из этой страны.
Он говорил, что позаимствовал это из какой-то старой программы на ЕС1046, так
что лет этому способу явно немало.
----- alike.ted begins -----
{ Функция оценки похожести двух стpок.
}
Function Account(A, B: String): Real;
Var
I, J, K: Word;
Q: Longint;
C: Char;
Tmp: String;
Begin
If Length(A) < Length(B) then begin Tmp := A; A := B; B := Tmp; End;
Q := 0;
For I := 1 to Length(A) do begin
K := 0;
For J := 1 to Length(B) do
If A[J] = B[J] Then
Inc(K)
Else begin
Inc(Q, Sqr(K));
K := 0;
End;
Inc(Q, Sqr(K));
C := A[1]; Move(A[2], A[1], Length(A) - 1); A[Length(A)] := C;
End;
Account := Sqrt(Q);
End;
Var
A, B: String;
Begin
Write('Пеpвая: '); Readln(A);
Write('Втоpая: '); Readln(B);
Writeln('Оценка: ', Account(A, B):1:2);
End.
Пpимеp pаботы:
Завод "Энеpгомаш" г.Владимиp
Владимиpский завод "Энеpгомаш"
Оценка: 18.55
Завод "Энеpгомаш" г.Владимиp
Минский тpактоpный завод
Оценка: 6.24
Завод "Энеpгомаш" г.Владимиp
Акционеpное общество с огpаниченной ответственностью "Спаpтак"
Оценка: 8.77
----- alike.ted ends -----
Замечание: алгоритм работает фактически с байтовыми строками, поэтому одним моим
знакомым профессиональным программистом были обнаружены проблемы(устранимые) при
работе с русскими кодировками, где буквы расположены не в правильном
порядке(КОИ8). Отсюда же следует необходимость приводить строки к одному
регистру(например верхнему) перед сравнением.
Hу и в заключение - поделюсь своей мечтой - встроить этот алгоритм в
проигрыватель mp3 (xmms), чтобы при сортировке плэйлиста похожие названия
оказывались рядом и можно было легко искать дубли. Hо я пока не знаю, как на
основе этого алгоритма написать сортировку.
Zahar(@spbdept.rbc.ru)
--- Msged/LNX 6.1.1
* Origin: Остров Большой Березовый: http://birch-island.spb.ru (2:5030/382.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
