y*****i
发帖数: 141 | 1 比如已知一个含有N个word的字典，现在随便给一个string，要找出所有包含这个
string作为子串的word。这种是用suffix tree来做吗？有更好写的方法吗？谢谢 |
y*****i
发帖数: 141 | 2 自己顶一下。
KMP不适合多次查询的情况，Aho-Corasick适合查前缀而不是任意位置的子串，所以只
能是suffix tree吧？ |
r*********n
发帖数: 4553 | 3 为什么KMP不适合呢？KMP只学要预处理一次pattern，然后用生成的dfa去查每个word |
s*******s
发帖数: 1031 | 4 应该是用prie。
【在 y*****i 的大作中提到】
: 比如已知一个含有N个word的字典，现在随便给一个string，要找出所有包含这个
: string作为子串的word。这种是用suffix tree来做吗？有更好写的方法吗？谢谢
|
l**********r
发帖数: 4612 | 5 prie是什么
【在 s*******s 的大作中提到】
: 应该是用prie。
|
s*******s
发帖数: 1031 | 6 TRIE
http://en.wikipedia.org/wiki/Trie
sorry for the typo
【在 l**********r 的大作中提到】
: prie是什么
|
y*****i
发帖数: 141 | 7 Prie是啥？没搜到。对string matching算法很不熟，唉。
【在 s*******s 的大作中提到】
: 应该是用prie。
|
y*****i
发帖数: 141 | 8 哦。got it。
但是trie能用来搜子串吗？比如wiki上这个例子，ten在这个字典里，现在如果要搜"en
"，trie就不行了吧。
【在 s*******s 的大作中提到】
: TRIE
: http://en.wikipedia.org/wiki/Trie
: sorry for the typo
|
s*******s
发帖数: 1031 | 9 你说得对，我的想法错了。呵呵
en
【在 y*****i 的大作中提到】
: 哦。got it。
: 但是trie能用来搜子串吗？比如wiki上这个例子，ten在这个字典里，现在如果要搜"en
: "，trie就不行了吧。
|
y*****i
发帖数: 141 | 10 字典是已知的，pattern是未知的，且多个。这样是不是KMP就不如suffix tree了。每
一个新pattern都得重新搜一次。
就是做题的时候suffix tree感觉比KMP难写多了。。。
【在 r*********n 的大作中提到】
: 为什么KMP不适合呢？KMP只学要预处理一次pattern，然后用生成的dfa去查每个word
|
|
|
c********p
发帖数: 1969 | |
J****3
发帖数: 427 | 12 为啥pattern这里是未知的啊？ 不是给定一个string 去字典里挨个找的吗？这个
string不就是pat? 字典的是txt?
【在 y*****i 的大作中提到】
: 字典是已知的，pattern是未知的，且多个。这样是不是KMP就不如suffix tree了。每
: 一个新pattern都得重新搜一次。
: 就是做题的时候suffix tree感觉比KMP难写多了。。。
|
y*****i
发帖数: 141 | 13 my bad. 没表述清楚。不是给定一个。是每次给一个。。就像一个真的dict一样。今天
你想查这个词，明天想查那个词，只不过现在我们查的是各种子串们。
【在 J****3 的大作中提到】
: 为啥pattern这里是未知的啊？ 不是给定一个string 去字典里挨个找的吗？这个
: string不就是pat? 字典的是txt?
|
g**G
发帖数: 767 | 14 如果没理解错的话，应该是trie而不是suffix tree做
trie一般用于这种类似字典的查找，suffix tree一般用来重复查找同一个字符串的子串
【在 y*****i 的大作中提到】
: 比如已知一个含有N个word的字典，现在随便给一个string，要找出所有包含这个
: string作为子串的word。这种是用suffix tree来做吗？有更好写的方法吗？谢谢
|
l*******0
发帖数: 63 | 15 我觉得trie不太行吧？trie是找前缀的，但他这个是要找子串。比如字典里有abcd，
mcd, ncd, 然后要找所有含cd的，那trie岂不是一个都找不出来。可是如果是suffix
tree的话 难道为每一个字典里的string都建一课suffix tree？我觉得可能用那个
rolling hash比较不错。
子串
【在 g**G 的大作中提到】
: 如果没理解错的话，应该是trie而不是suffix tree做
: trie一般用于这种类似字典的查找，suffix tree一般用来重复查找同一个字符串的子串
|
r*********n
发帖数: 4553 | 16 那可以把所有词的suffix都放到trie里面去，这样查找速度最快，但是预处理复杂度很
高，不过如果查找次数很多，预处理的overhead平均下来也就不算什么了。
【在 y*****i 的大作中提到】
: my bad. 没表述清楚。不是给定一个。是每次给一个。。就像一个真的dict一样。今天
: 你想查这个词，明天想查那个词，只不过现在我们查的是各种子串们。
|
p*****2
发帖数: 21240 | |
k*j
发帖数: 153 | 18 http://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/suffixtrees.pdf
PAGE 44
Determine the strings in a database {S1, S2, S3, ..., Sm} that contain
query string q:
Build generalized suffix tree for {S1, S2, S3, ..., Sm}
Follow the path for q in the suffix tree.
Suppose you end at node u: traverse the tree below u, and
output i if you find a string containing #i |
f*******b
发帖数: 520 | 19
赞同！
【在 l*******0 的大作中提到】
: 我觉得trie不太行吧？trie是找前缀的，但他这个是要找子串。比如字典里有abcd，
: mcd, ncd, 然后要找所有含cd的，那trie岂不是一个都找不出来。可是如果是suffix
: tree的话 难道为每一个字典里的string都建一课suffix tree？我觉得可能用那个
: rolling hash比较不错。
:
: 子串
|
