language-agnostic - 一个 StringToken 解析器，它提供谷歌搜索风格“你的意思是：”

Question

寻求一种方法：

在字符串中使用空格分隔的标记；返回一个建议的词

即：
谷歌搜索可以采用“fonetic wrd nterpreterr”，
并在结果页面顶部显示“您的意思是：语音单词解释器”

任何 C* 语言或 Java 的解决方案都是首选。

是否有任何执行此类功能的现有开放库？

或者有没有办法利用 Google API 来请求建议的单词？

score 11 · Accepted Answer

在他的文章How to Write a Spelling Corrector中，Peter Norvig 讨论了如何实现类似 Google 的拼写检查器。这篇文章包含一个 20 行的 Python 实现，以及指向 C、C++、C# 和 Java 的几个重新实现的链接。这是一段摘录：

像谷歌这样的工业级拼写校正器的全部细节比启发性更令人困惑，但我认为在回家的飞机上，用不到一页代码，我可以编写一个达到 80% 或 90% 的玩具拼写校正器处理速度至少为每秒 10 个字的准确度。

使用 Norvig 的代码和此文本作为训练集，我得到以下结果：

>>> import spellch
>>> [spellch.correct(w) for w in 'fonetic wrd nterpreterr'.split()]
['phonetic', 'word', 'interpreters']

score 2 · Accepted Answer

您可以在此处使用 yahoo 网络服务：http: //developer.yahoo.com/search/web/V1/spellingSuggestion.html

然而它只是一个网络服务......（即没有其他语言的 API 等......）但它输出 JSON 或 XML，所以......很容易适应任何语言......

score 2 · Accepted Answer

您还可以使用 Google API 进行拼写检查。这里有一个 ASP 实现（不过，我不相信这一点）。

score 2 · Accepted Answer

首先：

使用您选择的一种。我怀疑它针对一个字数限制正好为一个的拼写检查引擎运行查询，如果整个查询有效，它就什么也不做，否则它会用该词的最佳匹配替换每个词。换句话说，下面的算法（一个空的返回字符串意味着查询没有问题）：

startup()
{
   set the spelling engines word suggestion limit to 1
}

option 1()
{
   int currentPosition = engine.NextWord(start the search at word 0, querystring);

   if(currentPosition == -1)
      return empty string; // Query is a-ok.

   while(currentPosition != -1)
   {
       queryString = engine.ReplaceWord(engine.CurrentWord, queryString, the suggestion with index 0);
       currentPosition = engine.NextWord(currentPosition, querystring);
   }

   return queryString;
}

score 2 · Accepted Answer

由于还没有人提到它，我将再提供一个短语来搜索：“编辑距离”（例如，链接文本）。这可用于查找最接近的匹配项，假设是字母被转置、丢失或添加的拼写错误。

但通常这也伴随着某种相关性信息；或者通过简单的流行度（假设最常用的足够接近的匹配最有可能是正确的单词），或者通过上下文的可能性（在正确单词之后的单词，或者在一个之前的单词）。这进入了信息检索；一种开始的方法是查看二元组和三元组（一起看到的单词序列）。谷歌为这些提供了非常广泛的免费数据集。

对于简单的初始解决方案，尽管字典与基于 Levenshtein 的匹配器的效果非常好。

score 2 · Accepted Answer

您可以插入 Lucene，它具有实现 Levenshtein 距离方法的字典工具。

这是来自 Wiki 的示例，其中 2 是距离。

String[] l=spellChecker.suggestSimilar("sevanty", 2);
//l[0] = "seventy"

score 1 · Accepted Answer

如果您将字典存储为 trie，则有一种相当简单的方法可以找到最佳匹配条目，其中可以插入、删除或替换字符。

void match(trie t, char* w, string s, int budget){
  if (budget < 0) return;
  if (*w=='\0') print s;
  foreach (char c, subtrie t1 in t){
    /* try matching or replacing c */
    match(t1, w+1, s+c, (*w==c ? budget : budget-1));
    /* try deleting c */
    match(t1, w, s, budget-1);
  }
  /* try inserting *w */
  match(t, w+1, s + *w, budget-1);
}

这个想法是，首先你用零预算调用它，看看它是否打印出任何东西。然后尝试预算 1，依此类推，直到打印出一些匹配项。预算越大，花费的时间就越长。您可能只想达到 2 的预算。

补充：扩展它来处理常见的前缀和后缀并不难。例如，像“un”、“anti”和“dis”这样的英文前缀可以在字典中，然后可以链接回字典的顶部。对于像 "ism"、"'s" 和 "ed" 这样的后缀，可以有一个单独的 trie，只包含后缀，并且大多数单词都可以链接到该后缀 trie。然后它可以处理诸如“反国有化”之类的奇怪词。

score 1 · Accepted Answer

1

Google SOAP 搜索 API就是这样做的。

于 2009-04-04T11:36:57.647 回答

language-agnostic - 一个 StringToken 解析器，它提供谷歌搜索风格“你的意思是：”

寻求一种方法：

在字符串中使用空格分隔的标记；返回一个建议的词

8 回答 8

Related

Reference