Алгоритм сравнения строк Функция нечёткого сравнения использует в качестве аргументов две строки и параметр сравнения - максимальную длину сравниваемых подстрок. Результатом работы функции является число, лежащее в пределах от 0 до 1. 0 соответствует полному несовпадению двух строк, а 1 - полной (в определённом ниже смысле) их идентичности. Сравнение строк происходит по следующей схеме. Пусть, например, в качестве аргументов заданы две строки "test" и "text" и некоторая максимальная длина подстрок, скажем, 4. Функция сравнения составляет все возможные комбинации подстрок с длинной вплоть до указанной и подсчитывает их совпадения в двух сравниваемых строках. Количество совпадений, разделённое на число вариантов, объявляется коэффициентом схожести строк и выдаётся в качестве результата работы функции.
Продолжим пример.
Сравниваемая подстрока
Подстроки второй строки
Есть совпадение?
Количество совпадений
Количество вариантов
Сравниваем строку test со строкой text по подстрокам длины 1.
t
t, e, x, t
да
3
4
e
t, e, x, t
да
s
t, e, x, t
нет
t
t, e, x, t
да
Сравниваем строку text со строкой test по подстрокам длины 1.
t
t, e, s, t
да
3
4
e
t, e, s, t
да
x
t, e, s, t
нет
t
t, e, s, t
да
Сравниваем строку test со строкой text по подстрокам длины 2.
te
te, ex, xt
да
1
3
es
te, ex, xt
нет
st
te, ex, xt
нет
Сравниваем строку text со строкой test по подстрокам длины 2.
te
te, es, st
да
1
3
ex
te, es, st
нет
xt
te, es, st
нет
Сравниваем строку test со строкой text по подстрокам длины 3.
tes
tex, ext
нет
0
2
est
tex, ext
нет
Сравниваем строку text со строкой test по подстрокам длины 3.
tex
tes, est
нет
0
2
ext
tes, est
нет
Сравниваем строку test со строкой text по подстрокам длины 4.
test
text
нет
0
1
Сравниваем строку text со строкой test по подстрокам длины 4.
text
test
нет
0
1
Итого
8
20
|
