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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 这个网上有不少讨论的，有专门的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 的大作中提到】
: 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 的大作中提到】
: how to define misspell?
: only 1 letter is wrong within exisiting words?
:
: you
|
