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

Я только что написал код для приблизительного сопоставления строк. Я хотел бы сравнить свой наивный алгоритм с более зрелой реализацией, работающей на JVM. Какие-либо предложения?


java regex approximate
person Gabriel Mitchell    schedule 17.07.2010    source источник
comment
Это приблизительный технический термин, о котором я никогда не слышал, или ваш код примерно верен?   -  person Carl Smotricz    schedule 18.07.2010
comment
Если это для биоинформатики, вы изобретаете несколько сложных колес.   -  person msw    schedule 18.07.2010
comment
@Carl Smotricz Под приблизительным значением я хочу сказать, что две строки приблизительно совпадают, если они находятся в пределах определенного расстояния редактирования друг от друга. См., Например, en.wikipedia.org/wiki/Approximate_string_matching.   -  person Gabriel Mitchell    schedule 18.07.2010
comment
@ msw - Да, я пытаюсь узнать кое-что о выравнивании биологической последовательности, решая некоторые канонические (и забавные) проблемы. Я не думаю, что мой хак будет конкурировать с современными программами выравнивания. Однако мне любопытно посмотреть, насколько сильно это не удается. В любом случае, если вы знаете хорошую библиотеку Java, я хотел бы о ней услышать.   -  person Gabriel Mitchell    schedule 18.07.2010
comment
Для меня это был познавательный опыт, спасибо! Я постарался включить в свой ответ хоть немного полезной информации.   -  person Carl Smotricz    schedule 18.07.2010

Ответы (2)


arrow_upward
2
arrow_downward

Я нашел эти ответы в другом месте на этом сайте для аналогичных проблем.

В Commons Lang есть реализация расстояния Левенштейна.
http://commons.apache.org/lang/api-release/org/apache/commons/lang/StringUtils.html

В кодеке Commons есть реализация soundex и метафона.
http://commons.apache.org/codec/api-release/org/apache/commons/codec/language/Soundex.html
http://commons.apache.org/codec/api-release/org/apache/commons/codec/language/Metaphone.html

(источник)

Lucene (http://lucene.apache.org/) также реализует расстояние редактирования Левенштейна.

(исходный код: zarawesome)

person Gunslinger47    schedule 17.07.2010
comment
Спасибо, Стрелок. Расстояние Левенштейна от StringUtils будет полезно для прямого сравнения производительности. - person Gabriel Mitchell; 18.07.2010

arrow_upward
0
arrow_downward

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

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

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

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

ИЗМЕНИТЬ

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

person Carl Smotricz    schedule 17.07.2010