Так получилось, что я заново изобрел это колесо много лет назад - в программе FORTRAN на мэйнфрейме:)
Когда я с гордостью рассказывал другим людям в Интернете о моем алгоритме, они смеялись и указывали мне на двоих.(четыре?) громких имени в этой области:
Это алгоритмы сравнения огромных последовательностей похожих строк.Требуемая память составляет около m + n, где m и n - размеры строк, а время выполнения - около m * n.
Gunslinger47 упоминает Левенштейна, Soundex и Metaphone.Левенштейн также является мощным средством вычисления расстояний между строками, но он лучше подходит для «нормального» текста.Soundex и Metaphone вычисляют короткую строку, предназначенную для кодирования звука строки, когда человек говорит ... они становятся неэффективными после примерно 3 слогов, они действительно предназначены для слов на человеческом языке, а не для строк геномов или тому подобного.
РЕДАКТИРОВАТЬ
Ой, я только что нашел свои 4 громких имени внизу статьи, которую вы цитировали.Итак, вы уже знаете о них.Я думаю, что если вы ищете эти имена и «Java», вы должны найти реализации. Вот первый, который я нашел .