Лучший алгоритм сопоставления строк для реализации в Java?

Я хочу реализовать алгоритм на Java, чтобы найти ближайшие похожие строки.

У меня есть имена станций в базе данных mysql, например: 23 ST, 233 ST, 21 ST, 14 St Times Sq, 24 ST

и если пользователь вводит строку поиска, например 23-я станция, я должен возвращать 23 ST и 233 ST, или если пользователь вводит, например, Times Square, результат должен быть 14 Санкт-Таймс-сквер.

Я нашел много алгоритмов в Интернете, но не понимаю, какой из них использовать.

Не могли бы вы предложить мне лучший алгоритм, который я могу реализовать на Java?

заранее спасибо


java string-matching similarity
person Deepu    schedule 26.12.2012    source источник
comment
Не могли бы вы предложить мне лучший алгоритм. Я бы обычно выбрал алгоритм в горошек, так как он красивее. Конечно, ваше определение «лучше» может не включать визуальный эффект, так почему бы вам не рассказать нам, что вы подразумеваете под словом «лучше»?   -  person Andrew Thompson    schedule 26.12.2012
comment
Спасибо, Эндрю за ваш ответ, лучший алгоритм означает, что в результате будут получены наиболее похожие строки, которые пользователь хочет искать, например для 23 ST пользователь может указать такие строки поиска, как 23rd Station / 23 Station / 23rd St ect   -  person Deepu    schedule 26.12.2012
comment
en.wikipedia.org/wiki/String_searching_algorithm рассказывает о некоторых популярных алгоритмах, но вам необходимо реализовать их на Java   -  person AurA    schedule 26.12.2012
comment
Может помочь. Точно сказать не могу. stackoverflow.com/q/2891514/1135954   -  person mtk    schedule 26.12.2012
comment
Спасибо @AurA и mtk за ваши предложения   -  person Deepu    schedule 26.12.2012

Ответы (2)


arrow_upward
2
arrow_downward

Чтобы ответить на ваш вопрос, в целом не существует лучшего алгоритма, а только тот, который лучше всего работает в вашем конкретном случае.

Вам нужно будет определить одну или несколько метрик для измерения различий между вводом и строками, которые у вас есть в БД, а затем отсортировать результаты по баллам (см. Строковый показатель).

Проблема в том, что наиболее похожая строка не всегда является ближайшим адресом. Вот почему я сказал, что вы должны определить свою собственную метрику.

person Sandi Hrvić    schedule 26.12.2012
comment
Спасибо, Сэнди, я попробую. - person Deepu; 26.12.2012

arrow_upward
1
arrow_downward

Есть много способов сделать это. Например, вы можете сказать, что 21 ST ближе к 23rd station, чем 233 ST. Вы должны разработать то, что вы хотите, и найти подход, который лучше всего подходит для этого.

Вполне вероятно, что вам может понадобиться несколько подходов, а затем оценить результаты. Я бы так и поступил.

Вы можете протестировать другой подход, предоставив большой набор тестов для выборки данных и выяснив, какой из подходов (или их комбинация) дает вам самый высокий процент успеха.

person Peter Lawrey    schedule 26.12.2012
comment
Спасибо, Питер, за ваш ответ, я хочу вернуть наиболее похожие строки, которые пользователь хочет искать, например для 23 ST ** (фактическое название станции) пользователь может ввести строки поиска - ** 23-я станция / 23-я станция / 23-я улица - person Deepu; 26.12.2012
comment
Можете дать определение наиболее похожему? Хотя это то, о чем большинство людей имеет представление, для компьютера вам нужно определить это формально. - person Peter Lawrey; 26.12.2012