[ 搜索引擎 ] - spellChecker原理分析

 

spellChecker是用来对用户输入的“检索内容”进行校正，例如百度上搜索“麻辣将”，他的提示如下图所示：

 我们首先借用lucene简单实现该功能。

本文内容如下（简单实现、原理简介、现有问题）

 

---

 

lucene中spellchecker简述

lucene 的扩展包中包含了spellchecker，利用它我们可以方便的实现拼写检查的功能，但是检查的效果（推荐的准确程度）需要开发者进行调整、优化。

 

lucene实现“拼写检查”的步骤

步骤1：建立spellchecker所需的索引文件

spellchecker也需要借助lucene的索引实现的，只不过其采用了特殊的分词方式和相关度计算方式。

建立spellchecker所需的索引文件可以用文本文件提供内容，一行一个词组，类似于字典结构。

例如（dic.txt）：

 

麻辣烫
中文测试
麻辣酱
麻辣火锅
中国人
中华人民共和国

 建立spellchecker索引的关键代码如下：

 

 

 /**
	 * 根据字典文件创建spellchecker所使用的索引。
	 * 
	 * @param spellIndexPath
	 *            spellchecker索引文件路径
	 * @param idcFilePath
	 *            原始字典文件路径
	 * @throws IOException
	 */
	public void createSpellIndex(String spellIndexPath, String idcFilePath)
			throws IOException {
		Directory spellIndexDir = FSDirectory.open(new File(spellIndexPath));
		SpellChecker spellChecker = new SpellChecker(spellIndexDir);
		IndexWriterConfig config = new IndexWriterConfig(Version.LUCENE_35,
				null);
		spellChecker.indexDictionary(new PlainTextDictionary(new File(
				idcFilePath)), config, false);
		// close
		spellIndexDir.close();
		spellChecker.close();
	}

 这里使用了PlainTextDictionary对象，他实现了Dictionary接口，类结构如下图所示：

 

 

除了PlainTextDictionary（1 word per line），我们还可以使用：

• FileDictionary（1 string per line, optionally with a tab-separated integer value | 词组之间用tab分隔）
• LuceneDictionary（Lucene Dictionary: terms taken from the given field of a Lucene index | 用现有的index的term建立索引）
• HighFrequencyDictionary（HighFrequencyDictionary: terms taken from the given field of a Lucene index, which appear in a number of documents above a given threshold. | 在LuceneDictionary的基础上加入了一定的限定，term只有出现在各document中的次数满足一定数量时才被spellchecker采用）

例如我们采用luceneDictionary，主要代码如下：

 

 

/**
	 * 根据指定索引中的字典创建spellchecker所使用的索引。
	 * 
	 * @param oriIndexPath
	 *            指定原始索引
	 * @param fieldName
	 *            索引字段（某个字段的字典）
	 * @param spellIndexPath
	 *            原始字典文件路径
	 * @throws IOException
	 */
	public void createSpellIndex(String oriIndexPath, String fieldName,
			String spellIndexPath) throws IOException {
		IndexReader oriIndex = IndexReader.open(FSDirectory.open(new File(
				oriIndexPath)));
		LuceneDictionary dict = new LuceneDictionary(oriIndex, fieldName);
		Directory spellIndexDir = FSDirectory.open(new File(spellIndexPath));
		SpellChecker spellChecker = new SpellChecker(spellIndexDir);
		IndexWriterConfig config = new IndexWriterConfig(Version.LUCENE_35,
				null);
		spellChecker.indexDictionary(dict, config, true);
	}

 

我们对dic.txt建立索引后，可以对其内部文档和term进行进一步了解，如下：

 

Document<stored,indexed,omitNorms,indexOptions=DOCS_ONLY<word:麻辣烫>>
Document<stored,indexed,omitNorms,indexOptions=DOCS_ONLY<word:中文测试>>
Document<stored,indexed,omitNorms,indexOptions=DOCS_ONLY<word:麻辣酱>>
Document<stored,indexed,omitNorms,indexOptions=DOCS_ONLY<word:麻辣火锅>>
Document<stored,indexed,omitNorms,indexOptions=DOCS_ONLY<word:中国人>>
Document<stored,indexed,omitNorms,indexOptions=DOCS_ONLY<word:中华人民共和国>>
end1:人	
end1:烫	end1:试	end1:酱	end1:锅	end2:国人	end2:测试	end2:火锅	end2:辣烫	end2:辣酱	end3:共和国	
end4:民共和国	gram1:中	gram1:人	gram1:国	gram1:文	gram1:测	gram1:火	gram1:烫	gram1:试	gram1:辣	
gram1:酱	gram1:锅	gram1:麻	gram1:	gram2:中国	gram2:中文	gram2:国人	gram2:文测	gram2:测试	gram2:火锅	
gram2:辣火	gram2:辣烫	gram2:辣酱	gram2:麻辣	gram2:麻	gram3:中华人	gram3:人民共	gram3:共和国	gram3:华人民	gram3:民共和	
gram4:中华人民	gram4:人民共和	gram4:华人民共	gram4:民共和国	start1:中	start1:麻	start1:	start2:中国	start2:中文	start2:麻辣	
start2:麻	start3:中华人	start4:中华人民	word:中华人民共和国	word:中国人	word:中文测试	word:麻辣火锅	word:麻辣酱	word:麻辣烫	

 可以看出，每一个词组（dic.txt每一行的内容）被当成一个document，然后采用特殊的分词方式对其进行分词，我们可以看出field的名称比较奇怪，例如：end1，end2，gram1，gram2等等。

 

 

为什么这么做，什么原理？我们先留下这个疑问，看完效果后再说明！

 

步骤二：spellchecker的“检查建议”

我们使用第一步创建的索引，利用spellChecker.suggestSimilar方法进行拼写检查。全部代码如下：

 

package com.fox.lab;

import java.io.File;
import java.io.IOException;
import java.util.Iterator;

import org.apache.lucene.index.IndexReader;
import org.apache.lucene.search.spell.LuceneDictionary;
import org.apache.lucene.search.spell.SpellChecker;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.FSDirectory;

/**
 * @author huangfox
 * @createDate 2012-2-16
 * @eMail [e-mail]
 */
public class DidYouMeanSearcher {
	SpellChecker spellChecker = null;
	LuceneDictionary dict = null;

	/**
	 * 
	 * @param spellCheckIndexPath
	 *            spellChecker索引位置
	 */
	public DidYouMeanSearcher(String spellCheckIndexPath, String oriIndexPath,
			String fieldName) {
		Directory directory;
		try {
			directory = FSDirectory.open(new File(spellCheckIndexPath));
			spellChecker = new SpellChecker(directory);
			IndexReader oriIndex = IndexReader.open(FSDirectory.open(new File(
					oriIndexPath)));
			dict = new LuceneDictionary(oriIndex, fieldName);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	/**
	 * 设定精度，默认0.5
	 * 
	 * @param v
	 */
	public void setAccuracy(float v) {
		spellChecker.setAccuracy(v);
	}

	/**
	 * 针对检索式进行spell check
	 * 
	 * @param queryString
	 *            检索式
	 * @param suggestionsNumber
	 *            推荐的最大数量
	 * @return
	 */
	public String[] search(String queryString, int suggestionsNumber) {
		String[] suggestions = null;
		try {
			// if (exist(queryString))
			// return null;
			suggestions = spellChecker.suggestSimilar(queryString,
					suggestionsNumber);
		} catch (IOException e) {
			e.printStackTrace();
		}
		return suggestions;
	}

	private boolean exist(String queryString) {
		Iterator<String> ite = dict.getWordsIterator();
		while (ite.hasNext()) {
			if (ite.next().equals(queryString))
				return true;
		}
		return false;
	}
}

 测试效果：

 

package com.fox.lab;

import java.io.IOException;

public class DidYouMeanMainApp {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// 创建index
		DidYouMeanIndexer indexer = new DidYouMeanIndexer();
		String spellIndexPath = "D:\\spellchecker";
		String idcFilePath = "D:\\dic.txt";
		String oriIndexPath = "D:\\solrHome\\example\\solr\\data\\index";
		String fieldName = "ab";
		DidYouMeanSearcher searcher = new DidYouMeanSearcher(spellIndexPath,
				oriIndexPath, fieldName);
		searcher.setAccuracy(0.5f);
		int suggestionsNumber = 15;
		String queryString = "麻辣将";
//		try {
//			indexer.createSpellIndex(spellIndexPath, idcFilePath);
		// indexer.createSpellIndex(oriIndexPath, fieldName, spellIndexPath);
		// } catch (IOException e) {
		// e.printStackTrace();
		// }
		String[] result = searcher.search(queryString, suggestionsNumber);
		if (result == null || result.length == 0) {
			System.out.println("我不知道你要什么，或许你就是对的！");
		} else {
			System.out.println("你是不是想找：");
			for (int i = 0; i < result.length; i++) {
				System.out.println(result[i]);
			}
		}
	}

}

输出：

你是不是想找：
麻辣酱
麻辣火锅
麻辣烫

 将queryString改为“中文测式”，输出：

 

你是不是想找：
中文测试

 当输入正确时，例如“中文测试”，则输出：

我不知道你要什么，或许你就是对的！

 

 

---

拼写检查的基本功能实现了，虽然还存在很多问题需要改进调整。我们先来了解其中两个基本原理。

第一原理：N-gram

我们要实现spellchecker，其实简单理解就是将用户输入的词组（英文为单词，中文为词组）和字典里面“标准”的词组进行“相似性”比较，并给出相似程度最高的词组。

那么如何比较两个字符串的相似程度就是spellchecker的关键所在。

字符串P 的N-gram 是P 中任意长度为N 的子串。例如，单词waist 的Bigram 有wa、ai、is 和st 四个。对于给定的字符串P 和W，其N-gram 相似度gram-count(P,W) 定义为同时在P 和W 中出现的N-gram 数目。在lucene的spellchecker中对N-gram进行了扩展，对整个单词、单词的头尾都做了处理，例如：麻辣烤翅，分解成：

start2:麻	
start3:麻辣

end2:烤翅	
end3:辣烤翅

gram2:烤翅	
gram2:辣烤	
gram2:麻辣	
gram2:麻	

gram3:辣烤翅	
gram3:麻辣烤	
gram3:麻辣	

word:麻辣烤翅

 当用户输入“麻辣靠翅”时，被分解成：

end2:靠翅 end3:辣靠翅 gram2:靠翅 gram2:辣靠 gram2:麻辣 gram2:麻 gram3:辣靠翅 gram3:麻辣靠 gram3:麻辣 start2:麻 start3:麻辣 word:麻辣靠翅

并将这些term组成一个用OR连接的检索式（不同的term可能赋予不同的权重），在spellchecker的索引里进行检索，即可匹配到文档“麻辣烤翅”。但是不是就要把它推荐（suggest）出来呢？还要看他们的相识度是否符合要求。在lucene的spellchecker中，默认相似度为0.5。

lucene——spellchecker的n-gram分词算法如下：

private static void addGram(String text, Document doc, int ng1, int ng2) {
    int len = text.length();
    for (int ng = ng1; ng <= ng2; ng++) {
      String key = "gram" + ng;
      String end = null;
      for (int i = 0; i < len - ng + 1; i++) {
        String gram = text.substring(i, i + ng);
        Field ngramField = new Field(key, gram, Field.Store.NO, Field.Index.NOT_ANALYZED);
        // spellchecker does not use positional queries, but we want freqs
        // for scoring these multivalued n-gram fields.
        ngramField.setIndexOptions(IndexOptions.DOCS_AND_FREQS);
        doc.add(ngramField);
        if (i == 0) {
          // only one term possible in the startXXField, TF/pos and norms aren't needed.
          Field startField = new Field("start" + ng, gram, Field.Store.NO, Field.Index.NOT_ANALYZED);
          startField.setIndexOptions(IndexOptions.DOCS_ONLY);
          startField.setOmitNorms(true);
          doc.add(startField);
        }
        end = gram;
      }
      if (end != null) { // may not be present if len==ng1
        // only one term possible in the endXXField, TF/pos and norms aren't needed.
        Field endField = new Field("end" + ng, end, Field.Store.NO, Field.Index.NOT_ANALYZED);
        endField.setIndexOptions(IndexOptions.DOCS_ONLY);
        endField.setOmitNorms(true);
        doc.add(endField);
      }
    }
  }

 第二原理：相似度计算（stringDistance）

在lucene的spellchecker中，StringDistance作为接口，有三个实现类，如下：

• JaroWinklerDistance
• LevensteinDistance
• NGramDistance

我们这里采用LevensteinDistance进行字符串相似度计算。LevensteinDistance就是edit distance（编辑距离）。

编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

例如将kitten一字转成sitting：

　　sitten （k→s） 

　　sittin （e→i） 

　　sitting （→g） 

　　俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

lucene中算法如下：

public float getDistance (String target, String other) {
      char[] sa;
      int n;
      int p[]; //'previous' cost array, horizontally
      int d[]; // cost array, horizontally
      int _d[]; //placeholder to assist in swapping p and d
      
        /*
           The difference between this impl. and the previous is that, rather
           than creating and retaining a matrix of size s.length()+1 by t.length()+1,
           we maintain two single-dimensional arrays of length s.length()+1.  The first, d,
           is the 'current working' distance array that maintains the newest distance cost
           counts as we iterate through the characters of String s.  Each time we increment
           the index of String t we are comparing, d is copied to p, the second int[].  Doing so
           allows us to retain the previous cost counts as required by the algorithm (taking
           the minimum of the cost count to the left, up one, and diagonally up and to the left
           of the current cost count being calculated).  (Note that the arrays aren't really
           copied anymore, just switched...this is clearly much better than cloning an array
           or doing a System.arraycopy() each time  through the outer loop.)

           Effectively, the difference between the two implementations is this one does not
           cause an out of memory condition when calculating the LD over two very large strings.
         */

        sa = target.toCharArray();
        n = sa.length;
        p = new int[n+1]; 
        d = new int[n+1]; 
      
        final int m = other.length();
        if (n == 0 || m == 0) {
          if (n == m) {
            return 1;
          }
          else {
            return 0;
          }
        } 


        // indexes into strings s and t
        int i; // iterates through s
        int j; // iterates through t

        char t_j; // jth character of t

        int cost; // cost

        for (i = 0; i<=n; i++) {
            p[i] = i;
        }

        for (j = 1; j<=m; j++) {
            t_j = other.charAt(j-1);
            d[0] = j;

            for (i=1; i<=n; i++) {
                cost = sa[i-1]==t_j ? 0 : 1;
                // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
                d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1),  p[i-1]+cost);
            }

            // copy current distance counts to 'previous row' distance counts
            _d = p;
            p = d;
            d = _d;
        }

        // our last action in the above loop was to switch d and p, so p now
        // actually has the most recent cost counts
        return 1.0f - ((float) p[n] / Math.max(other.length(), sa.length));
    }

 

---

 需要改进的地方

1.精度不高，特别是对于两个字的词组。可以在距离计算（相似度计算）方面进行调整。

2.没有拼音的功能，例如麻辣kao翅，将无法进行校正。

3.对于字符串中出现的错误无法进行校正，例如“常州哪里有卖变态麻辣靠翅”。

 

 

 

 

 

 

评论

3 楼 matay 2013-02-17  

请问，在找候选词字符串时JaroWinklerDistance，LevensteinDistance，NGramDistance这三个之中哪个算法的准确度最好？

2 楼 huangfoxAgain 2012-06-18  

whiletrue 写道

这是篇好文章唉，居然无人评论，谢谢分享。

多谢关注！
http://www.iteye.com/topic/1121493 上的格式比较好看一点！
当时没注意在论坛和博客上搞了两次。。。

1 楼 whiletrue 2012-06-18  

这是篇好文章唉，居然无人评论，谢谢分享。