Приблизительная библиотека регулярных выражений для Java?

Так получилось, что я изобрел это колесо много лет назад - в программе на FORTRAN на мэйнфрейме :)

Когда я с гордостью рассказывал о своем алгоритме другим людям в Интернете, они смеялись и указывали мне на два (четыре?) больших имени в этой области:

• Needleman-Wunsch и
• Smith-Waterman.

Это алгоритмы для сравнения огромных последовательностей похожих строк. Требуется память около m + n, где m и n - размеры строк, а время работы - около m * n.

Gunslinger47 упоминает Levenshtein, Soundex и Metaphone. Левенштейн также является мощным средством вычисления расстояний между строками, но он лучше подходит для "нормального" текста. Soundex и Metaphone вычисляют короткую строку, предназначенную для кодирования звука строки при произнесении человеком... они становятся неэффективными примерно после 3 слогов, они действительно предназначены для слов в человеческом языке, а не для строк геномов или тому подобного.

EDIT

Упс, я только что нашел свои 4 громких имени внизу статьи, которую вы цитировали. Так что вы уже знаете о них. Я думаю, что если вы проведете поиск по этим именам и "Java", вы должны найти их реализации. Вот первое, что я нашел.