在实现伴随单词建议的拼写检查器时,通常使用什么算法？
起初我认为检查每个键入的新单词(如果没有在字典中找到)与字典中的每个其他单词的Levenshtein距离并返回最高结果可能是有意义的.然而,这似乎非常低效,不得不反复评估整个字典.
这通常是怎么做的？
language-agnostic algorithm spell-checking levenshtein-distance
你更喜欢哪个？为什么？
它们都可以用来完成类似的任务,但我很好奇,看看人们在实际应用中使用了什么,以及他们这样做的推理.
我需要存储一个大型自然语言词典 - 最多120,000,具体取决于语言.这些需要保存在内存中,因为分析表明利用阵列的算法是系统中的时间瓶颈.(它本质上是一种拼写检查/自动更正算法,但细节并不重要.)在具有16MB内存的Android设备上,与Java相关的内存开销String导致我们的空间不足.请注意,每个String都有一个与之相关的38字节开销,这会产生高达5MB的开销.
乍一看,一个选项是替代char[]的String.(或者甚至byte[],因为UTF-8在这种情况下更紧凑.)但同样,内存开销是个问题:每个Java数组都有32字节的开销.
另一种替代方法ArrayList<String>是创建一个具有相同接口的类,该类在内部将所有字符串连接成一个巨大的字符串,例如表示为单个字符串,byte[]然后将偏移存储到该巨大的字符串中.每个偏移量将占用4个字节,从而提供更节省空间的解决方案.
我的问题是a)是否有任何其他解决问题的方法,同样低开销*和b)是现成的任何解决方案吗？通过Guava,trove和PCJ集合库搜索没有任何结果.
*我知道可以将开销降到4字节以下,但收益递减.
NB.是否支持在HotSpot JVM中删除压缩字符串？表明JVM选项-XX:+UseCompressedStrings在这里没有帮助.