使用编辑距离和Trie自动修正拼写

介绍

我们熟悉拼写检查器。对于大多数拼写检查器，如果在一长串称为字典的有效单词中找到候选单词，则该单词被认为拼写正确。Google提供了更强大的拼写校正器，用于验证我们在输入文本框中键入的关键字。它检查字典。如果在词典中找不到关键字，则建议最有可能的替代方法。为此，它与字典中的每个单词关联一个频率，即该单词在大型文档中出现的次数。当单词拼写错误（即在词典中找不到）时，Google会建议一个“相似”单词，其频率大于或等于任何其他“相似”单词。在本文中，我将介绍如何实现拼写自动更正的方法。这包括

Trie
Edit distance
Nested HashMap

特里（数据结构）

对于此程序，我们需要类似于Google的字典。我们的字典是使用大型文本文件生成的。文本文件包含大量未排序的单词。每次我们的程序运行时，它将从该文本文件创建字典。词典将包含文本文件中的每个单词以及该单词的频率。

我们将使用Tire创建字典。Trie是一种基于树的数据结构，旨在存储作为字母字符序列的项目。每个Trie节点存储一个计数和一系列节点，每个字母和字母表中的每个元素。每个Trie节点都有一个父节点，但Trie的根节点没有父节点。字母中的字符序列存储在Trie中，作为Trie中从序列根部到最后一个字符的路径。

这是我们定义TrieNode的方法。它类似于TreeNode。但是有一些区别：（1）它具有一个节点数组，类似于TreeNode的子节点。数组长度为26，即字母中的字母数；（2）具有可变的计数来存储单词的频率；（3）布尔变量isEnd用于指示节点是否为单词的结尾。

class TrieNode  {

    TrieNode[] nodes = new TrieNode[26];
    int count;
    boolean isEnd;

    public int getValue() {     
        return count;
    }

    public void incrementValue() {
        count++;    
    }
}

在每个节点根的节点的数组表示存储在Trie树的单词的第一个字母。这些节点中的每个节点都有一个单词第二个字母的节点数组，依此类推。例如，单词“ kick”将存储如下：

root.nodes[‘k’].nodes[‘i’].nodes[‘c’].nodes[‘k’]

节点中的计数表示从根到该节点的路径表示的单词出现在从中创建字典的文本文件中的次数。因此，如果单词“ kick”出现两次，则root.nodes[‘k’].nodes[‘i’].nodes[‘c’].nodes[‘k’].count = 2。

如果单词“ kicks”在文本文件中至少出现一次，则它将被存储为 root .nodes ['k']。nodes ['i']。nodes ['c']。nodes ['k']。 node ['s']和 root.nodes ['k']。nodes ['i']。nodes ['c']。nodes ['k']。nodes ['s']。count大于或等于一。如果任何节点的计数值n为零，则从根到n 的路径表示的单词不会出现在原始文本文件中。例如，如果root .nodes ['k']。nodes ['i']。count = 0，则单词“ ki”不会出现在原始文本文件中。一个节点即使其计数为零，也可能具有后代节点。使用上面的示例，代表“踢”和“踢”的某些节点的计数为0（例如，root .nodes[‘k’], root .nodes[‘k’].nodes[‘i’], and root .nodes[‘k’].nodes[‘i’].nodes[‘c’]) but root .nodes[‘k’].node[‘i’].nodes[‘c’].nodes[‘k’] and root .nodes[‘k’].node[‘i’].nodes[‘c’].nodes[‘k’].nodes[‘s’] would have counts greater than 0.。

使用上面的示例，在Trie中只有“ kick”和“ kicks”时，它将有2个单词和6个节点（root，k，i，c，k，s）。如果我们要添加“踢球者”，则Trie将具有3个单词和8个节点。如果我们将“apple”一词添加到同一个Trie中，它将有4个单词和13个节点。添加单词“ ape”将得到5个单词和14个节点。添加“砖”将导致6个单词和19个节点。

Trie trie = new Trie();     
trie.add("kick");
trie.add("kicks");
trie.add("kicker");
trie.add("apple");
trie.add("ape");
trie.add("brick");
System.out.println("word count:"+trie.getWordCount()); //return 9
System.out.println("node count:"+trie.getNodeCount()); //return 16

编辑距离

什么是编辑距离？编辑距离是将一个字符串转换为另一个字符串所需的最小操作数。

编辑距离的不同定义使用不同的字符串操作集。Levenshtein距离运算（在Wiki中）是删除，插入或替换字符串中的字符。有时，Levenshtein距离一词经常与编辑距离互换使用。

在这里，我们使用4种操作来测量编辑距离。它们是删除距离，转座距离，改变距离和插入距离。以下是详细信息和示例。

四个编辑距离：

删除距离：当且仅当t 等于s 且删除一个字符时，字符串s与另一字符串t 的删除距离为1 。与“ bird”的删除距离为1的唯一字符串是“ ird”，“ brd”，“ bid”和“ bir”。请注意，如果字符串s 与另一个字符串t 的删除距离为1，则| s | = | t | -1。另外，还有| t | 与t的删除距离为1的字符串。字典可能包含0到n个从t开始有一个删除距离的字符串。换位距离：当且仅当t 等于s 且两个相邻字符换位时，字符串s与另一个字符串t 的换位距离为1 。与“ house”的移调距离为1的唯一字符串是“ ohuse”，“ huose”，“ hosue”和“ houes”。请注意，如果字符串s 与另一个字符串t 的转置距离为1，则| s | = | t |。另外，还有| t | — 1个与t的换位距离为1的字符串。字典中可能包含0到n个与t换位距离为n 的字符串。
更改距离：当且仅当t 等于s且字符串s 中恰好一个字符被不等于原始字母的小写字母替换时，字符串s与另一字符串t 的更改距离为1 。与“顶部”的交替距离为1的唯一字符串是“ aop”，“ bop”，…，“ zop”，“ tap”，“ tbp”，…，“ tzp”，“ toa”，“ tob” ，……和“ toz”。请注意，如果字符串s 与另一个字符串t的距离为1，则| s | = | t |。另外，正好有25 * | t | 相距t的距离为1的字符串。字典可能包含0到n 个字符串，距离一个改变距离Ť。
插入距离：当且仅当t 与s的删除距离为1时，字符串s与另一字符串t 的插入距离为1 。距“ ask”的插入距离为1的唯一字符串是“ aask”，“ bask”，“ cask”，……“ zask”，“ aask”，“ absk”，“ acsk”，……“ azsk”，“ asak”，“ asbk”，“ asck”，……“ aszk”，“ aska”，“ askb”，“ askc”，……“ askz”。请注意，如果字符串s 与另一个字符串t 的插入距离为1，则| s | = | t | +1。而且，正好有26 *（| t | + 1）个字符串，它们与t的插入距离为1 。字典可能包含0到n 个字符串，距t的插入距离为一。根据Levenshtein距离，有两种查找编辑距离的方法：递归和动态编程。在这里，我们应用动态编程。请注意，我们有4种操作，因此算法与Wiki略有不同。

//Time O(n*m), Space O(n*m), n is word1 length, m is word2 length
private int editDistance(String word1, String word2) {
    int n = word1.length();
    int m = word2.length();
    int dp[][] = new int[n+1][m+1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0)
                dp[i][j] = j;      
            else if (j == 0)
                dp[i][j] = i; 
            else if (word1.charAt(i-1) == word2.charAt(j-1))
                dp[i][j] = dp[i-1][j-1];                
            else if (i>1 && j>1  && word1.charAt(i-1) == word2.charAt(j-2) 
                    && word1.charAt(i-2) == word2.charAt(j-1))
                dp[i][j] = 1 + Math.min(Math.min(dp[i-2][j-2], dp[i-1][j]), Math.min(dp[i][j-1], dp[i-1][j-1]));
            else
                dp[i][j] = 1 + Math.min(dp[i][j-1], Math.min(dp[i-1][j], dp[i-1][j-1])); 
        }
    } 
    return dp[n][m];
}

拼写自动更正-放在一起

首先，我们使用Trie.add（String）将在提供的文件中找到的所有单词加载到Trie中。将使用Trie.find（String）将用户的输入字符串与Trie进行比较。如果在Trie中找到了输入字符串（与大小写无关），则程序将通过返回单词的最后一个Node来表明其拼写正确。如果找不到输入字符串的大小写无关版本，则程序将返回最“相似”词的节点，如下所示。如果找不到输入字符串，并且没有与之相似的词，则程序应返回null。

以下规则定义了如何确定单词最相似：

它具有距输入字符串“最近”的编辑距离
如果多个单词具有相同的编辑距离，则最相似的单词是在词典中找到次数最多的最接近编辑距离的单词
如果多个单词的编辑距离相同且计数/频率相同，则最相似的单词是第一个按字母顺序排列的单词

如果字典中的一个以上单词与输入字符串的编辑距离为1，则返回在原始文本文件中出现次数最多的单词。如果两个或多个单词与输入字符串的编辑距离为1，并且它们在输入文件中出现的次数相同，请返回按字母顺序排列的单词。如果没有单词与输入字符串的编辑距离为1，则词典中最“相似”的单词（如果存在）的编辑距离为2。词典中的单词w 的编辑距离为2如果存在字符串s （s 不必在字典中），则从输入字符串开始，以使s 与输入字符串的编辑距离为1，并且w 与s的编辑距离为1 。与1的编辑距离一样，如果一个单词到输入字符串的编辑距离为2，则选择输入文件中最常出现的单词。如果两个以上同时出现，请选择按字母顺序排列的第一个。如果词典中没有单词的编辑距离为1或2，则词典中没有与输入字符串“相似”的单词。在这种情况下，返回null。

该实现使用嵌套的TreeMap。在外部TreeMap中，键是输入单词和词典中单词的编辑距离。在内部TreeMap中，关键是字典中单词的出现频率。内部TreeMap的值是TreeSet，其中包含按字母顺序排序的相似单词。内部的TreeMap按单词的频率排序。外部treeMap按编辑距离排序。当我们在字典中找不到输入的单词时，我们可以以最小的编辑距离，最大的频率和前一个字母顺序返回该单词。

//Time O(S*n*m) ~ O(S), Space(K*N), S is number of words in dictionary 
//K is number of edit distance, N is the max number of similar words
private String suggestSimilarWord(String inputWord) {
    if (inputWord.length()==0 || inputWord==null || invalid.contains(inputWord.toLowerCase()) )
        return null;
    String s = inputWord.toLowerCase();
    String res=null;
    TreeMap<Integer, TreeMap<Integer, TreeSet<String>>> map = new TreeMap<>();      
    TrieNode node = trie.find(s);           
    if(node == null) {
        for (String w: dict.keySet()) {
            int dist = editDistance(w, s);              
            TreeMap<Integer, TreeSet<String>> similarWords = map.getOrDefault(dist, new TreeMap<>());
            int freq = dict.get(w);
            TreeSet<String> set = similarWords.getOrDefault(freq, new TreeSet<>());
            set.add(w);         
            similarWords.put(freq, set);
            map.put(dist, similarWords);        
        }       
        res = map.firstEntry().getValue().lastEntry().getValue().first();
    } else if (node !=null) {
            res = s;
    }
    return res;
}

结论

拼写自动更正是搜索中广泛使用的功能。在此实现中，我们应用了Trie数据结构编辑距离和嵌套的HashMap进行求解。

原文链接：http://codingdict.com

使用编辑距离和Trie自动修正拼写

热门标签