轻量级模糊搜索库

Lightweight fuzzy search library

您能建议一些轻量级的模糊文本搜索库吗？

我想要做的是允许用户使用错别字为搜索词找到正确的数据。

我可以使用像Lucene这样的全文搜索引擎，但是我认为这太过分了。

编辑：
为了使问题更清楚，这里是该库的主要方案：
我有很多字符串。我希望能够在此列表中进行搜索(类似于MSVS的intellisense)，但应该可以通过其中不存在但与列表中某个字符串足够接近的字符串来过滤此列表。
示例：

红
绿色
蓝色

当我在文本框中键入'Gren'或'Geen'时，我想在结果集中看到'Green'。

索引数据的主要语言是英语。

我认为露西恩(Lucene)要完成这项任务。

更新：

我找到了一款符合我要求的产品。它是ShuffleText。
您知道其他选择吗？

Lucene具有很好的可扩展性，这也意味着它对于少量应用程序也有好处。如果需要，您可以在内存中快速创建索引。

对于模糊搜索，您确实需要确定要使用哪种算法。通过信息检索，我成功地将Lucene与n-gram技术结合使用。但这是一种特殊的索引技术，本身不是"库"。

在不了解您的应用程序的情况下，推荐合适的库并不容易。您要搜索多少数据？数据是什么格式？数据多久更新一次？

我不确定Lucene是否适合模糊搜索，自定义库将是更好的选择。例如，此搜索是使用Java完成的，并且运行起来非常快，但是它是针对以下任务而定制的：
http://www.softcorporation.com/products/people/

尝试使用基于Lucene API的Walnutil(集成到SQL Server和Oracle DB)。您可以创建任何类型的索引，然后使用它。对于简单的搜索，您可以使用核桃软件的一些方法，对于更复杂的搜索情况，可以使用Lucene API。请参阅基于Web的示例，其中使用了从Walnutil Tools创建的索引。您还可以看到一些用Java和C#编写的代码示例，可将其用于创建不同类型的搜索。
该工具是免费的。
http://www.walnutilsoft.com/

您没有指定开发平台，但是如果它的PHP则建议您查看ZEND Lucene库：

http://ifacethoughts.net/2008/02/07/zend-brings-lucene-to-php/
http://framework.zend.com/manual/zh/zend.search.lucene.html

由于它的LAMP比Java上的Lucene轻得多，并且可以轻松扩展为其他文件类型，前提是您可以找到转换库或cmd行转换器-有很多OSS解决方案可以做到这一点。

如果可以选择使用数据库，建议使用PostgreSQL及其模糊字符串匹配功能。

如果可以使用Ruby，建议您研究amatch库。

Soundex的编码非常"英文"-Daitch-Mokotoff适用于许多名称，尤其是欧洲(德语)和犹太名称。在我以英国为中心的世界中，这就是我所使用的。

Wiki在这里。

狮身人面像是一种功能强大，轻巧的解决方案。

它比Lucene小，并且支持消除歧义。

它是用c编写的，它经过快速，可靠的测试，具有每个env的库，并且已被craigslists.org等大型公司使用。

@aku-指向正常工作的soundex库的链接位于页面底部。

关于Levenshtein距离，有关Wikipedia的文章也在底部列出了实现。