计算两个字符串之间的编辑距离

Question

我正在执行以下 Postgres 查询。

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

我正在使用以下代码执行上述查询。

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

最通用的 levenshtein function 版本是：

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

Both source and target can be any non-null string, with a maximum of 255 characters. The cost parameters specify how much to charge for a character insertion, deletion, or substitution, respectively. You can omit the cost parameters, as in the second version of the function; in that case they all default to 1.

因此，使用默认成本参数，您得到的结果是您需要在 source 中更改（通过插入、删除或替换）字符的总数，以获得 target.

如果您需要计算百分比差异，您应该将 levenshtein 函数结果除以源文本的长度（或目标长度 - 根据您对百分比差异的定义）。

Answer 2

使用这个：

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

Levenshtein 距离是一个字符串变为另一个字符串必须更改（移动、删除或插入）多少个字母的计数。简单来说，就是不同.

的字母数量

那么相同的字母个数就是length - levenshtein.

将其表示为分数，除以长度，即(length - levenshtein) / length。

要将分数表示为 百分比，请乘以 100。

我先100执行乘法以避免整数除法截断问题。

计算两个字符串之间的编辑距离

Calculating levenshtein distance between two strings

java

postgresql

levenshtein-distance