在最近的一次亚马逊采访中，我被要求实现谷歌的“建议”功能。当用户输入“Aeniffer Aninston”时，Google 会提示“您的意思是 Jeniffer Aninston”。我试图通过使用散列来解决它，但无法覆盖极端情况。请让我知道您对此的看法。
问问题
1980 次
1 回答
2
有 4 种最常见的错误类型 -
- 省略的字母：“stck”而不是“stack”
- 一个字母错字：“styck”而不是“stack”
- 额外的字母：“starck”而不是“stack”
- 相邻字母交换：“satck”而不是“stack”
顺便说一句，我们可以交换不相邻的字母，但可以交换任何字母，但这不是常见的错字。
初始状态 - 键入的单词。从初始顶点运行 BFS/DFS。搜索深度是您自己的选择。请记住，搜索深度的增加会导致“可能更正”的数量急剧增加。我认为深度〜4-5是一个好的开始。
在生成“可能的更正”后，在字典中搜索每个生成的候选词 - 在排序的字典中进行二进制搜索或在填充有您的字典的树中搜索。
Trie 更快，但二进制搜索允许在随机访问文件中搜索，而无需将字典加载到 RAM。您必须仅加载预先计算的integer数组 []。Array[i]为您提供要跳过的字节数以访问第 i 个单词。随机存取文件中的单词应按排序顺序写入。如果您有足够的 RAM 来存储字典，请使用 trie。
在建议更正之前检查键入的单词 - 如果它在字典中，则不要提供任何内容。
更新
生成更正应该由 BFS 完成 - 当我尝试 DFS 时，像“Jeniffer”这样的条目显示“编辑距离 = 3”。DFS 不起作用，因为它做了很多可以一步完成的更改 - 例如，Jniffer->nJiffer->enJiffer->eJniffer->Jeniffer而不是Jniffer->Jeniffer.
BFS 生成校正的示例代码
static class Pair
{
private String word;
private byte dist;
// dist is byte because dist<=128.
// Moreover, dist<=6 in real application
public Pair(String word,byte dist)
{
this.word = word;
this.dist = dist;
}
public String getWord()
{
return word;
}
public int getDist()
{
return dist;
}
}
public static void main(String[] args) throws Exception
{
HashSet<String> usedWords;
HashSet<String> dict;
ArrayList<String> corrections;
ArrayDeque<Pair> states;
usedWords = new HashSet<String>();
corrections = new ArrayList<String>();
dict = new HashSet<String>();
states = new ArrayDeque<Pair>();
// populate dictionary. In real usage should be populated from prepared file.
dict.add("Jeniffer");
dict.add("Jeniffert"); //depth 2 test
usedWords.add("Jniffer");
states.add(new Pair("Jniffer", (byte)0));
while(!states.isEmpty())
{
Pair head = states.pollFirst();
//System.out.println(head.getWord()+" "+head.getDist());
if(head.getDist()<=2)
{
// checking reached depth.
//4 is the first depth where we don't generate anything
// swap adjacent letters
for(int i=0;i<head.getWord().length()-1;i++)
{
// swap i-th and i+1-th letters
String newWord = head.getWord().substring(0,i)+head.getWord().charAt(i+1)+head.getWord().charAt(i)+head.getWord().substring(i+2);
// even if i==curWord.length()-2 and then i+2==curWord.length
//substring(i+2) doesn't throw exception and returns empty string
// the same for substring(0,i) when i==0
if(!usedWords.contains(newWord))
{
usedWords.add(newWord);
if(dict.contains(newWord))
{
corrections.add(newWord);
}
states.addLast(new Pair(newWord, (byte)(head.getDist()+1)));
}
}
// insert letters
for(int i=0;i<=head.getWord().length();i++)
for(char ch='a';ch<='z';ch++)
{
String newWord = head.getWord().substring(0,i)+ch+head.getWord().substring(i);
if(!usedWords.contains(newWord))
{
usedWords.add(newWord);
if(dict.contains(newWord))
{
corrections.add(newWord);
}
states.addLast(new Pair(newWord, (byte)(head.getDist()+1)));
}
}
}
}
for(String correction:corrections)
{
System.out.println("Did you mean "+correction+"?");
}
usedWords.clear();
corrections.clear();
// helper data structures must be cleared after each generateCorrections call - must be empty for the future usage.
}
字典中的单词 - Jeniffer，Jeniffer。Jeniffert 仅用于测试）
输出：
你是说珍妮弗吗？
你是说珍妮弗特吗？
重要的！
我选择生成深度 = 2。在实际应用程序中深度应该是 4-6，但是随着组合的数量呈指数增长，我不会那么深。有一些优化专门用于减少搜索树中的分支数量，但我对它们的考虑不多。我只写了主要思想。
此外，我使用 HashSet 来存储字典和标记使用过的单词。当它包含百万个对象时，HashSet 的常量似乎太大了。可能你应该使用 trie 来检查字典中的单词 和 单词标签检查。
我没有实现擦除字母和更改字母操作，因为我只想展示主要思想。
于 2013-08-14T10:37:09.927 回答