Расчет расстояния levenshtein между двумя строками

Question

Выполнение следующего запроса Postgres.

SELECT * FROM description WHERE levenshtein(desci, 'Description text?') <= 6 LIMIT 10; 

Im, используя следующий код, выполните вышеуказанный запрос.

public static boolean authQuestion(String question) throws SQLException{ 
    boolean isDescAvailable = false; 
    Connection connection = null; 
    try { 
     connection = DbRes.getConnection(); 
     String query = "SELECT * FROM description WHERE levenshtein(desci, ?) <= 6"; 
     PreparedStatement checkStmt = dbCon.prepareStatement(query); 
     checkStmt.setString(1, question); 
     ResultSet rs = checkStmt.executeQuery(); 
     while (rs.next()) {  
      isDescAvailable = true; 
     } 
    } catch (URISyntaxException e1) { 
     e1.printStackTrace(); 
    } catch (SQLException sqle) { 
     sqle.printStackTrace(); 
    } catch (Exception e) { 
     if (connection != null) 
      connection.close(); 
    } finally { 
     if (connection != null) 
      connection.close(); 
    } 
    return isDescAvailable; 
} 

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

Answer 1

Используйте это:

SELECT * 
FROM description 
WHERE 100 * (length(desci) - levenshtein(desci, ?)) 
     /length(desci) > 60 

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

Число букв, которые являются одинаковыми, то length - levenshtein.

Чтобы выразить это как , разделите его на длину, т.е. (length - levenshtein)/length.

Чтобы выразить фракцию как процент, умножьте на 100.

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

Answer 2

Наиболее общий вариант levenshtein function является:

levenshtein(text source, text target, int ins_cost, int del_cost, int sub_cost) returns int 

Оба источника и цели могут быть любой непустой строкой, с максимумом 255 символов. В параметрах стоимости указывается, сколько нужно взимать за вставку, удаление или замену символов соответственно. Вы можете опустить параметры стоимости, как во второй версии функции; в этом случае все они по умолчанию 1.

Так, с параметрами по умолчанию стоимости, в результате вы получите общее число символов, которое необходимо изменить (путем вставки, удаления или замены) в source для получения target.

Если вам нужно рассчитать процентную разницу, вы должны разделить результат функции levenshtein на длину вашего исходного текста (или целевую длину - в соответствии с вашим определением процентной разницы).