b***m
发帖数: 5987 | 1 有两个纯文本文件，其中一个较大，大约上万行，每行是一个具体的域名，比如bjhmm.
seattle.washington.usa。另外一个较小，大约一千多行，每行是一个大域名，比如
washington.usa。现在想找到一个较快的算法，迅速判断小文件中的大域名清单是否能
涵盖大文件中的所有域名。我目前想到的是用后缀树或者前缀树，大家有什么好办法？ |
p*****2
发帖数: 21240 | 2 hashtable就可以了
【在 b***m 的大作中提到】
: 有两个纯文本文件，其中一个较大，大约上万行，每行是一个具体的域名，比如bjhmm.
: seattle.washington.usa。另外一个较小，大约一千多行，每行是一个大域名，比如
: washington.usa。现在想找到一个较快的算法，迅速判断小文件中的大域名清单是否能
: 涵盖大文件中的所有域名。我目前想到的是用后缀树或者前缀树，大家有什么好办法？
|
w****x
发帖数: 2483 | 3
bjhmm.
这不需要树结构的吧....
【在 b***m 的大作中提到】
: 有两个纯文本文件，其中一个较大，大约上万行，每行是一个具体的域名，比如bjhmm.
: seattle.washington.usa。另外一个较小，大约一千多行，每行是一个大域名，比如
: washington.usa。现在想找到一个较快的算法，迅速判断小文件中的大域名清单是否能
: 涵盖大文件中的所有域名。我目前想到的是用后缀树或者前缀树，大家有什么好办法？
|
r*******n
发帖数: 3020 | 4 我觉得楼上的是正解啊
【在 w****x 的大作中提到】
:
: bjhmm.
: 这不需要树结构的吧....
|
b***m
发帖数: 5987 | 5
具体说说？每个具体域名只是域名清单中某个具体大域名的一部分啊。
【在 p*****2 的大作中提到】
: hashtable就可以了
|
t****a
发帖数: 1212 | |
e****e
发帖数: 418 | 7 hashtable这里不好使吧, 原因好猫已经说了.
我觉得从小文件里建个tree.具体如下：
1. 对小文件里的每行的域名double reverse(老题...),
i.e. washington.usa -> usa.washington
2. 再建立prefix tree.
i.e (root)
|
|
usa
/ \
/ \
oregon washington
3. 遍历大文件里的域名, double reverse 之后和比较.
优化：
prefix tree只需要建立第一层就可以了. 至此，我觉得hashtable更好！
其实是个hashset,里面放小文件里域名反转之后的第一级域名.
i.e.
usa
china
canada
然后遍历大文件, 看hashset包含反转域名之后第一级域名.
i.e.
bjhmm.seattle.washington.usa --> usa.washington.seattle.bjhmm
hashset包含usa, 继续下一行, 不包含，返回false.
继续优化:
不搞double reverse,直接用正则表达式扣出来一级域名,也就是最后一个逗号之后的那
个东西---一级域名. |
e****e
发帖数: 418 | |
t****a
发帖数: 1212 | 9 为啥不能用呢，我试了下可以，哪里不对》
one
【在 e****e 的大作中提到】
: 这里grep -f 没法直接用吧.
: "Finally, -f allows you to specify a file containing the search string, one
: instance where this could be useful is if one had a complex search string
: that one may not want to type over and over again."
: Please refer for details http://www.uccs.edu/~ahitchco/grep/
:
: utf-
|
l*******b
发帖数: 2586 | 10 grep是找match的条目, 找不match得加个步骤吧
查了下,好像是 -v
【在 t****a 的大作中提到】
: 为啥不能用呢，我试了下可以，哪里不对》
:
: one
|
|
|
e****e
发帖数: 418 | 11 我手头上没*nix有环境，我是根据grep文档, 链接已给出. 我以为grep是把小文件的所
有内容做为一个字符串，再查看大文件内容，看是否有匹配，如果有就返回匹配处所在
的行数.
你试验可以，那表明grep把小文件里每行都作为一个字符串,大文件里的任何一处和小
文件里的任何一行字符串匹配，就返回行号. 最后看大文件里所有的行号都返回了，就
是个全包含！
【在 t****a 的大作中提到】
: 为啥不能用呢，我试了下可以，哪里不对》
:
: one
|
t****a
发帖数: 1212 | 12 呵呵，按行的。
【在 e****e 的大作中提到】
: 我手头上没*nix有环境，我是根据grep文档, 链接已给出. 我以为grep是把小文件的所
: 有内容做为一个字符串，再查看大文件内容，看是否有匹配，如果有就返回匹配处所在
: 的行数.
: 你试验可以，那表明grep把小文件里每行都作为一个字符串,大文件里的任何一处和小
: 文件里的任何一行字符串匹配，就返回行号. 最后看大文件里所有的行号都返回了，就
: 是个全包含！
|
e****e
发帖数: 418 | 13 Good to know. Thanks for sharing your solution.
【在 t****a 的大作中提到】
: 呵呵，按行的。
|
b***m
发帖数: 5987 | 14 写了20来行Perl程序搞定。grep对下面这个情况适用吗？
file 1:
bjhmm.microsoft.redmond.washington.usa
file 2:
redmond.wa |
p*****2
发帖数: 21240 | 15
大牛用perl呀？
【在 b***m 的大作中提到】
: 写了20来行Perl程序搞定。grep对下面这个情况适用吗？
: file 1:
: bjhmm.microsoft.redmond.washington.usa
: file 2:
: redmond.wa
|
e****e
发帖数: 418 | 16 redmond.wa出现在file1里，正好可以吧.
【在 b***m 的大作中提到】
: 写了20来行Perl程序搞定。grep对下面这个情况适用吗？
: file 1:
: bjhmm.microsoft.redmond.washington.usa
: file 2:
: redmond.wa
|
