mmotop20oo12
Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Доброго времени всем. Есть задача - реализовать алгоритм ПОХОЖЕСТИ строк методом Рабина-Карпа. Но все реализации данного алгоритма, а также его описания, сводятся к Идентичности этих самых строк. Например, вот по этой ссылке есть реализация на С++. https://mindhalls.ru/rabin-karp-search/ Собственно, а как я могу, исходя из хешей 2х строк (по алгоритму вычисляются хеши), делать вывод о похожести. Первая идея была в высчитывании интервала, между 2мя хешами, и высчитывать некоторый процент, но увы, чем длинее строка, тем больше хеш и тем меньше соотношение в разнице между 2мя полученными хешами. Т.е. хеши: 200000 и 190000 могут быть совершенно разными строками, а 50 и 45 очень похожимы, но отношение 45/50 говорит о большей "непохожести" нежели 190000/200000. Можно ли как-нибудь, используя алгоритм Рабина-Карпа, вычислять похожесть? |