Find the words in a long stream of characters. Auto-tokenize

Question

你如何在长长的角色中找到正确的单词？

输入:

"The revised report onthesyntactictheoriesofsequentialcontrolandstate"

谷歌的输出:

"The revised report on syntactic theories sequential controlandstate"

(考虑到他们产生输出的时间足够接近)

您认为Google如何做到这一点？你会如何提高准确度？

Answer 1

我会尝试这样的递归算法:

• 尝试在每个位置插入一个空格.如果左侧部分是单词,则在右侧部分重复出现.
• 计算所有最终输出中的有效字数/总字数.具有最佳比例的那个可能是你的答案.

例如,给它"thisntenceisgood"会运行:

thesentenceisgood
the sentenceisgood
    sent enceisgood
         enceisgood: OUT1: the sent enceisgood, 2/3
    sentence isgood
             is good
                go od: OUT2: the sentence is go od, 4/5
             is good: OUT3: the sentence is good, 4/4
    sentenceisgood: OUT4: the sentenceisgood, 1/2
these ntenceisgood
      ntenceisgood: OUT5: these ntenceisgood, 1/2

所以你会选择OUT3作为答案.

Answer 2

尝试使用以下规则的随机规则语法(相当于隐马尔可夫模型):

for every word in a dictionary:
stream -> word_i stream with probability p_w
word_i -> letter_i1 ...letter_in` with probability q_w (this is the spelling of word_i)
stream -> letter stream with prob p (for any letter)
stream -> epsilon with prob 1

概率可以从训练集中导出,但请参见以下讨论.最可能的解析是使用维特比算法计算的,该算法在隐藏状态的数量上具有二次时间复杂度,在这种情况下是您的词汇表,因此您可能会遇到大型词汇表的速度问题.但是,如果你设置所有p_w = 1,q_w = 1 p = .5这意味着,这些是人工语言模型中的概率,其中所有单词都具有相同的可能性,并且所有非单词同样不太可能.当然,如果不使用这种简化,你可以更好地分段,但算法的复杂性会下降很多.如果您查看维基百科条目中的递归关系,您可以尝试简化它以适应这种特殊情况.直到位置k的维特比解析概率可以简化为VP(k) = max_l(VP(k-l) * (1 if text[k-l:k] is a word else .5^l)你可以用一个单词的最大长度来限制l,并找出al字母是否与散列搜索形成一个单词.这种复杂性与词汇量大小无关O(<text length> <max l>).对不起,这不是一个证明,只是一个草图,但应该让你去.另一个潜在的优化,如果您创建字典的trie,您可以检查子字符串是否是任何正确单词的前缀.因此,当您查询文本[kl:k]并得到否定答案时,您已经知道任何d的文本[kl:k + d]都是如此.要利用这一点,你必须重新安排递归,所以我不确定这是否可以被完全利用(它可以看到注释).