java auto правильное сопоставление с образцом - какой элемент больше всего похож в данном наборе?

Question

Мне было интересно, как реализовать следующую проблему: скажем, у меня есть «набор» строк, и я хочу знать, какой из них наиболее связан с данным значением.

Пример:

String value= "ABBCCE";

Набор содержит: {"JJKKLL", "ABBCC", "AAPPFFEE", "AABBCCDD", "ABBCEE", "AABBCCEE"}

Под «самым близким» я предполагаю, что может быть много вариантов (допустимыми могут быть последние 2), но, по крайней мере, мы можем игнорировать некоторые элементы (JJKKLLL).

Какой должен быть подход для решения такого рода проблемы (чтобы при минимуме такой результат, как AABBCCEE был бы приемлемым)

Любой Java-код будет оценен: -)

Answer 1

Вы можете попробовать использовать Расстояние Левенштейна между вашей «целевой» строкой (например, «ABBCCE») и каждым элементом в вашем наборе. Выберите максимальный порог, выше которого вы будете считать элементы несвязанными (в вашем примере это порог, возможно, один или два), и отклоните все в наборе, у которого расстояние Левенштейна больше, чем у целевой строки.

Пример реализации вычисления расстояния Левенштейна в Java можно найти здесь .

Answer 2

Вас может заинтересовать Метрика расстояния Левенштейна , которая измеряет сходство между двумя строками, включая вставки и удаления.