问一道NLP的题目 - 未名空间MITBBS历史存档

s*n2011-12-03 08:12

1 楼

Word segmentation.
From an arbitrary input string, we want to be able to extract all relevant
tokens from the string. Relevant is defined as the most probable message
being conveyed in the string.
E.g.
Input: ellow!or#ldt.h.i.s.isasen tence. ano&the*r s e n t-en_ce.
Output: hello world this is a sentence. another sentence.
当时给了一天时间要求完成，任何语言，实在做不出他们要求的解，后来也被拒了
现在想知道这题到底有多难br />

q*x2011-12-03 08:12

2 楼

which firm?

【在 s*******n 的大作中提到】

: Word segmentation.
: From an arbitrary input string, we want to be able to extract all relevant
: tokens from the string. Relevant is defined as the most probable message
: being conveyed in the string.
: E.g.
: Input: ellow!or#ldt.h.i.s.isasen tence. ano&the*r s e n t-en_ce.
: Output: hello world this is a sentence. another sentence.
: 当时给了一天时间要求完成，任何语言，实在做不出他们要求的解，后来也被拒了
: 现在想知道这题到底有多难br />

s*n2011-12-03 08:12

3 楼

很小的start-up
1MPERM1UM
1->I

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

: which firm?

q*x2011-12-03 08:12

4 楼

先把特殊字符滤掉？
elloworldthisisasentenceanothersentence.

【在 s*******n 的大作中提到】

: Word segmentation.
: From an arbitrary input string, we want to be able to extract all relevant
: tokens from the string. Relevant is defined as the most probable message
: being conveyed in the string.
: E.g.
: Input: ellow!or#ldt.h.i.s.isasen tence. ano&the*r s e n t-en_ce.
: Output: hello world this is a sentence. another sentence.
: 当时给了一天时间要求完成，任何语言，实在做不出他们要求的解，后来也被拒了
: 现在想知道这题到底有多难br />

q*x2011-12-03 08:12

5 楼

这个加密厉害。

【在 s*******n 的大作中提到】

: 很小的start-up
: 1MPERM1UM
: 1->I

s*n2011-12-03 08:12

6 楼

先滤掉再分词

q*x2011-12-03 08:12

7 楼

还是有点麻烦。ello->hello

【在 s******n 的大作中提到】

: 先滤掉再分词

s*n2011-12-03 08:12

8 楼

没办法定义 most probable message
除非有辅助函数，或者建model，上SVR，或者gaussian process
这个就不是考题了，是implement paper了

s*n2011-12-03 08:12

9 楼

分词是难点，还有别字的

【在 s******n 的大作中提到】

: 先滤掉再分词

s*n2011-12-03 08:12

10 楼

问题是找来的dict big.txt里面，HELLO WORLD没出现过，HELLO也只有两次

【在 s******n 的大作中提到】

: 没办法定义 most probable message
: 除非有辅助函数，或者建model，上SVR，或者gaussian process
: 这个就不是考题了，是implement paper了

w*n2011-12-03 08:12

11 楼

如果你帖子有typo, input最前面少了一个h的话, 1小时内就能code出
否则相当难, 如何从 ello=> hello....
难道还得上一个corpus 来提取2-grams, 然后选择most frequent的world的前缀.....

【在 s*******n 的大作中提到】

: Word segmentation.
: From an arbitrary input string, we want to be able to extract all relevant
: tokens from the string. Relevant is defined as the most probable message
: being conveyed in the string.
: E.g.
: Input: ellow!or#ldt.h.i.s.isasen tence. ano&the*r s e n t-en_ce.
: Output: hello world this is a sentence. another sentence.
: 当时给了一天时间要求完成，任何语言，实在做不出他们要求的解，后来也被拒了
: 现在想知道这题到底有多难br />

s*n2011-12-03 08:12

12 楼

就是这样的INPUT,没TYPO
公司说我CODE不WORK,就是找不出他要的解
他们最近要找不少人，欢迎大家去试试

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

: 如果你帖子有typo, input最前面少了一个h的话, 1小时内就能code出
: 否则相当难, 如何从 ello=> hello....
: 难道还得上一个corpus 来提取2-grams, 然后选择most frequent的world的前缀.....

s*n2011-12-03 08:12

13 楼

问题还要加上句末的标点。。。

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

: 如果你帖子有typo, input最前面少了一个h的话, 1小时内就能code出
: 否则相当难, 如何从 ello=> hello....
: 难道还得上一个corpus 来提取2-grams, 然后选择most frequent的world的前缀.....

q*x2011-12-03 08:12

14 楼

这种公司，这种题，还是算了。还有啥有意思的小题吗？

【在 s*******n 的大作中提到】

: 就是这样的INPUT,没TYPO
: 公司说我CODE不WORK,就是找不出他要的解
: 他们最近要找不少人，欢迎大家去试试

s*n2011-12-03 08:12

15 楼

我觉得fail了没什么好遗憾的
这题1小时，我是做不出来， paypal的test比他要reasonable，时间上至少可解

w*n2011-12-03 08:12

16 楼

那真得上nlp了.... 加上词性和句子结构
做过类似的course project, 全力去做也许一天能搞定... 但是做出来了又不一定有
offer...谁做阿, 真不知道这些公司怎么想的

【在 s*******n 的大作中提到】

: 问题还要加上句末的标点。。。

b*e2011-12-03 08:12

17 楼

可以考虑用动态规划啊。
去掉特殊符号以后，利用动态规划原理寻找分段点(空格符)，使得分出来的字符串中所
含的能够在字典里找到的单词个数最大。
如果还要考虑语义连贯性的，难度就太大了吧。

s*n2011-12-03 08:12

18 楼

如果有A打头的单词，肯定被分成A了吧，因为数量最多
只要一个空格加错了，后面整句都不对
还要考虑有错别字

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

: 可以考虑用动态规划啊。
: 去掉特殊符号以后，利用动态规划原理寻找分段点(空格符)，使得分出来的字符串中所
: 含的能够在字典里找到的单词个数最大。
: 如果还要考虑语义连贯性的，难度就太大了吧。

b*e2011-12-03 08:12

19 楼

如果涉及到语义，那么在相应的字典里（或者另外一个文件里）就应该给出类似的字符
串。比如 hello world, this is, 之类的能够让我们作为判断依据的字符串。否则，
怎么去做判断到底是不是the most probable message？

【在 s*******n 的大作中提到】

: 如果有A打头的单词，肯定被分成A了吧，因为数量最多
: 只要一个空格加错了，后面整句都不对
: 还要考虑有错别字

s*n2011-12-03 08:12

20 楼

我觉得他们不是在招人，他们是找免费的consultant！

y*g2011-12-03 08:12

21 楼

感觉需要ai之类的方法了
没有准确的定义，不像算法题

【在 s*******n 的大作中提到】

: Word segmentation.
: From an arbitrary input string, we want to be able to extract all relevant
: tokens from the string. Relevant is defined as the most probable message
: being conveyed in the string.
: E.g.
: Input: ellow!or#ldt.h.i.s.isasen tence. ano&the*r s e n t-en_ce.
: Output: hello world this is a sentence. another sentence.
: 当时给了一天时间要求完成，任何语言，实在做不出他们要求的解，后来也被拒了
: 现在想知道这题到底有多难br />

y*d2011-12-03 08:12

22 楼

同感。

【在 s******n 的大作中提到】

: 我觉得他们不是在招人，他们是找免费的consultant！