0

我想检查数据库值和用户输入之间的单词顺序。

前任：

示例一：

DB 值：Lorem Ipsum

用户输入：Ipsum Lorem

示例 2：

DB 值：Lorem Ipsum Dolo

用户输入：Dolo Lorem Ipsum（以及除了确切的 db 值之外的可能组合）

我会在空格上进行拆分并比较匹配单词的索引，但总是有拼写错误的机会。前任：

DB 值：Lorem Ipsum

用户输入：Lorm Ipsm

在我的应用程序中，我必须允许一些拼写错误。有没有办法以任何其他方式检查订单？

我目前正在通过以下方式使用 Levenshtein（Ruby on Rails 代码）

answer = 'Lorem Ipsum'

response = 'Ipsum Lorem'

score = Text::Levenshtein.distance(answer,response)/answer.length.to_f

这是使用 levenshtein 得分的正确方法吗？如果是，我如何确定可接受的分数？有相同的示例数据资源吗？对于上面这个特定的例子，我得到的分数是0.72

4

2 回答 2

0

我认为这可以通过将用户输入和数据库记录拆分为单词数组来解决，然后计算每对单词的 levenshtein 距离。然后你需要计算出哪一组配对使分数最小化。

然后，用户输入中的每组单词都将与 db 记录中的一个单词匹配，因此您可以根据它们是否位于相同位置来计算分数

于 2013-10-11T13:24:50.827 回答
0

所以你有2个问题需要解决：

  1. 检查单词的排列
  2. 为拼写错误增加回旋余地

两者都可以通过使用 Levenshtein 距离算法来解决，但有一个转折：

  1. 您正在查看模糊搜索或近似字符串匹配。那里有很多算法，但在我看来，Damerau-Levenshtein Distance Algorithm或Bitap Algorithm。它们都基于 Levenshtein。您可以为您的应用程序搜索更好的算法。
  2. 拼写错误——Levenshtein distance 可能更容易实现和使用；并且可能也很有效。

高温高压

编辑：我要解决的第一件事是Levenshtein distance在单个单词上实现。因为，我们并不真正了解您在这里所说的 DB 是什么意思（可能是包含您的句子的简单文本文件或实际的 DBMS MySQL），假设它是一个 DBMS，我将创建一个包含所有句子中出现的所有单词的字典。接下来我将编写一个Stored Procedure实现Levenshtein distance. 传递测试语句的单词数组并将存储过程应用于所有单词。然后用最对齐单词的 ID 替换 DB 句子中的单词以及您的测试句子。

例如，在 DB 中，您有一个句子“Lorem Ipsum”，并保留一个单词表，我们将有一个名为“words”的表，其中包含 2 条记录：

|---------------------|
| id | words          |
|---------------------|
|  1 | Lorem          |
|  2 | Ipsum          |
|---------------------|

创建一个Stored Procedure实现Levenshtein Distance并传递测试语句数组（用户输入） say [Ipsum, Lorem]。

对于用户输入的每个单词，您至少会得到一个对齐的单词。id用表中的连续替换它们words。在我们的示例中，返回数组可能看起来像[2,1].

这解决了拼写错误的第二个问题。

id对于模糊搜索，从 DB 中获取一条记录（句子），用from table替换单词words（您已经有一个从先前存储过程返回的 id 数组）并应用任何算法，如Damerau-Levenshtein Distance Algorithm, Bitap Algorithm, Smith-Waterman Algorithm, Needleman-Wunsch Algorithm。实际上，我建议您实施其中的 2-3 个，并比较哪种方法更适合您的情况。

高温高压

于 2013-10-11T13:15:04.663 回答