12

您如何在长长的字符流中找到正确的单词？

输入 ：

"The revised report onthesyntactictheoriesofsequentialcontrolandstate"

谷歌的输出：

"The revised report on syntactic theories sequential controlandstate"

（考虑到他们产生输出的时间，这已经足够接近了）

你觉得谷歌是怎么做到的？您将如何提高准确性？

4

5 回答 5

11

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

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

例如，给它“thesentenceisgood”会运行：

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 作为答案。

于 2010-10-11T03:17:13.007 回答
7

尝试使用以下规则的随机正则文法（相当于隐马尔可夫模型）：

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

概率可以从训练集导出，但请参见以下讨论。最可能的解析是使用 Viterbi 算法计算的，该算法在隐藏状态的数量上具有二次时间复杂度，在这种情况下是您的词汇表，因此您可能会遇到大型词汇表的速度问题。但是如果你设置所有的 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 与单词的最大长度绑定，并通过哈希搜索查找所有字母是否构成单词。其复杂性与词汇量无关，并且是O(<text length> <max l>). 抱歉，这不是一个证明，只是一个草图，但应该能让你继续前进。另一个潜在的优化，如果您创建字典的 trie，您可以检查子字符串是否是任何正确单词的前缀。因此，当您查询 text[kl:k] 并得到否定答案时，您已经知道对于任何 d 的 text[kl:k+d] 也是如此。要利用这一点，您必须显着重新安排递归，所以我不确定这可以被充分利用（它可以看到评论）。

于 2010-10-22T17:09:20.700 回答
3

这是我开始为最近的代码高尔夫开发的 Mathematica 代码。
它是一种最小匹配、非贪婪、递归算法。这意味着句子“笔比剑更强大”（没有空格）返回{“笔比剑更强大}:)

findAll[s_] :=
  Module[{a = s, b = "", c, sy = "="},
  While[
   StringLength[a] != 0,
   j = "";
   While[(c = findFirst[a]) == {} && StringLength[a] != 0,
    j = j <> StringTake[a, 1];
    sy = "~";
    a = StringDrop[a, 1];
   ];
   b = b <> " " <> j ;
   If[c != {},
    b = b <> " " <> c[[1]];
    a = StringDrop[a, StringLength[c[[1]]]];
   ];
  ];
   Return[{StringTrim[StringReplace[b, "  " -> " "]], sy}];
]

findFirst[s_] :=
  If[s != "" && (c = DictionaryLookup[s]) == {}, 
   findFirst[StringDrop[s, -1]], Return[c]];

样本输入

ss = {"twodreamstop", 
      "onebackstop", 
      "butterfingers", 
      "dependentrelationship", 
      "payperiodmatchcode", 
      "labordistributioncodedesc", 
      "benefitcalcrulecodedesc", 
      "psaddresstype", 
      "ageconrolnoticeperiod",
      "month05", 
      "as_benefits", 
      "fname"}

输出

 twodreamstop              = two dreams top
 onebackstop               = one backstop
 butterfingers             = butterfingers
 dependentrelationship     = dependent relationship
 payperiodmatchcode        = pay period match code
 labordistributioncodedesc ~ labor distribution coded es c
 benefitcalcrulecodedesc   ~ benefit c a lc rule coded es c
 psaddresstype             ~ p sad dress type
 ageconrolnoticeperiod     ~ age con rol notice period
 month05                   ~ month 05
 as_benefits               ~ as _ benefits
 fname                     ~ f name

高温高压

于 2010-10-11T02:56:43.523 回答
0

检查拼写校正算法。这是一篇关于 google 中使用的算法的文章的链接 - http://www.norvig.com/spell-correct.html。在这里，您将找到来自 google 的关于该主题的科学论文。

于 2010-10-10T17:17:58.327 回答
0

在进行递归拆分和字典查找之后，为了提高短语中单词对的质量，您可能有兴趣使用单词对的互信息。

这本质上是通过一个训练集并找出单词对的 MI 值，告诉你阿尔伯特辛普森比阿尔伯特爱因斯坦更不可能:)

您可以尝试在 Science Direct 中搜索此主题的学术论文。有关 Mutual 信息的基本信息，请参阅http://en.wikipedia.org/wiki/Mutual_information

去年，我参与了一个搜索引擎项目的短语搜索部分，我试图解析维基百科数据集并对每个单词对进行排名。我有 C++ 中的代码，如果你愿意的话，如果你能找到它的一些用途，可以与你分享。它解析维基媒体并为每个单词对找出相互信息。

于 2010-10-29T03:00:39.640 回答