s***n 发帖数: 116 | 1 a dictionary is given. You have a word which may be misspelled. How will you
check if it is misspelled?
应该用hashtable吧?
谁能给个hash function? |
z***e 发帖数: 5393 | 2 why hash table?
prefix tree, or just sort the dictionary (usually already sorted) and then
search it.
you
【在 s***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : a dictionary is given. You have a word which may be misspelled. How will you : check if it is misspelled? : 应该用hashtable吧? : 谁能给个hash function?
|
g*******y 发帖数: 1930 | 3 这个网上有不少讨论的,有专门的paper,网站,专门的spell checker,不是一个简简
单单的算法问题。这个我这两天也正准备学习一下。
不过基本的思路呢,差不多都是基于edit distance的,这里就需要define一个metrics
来计算这个edit distance,比如insert delete replace swap等等操作可以有各自的
权重,复杂的还有要额外考虑英语发音相同相似的元音/音节,相似的拼写等等
然后我能想到的思路大概就是,对于每个dictionary里面的单词,计算出以它为root的
一颗树(每次往外算一层nearest neighbor,有点像是BFS的感觉,也有点计算最短路径
的感觉,当然其实BFS也就是一种最短路径的特例算法),所有的节点到该单词的edit
distance小于等于某个设定的值。
很多的树凑在一起,就形成了一个图(不同的树之间可以有shared node)
然后对一个misspelled word,就可以查询到和它距离<=给定值的正确单词集合,为了
快速查询,可以使用hash来存储: 单词->图的节点。
you
【在 s***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : a dictionary is given. You have a word which may be misspelled. How will you : check if it is misspelled? : 应该用hashtable吧? : 谁能给个hash function?
|
a*****e 发帖数: 51 | 4 The interviewer just asked to find whether the word is wrong or not...
metrics
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个网上有不少讨论的,有专门的paper,网站,专门的spell checker,不是一个简简 : 单单的算法问题。这个我这两天也正准备学习一下。 : 不过基本的思路呢,差不多都是基于edit distance的,这里就需要define一个metrics : 来计算这个edit distance,比如insert delete replace swap等等操作可以有各自的 : 权重,复杂的还有要额外考虑英语发音相同相似的元音/音节,相似的拼写等等 : 然后我能想到的思路大概就是,对于每个dictionary里面的单词,计算出以它为root的 : 一颗树(每次往外算一层nearest neighbor,有点像是BFS的感觉,也有点计算最短路径 : 的感觉,当然其实BFS也就是一种最短路径的特例算法),所有的节点到该单词的edit : distance小于等于某个设定的值。 : 很多的树凑在一起,就形成了一个图(不同的树之间可以有shared node)
|
a****n 发帖数: 1887 | 5 单词的字母sort,作为hash key
'me' --> ‘em’
...
然后再一个一个比对, 词少的时候快不了多少。。。 |
l*****a 发帖数: 14598 | 6 how to define misspell?
only 1 letter is wrong within exisiting words?
you
【在 s***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : a dictionary is given. You have a word which may be misspelled. How will you : check if it is misspelled? : 应该用hashtable吧? : 谁能给个hash function?
|
c****p 发帖数: 32 | 7 不存在什么misspell的问题,你能在dictionary里面找到就是对的,否则就是错的。我
觉得就是个基本的search问题,唯一要做的就是定义
bool operator>(string s1, string s2)
{
//缺省的未必对,需要自己实现字典顺序
}
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : how to define misspell? : only 1 letter is wrong within exisiting words? : : you
|