Алгоритм сравнения строк
Функция нечёткого сравнения
использует в качестве аргументов две строки и параметр сравнения -
максимальную длину сравниваемых подстрок. Результатом работы функции
является число, лежащее в пределах от 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 |
Приведённая таблица иллюстрирует алгоритм подсчёта коэффициента схожести двух строк. Для строк "test" и "text" и длины
|
