Sab*_*bya 18 language-agnostic nlp information-retrieval spell-checking autosuggest
我有以下要求: -
我有很多(比方说100万)值(名字).用户将键入搜索字符串.
我不希望用户正确拼写名称.
所以,我想让谷歌成为"你的意思".这将列出我的数据存储区中的所有可能值.有一个相似但不相同的问题在这里.这没有回答我的问题.
我的问题: - 1)我认为不建议将这些数据存储在RDBMS中.因为那时我不会对SQL查询进行过滤.我必须做全表扫描.那么,在这种情况下应该如何存储数据？
2)第二个问题与此相同.但是,仅仅为了我的问题的完整性:我如何搜索大数据集？假设,数据集中有一个名称Franky.如果用户输入Phranky,我该如何匹配Franky？我是否必须遍历所有名称？
我遇到了Levenshtein Distance,这将是一个很好的技术来找到可能的字符串.但同样,我的问题是我必须对数据存储中的所有100万个值进行操作吗？
3)我知道,Google通过观察用户行为来做到这一点.但是我想在不看用户行为的情况下这样做,即通过使用,我还不知道,说距离算法.因为前一种方法需要大量的搜索才能开始!
4)正如Kirk Broadhurst在下面的答案中指出的,有两种可能的情况: -
我对这两个都很感兴趣.它们实际上是两个不同的东西; 例如Sean和Shawn的声音相同,但编辑距离为3 - 太高而不能被视为拼写错误.
Soundex算法可以帮助您解决这个问题.
http://en.wikipedia.org/wiki/Soundex
您可以为每个名称预生成soundex值并将其存储在数据库中,然后对其进行索引以避免必须扫描表.
该Bitap算法设计在文本中发现的体近似匹配.也许你可以用它来计算可能的匹配.(它基于Levenshtein距离)
(更新:在阅读Ben S 回答之后(可能使用现有的解决方案aspell)是要走的路)
正如其他人所说,谷歌通过观察用户自我纠正来进行自动纠正.如果我搜索" someting"(原文如此),然后立即搜索" something",则第一个查询很可能是不正确的.可能的启发式检测方法是:
然后第二个查询是第一个查询的可能细化,您可以存储并呈现给其他用户.
请注意,您可能需要大量查询来收集足够的数据,以使这些建议有用.