data-structures - 谷歌搜索建议实现

Question

在最近的一次亚马逊采访中，我被要求实现谷歌“建议”功能。当用户输入“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 中搜索。

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

在建议更正之前检查输入的单词 - 如果它在字典中，则什么也不提供。

更新

生成校正应该由 BFS 完成 - 当我尝试 DFS 时，像“Jeniffer”这样的条目显示“edit distance = 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 来检查字典中的单词和是单词标签检查。

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