Как сравнить почти похожие строки в Java? (Мерная длина строки)

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

Я не знаком с существующими методами в Java, но для PHP я знаю функцию levenshtein.

Есть ли лучшие методы в Java?

Ответ 1

Расстояние Левенштейна - это мера того, как подобны строки. Или, точнее, сколько изменений необходимо сделать, чтобы они были одинаковыми.

Алгоритм доступен в псевдокоде в Википедии. Преобразование этого в Java не должно быть большой проблемой, но оно не встроено в библиотеку базового класса.

Wikipedia содержит еще несколько алгоритмов, которые измеряют сходство строк.

Ответ 2

Следующие библиотеки Java предлагают несколько алгоритмов сравнения (Levenshtein, Jaro Winkler,...):

Apache Commons Lang 3: https://commons.apache.org/proper/commons-lang/
Симметрия: http://sourceforge.net/projects/simmetrics/

Обе библиотеки имеют java-документацию (Apache Commons Lang Javadoc, Симметрия Javadoc).

//Usage of Apache Commons Lang 3
import org.apache.commons.lang3.StringUtils;   
public double compareStrings(String stringA, String stringB) {
    return StringUtils.getJaroWinklerDistance(stringA, stringB);
}

 //Usage of Simmetrics
import uk.ac.shef.wit.simmetrics.similaritymetrics.JaroWinkler    
public double compareStrings(String stringA, String stringB) {
    JaroWinkler algorithm = new JaroWinkler();
    return algorithm.getSimilarity(stringA, stringB);
}

Ответ 3

Да, это хорошая метрика, вы можете использовать StringUtil.getLevenshteinDistance() из apache commons

Ответ 4

Я нашел алгоритм Левенштейна на эту страницу.

Ответ 5

Вы можете найти реализации Левенштейна и других методов сходства/расстояния строки на https://github.com/tdebatty/java-string-similarity

Если ваш проект использует maven, установка выполняется так же просто, как

<dependency>
  <groupId>info.debatty</groupId>
  <artifactId>java-string-similarity</artifactId>
  <version>RELEASE</version>
</dependency>

Затем, например, использовать Левенштейна

import info.debatty.java.stringsimilarity.*;

public class MyApp {

  public static void main (String[] args) {
    Levenshtein l = new Levenshtein();

    System.out.println(l.distance("My string", "My $tring"));
    System.out.println(l.distance("My string", "My $tring"));
    System.out.println(l.distance("My string", "My $tring"));
  }
}

Ответ 6

Бесстыдный плагин, но я написал также библиотеку:

https://github.com/vickumar1981/stringdistance

У этого есть все эти функции, плюс несколько для фонетического сходства (если одно слово "звучит как" другое слово "- возвращает либо true, либо false, в отличие от других нечетких сходств, которые являются числами между 0-1).

Также включает алгоритмы секвенирования ДНК, такие как Smith-Waterman и Needleman-Wunsch, которые являются обобщенными версиями Левенштейна.

Я планирую в ближайшем будущем сделать эту работу с любым массивом, а не только с строками (массив символов).