data-structures - Google搜索建议实现

Question

在最近的一次亚马逊采访中，我被要求实现 Google“建议”功能。当用户输入“Aeniffer Aninston”时，Google 会建议“您是指 Jeniffer Aninston”吗？我尝试使用散列来解决它，但无法涵盖极端情况。请让我知道您对此的想法。

Answer 1

有 4 种最常见的错误类型 -

1. 省略字母:“stck”而不是“stack”
2. 一个字母拼写错误:“styck”而不是“stack”
3. 额外的字母:“starck”而不是“stack”
4. 相邻字母交换:“satck”而不是“stack”

顺便说一句，我们可以交换任何字母，而不是相邻字母，但这不是常见的拼写错误。

初始状态 - 键入的单词。从初始顶点运行 BFS/DFS。搜索深度是您自己的选择。请记住，搜索深度的增加会导致“可能的更正”数量急剧增加。我认为深度 ~ 4-5 是一个好的开始。

生成“可能的更正”后，在字典中搜索每个生成的候选单词 - 在排序字典中进行二分搜索，或在填充了字典的字典树中进行搜索。

Trie 更快，但二分搜索允许在随机访问文件中搜索，而无需将字典加载到 RAM。您必须仅加载预先计算的整数数组[]。 Array[i] 为您提供访问第 i 个单词时要跳过的字节数。随机访问文件中的单词应按排序顺序写入。如果您有足够的 RAM 来存储字典，请使用 trie。

在建议更正之前检查输入的单词 - 如果它在字典中，则不提供任何内容。

更新

生成更正应该由 BFS 完成 - 当我尝试 DFS 时，像“Jeniffer”这样的条目显示“编辑距离 = 3”。 DFS 不起作用，因为它做了很多可以一步完成的更改 - 例如，Jniffer->nJiffer->enJiffer->eJniffer->Jeniffer 而不是 Jniffer ->詹尼弗。

通过 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，Jeniffert。 Jeniffert仅供测试)

输出:

你是说詹妮弗吗？
您是说詹尼弗特吗？

重要!

我选择生成深度= 2。在实际应用中深度应该是4-6，但随着组合数量呈指数级增长，我不会那么深。有一些优化致力于减少搜索树中的分支数量，但我没有考虑太多。我只写了主要思想。

此外，我使用 HashSet 来存储字典并标记使用过的单词。当 HashSet 包含百万个对象时，它的常量似乎太大了。也许您应该使用 trie 来检查字典中的单词和检查单词标记。

我没有实现删除字母和更改字母操作，因为我只想展示主要思想。