12

長い文字の流れの中から正しい単語をどのように見つけますか？

入力：

"The revised report onthesyntactictheoriesofsequentialcontrolandstate"

Googleの出力：

"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

確率はトレーニング セットから導出できますが、次の説明を参照してください。最も可能性の高い解析は、ビタビ アルゴリズムを使用して計算されます。ビタビ アルゴリズムは、隠れ状態 (この場合は語彙) の数が 2 次時間複雑であるため、大きな語彙では速度の問題が発生する可能性があります。しかし、すべての 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>). 申し訳ありませんが、これは証明ではなく、単なるスケッチですが、うまくいくはずです。別の潜在的な最適化として、辞書のトライを作成すると、部分文字列が正しい単語のプレフィックスであるかどうかを確認できます。したがって、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

HTH

于 2010-10-11T02:56:43.523 に答える
0

再帰的な分割と辞書検索を行った後、フレーズ内の単語ペアの品質を向上させるために、単語ペアの相互情報量を使用することをお勧めします。

これは基本的にトレーニングセットを通過し、AlbertSimpsonがAlbertEinsteinよりも可能性が低いことを示す単語ペアのMI値を見つけます:)

このテーマの学術論文をScienceDirectで検索してみてください。相互情報量の基本情報については、http：//en.wikipedia.org/wiki/Mutual_informationを参照してください。

昨年、私は検索エンジンプロジェクトのフレーズ検索の部分に携わっていました。そこでは、ウィキペディアのデータセットを解析して各単語のペアをランク付けしようとしていました。あなたがそれのいくつかの使用法を見つけることができればあなたがそれをあなたと共有することができればあなたが気にかけているなら私はC++のコードを持っています。ウィキメディアを解析し、単語のペアごとに相互情報量を見つけます。

于 2010-10-29T03:00:39.640 に答える
0

スペル修正アルゴリズムを確認してください。これは、Google で使用されるアルゴリズムに関する記事へのリンクです - http://www.norvig.com/spell-correct.html。ここでは、このトピックに関する Google の科学論文をご覧いただけます。

于 2010-10-10T17:17:58.327 に答える