模糊字符串记录搜索算法(支持单词转置和字符转置)

Question

我正在努力为我的特定应用程序找到最佳算法。我在SO、谷歌上搜索过，读过各种关于Levenstein距离的文章，等等，但老实说，这有点超出了我的专业范围。大多数人似乎发现两个输入字符串有多相似，比如字符串之间的汉明距离。

我正在寻找的是不同的，更多的是模糊记录搜索(我相信它有一个名字，我不知道谷歌)。我相信以前有人解决过这个问题，我正在寻找一个建议，为我的进一步研究指明正确的方向。

在我的情况下，我需要对音乐艺术家及其专辑的条目数据库进行模糊搜索。正如你所能想象的，数据库将有数百万个条目，因此一个规模良好的算法至关重要。对于我的问题来说，Artist和Album在不同的列中并不重要，如果有助于搜索的话，数据库可以将所有单词存储在一列中。

要搜索的数据库：

|-------------------|---------------------|
| Artist            | Album               |
|-------------------|---------------------|
| Alanis Morissette | Jagged Little Pill  |
| Moby              | Everything is Wrong |
| Air               | Moon Safari         |
| Pearl Jam         | Ten                 |
| Nirvana           | Nevermind           |
| Radiohead         | OK Computer         |
| Beck              | Odelay              |
|-------------------|---------------------|

查询文本将包含从整个Artist_Album串联中的一个单词到整个单词。查询文本来自OCR，可能有单个字符的换位，但最有可能的是单词不能保证有正确的顺序。此外，搜索中可能有多余的单词不属于专辑的一部分(比如封面艺术文本)。例如，"OK Computer"可能在专辑的顶部，"Radiohead"可能在其下方，或者一些专辑的文本排列在列中，将单词顺序混合在一起。

可能的搜索字符串：

C0mputer Rad1ohead
Pearl Ten Jan
Alanis Jagged Morisse11e Litt1e Pi11
Air Moon Virgin Records
Moby Everything

请注意，使用OCR，有些字母看起来像数字，或者完全是错误的字母(Jan而不是Jam)。在Radiohead的OK Computer和Moby的Everything Is Wrong的情况下，查询文本甚至没有所有的单词。在Air的Moon Safari中，会搜索额外的单词Virgin Records，但Safari不见了。

有没有一种通用算法可以从数据库中返回最有可能的结果，如果没有一个满足某个"可能性"分数阈值，它就什么都不返回？事实上，我正在Python中开发这个，但这只是一个额外的收获，我正在寻找更多的开始研究的地方。

Answer 1

让我们将问题分解为两部分。

• 首先，您想要定义一些相似性的度量(这被称为度量)。如果查询文本与专辑/艺术家封面非常匹配，则此指标应返回一个较小的数字，否则返回一个较大的数字
• 其次，您需要一个能够加快此过程的数据结构。显然，您不希望每次运行查询时都计算这个度量

第1部分：度量

你已经提到了Levenstein距离，这是一个很好的起点。不过要跳出框框思考。

LD做出某些假设(每个字符替换的可能性相等，删除的可能性与插入的可能性相等等)。通过考虑OCR可能引入的故障，显然可以提高此度量的性能。

例如，把"1"变成"i"不应该像把"0"变成"_"那样受到严厉的惩罚。

我将分两个阶段实施度量。对于任何给定的两个字符串：

• 在标记中拆分两个字符串(假定空格为分隔符)
• 查找最相似的单词(使用LD的修改版本)
• 根据"匹配单词"、"缺失单词"one_answers"添加单词"(最好加权)分配最终分数

这是一个示例实现(摆弄常量)：

static double m(String a, String b){
String[] aParts = a.split(" ");
String[] bParts = b.split(" ");
boolean[] bUsed = new boolean[bParts.length];
int matchedTokens = 0;
int tokensInANotInB = 0;
int tokensInBNotInA = 0;
for(int i=0;i<aParts.length;i++){
String a0 = aParts[i];
boolean wasMatched = true;
for(int j=0;j<bParts.length;j++){
String b0 = bParts[j];
double d = levenshtein(a0, b0);
/* If we match the token a0 with a token from b0
* update the number of matchedTokens
* escape the loop
*/
if(d < 2){
bUsed[j]=true;
wasMatched = true;
matchedTokens++;
break;
}
}
if(!wasMatched){
tokensInANotInB++;
}
}
for(boolean partUsed : bUsed){
if(!partUsed){
tokensInBNotInA++;
}
}
return (matchedTokens 
+ tokensInANotInB * -0.3  // the query is allowed to contain extra words at minimal cost
+ tokensInBNotInA * -0.5  // the album title should not contain too many extra words
) / java.lang.Math.max(aParts.length, bParts.length); 
}

此函数使用了一个修改后的Levenstein函数：

static double levenshtein(String x, String y) {
double[][] dp = new double[x.length() + 1][y.length() + 1];
for (int i = 0; i <= x.length(); i++) {
for (int j = 0; j <= y.length(); j++) {
if (i == 0) {
dp[i][j] = j;
}
else if (j == 0) {
dp[i][j] = i;
}
else {
dp[i][j] = min(dp[i - 1][j - 1] 
+ costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)), 
dp[i - 1][j] + 1, 
dp[i][j - 1] + 1);
}
}
}
return dp[x.length()][y.length()];
}

使用"替代成本"函数(如所述)

static double costOfSubstitution(char a, char b){
if(a == b)
return 0.0;
else{
// 1 and i
if(a == '1' && b == 'i')
return 0.5;
if(a == 'i' && b == '1')
return 0.5;
// 0 and O
if(a == '0' && b == 'o')
return 0.5;
if(a == 'o' && b == '0')
return 0.5;
if(a == '0' && b == 'O')
return 0.5;
if(a == 'O' && b == '0')
return 0.5;
// default
return 1.0; 
}
}

我只包括了几个例子(将"1"变成"I"或将"0"变成"o")。但我相信你会明白的。

第2部分：数据结构

看看BK树。它们是保存度量信息的特定数据结构。你的度量需要是一个真正的度量(从数学的意义上来说)。但这很容易安排。