探讨加请教：我工作中的一道题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

探讨加请教：我工作中的一道题

探讨加请教：我工作中的一道题# JobHunting - 待字闺中

b*m2013-01-30 08:01

1 楼

有两个纯文本文件，其中一个较大，大约上万行，每行是一个具体的域名，比如bjhmm.
seattle.washington.usa。另外一个较小，大约一千多行，每行是一个大域名，比如
washington.usa。现在想找到一个较快的算法，迅速判断小文件中的大域名清单是否能
涵盖大文件中的所有域名。我目前想到的是用后缀树或者前缀树，大家有什么好办法？

p*22013-01-30 08:01

2 楼

hashtable就可以了

【在 b***m 的大作中提到】

: 有两个纯文本文件，其中一个较大，大约上万行，每行是一个具体的域名，比如bjhmm.
: seattle.washington.usa。另外一个较小，大约一千多行，每行是一个大域名，比如
: washington.usa。现在想找到一个较快的算法，迅速判断小文件中的大域名清单是否能
: 涵盖大文件中的所有域名。我目前想到的是用后缀树或者前缀树，大家有什么好办法？

w*x2013-01-30 08:01

3 楼

bjhmm.
这不需要树结构的吧....

【在 b***m 的大作中提到】

r*n2013-01-30 08:01

4 楼

我觉得楼上的是正解啊

【在 w****x 的大作中提到】

:
: bjhmm.
: 这不需要树结构的吧....

b*m2013-01-30 08:01

5 楼

具体说说？每个具体域名只是域名清单中某个具体大域名的一部分啊。

【在 p*****2 的大作中提到】

: hashtable就可以了

t*a2013-01-30 08:01

6 楼

数据不大，犯不着自己造轮子了吧。自己造轮子是大忌。
file1:
http://www.mitbbs.com/article_t/JobHunting/32314419.html
http://www.mitbbs.com/bbsdoc/JobHunting.html
https://mail.google.com/mail/
https://console.aws.amazon.com/datapipeline/home
http://dagama.aka.amazon.com/research/kindleads/diary.html
https://www.google.com/search?client=ubuntu&channel=fs&q=prematurely&ie=utf-
8&oe=utf-8
file2:
google.com
amazon.com
mitbbs.com
command:
grep -f 2.txt 1.txt

e*e2013-01-30 08:01

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*e2013-01-30 08:01

8 楼

这里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-

【在 t****a 的大作中提到】

: 数据不大，犯不着自己造轮子了吧。自己造轮子是大忌。
: file1:
: http://www.mitbbs.com/article_t/JobHunting/32314419.html
: http://www.mitbbs.com/bbsdoc/JobHunting.html
: https://mail.google.com/mail/
: https://console.aws.amazon.com/datapipeline/home
: http://dagama.aka.amazon.com/research/kindleads/diary.html
: https://www.google.com/search?client=ubuntu&channel=fs&q=prematurely&ie=utf-
: 8&oe=utf-8
: file2:

t*a2013-01-30 08:01

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*b2013-01-30 08:01

10 楼

grep是找match的条目, 找不match得加个步骤吧
查了下,好像是 -v

【在 t****a 的大作中提到】

: 为啥不能用呢，我试了下可以，哪里不对》
:
: one

e*e2013-01-30 08:01

11 楼

我手头上没*nix有环境，我是根据grep文档, 链接已给出. 我以为grep是把小文件的所
有内容做为一个字符串，再查看大文件内容，看是否有匹配，如果有就返回匹配处所在
的行数.
你试验可以，那表明grep把小文件里每行都作为一个字符串,大文件里的任何一处和小
文件里的任何一行字符串匹配，就返回行号. 最后看大文件里所有的行号都返回了，就
是个全包含！

【在 t****a 的大作中提到】

: 为啥不能用呢，我试了下可以，哪里不对》
:
: one

t*a2013-01-30 08:01

12 楼

呵呵，按行的。

【在 e****e 的大作中提到】

: 我手头上没*nix有环境，我是根据grep文档, 链接已给出. 我以为grep是把小文件的所
: 有内容做为一个字符串，再查看大文件内容，看是否有匹配，如果有就返回匹配处所在
: 的行数.
: 你试验可以，那表明grep把小文件里每行都作为一个字符串,大文件里的任何一处和小
: 文件里的任何一行字符串匹配，就返回行号. 最后看大文件里所有的行号都返回了，就
: 是个全包含！

e*e2013-01-30 08:01

13 楼

Good to know. Thanks for sharing your solution.

【在 t****a 的大作中提到】

: 呵呵，按行的。

b*m2013-01-30 08:01

14 楼

写了20来行Perl程序搞定。grep对下面这个情况适用吗？
file 1:
bjhmm.microsoft.redmond.washington.usa
file 2:
redmond.wa

p*22013-01-30 08:01

15 楼

大牛用perl呀？

【在 b***m 的大作中提到】

: 写了20来行Perl程序搞定。grep对下面这个情况适用吗？
: file 1:
: bjhmm.microsoft.redmond.washington.usa
: file 2:
: redmond.wa

e*e2013-01-30 08:01

16 楼

redmond.wa出现在file1里，正好可以吧.

【在 b***m 的大作中提到】

: 写了20来行Perl程序搞定。grep对下面这个情况适用吗？
: file 1:
: bjhmm.microsoft.redmond.washington.usa
: file 2:
: redmond.wa