请教一道T家的题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一道T家的题

请教一道T家的题# JobHunting - 待字闺中

f*m2013-03-12 07:03

1 楼

给一组tweet的inverted index，怎么找一个phrase（多个词）的最短组合，比如找
phrase "twitter good tool", twitter is a good tool就比twitter is good,
facebook is a better tool距离近
多谢。

r*h2013-03-12 07:03

2 楼

和那个“包含一个集合里面所有字母的最小连续子串”的思路应该是一样的吧？
只不过把字母换成字符串

f*e2013-03-12 07:03

3 楼

这个得学了data mining才知道。

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

: 给一组tweet的inverted index，怎么找一个phrase（多个词）的最短组合，比如找
: phrase "twitter good tool", twitter is a good tool就比twitter is good,
: facebook is a better tool距离近
: 多谢。

j*y2013-03-12 07:03

4 楼

data ming 有什么经典的 text book吗？

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

: 这个得学了data mining才知道。

l*a2013-03-12 07:03

5 楼

这不是那道滑动窗口的题吗？

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

d*x2013-03-12 07:03

6 楼

不过我咋觉得这道题不过是edit dist里面的单元从character变成word了呢。。

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

: 这个得学了data mining才知道。

l*a2013-03-12 07:03

7 楼

是你说的那样吗？

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

: 不过我咋觉得这道题不过是edit dist里面的单元从character变成word了呢。。

d*x2013-03-12 07:03

8 楼

不知道啊，感觉题目叙述有点模糊，等信息

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

: 是你说的那样吗？

d*x2013-03-12 07:03

9 楼

这应该是一种评价两个句子差异的办法。归根结底面试官想要的是评价两个句子的距离
的办法。
http://en.wikipedia.org/wiki/Levenshtein_distance

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

: 是你说的那样吗？

p*p2013-03-12 07:03

10 楼

这里面有twitter is a good tool facebook better这几个词
按每个词出现为1，不出现为0
得到向量：
twitter good tool - (1 0 0 1 1 0 0)
twitter is a good tool - (1 1 1 1 1 0 0)
twitter is good - (1 1 0 1 0 0 0)
facebook is a better tool - (0 1 1 0 1 1 1)
最接近的是向量夹角最小的那个

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

p*p2013-03-12 07:03

11 楼

这样的话twitter is goo要比twitter is good yeah距离近吧

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

: 这应该是一种评价两个句子差异的办法。归根结底面试官想要的是评价两个句子的距离
: 的办法。
: http://en.wikipedia.org/wiki/Levenshtein_distance

d*x2013-03-12 07:03

12 楼

goo是啥
这个是词level的，和你说的那个很相近
具体距离取决与各种操作的cost

距离

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

: 这样的话twitter is goo要比twitter is good yeah距离近吧

p*p2013-03-12 07:03

13 楼

就是举个例子，因为leven那个是字level的
不过按词的话应该就行了

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

: goo是啥
: 这个是词level的，和你说的那个很相近
: 具体距离取决与各种操作的cost
:
: 距离

c*t2013-03-12 07:03

14 楼

问一下顺序有要求吗？比如 "good tool twitter" 是不是比 “twitter is a good
tool"更近？

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

f*m2013-03-12 07:03

15 楼

我也没有关于这提过多的信息。这道题是我从下面的面经找到的，里边有人提供了思路
，不过我不敢肯定是不是对的。
http://www.mitbbs.com/article_t/JobHunting/32045491.html

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

f*m2013-03-12 07:03

16 楼

每个cadidant句子是一个tweet吧？从inverted index中得到的吧？

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

: 这里面有twitter is a good tool facebook better这几个词
: 按每个词出现为1，不出现为0
: 得到向量：
: twitter good tool - (1 0 0 1 1 0 0)
: twitter is a good tool - (1 1 1 1 1 0 0)
: twitter is good - (1 1 0 1 0 0 0)
: facebook is a better tool - (0 1 1 0 1 1 1)
: 最接近的是向量夹角最小的那个

f*m2013-03-12 07:03

17 楼

是有些像。
我觉得除了edit distance小之外，还有考虑长度最短吧？
edit distance最小不一定长度就最短吧。

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

: 不过我咋觉得这道题不过是edit dist里面的单元从character变成word了呢。。

d*x2013-03-12 07:03

18 楼

题目叙述太模糊了。。。
如果是只有inverted index，那貌似就完全是另外一道题了。。

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

: 是有些像。
: 我觉得除了edit distance小之外，还有考虑长度最短吧？
: edit distance最小不一定长度就最短吧。

f*m2013-03-12 07:03

19 楼

可以通过给定的phase中的每个单词找到对应的tweets，每个tweet可以看成是一个
Phase，这样就有很多candidate phases.然后从中间选，比如用edit distance,但是还
没想明白怎么找到最短的。

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

: 题目叙述太模糊了。。。
: 如果是只有inverted index，那貌似就完全是另外一道题了。。

a*32013-03-12 07:03

20 楼

说了inverted index，应该是吧tweet good tool三个词分别拉出倒排doc list
对出现同时在三个doc list中的doc(phrase）,找最小的吧
如果找不到的话就对同时出现在tweet good或者tweet tool或者good tool的phrase找
最小的

Y*f2013-03-12 07:03

21 楼

如果有顺序要求，如题目的例子，要求twitter 在good前面，good在tool前面，那么建
立一个数组，数组第i个元素是包含i+1的word的最近的位置。类似于dp
如果没有顺序要求，用set，set的每个元素是最近word的位置，每个word的位置只能出
现一个（扫面过程中，如果该word在set中已经有位置，先把它从set中删除）， set中
最大位置和最小位置的差就是当前的包含所有word的字符串的长度。

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