3

在最近的一次亚马逊采访中,我被要求实现谷歌的“建议”功能。当用户输入“Aeniffer Aninston”时,Google 会提示“您的意思是 Jeniffer Aninston”。我试图通过使用散列来解决它,但无法覆盖极端情况。请让我知道您对此的看法。

4

1 回答 1

2

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

  1. 省略的字母:“stck”而不是“stack”
  2. 一个字母错字:“styck”而不是“stack”
  3. 额外的字母:“starck”而不是“stack”
  4. 相邻字母交换:“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 回答